[PYTHON] Codeforces Runde # 613 (Div. 2) Bacha Review (10/1)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ist es als Klasse in Ordnung? ** Ich konnte die Levelbereichsprobleme lösen, die ich lösen musste **, was von mir hoch bewertet wird. Ich bedauere jedoch, dass ich das E-Problem nicht vollständig berücksichtigen konnte, indem ich den Stuhl in der verbleibenden Stunde erwärmte **.
(Dieses Mal werde ich das E-Problem überspringen, da die Richtlinie nicht sofort veröffentlicht wurde.)
Problem A
Wenn Sie so weit wie möglich nach links gehen möchten, erreichen Sie die Koordinaten von- (die Anzahl von $ L $ in der Zeichenfolge), und wenn Sie so weit wie möglich nach rechts gehen möchten, erreichen Sie die Koordinaten (die Anzahl von $ R $ in der Zeichenfolge). Außerdem können ** alle dazwischen liegenden Koordinaten erreicht werden **, sodass die Antwort (die Anzahl von $ R $ in der Zeichenfolge) + (die Anzahl von $ L $ in der Zeichenfolge) + 1 lautet.
(** Nur beide Enden des Bereichs prüfen! **)
A.py
n=int(input())
s=input()
print(s.count("L")+s.count("R")+1)
B-Problem
Ich habe verschiedene Problemsätze verpasst. Es ist ein Spiegelbild. Insbesondere sollte beachtet werden, dass Adel ** fortlaufende Unterspalten ** und ** nicht das gesamte ** auswählen kann.
Hier wird die Köstlichkeit des von Yasser ausgewählten Kuchens nur mit $ O (N) $ berechnet, sodass ** Adel den Maximalwert ** (✳︎) in der durchgehenden Teilzeichenfolge findet, die ausgewählt werden kann, und dieser Wert ist Wenn es kleiner als die Summe ist, sollte "JA" ausgegeben werden, andernfalls sollte "NEIN" ausgegeben werden.
Wenn der Maximalwert in einer fortlaufenden Unterspalte $ dp [i]: = $ ist (der Maximalwert der Teilsumme der fortlaufenden Unterspalten, die mit $ i $ th enden), ist ** $ i-1 $ th das Ende. Sie kann von DP berechnet werden, indem nur überlegt wird, ob sie an den kontinuierlichen Teilstring mit as angehängt werden soll oder nicht. Wenn jedoch ein normaler DP für eine bestimmte Anzahl von Spalten ausgeführt wird, erfüllt er nicht die Bedingung, dass ** das Ganze nicht ausgewählt werden kann **.
Mit anderen Worten, Sie können antworten, indem Sie sagen, dass Sie nicht gleichzeitig das erste und das letzte Element auswählen müssen. Daher führt $ dp1 $ DP aus, um den Maximalwert der Summe zu ermitteln, wenn eine fortlaufende Unterspalte aus $ n $ -1st Element ausgewählt wird und $ dp2 $ $ aus dem 2. Element ist Führt DP aus, um den Maximalwert der Summe zu ermitteln, wenn eine fortlaufende Unterspalte aus dem n-ten Element ausgewählt wird. Der von diesen beiden DPs erhaltene Maximalwert ist der Maximalwert in (✳︎).
B.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
inf=10**15
dp1=[-inf]*(n-1)
dp1[0]=a[0]
for i in range(1,n-1):
dp1[i]=max(dp1[i-1]+a[i],a[i])
dp2=[-inf]*(n-1)
dp2[0]=a[1]
for i in range(2,n):
dp2[i-1]=max(dp2[i-2]+a[i],a[i])
if max(dp1+dp2)<sum(a):
print("YES")
else:
print("NO")
C-Problem
Erstens sind unter der Bedingung, dass $ LCM (a, b) = X $, ** $ a und b $ jeweils ein Bruchteil von $ X $ ** sind. Aufgrund der Einschränkungen des Problems können ** alle Brüche durchsucht werden **, sodass $ a $ als Bruch von $ X $ verwendet wird und alle Suchvorgänge ausgeführt werden.
Betrachten Sie das kleinste $ b $, wobei ** $ a $ festgelegt ist **. Wenn zu diesem Zeitpunkt $ GCD (a, b) = 1 $ ist, ist $ b = \ frac {X} {a} $ das Minimum von $ b $. Im Fall von $ GCD (a, b) \ neq 1 $ wird, wenn $ LCM (a, b) = X $ transformiert wird, $ b = \ frac {X} {\ frac {a} {GCD (a, b)}} Es wird $ sein, aber $ \ frac {a} {GCD (a, b)} $ ist auch ein Bruchteil von $ X $, sodass Sie es nicht nachschlagen müssen ** (). Daher können Sie den mit dem kleinsten $ max (a, b) $ in jedem $ a $ finden.
✳︎… Ich habe den Beweis für $ GCD (a, b) \ neq 1 $ nicht gemacht, als ich ihn gelöst habe. Ich kann nicht anders, weil ich ungeduldig war, aber es ist nicht offensichtlich, also werde ich versuchen, es in meinem Kopf zu beweisen.
C.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
vector<ll> divisors;//Ein Array, das die Brüche speichert
void make_divisors(ll n){
FOR(i,1,sqrt(n)){
if(n%i==0){
divisors.PB(i);
if(i!=n/i){
divisors.PB(n/i);
}
}
}
}
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll x;cin>>x;
make_divisors(x);
//Machen Sie das erste Element größer
pair<ll,ll> ans=MP(INF,INF);
FORA(a,divisors){
if(gcd(a,x/a)!=1)continue;
pair<ll,ll> ans_sub;
if(a>x/a){
ans_sub=MP(a,x/a);
}else{
ans_sub=MP(x/a,a);
}
if(ans_sub.F<ans.F){
ans=ans_sub;
}
}
cout<<ans.F<<" "<<ans.S<<endl;
}
D Problem
Ich war enttäuscht, dass ich ein ähnliches Problem mit HUPC nicht lösen konnte, deshalb bin ich sehr glücklich, dieses Mal Rache üben zu können.
Erstens fiel es mir schwer, mich aus den obigen Punkten zu entscheiden ** und sie gierig kleiner zu machen **. Berücksichtigen Sie jedoch in der Diskussion ** den Maximalwert für jedes Bit ** und finden Sie Folgendes ($ , da die Berechnung von $$ oplus $ Bit für Bit unabhängig ist). Das heißt, wenn das $ i $ -Bit von $ X $ 0 ist, ist das $ (a \ _i \ oplus X) \ _ {max} $ des $ i $ -Bits das $ i $ -Bit von ** $ a $. Wenn die Zahl, die 1 wird, und das x oder von $ X $ genommen werden, wird es $ 2 ^ i $, und wenn das $ i $ -Bit von $ X $ 1 ist, wird die entgegengesetzte Beziehung erhalten.
Teilen Sie daher ** die Zahl, die das $ i $ -te Bit von $ X $ maximiert, vom oberen Bit ** durch 0 oder 1 und rekursiv $ i-1 sogar für die Menge der geteilten Zahlen. Schauen Sie sich einfach das $ -Bit an und teilen Sie es. Da wir endlich das Minimum $ (a \ _i \ oplus X) \ _ {max} $ finden möchten, ist der Rückgabewert der rekursiven Funktion $ min $ ($ i $ Satz von Zahlen, deren Bits 0 sind). Als Ergebnis der Berechnung der $ i-1 $ -Bits und danach das Ergebnis der Berechnung der $ i-1 $ -Bits und danach für eine Menge von Zahlen, deren $ i $ -Bits 0 sind) + $ 2 ^ i $ Das ist gut. Wenn außerdem die ** $ i $ -Bits des Satzes von Zahlen, die der rekursiven Funktion gegeben wurden, alle gleich sind **, werden die gleichen Bits wie diese Bits gegeben, um das Maximum $ (a \ _ i \ oplus X) der $ i $ -Bits zu ergeben. ) \ _ {Max} $ ist 0, und Sie können das Ergebnis der Berechnung von $ i-1 $ und nachfolgenden Bits ohne Division zurückgeben. Wenn $ i = 0 $ ist, wird die Wiederholung beendet.
Wenn Sie die obige rekursive Funktion implementieren, können Sie das Minimum $ (a \ _ i \ oplus X) \ _ {max} $ finden und ausgeben. Ich war auch besorgt über den Umfang der Berechnung der rekursiven Funktion, aber da jedes Element bei jeder Wiederholung geteilt wird, wird jedes Element nur einmal am ** $ i $ Bit **, $ O (\ log {a \ ) aufgerufen Es kann durch _ {max}} n) $ unterdrückt werden und arbeitet schnell genug.
D.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
ll rec(vector<ll> vec,ll ind){
ll ret=0;
vector<ll> vec0,vec1;
FORA(i,vec){
if((i>>ind)&1){
vec0.PB(i);
}else{
vec1.PB(i);
}
}
if(SIZE(vec0)==0){
if(ind==0)return 0;
return rec(vec1,ind-1);
}
if(SIZE(vec1)==0){
if(ind==0)return 0;
return rec(vec0,ind-1);
}
//Weder ist 0(Geben Sie den kleineren zurück)
//+2^ich
if(ind==0)return 1;
return min(rec(vec0,ind-1),rec(vec1,ind-1))+(1<<ind);
}
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
cout<<rec(a,31)<<endl;
}
Nach dem E-Problem
Ich werde diesmal überspringen.
Recommended Posts