[PYTHON] Codeforces Runde # 592 (Div. 2) Bacha Review (11/03)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich habe aufgrund des C-Problems einen Fehler in der Mathematik der High School gemacht. Zum Teil, weil ich die Bibliothek zum zweiten Mal benutzt habe, bin ich enttäuscht, dass ich sie während des Wettbewerbs nicht debuggen konnte.

Außerdem war das D-Problem so einfach, dass ich noch mehr enttäuscht war ... Ich würde gerne mein Bedauern nähren, aber es ist schwierig, damit umzugehen, wenn ich einen Fehler mache.

Problem A

Das ist einfach. Alles, was Sie tun müssen, ist, genügend Kugelschreiber und Bleistifte für die Vorlesung und den praktischen Unterricht vorzubereiten. Mit anderen Worten, Sie benötigen nur $ - (- a // c) bzw. - (- b // d) $ Bücher.

A.py

for _ in range(int(input())):
    a,b,c,d,k=map(int,input().split())
    x=-(-a//c)
    y=-(-b//d)
    if x+y>k:
        print(-1)
    else:
        print(x,y)

B-Problem

Ich denke, dass es ein Problem ist, das Esper-Power erfordert. Wenn Sie mit ** Proben ** experimentieren, werden Sie feststellen, dass ** alle Räume zurückverfolgt werden können, wenn die Endräume im Ober- und Untergeschoss verbunden sind **. Wenn dies auf andere Fälle angewendet wird, ist es daher am besten, nur dem Raum auf dieser Etage zu folgen oder in eine andere Etage in dem Raum zu wechseln, der der Kante ** am nächsten liegt, während die oberen und unteren Etagen miteinander verbunden sind. ist. Sie können es sehen, indem Sie die Abbildung unten betrachten.

Daher können Sie den folgenden Code unter Berücksichtigung der drei Muster schreiben, mit denen Sie vom linken und rechten Ende in eine andere Etage wechseln und nur den Raum auf einer Etage verfolgen.

B.py

for _ in range(int(input())):
    n=int(input())
    s=list(map(int,input()))
    ans=n
    if 1 not in s:
        print(ans)
        continue
    for i in range(n):
        if s[i]==1:
            ans=max(ans,n*2-i*2)
            break
    for i in range(n-1,-1,-1):
        if s[i]==1:
            ans=max(ans,n*2-(n-1-i)*2)
            break
    print(ans)

C-Problem

Es gab ein Problem ** wie die Notwendigkeit, es zu einer 128-Bit-Ganzzahl zu machen **, also war ich ungeduldig und konnte nicht debuggen. In diesem Problem wird $ w, d, p, n $ angegeben, um zu bestimmen, ob es eine nicht negative ganze Zahl $ x, y, z $ gibt, die die folgenden Anforderungen erfüllt, und wenn ja, wird die entsprechende Menge ausgewählt. Fragen Sie einfach.

wx+dy=p…① x+y+z=n…②

Erstens gibt es nur zwei Gleichungen für die drei Variablen $ x, y und z $, sodass die Antwort nicht eindeutig bestimmt wird **. Hier wird $ z $ nur in ② angezeigt. Entscheiden Sie sich also zuerst für $ x, y $. Mit anderen Worten, wenn Sie sich Gleichung (1) ansehen, können Sie sehen, dass es sich um eine quadratische lineare unbestimmte Gleichung handelt. Lösen Sie diese Lösung, um eine Menge von $ x, y $ zu finden, die $ x + y $ so klein wie möglich macht, und dass $ x, y $ $ ist. Wenn x + y \ leqq n $ erfüllt ist, existiert auch $ z $.

Nun, da $ d \ <w $, sollten Sie versuchen, $ x $ so groß wie möglich zu machen ($ \ leftrightarrow $ ** $ y $ so klein wie möglich **). Wenn Sie die gestern erstellte Bibliothek binärer linearer unbestimmter Gleichungen verwenden, ist $ x = x \ _ 0 + m * b, y = y \ _0- Sie können $ x \ _0, y \ _0, a, b $ finden, was m * a $ ist. Wenn also $ y \ _0 $ positiv ist, ist $ m = Etage (y \ _ 0, a) $, und wenn $ y \ _0 $ negativ ist, ist $ m = Ceil (-y \ _ 0, a) $. Dann wird $ y $ zum Minimum, also ist $ x, y $, das für dieses $ m $ erhalten wird, eine Menge von $ x, y $, die $ x + y $ minimiert, und dies erfüllt die obige Bedingung. Denken Sie nur darüber nach.

C_overflow.cc

//Debug-Optionen:-fsanitize=undefined,address

//Compileroptimierung
#pragma GCC optimize("Ofast")

//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //Einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares

//Rückgabewert:Maximale Verpflichtungen für a und b
// ax + by = gcd(a, b)Treffen(x, y)Wird gelagert
ll extGCD(ll a, ll b, ll &x, ll &y) {
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll d=extGCD(b,a%b,y,x);
    y-=a/b*x;
    return d;
}


signed main(){
    //Ausgabespezifikation der Anzahl der Bruchstellen
    //cout<<fixed<<setprecision(10);
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,p,w,d;cin>>n>>p>>w>>d;
    if(p%gcd(w,d)!=0){
        cout<<-1<<endl;
        return 0;
    }
    ll f=gcd(w,d);
    ll h=p/f;
    ll x,y;
    extGCD(w,d,x,y);
    //Zu diesem Zeitpunkt sollte y so klein wie möglich sein(x ist groß)
    x*=h;y*=h;
    // /cout<<x<<" "<<y<<endl;
    w/=f;
    d/=f;
    if(y>=0){
        ll g=y/w;
        x+=g*d;
        y-=g*w;
    }else{
        ll g=(-y+(w-1))/w;
        x-=g*d;
        y+=g*w;
    }
    //cout<<x<<" "<<y<<endl;
    if(x<0 or x+y>n){
        cout<<-1<<endl;
    }else{
        //cout<<x<<endl;
        //cout<<(n-x-y)<<endl;
        cout<<x<<" "<<y<<" "<<(n-x-y)<<endl;
    }
}

C.py

from sys import setrecursionlimit
setrecursionlimit(10**8)
def extgcd(a,b,x,y):
    if b==0:
        x[0]=1
        y[0]=0
        return a
    e=extgcd(b,a%b,y,x)
    y[0]-=(a//b)*x[0]
    return e

n,p,w,d=map(int,input().split())
from math import gcd
if p%gcd(w,d)!=0:
    print(-1)
    exit()
f=gcd(w,d)
h=p//f
x,y=[0],[0]
extgcd(w,d,x,y)
x=x[0]*h
y=y[0]*h
w//=f
d//=f
if y>=0:
    g=y//w
    x+=g*d
    y-=g*w
else:
    g=-(y//w)
    x-=g*d
    y+=g*w
if x<0 or x+y>n:
    print(-1)
else:
    print(x,y,n-x-y)

D Problem

Es war 2000 Mal einfacher als das C-Problem, als es nach dem Wettbewerb gelöst wurde. Was?

Als ich es zum ersten Mal las, dachte ich, es sei ein Baum-DP, aber ich muss nicht so viel tun. Erstens ist die Bedingung, dass die Scheitelpunkte in dem Pfad, der durch drei verschiedene Scheitelpunkte dargestellt wird, in verschiedenen Farben gezeichnet werden, dass ** es keine Scheitelpunkte des Grades 3 oder höher ** geben darf. Dies kann durch die Absurditätsmethode gezeigt werden.

Zu diesem Zeitpunkt gibt es nur einen ** Pfadgraphen ** als verketteten Graphen, in dem die Reihenfolge eines Scheitelpunkts 2 oder weniger beträgt und keinen geschlossenen Pfad enthält. Sie können es leicht verstehen, indem Sie die Seiten in der Reihenfolge vom oberen Ende des Endes (der Reihenfolge 1) verlängern. Daher wird zuerst bestimmt, ob es sich um einen Pfadgraphen handelt, und wenn es sich nicht um einen Pfadgraphen handelt, wird sofort -1 ausgegeben. Auf der anderen Seite ist es bei Pfaddiagrammen leicht zu zeigen, dass es eine Möglichkeit gibt, Farben zu malen, die immer die Bedingungen erfüllen. Mit anderen Worten, wenn Sie die Farbe $ a, b, c $ vom Rand aus malen, werden die verbleibenden Scheitelpunkte eindeutig als $ a, b, c, a, b, c, ... $ gezeichnet. Daher müssen nur die Kosten für jede der drei Möglichkeiten zum Malen der Farben der drei Scheitelpunkte am Ende des Pfaddiagramms (3! Wege) ermittelt und der Mindestwert ** ermittelt werden. Außerdem können 3! Streets mit der Permutationsfunktion ausgeschrieben werden. In jedem Fall müssen nur Berechnungen bis zu 10 ^ 5 $ Mal durchgeführt werden, damit sie ausreichend schnell arbeiten. Die kumulative Summe kann das konstante Vielfache reduzieren, ist jedoch nicht erforderlich, da der Berechnungsbetrag einen Spielraum aufweist.

D.py

n=int(input())
c=[list(map(int,input().split())) for i in range(3)]
edges=[[] for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)
for i in range(n):
    if len(edges[i])>2:
        print(-1)
        exit()
path=[]
for i in range(n):
    if len(edges[i])==1:
        path.append(i)
        break
#print(path)
#print(edges)
seen=[False]*n
seen[path[-1]]=True
#exit()
while True:
    for i in edges[path[-1]]:
        if not seen[i]:
            path.append(i)
            seen[i]=True
            break
    else:
        break
#print(path)
d=[[0]*n for i in range(3)]
for i in range(3):
    now=0
    for j in path:
        d[i][now]=c[i][j]
        now+=1
#print(d)
from itertools import permutations
ans=10**30
now=[]
for i in permutations(range(3),3):
    ans_sub=0
    now_sub=[0]*n
    for j in range(n):
        now_sub[path[j]]=i[j%3]+1
        ans_sub+=d[i[j%3]][j]
    if ans_sub<ans:
        ans=ans_sub
        now=now_sub
print(ans)
print(" ".join(map(str,now)))

Nach dem E-Problem

Ich werde diesmal nicht lösen.