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

Die zweite Frage, die ich zuvor gelöst habe

Benötigte Zeit

Problem A

Beurteilen Sie einfach, ob Anfang und Ende gleich sind (behandeln Sie es wie eine Zeichenfolge)

answerA.py

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

B-Problem

Der gemeinsame Teil (die Zeit, die die beiden Personen gedrückt haben) liegt zwischen max von a und c und min von b und d. Wenn es also existiert, können Sie die Zeit finden, wenn es existiert. ..

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)

C-Problem

Das Problem des minimalen gemeinsamen Vielfachen, das in 2 Sekunden verstanden werden kann, habe ich in Python gelöst, als ich es das letzte Mal gelöst habe, aber dieses Mal habe ich es in C ++ gelöst. Python muss nur die gcd-Funktion verwenden, um lcm auszugeben, aber C ++ kann das nicht. (Derzeit werden sowohl gcd als auch lcm in C ++ implementiert und in eine Bibliothek umgewandelt.) Erstens müssen Sie long long verwenden, da es aufgrund der Einschränkung des Problems nicht in int passt (long long ist immer ll). Außerdem habe ich bei lcm eine Multiplikation ** durchgeführt, die den Bereich von ** long long überschreiten könnte, also habe ich zuerst die Division und dann die Multiplikation durchgeführt.

answerC.cc

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

//Machen Sie es mit while kleiner
ll gcd(ll x,ll y){
  if(x<y) swap(x,y);
  //x ist immer größer
  while(y>0){
    ll r=x%y;
    x=y;
    y=r;
  }
  return x;
}

ll lcm(ll x,ll y){
  //Es wird zu groß, wenn Sie es anziehen
  return ll(x/gcd(x,y))*y;
  //Ursprünglich ll(x*y/gcd(x,y));Hat gemacht
}

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)

D Problem

Ich habe mich für C ++ für die Baumstruktur entschieden (da es schwierig ist, den Rechenaufwand abzuschätzen, und es oft schwierig ist, dies mit Python zu tun). Der erste Code ist der Code, der zuvor gelöst wurde, und der zweite Code ist der Code, der dieses Mal gelöst wurde. Als ich es das erste Mal gelöst habe, habe ich mir zu viel Zeit genommen, um darüber nachzudenken, aber am Ende ist klar, dass ich die Entfernung wissen möchte. Wenn ich also davon ausgehe, dass es sich um einen Baum handelt, kann ich normalerweise eine Suche mit Tiefenpriorität oder eine Suche mit Breitenpriorität durchführen. Ich verstehe. (** Ich denke immer, dass die Abstraktion von Suchproblemen in einer Baumstruktur oft fehlschlägt. ) Hier habe ich die Suche nach Tiefenpriorität (ohne Grund) ausgewählt, den Baum, der die Informationen der Seite enthält, die sich von jedem Knoten erstreckt, den Baum_len, der die kürzeste Route von k enthält, und die Prüfung, ob ein Besuch stattgefunden hat oder nicht. Wenn vorbereitet, kann der kürzeste Weg von k erhalten werden, indem eine normale Tiefenprioritätssuche durchgeführt wird. Einmal gefragt, besteht die Antwort darin, die Länge der kürzesten Route in k → x und die Länge der kürzesten Route in k → y in jeder Fragenabfrage hinzuzufügen. ( Ich möchte in der Lage sein, den Code für die Suche nach Tiefenprioritäten schnell zu schreiben, ohne ihn in eine Bibliothek zu verschieben. Es geht darum, die Informationen des aktuellen Knotens gründlich umzuschreiben und den von ihm verbundenen Knoten rekursiv aufzurufen. Vergessen Sie nicht, den Code zu schreiben, um zu überprüfen, ob Sie besucht haben. **) Außerdem läuft dieses Problem auch mit ** int über, so dass es notwendig ist, es lang lang ** zu machen. Außerdem habe ich einen Fehler gemacht **, weil es ein Baum ist, also dachte ich, es sei n, obwohl es nur n-1 Seiten hat, und habe versucht, Eingaben zu empfangen, und es ging in einen Eingabe-Standby-Zustand **.

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;

//Es ist klüger, keine Node-Klasse zu erstellen, damit Sie diese schneller schreiben können
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);//Informationen auf der Seite, die sich vom Knoten aus erstreckt
  vector<ll> tree_len(n,0);//Kürzeste Route
  vector<bool> check(n,false);//Ob du gefolgt bist
  //Ich konnte nicht mit n tippen
  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;
  }
}