[PYTHON] AtCoder Beginner Contest 070 Revue des questions précédentes

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

Temps requis

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;
  }
}