AtCoder Beginner Contest 067 Revue des questions précédentes

La deuxième question passée que j'ai déjà résolue

Temps requis

スクリーンショット 2019-12-25 19.42.34.png

Problème A

Cas multiples de 3

answerA.py


a,b=map(int,input().split())
if a%3==0 or b%3==0 or (a+b)%3==0:
    print("Possible")
else:
    print("Impossible")

Problème B

Obtenez k du plus grand

answerB.py


n,k=map(int,input().split())
l=[int(i) for i in input().split()]
l.sort(reverse=True)
print(sum(l[:k]))

Problème C

Regardez-le de face et mettez à jour mi

answerC.py


n=int(input())
a=[int(i) for i in input().split()]
s=sum(a)
c=0
b=[]
for i in range(n-1):
    c+=a[i]
    b.append(c)
mi=abs(s-2*b[0])
for i in range(n-1):
    mi=min(mi,abs(s-2*b[i]))
print(mi)

answerC2.py


n=int(input())
a=[int(i) for i in input().split()]
s=sum(a)
c=a[0]
mi=abs(s-2*c)
for i in range(1,n):
    c+=a[i]
    mi=min(mi,abs(s-2*c))
print(mi)

Problème D

À partir de la condition que nous peignons dans l'ordre à partir de l'endroit le plus proche, ** je pensais que celui le plus proche des nœuds 1 et N serait noir et blanc ** (Il a un peu grandi depuis que je suis devenu capable de faire cette idée. ), Mais je ne pouvais pas penser au cas où 1 et N sont à la même distance du nœud. En fait, je ne m'en rendais pas compte quand je le résolvais, mais je ne pouvais pas saisir le sens de «agir de manière optimale». Lorsqu'il existe un itinéraire reliant ** 1 et N, les couleurs sont peintes dans l'ordre à partir du nœud sur cet itinéraire, et lorsqu'il y a plusieurs itinéraires, la couleur est peinte dans l'ordre à partir de l'itinéraire avec plus de couleurs de l'autre côté. **, c'est ce que cela signifie. Imaginez que lorsque vous peignez ce chemin (voir la figure dans Explication), le plomb est "noir dans le premier nœud". En considérant cela ensemble, la distance entre les i-ème à j-ème nœuds est d (i, j), et ** d (1, i) <= d (N, i) est noir quand il tient sur ce chemin * Vous pouvez voir qu'il devient *. De plus, pour les nœuds qui ne sont pas sur ce chemin, la couleur est uniquement déterminée à partir de la couleur peinte sur ce chemin, et il est clair que d (1, i) <= d (N, i) est valable (s'il est noir). est. Si vous pouvez y penser comme ci-dessus, le code est le suivant car vous pouvez écrire BFS ou DFS. (Il est écrit en DFS.) (En fin de compte, le point est ** Je veux connaître la distance du Node car il est peint à partir d'un endroit proche **, ** Je veux éroder davantage la position de l'adversaire parce que j'agis de manière optimale ** ,.)

answerD.cc


#include<iostream>
#include<vector>

using namespace std;
typedef vector< vector<int> > vv;
#define INF 10000000

void dfs(int now,vv& tree,vector<int>& dep,int d,vector<bool>& check){
  dep[now]=d;
  check[now]=true;
  int l=tree[now].size();
  for(int i=0;i<l;i++){
    if(check[tree[now][i]]==false){dfs(tree[now][i],tree,dep,d+1,check);}
  }
}

int main(){
  int n;cin >> n;
  vv tree(n);
  for(int i=0;i<n-1;i++){
    int a,b;cin >> a >> b;
    tree[a-1].push_back(b-1);
    tree[b-1].push_back(a-1);
  }
  vector<int> dep1(n,INF);
  vector<bool> check1(n,false);
  vector<int> dep2(n,INF);
  vector<bool> check2(n,false);
  dfs(0,tree,dep1,0,check1);
  dfs(n-1,tree,dep2,0,check2);
  int c1=0;int c2=0;
  for(int i=0;i<n;i++){
    if(dep1[i]<=dep2[i]){
      c1+=1;
    }else{
      c2+=1;
    }
  }
  if(c1>c2){
    cout << "Fennec" << endl;
  }else{
    cout << "Snuke" << endl;
  }
}

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes