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

La deuxième question que j'ai résolue auparavant

Temps requis

スクリーンショット 2019-12-24 12.51.02.png

Problème A

Jugez simplement si le début et la fin sont les mêmes (manipulez comme une chaîne de caractères telle quelle)

answerA.py


n=input()
if n[0]==n[-1]:
    print("Yes")
else:
    print("No")

Problème B

La partie commune (le temps que les deux personnes poussaient) est entre max de a et c et min de b et d, donc si elle existe, vous pouvez trouver l'heure si elle existe. ..

answerB.py


a,b,c,d=map(int,input().split())
k,l=max(a,c),min(b,d)

if k>=l:
    print(0)
else:
    print(l-k)

Problème C

Le problème du multiple commun minimum qui peut être compris en 2 secondes, je l'ai résolu en Python la dernière fois que je l'ai résolu, mais cette fois je l'ai résolu en C ++. Python n'a besoin que de la fonction gcd pour générer lcm, mais C ++ ne peut pas le faire. (Pour le moment, gcd et lcm sont implémentés en C ++ et transformés en bibliothèque) Tout d'abord, vous devez utiliser long long car il ne rentre pas dans int en raison de la limitation du problème (long long vaut toujours ll). De plus, au lcm, je faisais une multiplication ** qui pouvait dépasser la plage de ** long long, donc j'ai d'abord fait la division puis la multiplication.

answerC.cc


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

//Réduisez-le avec while
ll gcd(ll x,ll y){
  if(x<y) swap(x,y);
  //x est toujours plus grand
  while(y>0){
    ll r=x%y;
    x=y;
    y=r;
  }
  return x;
}

ll lcm(ll x,ll y){
  //Ça devient trop gros quand tu le mets
  return ll(x/gcd(x,y))*y;
  //À l'origine ll(x*y/gcd(x,y));Était en train de faire
}

int main(){
  ll n;cin >> n;
  ll ans=1;
  for(int i=0;i<n;i++){
    //cout << ans << endl;
    ll t;cin >> t;
    ans=lcm(ans,t);
  }
  cout << ans << endl;
}

answerC.py


import fractions
n=int(input())
t=[int(input()) for i in range(n)]

if n==1:
    print(t[0])
else:
    x=t[0]*t[1]//fractions.gcd(t[0],t[1])
    for i in range(1,n-1):
        x=x*t[i+1]//fractions.gcd(x,t[i+1])
    print(x)

Problème D

J'ai décidé d'utiliser C ++ pour l'arborescence (car il est difficile d'estimer la quantité de calcul et c'est souvent difficile de le faire avec Python). Le premier code est le code qui a été résolu auparavant, et le deuxième code est le code qui a été résolu cette fois. Quand je l'ai résolu la première fois, j'ai pris trop de temps à réfléchir à sa conception, mais au final, il est clair que je veux connaître la distance, donc étant donné qu'il s'agit d'un arbre, je peux généralement faire une recherche de priorité de profondeur ou une recherche de priorité de largeur. Je comprends. (** Je pense toujours que l'abstraction des problèmes de recherche dans une arborescence échoue souvent. ) Ici, j'ai choisi la recherche de priorité de profondeur (sans raison), l'arbre qui contient les informations du côté s'étendant de chaque nœud, le tree_len qui contient l'itinéraire le plus court à partir de k, et le contrôle qui contient si une visite a été effectuée ou non. S'il est préparé, l'itinéraire le plus court à partir de k peut être obtenu en effectuant une recherche de priorité de profondeur normale. Une fois posée, la réponse est d'ajouter la longueur de la route la plus courte en k → x et la longueur de la route la plus courte en k → y dans chaque question. ( Je veux pouvoir écrire le code de recherche de priorité de profondeur rapidement sans en faire une bibliothèque. Le but est de réécrire complètement les informations du nœud actuel et lors de l'appel du nœud connecté à partir de celui-ci de manière récursive. N'oubliez pas d'écrire le code pour vérifier si vous avez visité. **) De plus, ce problème déborde également avec ** int, il est donc nécessaire de le rendre long long **. De plus, j'ai fait une erreur ** parce que c'est un arbre, donc j'ai pensé que c'était n même s'il n'avait que n-1 côtés, et j'ai essayé de recevoir une entrée, et il est passé dans un état d'attente d'entrée **.

answerD.cc


#include<iostream>
#include<vector>
#include<utility>
using namespace std;

class Node{
public:
  vector< pair<int,int> > v;
  long long dist;
  bool check=false;
};

void depth_search(vector<Node>& V,int k,long long d){
  V[k].dist=d;
  V[k].check=true;
  int l=V[k].v.size();
  for(int i=0;i<l;i++){
    if(V[V[k].v[i].first].check==false){
      depth_search(V,V[k].v[i].first,V[k].v[i].second+d);
    }
  }
}

int main(){
  int n;cin >> n;
  vector<Node> V(n);
  for(int i=0;i<n-1;i++){
    int a,b,c;cin >> a >> b >> c;
    V[a-1].v.push_back(make_pair(b-1,c));
    V[b-1].v.push_back(make_pair(a-1,c));
  }
  int q,k;cin >> q >> k;k-=1;
  depth_search(V,k,0);
  vector<long long> Q(q);
  int x,y;
  for(int i=0;i<q;i++){
    cin >> x >> y;
    Q[i]=V[x-1].dist+V[y-1].dist;
  }
  for(int i=0;i<q;i++){
    cout << Q[i] << endl;
  }
}

answerD.cc


#include<iostream>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
typedef vector< vector< pair<long long,long long> > > vvp;

//Il est plus intelligent de ne pas créer de classe Node, pour pouvoir l'écrire plus rapidement
void dfs(vvp& tree,vector<ll>& tree_len,vector<bool>& check,ll dep,ll now){
  tree_len[now]=dep;
  check[now]=true;
  ll l=tree[now].size();
  for(int i=0;i<l;i++){
    if(check[tree[now][i].first]==false) dfs(tree,tree_len,check,dep+tree[now][i].second,tree[now][i].first);
  }
}

int main(){
  ll n;cin >> n;
  vvp tree(n);//Informations sur le côté partant de Node
  vector<ll> tree_len(n,0);//Rétention d'itinéraire le plus court
  vector<bool> check(n,false);//Si vous avez suivi
  //Je n'ai pas pu finir de taper avec n
  for(int i=0;i<n-1;i++){
    ll a,b,c;cin >> a >> b >> c;
    tree[a-1].push_back(make_pair(b-1,c));
    tree[b-1].push_back(make_pair(a-1,c));
  }
  ll q,k;cin >> q >> k;
  dfs(tree,tree_len,check,0,k-1);
  for(int i=0;i<q;i++){
    ll x,y;cin >> x >> y;
    cout << tree_len[x-1]+tree_len[y-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 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 054 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 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 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
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