résultat

スクリーンショット 2020-09-05 11.12.16.png

Impressions

J'étais impatient et je ne pouvais pas non plus décider de la politique cette fois. Il existe de nombreux problèmes qui peuvent être résolus si vous restez calme, et je pense que vous avez besoin de la capacité d'organiser des politiques **.

Problème A

Faites juste attention aux personnages qui changent.

`A.py`


t="abcdefghijklmnopqrstuvwxyz"
s=input()
for i in range(26):
    if s[i]!=t[i]:
        print(t[i]+"to"+s[i])
        break

Problème B

Je pense qu'il est également facile d'élaborer une politique comme le problème A. En raison de contraintes, $ x $ (ou $ y $) ne peut prendre que 1 ~ $ z $ -1, alors faites une ** recherche complète **.

`B.py`


n,z=map(int,input().split())
for x in range(1,z):
    y=int((z**n-x**n)**(1/n))
    if x**n+y**n==z**n:
        print("Yes")
        break
else:
    print("No")

Problème C

Les problèmes A et B n'étaient pas graves, mais je n'ai pas pu terminer la politique.

Tout d'abord, considérons la ** simulation naïve **. À ce stade, lorsque $ a [i]> i $, au moins ce $ a [i] $ ne peut pas être déplacé **, donc ** tout $ i $ peut être utilisé comme $ a [i]. \ leqq i $ ** doit contenir (✳︎1). De plus, puisque cette condition doit toujours être vérifiée pendant la simulation, la simulation doit être effectuée dans l'ordre à partir du plus petit $ i $ dans lequel ** $ a [i] = i $ tient (✳︎2).

Ici, la simulation naïve est $ O (N ^ 2) $, mais dans la simulation naïve, +1 est ajouté à tout de 0 à $ i $ -1, donc l'élément avant l'élément ** $ i $ ème. Si vous enregistrez le nombre de fois que vous avez fait +1 **, vous pouvez calculer efficacement avec $ O (N) $. Aussi, pour cette raison, nous examinerons s'il est possible de déplacer les pierres dans l'ordre du plus grand $ i , mais ceci est ** différent de l'ordre de simulation ** ( \ parce que $ (✳︎2)). Cependant, le nombre total de pierres en mouvement est le même quel que soit l'ordre de la simulation, donc ** la simulation peut être effectuée à votre convenance tant que le nombre de pierres est correct.

Ici, si le nombre de pierres se déplaçant en regardant le $ i $ th carré est $ c $, alors la pierre se déplaçant de ce carré est $ a [i] + c $ **. Ce sera. À ce stade, si $ (a [i] + c) % i = 0 $, vous pouvez quitter cette cellule. De plus, quand il peut être déplacé, $ c = c + \ frac {a [i] + c} {i} $ tient. Pensez-y pour n'importe quel carré, et s'il tient, ce sera Oui, sinon ce sera Non.

(✳︎) 1… Si vous lisez attentivement l'énoncé du problème, cette condition est toujours vraie…. C'est une réflexion.

`C.py`


from itertools import dropwhile
n=int(input())
a=list(dropwhile(lambda x:x==0,list(map(int,input().split()))[::-1]))[::-1]
n=len(a)
if any(a[i]>i+1 for i in range(n)):
    print("No")
    exit()
c=0
for i in range(n-1,-1,-1):
    if (c+a[i])%(i+1)!=0:
        print("No")
        break
    c+=(c+a[i])//(i+1)
else:
    print("Yes")

Problème D

En premier lieu ** j'ai fait une erreur dans le calcul de la probabilité **….

Lors du calcul de la probabilité, $ F et S $ sont les suivants.

\begin{align}
F&=\frac{M \times _NC_K}{_{NM}P_K}\\
S&=\frac{(N-K+1) \times M^K}{_{NM}P_K}
\end{align}

De plus, $ F> S $ ressemble à ceci:

\begin{align}
&\frac{M \times _NC_K}{_{NM}P_K}>\frac{(N-K+1) \times M^K}{_{NM}P_K}\\
&\leftrightarrow M \times _NC_K>(N-K+1) \times M^K\\
&\leftrightarrow _NC_K>(N-K+1) \times M^{K-1}
\end{align}

Si le calcul est effectué tel quel, il coûtera environ $ O (K) $ pour chaque requête **, nous allons donc essayer d'accélérer par pré-calcul, mais comme il s'agit d'une multiplication telle quelle, ce sera un nombre énorme et un débordement et une grande quantité de calcul Ça prend du temps. Donc, ** utilisez logarithmique pour corriger la multiplication en une addition plus gérable **. Autrement dit, $ F> S $ ressemble à ceci:

\begin{align}
&N! \div (N-K)! \div K!>(N-K+1) \times M^{K-1}\\
&\leftrightarrow \sum_{i=1}^{N}{\log{i}}-\sum_{i=1}^{N-K}{\log{i}}-\sum_{i=1}^{K}{\log{i}}>\log{(N-K+1)}+(K-1)\log{M}
\end{align}

Ici, pour la partie $ \ log , la somme cumulée ( a [i]: = \ sum_ {j = 1} ^ {i} {\ log {j}} $) doit être obtenue à l'avance. Peut être calculé par $ O (N_ {max}) $ ($ N_ {max} $ est au plus 10 $ ^ 5 $).

D'après ce qui précède, chaque requête peut être calculée par $ O (1) $, donc le montant total du calcul est $ O (N_ {max} + Q) $.

`D.py`


from math import log2
from itertools import accumulate
x=[0]+[log2(i) for i in range(1,10**5+1)]
a=list(accumulate(x))

for _ in range(int(input())):
    n,m,k=map(int,input().split())
    ans=["Flush","Straight"]
    print(ans[a[n]-a[n-k]-a[k]>(a[n-k+1]-a[n-k])+(k-1)*(a[m]-a[m-1])])

E problème

Probablement la troisième fois que j'ai résolu le problème DP sur Kigami, mais j'ai pu le repérer immédiatement (je résolvais d'autres problèmes pendant le concours ...).

Tout d'abord, ** des informations sur le nombre de côtés connectés sont impliquées **, vous pouvez donc voir qu'il est susceptible d'utiliser ** DFS ou BFS **. De plus, puisque chaque score est fixé sur le dessus et ** ne peut pas être décidé avec gourmandise ** et ** chaque sommet n'a que deux états, qu'il existe ou non **, ** DP sur l'arbre. Vous pouvez le considérer comme **.

Et dans le cas de DP sur un arbre par DFS, ** lorsque vous êtes à un certain sommet, vous connaissez déjà les informations du sous-arbre dont le sommet est l'enfant de ce sommet **, et ** connectez le sommet que vous regardez et l'enfant Il semble qu'il puisse être implémenté en faisant attention au côté **, donc ici nous allons l'implémenter par DFS.

Le DP est réglé comme suit.

$ dp [i] [j]: = $ (score maximum dans les sous-arbres enracinés dans $ i $) (Cependant, lorsque $ j = 0 $, le sommet est effacé, et lorsque $ j = 1 $, le sommet n'est pas effacé.)

Considérons maintenant la transition DP, où le sommet que vous regardez est $ i $ et le sommet enfant est $ j $. De plus, DFS a déjà calculé $ dp [j] $.

(1) Transition vers $ dp [i] [0] $

Ajouter $ i $ augmentera seulement $ a [i] $.

dp[i][0]=a[i]+\sum_j{max(dp[j][0],dp[j][1])}

En faisant attention à chaque $ j $, si $ j $ existe, les deux $ i $ existent, donc $ b [i] + b [j] $ augmente.

dp[i][1]=\sum_j{max(dp[j][0],dp[j][1]+b[i]+b[j])}

dp[i]=[a[i],0]

Si la transition ci-dessus est mise en œuvre, ce sera comme suit. Si vous n'oubliez pas de ** augmenter la limite récursive ** et d'en faire une liste adjacente, vous pouvez l'implémenter telle quelle.

`E.py`


from sys import setrecursionlimit
setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
tree=[[] for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)
check=[False]*n
dp=[[0,0] for i in range(n)]

def dfs(i):
    global n,a,b,tree,check,dp
    #Lorsque vous n'effacez pas le sommet i
    dp[i]=[a[i],0]
    for j in tree[i]:
        if not check[j]:
            check[j]=True
            dfs(j)
            dp[i][0]+=max(dp[j][0],dp[j][1])
            dp[i][1]+=max(dp[j][0],dp[j][1]+b[i]+b[j])

check[0]=True
dfs(0)
print(max(dp[0]))

Problème F

Je ne résoudrai pas cette fois.

[PYTHON] concours yukicoder 264 avis