[PYTHON] Codeforces Round # 671 (Div. 2) Bacha Review (9/22)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Es war eine verschwenderische Zeit, weil ich ungeduldig war und meine Gedanken chaotisch wurden. Ich hatte das E-Problem im Ideenspiel, konnte mir aber nicht genug Zeit sichern.

Immerhin ** ist die Genauigkeit und Intuition der Betrachtung immer noch schlecht **, daher denke ich, dass es keine andere Wahl gibt, als mehr Probleme zu lösen und sie zu verfeinern.

Problem A

(Im Folgenden ist der erste Raze R und der zweite Breach B.)

** Achten Sie auf die letzte verbleibende Nummer **. Wenn die Anzahl der verbleibenden ungerade ist, gewinnt R, und wenn nicht, gewinnt B. Wenn zu diesem Zeitpunkt eine ungerade Zahl vorhanden ist, bleibt die ungerade Zahl am Ende, sodass es ausreicht, eine ungerade Zahl zu hinterlassen, damit das erste R gewinnt. Wenn die ungerade Zahl mindestens eine ungerade Zahl enthält, gewinnt R. Ich werde. Wenn es eine gerade Zahl gibt, bleibt die gerade Zahl am Ende, so dass es ausreicht, eine gerade Zahl zu belassen, damit B im zweiten Angriff gewinnt, und wenn es mindestens eine gerade Zahl in der geraden Zahl gibt, gewinnt B. Ich werde.

** Ich habe einen Fehler bei der Anzahl der Ausgänge gemacht und 1WA ausgegeben **.

A.py

for _ in range(int(input())):
    n=int(input())
    a=2**n+sum(2**i for i in range(1,n//2))
    b=sum(2**i for i in range(n//2,n))
    print(a-b)

B-Problem

Es war nicht trivial, also habe ich es aus anderen Problemen gelöst. Bei solchen Grafikproblemen ist es wichtig, das Experiment genau durchzuführen.

Eine $ n $ Stufentreppe, die nur aus $ n $ Quadraten besteht, wird als schön bezeichnet (zuerst wurde sie als Rechteck ** falsch verstanden **). Wir werden ein Experiment durchführen, das den Fall betrachtet, in dem diese schöne Treppe hergestellt werden kann.

Wenn Sie zu diesem Zeitpunkt kein ** möglichst großes Quadrat ** wie in der folgenden Abbildung gezeigt machen, können Sie es nicht mit nur $ n $ Stücken machen ($ \ weil $ Wenn Sie ein kleineres Quadrat verwenden, wird es definitiv $ n $ Stücke überschreiten. Weil es enden wird). Das heißt, es sieht aus wie in der Abbildung unten.

Die obige Abbildung zeigt die Zeit, zu der $ n $ = 1 ~ 7 ist, sie gilt jedoch nur, wenn $ n $ = 1,3,7. Es ist auch klar, dass es gilt, wenn es eine ungerade Zahl ist, und wenn Sie ein großes Rechteck erstellen, wenn $ n = 2k + 1 $, ** ist der Rest ein Rechteck mit zwei Größen $ k $ **. Mir ist aufgefallen. Mit anderen Worten, wenn die Größe der Treppe, die erstellt werden kann, $ a \ _i $ ist, muss sie $ a \ _ {i + 1} = 2a \ _i + 1 $ ($ a \ _0 = 1 $) sein.

Außerdem beträgt die Anzahl der angegebenen Kacheln höchstens $ 10 ^ {18} $, und $ a \ _i $ wächst schneller als die isobare Sequenz, sodass ** eine schöne Treppengröße $ a \ _0 $ ist Es reicht aus, bis $ a \ _ {29} $ ** zu finden.

Daher möchten Sie die Anzahl der ** verschiedenen schönen Treppen ** finden, die für eine bestimmte Anzahl von Fliesen $ x $ hergestellt werden können, und verschiedene Treppengrößen haben unterschiedliche Treppen, also machen Sie aus einer kleinen schönen Treppe. Sie können sie in der richtigen Reihenfolge erstellen, bis sie aufgebraucht sind. Beachten Sie auch, dass Sie $ \ frac {a \ _i (a \ _ i + 1)} {2} $ von $ x $ abziehen sollten, da Sie die Anzahl der Kacheln erhalten.

B.py

cand=[1]
for i in range(100):
    cand.append(cand[-1]*2+1)
    if cand[-1]>10**18:
        break
for i in range(int(input())):
    ans=0
    x=int(input())
    for i in cand:
        j=i*(i+1)//2
        if x-j<0:
            break
        else:
            x-=j
            ans+=1
    print(ans)

C-Problem

Während des Wettbewerbs habe ich mich beeilt, über eine seltsame Lösung nachzudenken, aber wenn ich ruhig bin, ist es nicht so schwierig.

Während des Wettbewerbs habe ich zuerst die folgenden Fälle betrachtet.

(1) Wenn alle $ x $ bewerten Sie können infizieren, ohne einmal einen Wettbewerb abzuhalten.

(2) Wenn die Gesamtbewertung aller Personen $ nx $ beträgt Sie müssen den Wettbewerb nur einmal öffnen, da Sie alle gleich $ x $ machen können, indem Sie den Gesamtbetrag der Änderungen auf 0 setzen.

(3) Andere als (1) und (2) ** Sie können alle bis auf eine Person machen ** $ x $, und Sie können jeden mit zwei Operationen infizieren.

Eigentlich sind (1) und (2) korrekt, aber ** (3) ist nicht immer korrekt **. Während des Wettbewerbs nahm ich AC in Betracht und dachte, wenn ich die bereits infizierte Person gut eingestellt hätte, würde es ausreichen, dies einmal zu tun, aber logischerweise ** Wenn mindestens eine Person bereits infiziert ist, diese Person Es kann gesagt werden, dass jeder auf einmal infiziert werden kann ** durch $ x $ außer. Wenn ich auf den Teil von ** außer einer Person achten könnte, könnte ich ihn wahrscheinlich richtig lösen, sodass ich der Meinung war, dass Genauigkeit für die Fallklassifizierung wichtig ist.

C.py

for _ in range(int(input())):
    n,x=map(int,input().split())
    a=list(map(int,input().split()))
    if a.count(x)==n:
        print(0)
    elif sum(a)==n*x:
        print(1)
    else:
        if a.count(x)>0:
            print(1)
        else:
            print(2)

D1-Problem

Da sie alle unterschiedlich sind, ist es möglich, 0-indiziert von der größten geraden Zahl in absteigender Reihenfolge und von der kleinsten ungeraden Zahl in aufsteigender Reihenfolge zu verwenden. Ich denke, das ist ein sehr einfaches Problem.

D.py

n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import deque
b=deque(a)
l=n//2-1 if n%2==0 else n//2
ans=[]
while len(b)>=2:
    ans.append(b.pop())
    ans.append(b.popleft())
if len(b)==1:
    ans.append(b.pop())
print(l)
print(" ".join(map(str,ans)))

D2-Problem

Es scheint, dass die Code-Implementierung der Richtlinie, die schließlich AC war, falsch war. ** Ich konnte nicht feststellen, ob die Richtlinie oder die Implementierung falsch war **. In Zukunft möchte ich meine Denkfähigkeit verbessern, damit ich sie nach gründlicher Festlegung der Richtlinie umsetzen kann.

Die maximale Anzahl von Eisbällen, die Sie kaufen können, wenn Sie in der folgenden Reihenfolge angeordnet sind, ist (ABC178-F ist ein ähnliches Thema).

Wenn die maximale Anzahl von Eisbällen mit demselben Preis $ [\ frac {n} {2}] $ beträgt, kann der maximale Wert bei D1 erreicht werden, und wenn er höher ist, entspricht die maximale Anzahl dem, was Sie arrangieren. Ich dachte, ich könnte es nicht erreichen, also habe ich es so arrangiert. ** Ich dachte, es gäbe keine andere rationale Vereinbarung **, also entschied ich mich für diese Anordnung.

Wenn Sie sich die Antwort ansehen, wenn Sie $ m $ Eisbälle kaufen können, gibt es kleinere Kombinationen von $ m + 1 $ Eisbällen, also ** die Methode, nach $ m $ durch Dichotomie zu suchen ** Ich habe es genommen. Wenn es eine Annahme gibt **, wann Sie ** $ m $ Eisbälle ** kaufen können **, sollte es keinen Grund geben, an eine Zweiteilung aus der Kombination von ** Monotonie und Maximalwert ** zu denken, also müssen Sie das Typische lernen. fühlte.

D.py

n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import deque
b=deque(a[:n//2])
c=deque(a[n//2:])
ans=[]
while len(b) or len(c):
    ans.append(c.popleft())
    if len(b)>0:
        ans.append(b.popleft())
#print(ans)
l=0
for i in range(1,n-1):
    if ans[i-1]>ans[i] and ans[i]<ans[i+1]:
        l+=1
print(l)
print(" ".join(map(str,ans)))

E Problem

Aufgrund eines Montagefehlers wurde es 10 Minuten nach Ende des Wettbewerbs behoben. Ich bin sehr enttäuscht. Wenn ein solches Problem stabil wird, denke ich, dass ich die Mauer sofort überwinden kann, also werde ich es ertragen und mich anstrengen.

Als ich beim Betrachten der Probe experimentierte, dachte ich, dass ** in vielen Fällen nicht einmal lcm eingenommen werden muss **. Daher werden wir die benachbarten Zahlen so anordnen, dass sie nicht zu Elementen voneinander werden. Da wir jedoch verhindern möchten, dass der gcd der benachbarten Zahlen 0 wird, ** achten Sie darauf, bei welcher Zahl die benachbarten Zahlen Vielfache sind **. tat. Insbesondere habe ich darauf geachtet, ** welche Primzahl jede Zahl ein Vielfaches von ** ist. Mit anderen Worten, Sie können es beispielsweise wie in der folgenden Abbildung gezeigt erstellen (ich denke, es gibt verschiedene Möglichkeiten, es zu erstellen, aber Sie können es sich leicht vorstellen, indem Sie darauf achten, ** welche Primzahl ein Vielfaches ist **).

Sie können zwischen beliebigen Elementen eine andere gcd als 1 erstellen, indem Sie ** davon ausgehen, dass der durch den gelben Kreis wie oben angegebene Grenzteil mit einer jeder Primzahl ** multipliziert wird. ..

Daher zählt $ O (\ sqrt {n}) $ die Brüche auf und speichert sie in "Teilern", und $ O (\ sqrt {n}) $ führt eine Primfaktorisierung durch und speichert sie in "prime". Die Elemente, die Vielfache jeder Primzahl sind, werden aus den "Teilern" in der Reihenfolge von der Vorderseite des "Prim" -Elements extrahiert und in dem Array "ans" gespeichert, das als Antwort ausgegeben wird. Da ich in aufsteigender Reihenfolge speichern möchte und die Geschwindigkeit des Herausnehmens stabil ist, setze ich "Divisors" bzw. "Prime" auf "Set".

Außerdem können Sie in "ans" ein Vielfaches jeder in "Teilern" verbleibenden Primzahl entsprechend speichern. Beachten Sie jedoch, dass ** der Begrenzungsteil separat ausgeführt werden muss **. Dies kann leicht erreicht werden, indem später das Produkt der betrachteten Primzahl und der nächsten Primzahl in "ans" gespeichert wird (Einzelheiten siehe Implementierung).

Darüber hinaus ist es wie in der ersten Stichprobe erforderlich, lcm ** zu nehmen, wenn es nur zwei verschiedene Primfaktoren gibt und $ n $ durch das Produkt der Primfaktoren ** dargestellt wird. In anderen Fällen können Sie die Bedingungen immer mit Ihrer eigenen Bauweise erfüllen.

E.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

//n ist nicht enthalten
set<ll> divisors;//Stellen Sie ein, um ungefähr zu speichern(Ich möchte es löschen)

void make_divisors(ll n){
    FOR(i,2,sqrt(n)){
        if(n%i==0){
            divisors.insert(i);
            if(i!=n/i){
                divisors.insert(n/i);
            }
        }
    }
}

set<ll> prime;//Karte, um zu speichern, wie viele jede Primzahl durch Primfaktorisierung herausgekommen sind

//O(√n)
//Ausgerichtet(Karte wird automatisch nach Schlüssel angeordnet)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
    FOR(i,2,l){
        if(n%i==0){
        prime_factorize(i);prime_factorize(ll(n/i));return;
        }
    }
    //Auch wenn der Schlüssel nicht in der Karte vorhanden ist, wird er automatisch erstellt.
    prime.insert(n);return;
}

signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll t;cin>>t;
    REP(_,t){
        ll n;cin>>n;
        vector<ll> ans;
        divisors.clear();
        prime.clear();
        make_divisors(n);
        prime_factorize(n);
        if(SIZE(prime)==2 and (*prime.begin())*(*++prime.begin())==n){
            cout<<*prime.begin()<<" "<<*++prime.begin()<<" "<<n<<endl;
            cout<<1<<endl;
            continue;
        }
        for(auto i=prime.begin();i!=prime.end();i++){
            deque<ll> sub;
            ll l,r;l=*i;r=0;
            if(++i!=prime.end()){
                r=*i;
                sub.PB(l*r);
                divisors.erase(l*r);
            }
            --i;
            auto j=divisors.begin();
            while(j!=divisors.end()){
                if((*j)%(*i)==0){
                    sub.PB(*j);
                    j=divisors.erase(j);
                }else{
                    j++;
                }
            }
            while(SIZE(sub)){
                ll p=sub.back();
                sub.pop_back();
                ans.PB(p);
            }
        }
        ans.PB(n);
        if(SIZE(prime)==2 and (*prime.begin())*(*++prime.begin())==n){
            REP(i,SIZE(ans)){
                if(i!=SIZE(ans)-1)cout<<ans[i]<<" ";
                else cout<<ans[i]<<endl;
            }
            cout<<1<<endl;
        }else{
            REP(i,SIZE(ans)){
                if(i!=SIZE(ans)-1)cout<<ans[i]<<" ";
                else cout<<ans[i]<<endl;
            }
            cout<<0<<endl;
        }
    }
}

F Problem

Ich werde diesmal überspringen