[PYTHON] Codeforces Runde # 666 (Div. 2) Bacha Review (9/2)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich bin wieder in ein schlechtes Muster geraten. Die Richtlinie war korrekt, aber ich gab vollständig auf, weil ich sie nicht lösen konnte. Grundsätzlich können die Levelprobleme, die in div2 auftreten, gelöst werden, wenn die Überlegung verfestigt ist, also möchte ich ** meine Konzentration behalten **. Wenn ich danach das Gefühl habe, vom Sumpf abhängig zu sein, werde ich versuchen, meine Gedanken zu klären und dann nachzudenken.

Problem A

Überlegen Sie, ob alles gleich sein kann. Zu diesem Zeitpunkt sollte ** die Häufigkeit, mit der jedes Alphabet erscheint, ein Vielfaches von $ n $ ** sein. Nachdem ich alle angezeigten Zeichenketten verbunden hatte, entschied ich mich, sie in eine Liste umzuwandeln und zu sortieren und dann die groupby-Funktion zu verwenden, um dieselben zu kombinieren. Ich habe es nach dem Ende bemerkt, aber ich denke, dass es einfacher zu implementieren ist, wenn Sie Counter anstelle der Groupby-Funktion verwenden.

A.py

from itertools import groupby
for _ in range(int(input())):
    n=int(input())
    s=""
    for i in range(n):
        s+=input()
    s=list(s)
    s.sort()
    for i,j in groupby(s):
        if len(list(j))%n!=0:
            print("NO")
            break
    else:
        print("YES")

B-Problem

Wenn Sie Probleme mit dem ersten Problem haben, ist es wahrscheinlicher, dass Sie versagen. Versuchen Sie daher, das erste Problem so sorgfältig wie möglich anzugehen.

(Es wird angenommen, dass $ a \ _i $ in aufsteigender Reihenfolge angeordnet sind.)

Erstens, wenn Sie $ c $ für $ c ^ i $ erhöhen, wird es exponentiell ansteigen, also denke ich, dass der Wert von ** $ c $ nicht so stark ansteigen wird **.

In Anbetracht dieses Punktes ist es wie folgt. Außerdem wird im Folgenden $ \ sum $ im Bereich von $ i $ = 0 ~ $ n $ -1 ausgeführt.

Zuerst,c=1Wenn alle Werte 1 sindwerdena\_i \geqq 1Damit\sum{|a\_i-c^i|}=\sum{(a\_i-1)}Es wird sein. Deshalb,\sum{c^i} < \sum{a\_i}+(\sum{(a\_i-1)})Sie können es unter suchen(\becauseWenn dies nicht erfüllt ist\sum{|a\_i-c^i|} \geqq \sum{(a\_i-1)}Es wird sein.).. Auch bei dieser Rate**cEs ist schwierig, die Obergrenze von zu finden**Daher wird die folgende Formeltransformation angewendet.

\begin{align}
&\sum{c^i} < \sum{a_i}+(\sum{(a_i-1)}) \\
&\rightarrow c^{n-1}< 2\sum{a_i}-n\\
&\rightarrow c< \sqrt[n-1]{2\sum{a_i}-n}\\
\end{align}

Daher konnten wir die Obergrenze von $ c $ festlegen. Experimente zeigen auch, dass dies unter den Bedingungen dieses Problems nicht viel zunimmt. Ich habe einen Fehler bei der Transformation der Formel gemacht und zu viel Zeit verschwendet.

B.py

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=10**18
for c in range(2,int((2*sum(a)-n)**(1/(n-1)))+1):
    x=1
    ans_sub=abs(a[0]-x)
    for i in range(n-1):
        x*=c
        ans_sub+=abs(a[i+1]-x)
    ans=min(ans,ans_sub)
print(min(ans,sum(a)-n))

C-Problem

Ich persönlich mag das, weil ich gut darüber nachdenken konnte.

Da es sich um ein Konstruktionsproblem handelt, denke ich darüber nach, die Operation auf nette Weise zu abstrahieren. Wenn ich beim Betrachten des Beispiels experimentierte und alle Zahlen in zwei Operationen zu einem Vielfachen von $ n $ gemacht werden konnten, konnten alle Zahlen auf 0 gesetzt werden, indem ** das Ganze in der letzten Operation ausgewählt wurde ** Mir ist aufgefallen. Wenn Sie ein Segment mit einer Länge von $ n-1 $ auswählen und eine Operation ausführen, sind ** $ n-1 $ und $ n $ gegenseitig Primzahlen, sodass Sie aus dem chinesischen Restsatz ein beliebiges Vielfaches von $ n $ machen können. Ich habe bemerkt, dass **. Ziehen Sie daher in Betracht, den Vorgang konkret zu simulieren.

Im Folgenden betrachten wir die Auswahl und den Betrieb eines Segments mit einer Länge von $ n $ → eines Segments mit einer Länge von 1 → eines Segments mit einer Länge von $ n-1 $.

(1) Wenn ein Segment mit einer Länge von $ n $ ausgewählt wird Die Operation sollte $ a [i] + n \ mal x $ zu einem Vielfachen von $ n-1 $ machen ($ n \ mal x $ ist die Zahl, die diesem Element hinzugefügt werden soll). Wenn die Formel transformiert wird, wird sie zu $ (a [i] + x) + (n-1) \ mal x $, also $ x = (n-1) -a [i] % (n-1) ) $ Um $ a [i] + n \ times x $ zu einem Vielfachen von $ n-1 $ zu machen. Tun Sie dies für jedes $ i $.

(2) Wenn ein Segment der Länge 1 ausgewählt ist Abhängig von der Operation ist jede Zahl ein Vielfaches von $ n-1 $. Da jedoch die Länge des letzten auswählbaren Segments $ n-1 $ beträgt, muss ein Element bereits auf 0 gesetzt sein. Hier wird das erste Element auf 0 gesetzt.

(3) Wenn ein Segment mit einer Länge von $ n-1 $ ausgewählt wird Ab (1) und (2) sind alle Segmente mit einer Länge von $ n-1 $ (mit Ausnahme des ersten Elements) $ n-1 $, sodass Sie Operationen ausführen können.

Wenn ** $ n = 1 $, 0 Division auftritt und wenn $ n = 2 $, verhält es sich unerwartet, wenn es sich um Ihre eigene Implementierung handelt **. In diesen Fällen unterscheidet es sich also als Eckfall. Ich werde es verarbeiten.

C.py

n=int(input())
a=list(map(int,input().split()))
#first
if n==1:
    print(f"1 1")
    print(f"{-a[0]}")
    print(f"1 1")
    print("0")
    print(f"1 1")
    print("0")
    exit()
if n==2:
    print(f"1 1")
    print(f"{-a[0]}")
    print(f"2 2")
    print(f"{-a[1]}")
    print(f"1 1")
    print("0")
    exit()
print(f"1 {n}")
x=[(n-1-a[i]%(n-1))*n for i in range(n)]
print(" ".join(map(str,x)))
print(f"1 1")
print(f"{-a[0]-x[0]}")
print(f"2 {n}")
print(" ".join(map(str,[-(a[i]+x[i]) for i in range(1,n)])))

D Problem

Das Spielproblem kann funktionieren (obwohl ich nicht sehr gut darin bin), wenn Sie es als ** betrachten, müssen Sie nur das Schlimmste bis zur letzten Phase vermeiden **.

Nehmen wir hier an, dass am Ende noch zwei Steintürme übrig sind und die Anzahl jedes Steins $ x, y $ beträgt. Zu diesem Zeitpunkt gewinnt die Person, die den ** mehr Turm auswählt . Da jede Person nur den Turm auswählen kann, der zuerst ausgewählt wurde, verliert die Person, der zuerst die Steine ausgehen. Da es sich hier um einen Vergleich zwischen zwei Türmen handelte, würde die Person, die die meisten Türme ausgewählt hat, gewinnen, aber selbst wenn es mehrere Türme gibt, ist die Anzahl der Steine im Turm mit den meisten Steinen die andere. Sie können gewinnen, wenn Sie mehr als die Gesamtzahl der Steine in einem Turm haben ( wenn die Anzahl der Steine in einem Turm einen Großteil der Gesamtzahl der Steine überschreitet **). Mit anderen Worten, ** wenn es von Anfang an in diesem Zustand ist ** ist der Sieg des vorhergehenden $ T $. Wenn $ n = 1 $ ist, ist es offensichtlich, dass $ T $ gewinnt.

In anderen Fällen ist es am besten, wenn Sie sich gegenseitig so verhalten, dass nicht mehr als die Hälfte der Steine vorhanden sind ($ \ leftrightarrow $ ** wählen Sie aus dem Turm mit den meisten Steinen **). Wenn Sie dies wiederholen, bleiben nur noch zwei Türme übrig und die Anzahl der verbleibenden Steine beträgt $ 1,1 $. Zu diesem Zeitpunkt kann jeder wählen, sodass die Person, die den letzten Stein genommen hat, gewinnt. Mit anderen Worten, ** betrachte die Seltsamkeit der Gesamtzahl der Steine **. Wenn es ungerade ist, ist es der erste $ T $ -Sieg, und wenn es gerade ist, ist es der zweite $ HL $ -Sieg.

D.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if n==1:
        print("T")
    elif max(a) > sum(a)//2:
        print("T")
    else:
        print(["T","HL"][(sum(a)-1)%2])

Nach dem E-Problem

Ich werde diesmal überspringen