Cette fois, j'ai pu résoudre jusqu'à E, mais ce n'était pas trop difficile, donc c'était comme hmm. De plus, le problème F était un problème de niveau bleu clair et j'ai remarqué comment le résoudre dans les 5 minutes restantes, mais je ne pouvais pas le résoudre, et je l'ai résolu 50 minutes après la fin du concours. Je suis désolé ...
Tout ce que vous avez à faire est de calculer en maths le nombre de fois dont vous avez besoin pour garder votre force physique en dessous de h
A.py
import math
h,a=map(int,input().split())
print(int(math.ceil(h/a)))
Jugez si vous pouvez tuer avec le coup spécial total
B.py
h,n=map(int,input().split())
a=[int(i) for i in input().split()]
print("Yes" if sum(a)>=h else "No")
Battez les monstres avec une force physique élevée avec un coup spécial.
C.py
n,k=map(int,input().split())
h=[int(i) for i in input().split()]
h.sort(reverse=True)
if k>=n:
print(0)
else:
print(sum(h[k:]))
Dans ce numéro, nous nous concentrons sur le fait que des monstres de même force naissent lorsqu'ils sont séparés. En d'autres termes, quand il y avait un monstre avec n force physique au début, n → n // 2, n // 2 → (n // 2) // 2, (n // 2) // 2, (n // 2) La force physique du monstre diminue à // 2, (n // 2) // 2, et lorsque la force physique devient 1, elle devient 0 lors de la prochaine attaque. En d'autres termes, si // est répété pour n jusqu'à ce que n devienne 0, et que le nombre de /// 2 jusqu'à ce point soit k, le nombre total d'attaques sur les monstres est de 2 $ ^ 0 + 2 ^ 1. Il devient + 2 ^ 2 +… + 2 ^ {k-1} $. Par conséquent, $ 2 ^ k-1 $ doit être calculé par le nombre total de fois.
answerD.py
h=int(input())
cnt=0
while True:
h=h//2
cnt+=1
if h==0:
break
print(2**cnt-1)
** Le problème d'un nombre illimité de sacs à dos ** (mais faites attention à la limite supérieure) (j'ai choisi le sac à dos DP car il n'y a pas de restrictions telles que la magie à choisir dans l'ordre). Le tableau dp stocke la puissance magique minimale requise pour réduire la force physique du monstre i dans le i-ème élément. Notez que ce tableau n'a pas de limite sur le nombre d'éléments, et seuls les éléments qui ne sont pas inf doivent être mis à jour dans l'ordre. De plus, à la fin, la force physique du monstre devrait être réduite à 0 ou moins avec la puissance magique minimale, il suffit donc de trouver la puissance magique minimale qui peut réduire la force physique du monstre de h ou plus. Aussi, je ne l'ai pas passé en Python, mais réécrit le même code en C ++ et AC. Quand je l'ai essayé après le concours, j'ai pu le réussir avec PyPy.
answerE.py
h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
a_sub,b_sub=map(int,input().split())
a.append(a_sub)
b.append(b_sub)
inf=10000000000000
ma=max(a)
dp=[inf]*(h+1+ma)
dp[0]=0
for i in range(n):
x=[a[i],b[i]]
for j in range(h+1+ma):
if dp[j]!=inf:
if j+x[0]<=h+ma:
dp[j+x[0]]=min(dp[j+x[0]],dp[j]+x[1])
else:
break
print(min(dp[h:]))
answerE.cc
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
signed main(){
ll h,n;cin >> h >> n;
vector<ll> a(n);
vector<ll> b(n);
for(ll i=0;i<n;i++){
cin >> a[i] >> b[i];
}
ll inf=10000000000;
ll ma=*max_element(a.begin(),a.end());
vector<ll> dp(h+1+ma,inf);dp[0]=0;
for(ll i=0;i<n;i++){
for(ll j=0;j<h+1+ma;j++){
if(dp[j]!=inf){
if(j+a[i]<=h+ma){
dp[j+a[i]]=min(dp[j+a[i]],dp[j]+b[i]);
}else{
break;
}
}
}
}
cout << *min_element(dp.begin()+h,dp.end()) << endl;
}
** Je veux utiliser des bombes pour vaincre les monstres aussi efficacement que possible **. Ici, arrangez les monstres dans un ordre coordonné. Premièrement, lorsque vous battez le monstre à l'extrême gauche, vous pouvez vaincre le monstre plus efficacement en ** alignant l'extrémité gauche de la section avec ce monstre **, et le nombre d'explosions requis à ce moment est ceil (h [0] / Il est clair que a) le sera. J'aimerais également enquêter sur les monstres impliqués dans cette explosion. Vous pouvez savoir à quel point cela s'effondre en ** vérifiant où se trouve l'extrémité droite de la section dans la dichotomie ** (car c'est à gauche de bisect_right, vous pouvez vérifier l'élément sur le côté le plus à droite de la section) Je vais. Jusqu'à présent, j'ai pu penser parfaitement pendant le concours. À ce rythme, vous pouvez voir qu'il est inefficace car il utilise une boucle for imbriquée pour réduire la force physique du monstre impliqué (le premier code ci-dessous). Ici, ** méthode Imosu peut être utilisée pour mettre à jour efficacement uniquement aux deux extrémités de la section **, donc Imosu Après avoir réfléchi à la loi, prenez la somme cumulée de la fin, et si la force physique du monstre est impliquée dans l'explosion et qu'elle est déjà égale ou inférieure à 0, sautez-la, et si elle est supérieure à 0, explosez autant de fois que nécessaire. Tout ce que vous avez à faire est de l'implémenter et cela ressemblera au deuxième code ci-dessous. (J'ai écrit la méthode Imosho plusieurs fois, donc c'était très difficile d'implémenter ** la simulation en même temps que la mise à jour **. En mots, j'ai fait beaucoup plus que ce à quoi je m'attendais. J'étais parfaitement conscient que je ne pouvais pas le faire, donc j'ai dû passer autant de temps pendant le concours ...)
answerF_TLE.py
import bisect
import math
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
cnt=0
for i in range(n):
#print(cnt)
if h[i]>0:
m=math.ceil(h[i]/a)
cnt+=m
k=bisect.bisect_right(x,x[i]+2*d,lo=i)
for j in range(i,k):
h[j]-=(m*a)
print(cnt)
answerF.py
import bisect
import math
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
g=[0]*n
cnt=0
for i in range(n):
if h[i]>0:
m=math.ceil(h[i]/a)
cnt+=m
k=bisect.bisect_right(x,x[i]+2*d,lo=i)
if i!=n-1:
h[i]-=m*a
g[i]-=m*a
if k<n:
g[k]+=m*a
g[i+1]+=g[i]
h[i+1]+=g[i+1]
else:
if i!=n-1:
g[i+1]+=g[i]
h[i+1]+=g[i+1]
print(cnt)
Recommended Posts