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 << " ";
  }
}


Recommended Posts

Examen des questions passées d'AtCoder (12 / 6,7)
Examen des questions passées d'AtCoder (12/5)
Concours AtCoder pour débutants Défi des questions passées 6
Concours AtCoder pour débutants Défi des questions passées 4
AtCoder Grand Contest Past Question Challenge 2
Concours AtCoder pour débutants Défi des questions passées 9
Concours AtCoder pour débutants Défi des questions passées 7
AtCoder Grand Contest Défi des questions passées 1
Concours AtCoder pour débutants Défi des questions passées 10
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutants Défi des questions passées 5
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 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 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 117 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