AtCoder Beginner Contest 061 Revue des questions précédentes

Temps requis

スクリーンショット 2020-01-06 11.52.06.png

Problème A

Sortie juste dans différents cas

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")

Problème B

Il suffit de compter le nombre de chaque ville

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])

Problème C

C ’est vraiment une grande croissance de pouvoir éliminer ces problèmes en quelques secondes. C'est ridicule de penser à chaque insertion, donc si vous pensez à quoi elle ressemblera à la fin, vous constaterez que vous devriez enfin trier par ordre croissant et commencer par la plus petite. Par conséquent, nous réalisons que nous devons considérer le nombre d'éléments de 1 à 10 ** 5, alors préparez un tableau pour compter chaque élément. Si vous pouvez le préparer, vous pouvez voir que le compte est compté à partir de l'avant et que l'élément lorsqu'il devient k ou plus est le K-ème plus petit nombre.

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

Problème D

C'est un problème de niveau bleu, mais j'ai pu le résoudre en 30 minutes environ! (J'ai également publié 4WA, donc je le regrette.) La politique elle-même a été mise en place assez rapidement, mais je n'ai pas pu terminer les détails. Tout d'abord, on soupçonne qu'il s'agit de la méthode de Bellmanford car les poids des côtés sont à la fois positifs et négatifs dans le graphe orienté pondéré ouvert et il semble que nous pouvons y aller même si nous regardons les contraintes. Cependant, comme il est difficile de trouver le chemin le plus long au lieu du chemin le plus court, les poids peuvent être inversés, ce qui peut être obtenu en multipliant les poids de tous les côtés par -1 (** Si vous considérez le chemin le plus long au lieu du chemin le plus court). J'ai appris qu'il peut être inversé en multipliant par -1. Je pense qu'il peut également être utilisé pour d'autres problèmes. ). En gros, vous pouvez le faire de cette façon ( N'oubliez pas de multiplier par -1 dans la sortie finale **), mais vous devez penser au cas de inf. Au début, j'ai utilisé la condition de fermeture négative de la méthode de Bellmanford sans penser à rien, mais dans certains cas, elle est devenue WA. Si vous y réfléchissez attentivement ici, même s'il y a une fermeture négative à un endroit qui n'a rien à voir avec le chemin que vous prenez en atteignant le Nième sommet, cette fermeture négative sera détectée, alors incluez le Nième sommet. Il s'avère que nous devons détecter les fermetures négatives.

Quand j'écrivais cet article, je lisais l'article de Kenchon et j'ai trouvé que c'était une fausse solution. Je voudrais le réécrire dans la bonne solution et le republier dans un autre article. La partie avec la ligne d'annulation ci-dessous est un mensonge, alors pensez-y en vous référant à l'article de Kenchon S'il te plait donne moi.

Le code de la méthode Bellmanford a été écrit dans une classe universitaire, donc le premier code consiste à utiliser ce code (toutes les informations sont gérées par la structure Node). De plus, int débordera, alors rendez-le long et définissez la valeur INF sur une valeur suffisamment grande. En tournant la boucle (nombre de sommets-1) dans cet état (s'il n'y a pas de fermeture négative, le chemin le plus court d'un sommet à certains sommets ne passe par au plus N sommets qu'une seule fois (nombre de sommets) -1) Vous pouvez trouver un tel itinéraire assez en 1), et l'itinéraire le plus court peut être trouvé. Ensuite, si le chemin le plus court vers le sommet N est mis à jour lorsque la boucle est à nouveau tournée, il peut être déterminé qu'il existe un chemin fermé négatif comprenant le sommet N. ~~ De plus, lorsque j'ai créé un code (deuxième code) lorsque la structure Node n'est pas utilisée, la vitesse a été augmentée d'un multiple constant et il était possible de la raccourcir de 47 ms à 8 ms.

answerD.cc


#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
//Tu dois en faire assez ici
#define INF 1000000000000

struct Node{
  //Informations sur le nœud
  vector<pair<ll,ll>> edge;//Numéro de nœud et coût de connexion à chaque bord
  //Données pour la méthode de Bellmanford
  ll mincost=INF;//Coût minimum pour ce nœud
};

//Supprimer les boucles non liées
bool bellmanford(vector<Node>& nodes,ll l1){
  //(l1-1)(Groom ordinaire)+1(détection)
  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;//Vrai s'il y a une fermeture négative
          }
        }
      }
    }
  }
  return false;//Faux s'il n'y a pas de clôture négative
}

int main(){
  ll n,m;cin >> n >> m;
  vector<Node> Nodes(n);
  //Mettez à jour uniquement mincost0 fermement
  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));
  }
  //Mettre à jour les nœuds
  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;
//Tu dois en faire assez ici
#define INF 1000000000000

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

//Supprimer les boucles non liées
bool bellmanford(vector< vector<Edge> >& Edges,vector<ll>& mincost,ll n){
  //(l1-1)(Groom ordinaire)+1(détection)
  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;//Vrai s'il y a une fermeture négative
          }
        }
      }
    }
  }
  return false;//Faux s'il n'y a pas de clôture négative
}

int main(){
  ll n,m;cin >> n >> m;
  vector<ll> mincost(n,INF);
  vector< vector<Edge> > Edges(n);
  //Mettez à jour uniquement mincost0 fermement
  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));
  }
  //Mettre à jour les nœuds
  if(bellmanford(Edges,mincost,n)){
    cout << "inf" << endl;
  }else{
    cout << -mincost[n-1] << endl;
  }
}

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 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 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 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
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes