[PYTHON] AtCoder Past Question Review (12/5)

Ich werde die Probleme aufzeichnen, die ich in den letzten Fragen von AtCoder falsch gemacht habe, und die Probleme, die mich beeindruckt haben.

ABC106-C(To infinity) 3WA Als ich 5000 Billionen Mal wiederholte, versuchte ich zunächst, alle Zahlen von vorne zu berechnen. (** Es ist klar, dass es angesichts des Rechenaufwands nicht rechtzeitig sein wird ) ( Überlegen Sie, was am Ende passieren wird, wenn zu viel vorhanden ist **) Als nächstes habe ich vergessen, den Fall zu betrachten, in dem auf 1s am Anfang mehrere folgen.

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 sah die Antwort

Zuerst habe ich versucht, sie in der Reihenfolge der oberen Ziffer zu finden, aber die Urteilsbedingungen waren schwieriger als erwartet. (Es gab keine Änderung in der Art zu denken, dass Sie in der Reihenfolge von der letzten Ziffer hier fragen sollten ) Ich habe vergessen zu klassifizieren, wenn n 0 ist. ( Stellen Sie sicher, dass Sie alles tun (denken Sie an Extremfälle) **)

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)

Ich habe die Antwort über 10WA gesehen

Ich bin nicht gut in Holzkonstruktionen, ich möchte sie wirklich überwinden. Ich wusste es nicht, bis ich die Antwort sah, und ich konnte sie nicht gut in Python schreiben. Python scheint nicht mit Wiederholungen kompatibel zu sein, daher schreibe ich Wiederholungen in C ++. Codebeschreibung finden Sie im Kommentar.

C++Antworten

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

using namespace std;

int main(){
  int n,q;cin >> n >> q;
  //u speichert die Scheitelpunkte, die mit den Scheitelpunkten verbunden sind, die dem Index entsprechen(Ich weiß nicht, welcher zum Zeitpunkt der Eingabe der Elternteil ist)
  vector< vector<int> > u(n);
  for(int i=0;i<n-1;i++){
    int a,b;cin >> a >> b;
    //Zweimal drücken_Beachten Sie, dass Sie zurück müssen
    u[a-1].push_back(b-1);
    u[b-1].push_back(a-1);
  }
  //c enthält den Wert des Zählers an jedem Scheitelpunkt
  vector<int> c(n,0);
  for(int i=0;i<q;i++){
    //Halten Sie den Anfangswert des Zählers einmal und geben Sie ihn an die untergeordneten Elemente weiter, und zwar in der Reihenfolge von der Stelle, die der Wurzel am nächsten liegt
    int p,x;cin >> p >> x;
　　c[p-1]+=x;
  }
  //Geben Sie die Informationen des Knotens ein, den Sie als Nächstes in der Suche nach der Breitenpriorität anzeigen möchten
  //Zu diesem Zeitpunkt sind nicht nur die Informationen des Scheitelpunkts, sondern auch die Informationen des vorherigen Scheitelpunkts erforderlich.(Verhindern Sie die Rückausbreitung)
  //Vektor ist in Ordnung, aber Löschen ist langsam, verwenden Sie also die Warteschlange
  queue< pair<int,int> > k;k.push(make_pair(-1,0));

  //Suche nach Breitenpriorität(Die Suche nach Tiefenpriorität ist ebenfalls in Ordnung)
  while(k.size()!=0){//Beenden Sie, wenn keine durchsuchbaren Scheitelpunkte mehr vorhanden sind
    int l1=k.size();
    for(int i=0;i<l1;i++){
      pair<int,int> a=k.front();
      int l2=u[a.second].size();
      //Untersuchen Sie die Scheitelpunkte, die sich von jedem Scheitelpunkt aus erstrecken
      for(int j=0;j<l2;j++){
        //Wenn der von diesem Apex ausgehende Apex nicht besucht wird(Wenn die Suche in Richtung des Kindes fortgesetzt wird), Addieren Sie den Wert des Zählers zu diesem Peak
        if(u[a.second][j]!=a.first){
          c[u[a.second][j]]+=c[a.second];
          #Suche weiter bis zum nächsten Gipfel
          k.push(make_pair(a.second,u[a.second][j]));
        }
      }
      #Löschen Sie es, weil es veraltet ist
      k.pop();
    }
  }

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