[PYTHON] AtCoder Beginner Contest 065 Rückblick auf frühere Fragen

Frühere Fragen zum ersten Mal gelöst

Benötigte Zeit

Problem A

answerA.py

x,a,b=map(int,input().split())
if b<=a:
    print("delicious")
elif b<=a+x:
    print("safe")
else:
    print("dangerous")

Mit dem ternären Operator

answerA_better.py

x,a,b=map(int,input().split())
print("delicious" if b<=a else ("safe" if b<=a+x else "dangerous"))

B-Problem

Schließen Sie die leuchtenden nacheinander an. Ich habe AtCoder gleich zu Beginn mit B gefüllt, und ich spürte Wachstum, als ich sah, dass es zu diesem Zeitpunkt nicht gut gemacht wurde.

answerB.py

n=int(input())
a=[int(input())-1 for i in range(n)]
now=0
x=[0]*n
i=0
while x[now]==0:
    i+=1
    x[now]=1
    now=a[now]
    if now==1:
        print(i)
        break
else:
    print(-1)

C-Problem

Ich habe eine Tabelle mit Binomialkoeffizienten erstellt, aber ich brauchte sie nicht.

answerC.cc

#include<iostream>
using namespace std;
typedef long long ll;

const int MAX = 10000000;
//Was zu teilen
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

//Vorbehandlung, um einen Tisch zu machen
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

//Berechnung des Binärkoeffizienten
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
  //Vorverarbeitung
  COMinit();
  int n,m;cin >> n >> m;
  if(n-m==1 or n-m==-1){
    cout << ((fac[n]%MOD)*fac[m])%MOD << endl;
  }else if(n==m){
    cout << (((fac[n]%MOD)*fac[m])%MOD*2)%MOD << endl;
  }else{
    cout << 0 << endl;
  }
}

D Problem

Als ich es zum ersten Mal sah, wusste ich nicht wirklich, was ich tun sollte (weil ich dachte, dass die Methode wahrscheinlich TLE ist). Wenn ich mir die Antwort anschaue, scheint es, dass der minimale Gesamtflächenbaum verwendet wird. Als ich ihn untersuchte, stellte ich fest, dass es zwei Methoden gibt, die prim-Methode und die claspal-Methode. Letzterer sagt, UnionFind zu verwenden, und UnionFind ist nicht sehr vertraut (ich habe vergessen, es zu implementieren, weil ich es zu oft verwendet habe, ich muss das Spiralbuch schnell weiterentwickeln). Wenn ich also versuche, es mit der prim-Methode zu implementieren, treten viele Fehler auf. Ich habe viel Zeit geschmolzen. (** Die Implementierung von Priority_queue ist in der Regel fehlerhaft und vergisst, dass durch Drücken die Spitze geändert werden kann **) Die prim-Methode ist ein Algorithmus, der der Dyxtra-Methode sehr ähnlich ist. Bei der Dyxtra-Methode wird ein Startpunkt bestimmt und der nächste Scheitelpunkt, der von diesem Startpunkt aus erreicht werden kann, als nächster zu besuchender Scheitelpunkt festgelegt. Danach werden die Besuche in der Reihenfolge ab dem Startpunkt wiederholt, der von dem im besuchten Scheitelpunktsatz enthaltenen Scheitelpunkt aus erreicht werden kann. Ich werde. Mit anderen Worten, bereiten Sie ein Array mit Informationen zu (mehreren) Kanten vor, die sich von jedem Scheitelpunkt aus erstrecken, extrahieren Sie nur die Kanten, die sich von dem besuchten Scheitelpunkt erstrecken, und tauchen Sie in die Priority_queue ein. Von den nicht besuchten Scheitelpunkten, die über die Kante erreicht werden können, die in die Prioritätswarteschlange eintaucht, ist ** der dem Startpunkt am nächsten liegende ** der nächste zu besuchende Scheitelpunkt (der Kostenteil der Kante ist ** der Abstand vom Startpunkt *) Vergessen Sie nicht, auf * zu aktualisieren und dann in priority_queue einzutauchen. Die kürzeste Route kann durch wiederholtes Wiederholen einer solchen Aktualisierung (Anzahl der Eckpunkte 1) ermittelt werden. Hier werden wir die prim-Methode betrachten, während wir sie mit der Dyxtra-Methode vergleichen. Bei der Dyxtra-Methode ist die letzte Anforderung ** der Abstand vom Startpunkt **. Mit anderen Worten, der nächste zu besuchende Scheitelpunkt ist derjenige mit der kürzesten Entfernung vom Startpunkt, der noch nicht besucht wurde. Andererseits ist bei der prim-Methode das Endergebnis der ** minimale Gesamtflächenbaum ** (siehe Beschreibung unten). Mit anderen Worten, die nächste zu wählende Kante ist ** die kostengünstigste Kante **, die sich vom besuchten Scheitelpunkt zum nicht besuchten Scheitelpunkt erstreckt. Aufgrund dieser Unterschiede erfordert die Dyxtra-Methode, dass der Schlüssel mit priority_queue verglichen wird, um auf den Abstand vom Startpunkt aktualisiert zu werden, während die Prim-Methode den Unterschied macht, dass der mit priority_queue zu vergleichende Schlüssel einfach die Kosten der Seite sind. .. Wenn Sie bei der Implementierung Ihre eigene Klasse in priority_queue einfügen, können Sie sie wie erwartet zum Funktionieren bringen, indem Sie nur <definieren. Weiterhin sind v1 und v2 hier nach x bzw. y sortiert. Dies liegt daran, dass klar ist, dass nur die Seite, die die Dinge verbindet, die auf beiden Seiten beim Sortieren nach Koordinaten auftreten, als Seite des minimalen Gesamtflächenbaums ausgewählt wird. (Einzelheiten finden Sie unter Erläuterung.)

Der gesamte Flächenbaum ist → ** Der Baum, der die gesamte Spitze des angegebenen Teilbaums verbindet ** Was ist der minimale Gesamtflächenbaum? → ** Alle Flächenbäume, die die Gesamtkosten minimieren **

answerD.cc

#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;

class Edge{
public:
  ll to_Node;
  ll cost;
  Edge(ll t,ll c){
    to_Node=t;cost=c;
  }
};

//pr_Warteschlange hat eine hohe Priorität(<Derjenige, der nach rechts kommt)Wird zuerst herausgenommen
bool operator< (const Edge& a,const Edge& b){
    return a.cost > b.cost;
};

ll distance(vector<ll>& a,vector<ll>& b){
  return min({abs(a[0]-b[0]),abs(a[1]-b[1])});
}

int main(){
  ll n;cin >> n;
  vector< vector<ll> > v1(n,vector<ll>(3,0));
  vector< vector<ll> > v2(n,vector<ll>(3,0));
  for(ll i=0;i<n;i++){
    ll x,y;cin >> x >> y;
    v1[i][0]=x;v1[i][1]=y;v1[i][2]=i;
    v2[i][0]=x;v2[i][1]=y;v2[i][2]=i;
  }
  sort(v1.begin(),v1.end(),[](vector<ll>&a,vector<ll>&b){returna[0]<b[0];});
  sort(v2.begin(),v2.end(),[](vector<ll>&a,vector<ll>&b){returna[1]<b[1];});

  //Stellen Sie hier die Seite, die sich von jedem Knoten erstreckt, in die Warteschlange
  vector< queue<Edge> > edges_before(n);
  for(ll i=0;i<n-1;i++){
    edges_before[v1[i][2]].push(Edge(v1[i+1][2],distance(v1[i],v1[i+1])));
    edges_before[v1[i+1][2]].push(Edge(v1[i][2],distance(v1[i],v1[i+1])));
    edges_before[v2[i][2]].push(Edge(v2[i+1][2],distance(v2[i],v2[i+1])));
    edges_before[v2[i+1][2]].push(Edge(v2[i][2],distance(v2[i],v2[i+1])));
  }

  //Machen Sie es ab 0 besucht
  vector<bool> check(n,false);check[0]=true;
  priority_queue<Edge> edges;
  ll l=edges_before[0].size();
  for(ll i=0;i<l;i++){
    edges.push(edges_before[0].front());
    edges_before[0].pop();
  }

  ll cost_sum=0;
  Edge now=edges.top();
  int i=0;
  //Ich werde immer mehr in Ordnung besuchen
  while(edges.size()!=0){
    //to_Ob der Knoten besucht wurde, wenn ja, einfach Priorität_Einfach aus der Warteschlange entfernen
    if(!check[now.to_Node]){
      check[now.to_Node]=true;//Machen Sie es besucht
      cost_sum+=now.cost;//Aktualisierung der Gesamtkosten
      int k=now.to_Node;
      ll l=edges_before[k].size();
      edges.pop();//Ausgenommen gebrauchte Seiten
      for(ll i=0;i<l;i++){//Priorität der Seite, die sich vom neu besuchten Scheitelpunkt erstreckt_Zur Warteschlange hinzufügen
        Edge s=edges_before[k].front();
        if(!check[s.to_Node]) edges.push(s);//Schieben Sie nur nicht besuchte Eckpunkte
        edges_before[k].pop();
      }
      now=edges.top();
      //Es wurde nicht viel schneller, aber n-mal ist genug, also ↓
      if(++i==n-1)break;
    }else{
      edges.pop();now=edges.top();
    }
  }
  cout << cost_sum << endl;
}