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

Questions passées résolues pour la première fois

Temps requis

スクリーンショット 2020-01-04 8.38.16.png

Problème A

answerA.py


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

Avec l'opérateur ternaire

answerA_better.py


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

Problème B

Connectez les brillants dans l'ordre. Je remplissais AtCoder avec B au tout début, et j'ai senti une croissance quand j'ai vu que ce n'était pas bien fait à ce moment-là.

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)

Problème C

J'ai fait un tableau de coefficients binomiaux, mais je n'en avais pas besoin.

answerC.cc


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

const int MAX = 10000000;
//Par quoi diviser
const int MOD = 1000000007;

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

//Prétraitement pour faire une table
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;
    }
}

//Calcul du coefficient binaire
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(){
  //Prétraitement
  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;
  }
}

Problème D

Quand je l'ai vu pour la première fois, je ne savais pas vraiment quoi faire (car la méthode que je pensais était susceptible d'être TLE). En regardant la réponse, il semble que l'arborescence de la superficie totale minimale soit utilisée, alors quand je l'ai étudié, j'ai trouvé qu'il y avait deux méthodes, la méthode prim et la méthode claspal. Ce dernier dit d'utiliser UnionFind, et UnionFind n'est pas très familier (j'ai oublié de l'implémenter car je l'ai trop utilisé, je dois faire avancer le livre en spirale rapidement), donc quand j'essaye de l'implémenter avec la méthode prim, beaucoup de bugs se produisent. J'ai fondu un bon bout de temps. (** L'implémentation de Priority_queue a tendance à être boguée et oublie que pousser peut changer le haut **) La méthode prim est un algorithme assez similaire à la méthode Dyxtra. Dans la méthode Dyxtra, un point de départ est déterminé et le sommet le plus proche pouvant être atteint à partir de ce point de départ est défini comme le prochain sommet à visiter, et par la suite, les visites sont répétées dans l'ordre à partir du point de départ qui peut être atteint à partir du sommet inclus dans l'ensemble de vertex visité. Je vais. En d'autres termes, préparez un tableau avec des informations sur les (multiples) arêtes s'étendant à partir de chaque sommet, extrayez uniquement les arêtes s'étendant à partir du sommet visité et plongez dans priority_queue. Ensuite, parmi les sommets non visités qui peuvent être atteints via l'arête qui plonge dans la priority_queue, ** le plus proche du point de départ ** est le prochain sommet à visiter (la partie coût de l'arête est ** la distance du point de départ * N'oubliez pas de mettre à jour vers * puis de plonger dans priority_queue). L'itinéraire le plus court peut être trouvé en répétant une telle mise à jour (nombre de sommets-1) fois. Ici, nous allons considérer la méthode prim en la comparant à la méthode Dyxtra. Dans la méthode Dyxtra, l'exigence finale est la ** distance du point de départ . En d'autres termes, le prochain sommet à visiter sera celui avec la distance la plus courte du point de départ qui n'a pas encore été visité. Par contre, dans la méthode prim, le résultat final est l ' arbre de la superficie totale minimale ** (voir description ci-dessous). En d'autres termes, l'arête suivante à choisir est ** l'arête la moins coûteuse ** qui s'étend du sommet visité au sommet non visité. En raison de ces différences, la méthode Dixtra nécessite que la clé à comparer par priority_queue soit mise à jour à la distance du point de départ, alors que la méthode Prim fait la différence que la clé à comparer par priority_queue est simplement le coût du côté. .. De plus, lors de l'implémentation, si vous mettez votre propre classe dans priority_queue, vous pouvez la faire fonctionner comme prévu en définissant uniquement <. De plus, v1 et v2 sont ici triés par x et y, respectivement. En effet, il est clair que seul le côté qui relie les éléments qui viennent des deux côtés lorsqu'ils sont triés par coordonnées est sélectionné comme côté de l'arborescence de l'aire totale minimale. (Pour plus de détails, voir Explication.)

L'arbre de surface entier est → ** L'arbre qui relie tous les sommets du sous-arbre donné ** Quel est l'arborescence de surface totale minimale? → ** L'arbre de toutes les surfaces minimise le coût total **

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_la file d'attente a une priorité élevée(<Celui qui vient à droite)Est sorti en premier
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];});

  //Ici, placez le côté s'étendant de chaque nœud dans la file d'attente
  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])));
  }

  //Rendez-le visité à partir de 0
  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;
  //Je visiterai de plus en plus dans l'ordre
  while(edges.size()!=0){
    //to_Si le nœud a été visité, si oui, simplement priorité_Retirer simplement de la file d'attente
    if(!check[now.to_Node]){
      check[now.to_Node]=true;//Faites-le visiter
      cost_sum+=now.cost;//Mise à jour du coût total
      int k=now.to_Node;
      ll l=edges_before[k].size();
      edges.pop();//Hors côtés usagés
      for(ll i=0;i<l;i++){//Priorité du côté partant du sommet nouvellement visité_Ajouter à la liste
        Edge s=edges_before[k].front();
        if(!check[s.to_Node]) edges.push(s);//Pousser uniquement les sommets non visités
        edges_before[k].pop();
      }
      now=edges.top();
      //Cela n'a pas été beaucoup plus rapide, mais n fois suffit, alors ↓
      if(++i==n-1)break;
    }else{
      edges.pop();now=edges.top();
    }
  }
  cout << cost_sum << 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 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 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 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 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
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes