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

Benötigte Zeit

Problem A

Einfach in verschiedenen Fällen ausgeben

answerA.py

a,b,c=map(int,input().split())
if a<=c<=b:
    print("Yes")
else:
    print("No")

answerA_better.py

a,b,c=map(int,input().split())
print("Yes" if a<=c<=b else "No")

B-Problem

Zählen Sie einfach die Nummer jeder Stadt

answerB.py

n,m=map(int,input().split())
x=[0]*n
for i in range(m):
    y,z=map(int,input().split())
    x[y-1]+=1
    x[z-1]+=1
for i in range(n):
    print(x[i])

C-Problem

Es ist wirklich ein großes Wachstum, diese Probleme in Sekundenschnelle lösen zu können. Es ist lächerlich, über jede Einfügung nachzudenken. Wenn Sie also darüber nachdenken, wie sie am Ende aussehen wird, werden Sie feststellen, dass Sie schließlich in aufsteigender Reihenfolge sortieren und von der kleinsten nehmen sollten. Daher erkennen wir, dass wir überlegen sollten, wie viele Elemente 1 bis 10 ** 5 sind. Bereiten Sie daher ein Array vor, um jedes Element zu zählen. Wenn Sie es vorbereiten können, können Sie sehen, dass die Anzahl von vorne gezählt wird und das Element, wenn es k oder mehr wird, die K-te kleinste Zahl ist.

answerC.py

n,k=map(int,input().split())
x=[0]*(10**5)#1~10**5
for i in range(n):
    a,b=map(int,input().split())
    x[a-1]+=b
for i in range(10**5):
    k-=x[i]
    if k<=0:
        print(i+1)
        break

D Problem

Es ist ein Problem mit dem blauen Level, aber ich konnte es in ungefähr 30 Minuten lösen! (Ich habe auch 4WA ausgestellt, also bereue ich es.) Die Richtlinie selbst wurde relativ schnell eingerichtet, aber ich konnte die Details nicht fertigstellen. Zunächst besteht der Verdacht, dass es sich um die Bellmanford-Methode handelt, da die Gewichte der Seiten im offen gewichteten gerichteten Diagramm sowohl positiv als auch negativ sind und es den Anschein hat, als könnten wir gehen, selbst wenn wir uns die Einschränkungen ansehen. Da es jedoch ein Problem ist, den längsten Pfad anstelle des kürzesten Pfades zu finden, können die Gewichte umgekehrt werden. Dies kann erreicht werden, indem die Gewichte aller Seiten mit -1 multipliziert werden (** Wenn Sie den längsten Pfad anstelle des kürzesten Pfades berücksichtigen). Ich habe festgestellt, dass es durch Multiplikation mit -1 umgekehrt werden kann. Ich denke, es kann auch für andere Probleme verwendet werden. ). Grundsätzlich können Sie dies auf diese Weise tun ( Vergessen Sie nicht, in der endgültigen Ausgabe mit -1 zu multiplizieren **), aber Sie müssen über den Fall von inf nachdenken. Zuerst benutzte ich die Bedingung des negativen Abschlusses der Bellmanford-Methode, ohne an irgendetwas zu denken, aber in einigen Fällen wurde es WA. Wenn Sie hier sorgfältig darüber nachdenken, wird dieser negative Verschluss erkannt, auch wenn es an einer Stelle einen negativen Verschluss gibt, der nichts mit dem Weg zu tun hat, den Sie beim Erreichen des N-ten Scheitelpunkts einschlagen. Schließen Sie also den N-ten Scheitelpunkt ein. Es stellt sich heraus, dass wir negative Verschlüsse erkennen müssen.

Als ich diesen Artikel schrieb, las ich Kenchons Artikel und stellte fest, dass es sich um eine falsche Lösung handelte. Ich möchte es auf die richtige Lösung umschreiben und in einem anderen Artikel erneut veröffentlichen. Der Teil mit der Stornierungszeile unten ist eine Lüge. Denken Sie also bitte an Kenchons Artikel. Bitte gib mir.

Der Code der Bellmanford-Methode wurde in einer Universitätsklasse geschrieben, daher verwendet der erste Code diesen Code (alle Informationen werden von der Knotenstruktur verwaltet). Außerdem läuft int über, machen Sie es also lang und setzen Sie den INF-Wert auf einen ausreichend großen Wert. Durch mehrmaliges Drehen der Schleife (Anzahl der Scheitelpunkte-1) in diesem Zustand (wenn kein negativer Abschluss vorliegt, verläuft der kürzeste Weg von einem Scheitelpunkt zu einem bestimmten Scheitelpunkt höchstens einmal N Scheitelpunkte (Anzahl der Scheitelpunkte). -1) Eine solche Route finden Sie in 1) ausreichend, und die kürzeste Route finden Sie. Wenn dann der kürzeste Pfad zum Scheitelpunkt N aktualisiert wird, wenn die Schleife erneut gedreht wird, kann festgestellt werden, dass es einen negativen geschlossenen Pfad gibt, der den Scheitelpunkt N enthält. ~~ Wenn ich einen Code (zweiten Code) erstellte, ohne dass die Knotenstruktur verwendet wurde, wurde die Geschwindigkeit um ein konstantes Vielfaches erhöht und es war möglich, sie von 47 ms auf 8 ms zu verkürzen.

answerD.cc

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
//Hier muss man genug tun
#define INF 1000000000000

struct Node{
  //Knoteninformationen
  vector<pair<ll,ll>> edge;//Knotennummer und Kosten für die Verbindung mit jeder Kante
  //Daten für die Bellmanford-Methode
  ll mincost=INF;//Mindestkosten für diesen Knoten
};

//Entfernen Sie nicht verwandte Schleifen
bool bellmanford(vector<Node>& nodes,ll l1){
  //(l1-1)(Gewöhnlicher Pagen)+1(Erkennung)
  for(ll i=0;i<l1;i++){
    for(ll j=0;j<l1;j++){
      Node x=nodes[j];
      if(x.mincost!=INF){
        ll l2=x.edge.size();
        for(ll k=0;k<l2;k++){
          ll a=x.mincost+x.edge[k].second;
          if(nodes[x.edge[k].first].mincost>a){
            nodes[x.edge[k].first].mincost=a;
            if(i==l1-1 and x.edge[k].first==l1-1) return true;//Richtig, wenn es einen negativen Abschluss gibt
          }
        }
      }
    }
  }
  return false;//Falsch, wenn kein negativer Abschluss vorliegt
}

int main(){
  ll n,m;cin >> n >> m;
  vector<Node> Nodes(n);
  //Aktualisieren Sie mincost0 nur fest
  Nodes[0].mincost=0;

  for(ll i=0;i<m;i++){
    ll a,b,c;cin >> a >> b >> c;
    Nodes[a-1].edge.push_back(make_pair(b-1,-c));
  }
  //Knoten aktualisieren
  if(bellmanford(Nodes,n)){
    cout << "inf" << endl;
  }else{
    cout << -Nodes[n-1].mincost << endl;
  }
}

answer.cc

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
//Hier muss man genug tun
#define INF 1000000000000

struct Edge{
  ll to_Node;
  ll cost;
  Edge(ll t,ll c){to_Node=t;cost=c;}
};

//Entfernen Sie nicht verwandte Schleifen
bool bellmanford(vector< vector<Edge> >& Edges,vector<ll>& mincost,ll n){
  //(l1-1)(Gewöhnlicher Pagen)+1(Erkennung)
  for(ll i=0;i<n;i++){
    for(ll j=0;j<n;j++){
      if(mincost[j]!=INF){
        ll e=Edges[j].size();
        for(ll k=0;k<e;k++){
          ll new_mincost=mincost[j]+Edges[j][k].cost;
          if(mincost[Edges[j][k].to_Node]>new_mincost){
            mincost[Edges[j][k].to_Node]=new_mincost;
            if(i==n-1 and Edges[j][k].to_Node==n-1)return true;//Richtig, wenn es einen negativen Abschluss gibt
          }
        }
      }
    }
  }
  return false;//Falsch, wenn kein negativer Abschluss vorliegt
}

int main(){
  ll n,m;cin >> n >> m;
  vector<ll> mincost(n,INF);
  vector< vector<Edge> > Edges(n);
  //Aktualisieren Sie mincost0 nur fest
  mincost[0]=0;

  for(ll i=0;i<m;i++){
    ll a,b,c;cin >> a >> b >> c;
    Edges[a-1].push_back(Edge(b-1,-c));
  }
  //Knoten aktualisieren
  if(bellmanford(Edges,mincost,n)){
    cout << "inf" << endl;
  }else{
    cout << -mincost[n-1] << endl;
  }
}