[PYTHON] Examen des questions passées d'AtCoder (12/5)

Je garderai une trace des problèmes que j'ai commis une erreur dans les questions passées d'AtCoder et des problèmes qui m'ont laissé une impression.

ABC106-C(To infinity) 3WA Premièrement, quand j'ai répété 5000 billions de fois, j'ai essayé de calculer tous les nombres à partir de l'avant. (** Il est clair que ce ne sera pas à temps compte tenu de la quantité de calcul ) ( Pensez à ce qui se passera à la fin s'il y en a trop **) Ensuite, j'ai oublié de considérer le cas où les 1 sont suivis de plusieurs au début.

s=list(map(int,list(input())))
k=int(input())
for i in range(len(s)):
    if s[i]!=1:
        if i>=k:
            print(1)
        else:
            print(s[i])
        break
else:
    print(1)

ABC105-C(Base -2 Number)

2WA a vu la réponse

Tout d'abord, j'ai essayé de le trouver dans l'ordre à partir du chiffre supérieur, mais les conditions de jugement étaient plus difficiles que prévu. (Il n'y a pas eu de changement dans la façon de penser que vous devriez demander dans l'ordre à partir du dernier chiffre ici ) J'ai oublié de classer quand n vaut 0. ( Assurez-vous de tout faire (pensez aux cas extrêmes) **)

n=int(input())
s=""

i=0
while n!=0:
    if abs(n)%2==0:
        s="0"+s
        n=n//2
    else:
        if i%2==0:
            n=(n-1)//2
        else:
            n=(n+1)//2
        s="1"+s
    i+=1
if s="":
    print("0")
else:
    print(s)

ABC138-D(Ki)

10WA ou plus j'ai vu la réponse

Je ne suis pas doué pour la structure en bois, je veux vraiment la surmonter. Je ne savais pas avant d'avoir vu la réponse, et je ne pouvais pas bien l'écrire en Python. Python semble incompatible avec la récurrence, donc j'écrirai la récurrence en C ++. Voir les commentaires pour la description du code.

C++Répondre

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<utility>

using namespace std;

int main(){
  int n,q;cin >> n >> q;
  //u stocke les sommets connectés aux sommets correspondant à l'index(Je ne sais pas lequel est le parent au moment de la saisie)
  vector< vector<int> > u(n);
  for(int i=0;i<n-1;i++){
    int a,b;cin >> a >> b;
    //Pousser deux fois_Notez que vous devez sauvegarder
    u[a-1].push_back(b-1);
    u[b-1].push_back(a-1);
  }
  //c contient la valeur du compteur à chaque sommet
  vector<int> c(n,0);
  for(int i=0;i<q;i++){
    //Maintenez la valeur initiale du compteur une fois et propagez-la à l'enfant dans l'ordre à partir de l'endroit le plus proche de la racine
    int p,x;cin >> p >> x;
　　c[p-1]+=x;
  }
  //Entrez les informations du nœud que vous souhaitez voir ensuite dans la recherche de priorité de largeur
  //À ce stade, non seulement les informations du sommet, mais également les informations du sommet précédent sont requises.(Empêcher la rétropropagation)
  //Le vecteur est correct, mais la suppression est lente, alors utilisez la file d'attente
  queue< pair<int,int> > k;k.push(make_pair(-1,0));

  //Recherche de priorité de largeur(La recherche de priorité à la profondeur est également OK)
  while(k.size()!=0){//Terminer lorsqu'il n'y a plus de sommets de recherche
    int l1=k.size();
    for(int i=0;i<l1;i++){
      pair<int,int> a=k.front();
      int l2=u[a.second].size();
      //Examinez les sommets s'étendant de chaque sommet
      for(int j=0;j<l2;j++){
        //Si l'apex partant de cet apex n'est pas visité(Si la fouille se déroule en direction de l'enfant), Ajoutez la valeur du compteur à ce pic
        if(u[a.second][j]!=a.first){
          c[u[a.second][j]]+=c[a.second];
          #Continuez la recherche jusqu'au prochain pic
          k.push(make_pair(a.second,u[a.second][j]));
        }
      }
      #Supprimez-le car il est obsolète
      k.pop();
    }
  }

  for(int i=0;i<n;i++){
    cout << c[i];
    if(i==n-1) cout << endl;
    else cout << " ";
  }
}