526互联

codeforces div 3 contest 894 solutions

发布时间 2023-09-01 04:48:42作者: yl_neo

IOI失利day1了，打div 3休息一下吧

https://codeforces.com/contest/1862/

 

A. Gift Carpet

贪心寻找第一个v, 其他的找最早的i,k,a就好了。 应该不需要多说（？)

 

B.Sequence Game

就是想想看当我们有4 3的时候应该怎么做? 就放一个3在他们中间就对了。

 所以就是每个a[i]<a[i-1]的时候就多push_back 一个a[i]

 

C. Flower City Fence

没什么的呀，就整个东西倒反过来的话我们可以想象[0,h[i]]的区域会+1

那么就做前缀和，然后比较是不是一样就可以了。

 

D. Ice Cream Ball

题目就是要寻找 max k满足: k(k-1)/2<=n,

答案就是n-k(k-1)/2+k

但是呢如果1个1个加的话, 复杂度为O(sqrt(n)),过不了

那么解个方程就好了。 复杂度 O(1)

 

E. Kolya and Movie Theatre

非常明显的就是类似于求max k 和的题目。

就是如果说现在要拿i的时候, ans= max( a[x]+ a[y]+...+a[k]-k*d )

所以直接上multiset 维护max m-1个值,注意负值不需要加入multiset

 

F. Magic Will Save The World

一眼就看出你可以等到f,w够了再出发。

那么我们就可以看到唯一需要找到的就是我们需要多少个f的巫术。那么我们可以看到dp

dp[i][j]=当我们已经考虑了 i 列,和为 j 的时候,此状态是否可以到达

dp[i][j] |= dp[i-1][j-a[i]]

dp[i][j] |= dp[i-1][j]

基础状态为: dp[0][0]=true

那么就可以找到答案啦，看到n可以到的每个状态s,

另S=sum(a[]), g=ceil(s/f) ，r=ceil((S-s)/w)

ans=min(ans,max(r,g))

可能会mle? 所以使用bitset可以加速， 或是翻滚dp也行 （我用了bitset加速，在极端的样例下93 ms）

 

G. The Great Equalizer

可以看到的是每次走完相邻的差就减一了， 那么答案就是max s[i] + max abs diff

利用multiset解决就可以了(好麻烦的）

 

给个评价吧（？）：

a,b,c 就还行（

 

d说实话感觉挺傻的（？），不是说那个问题不好还是作者写的不好什么的,感觉看到 ans= n-k*(k-1)/2+k 就已经

满不错了的？ 如果是我写题目的话应该会给O(sqrt(n))过？

 

e,f 好简单(?） 可能看过类似的吧？ (a,b,c,d 各个第一次的submission都没过, ef一次就过了？）

g有点恶心，要把答案看出来不简单。代码难度蛮高的。

 

IOI 2023 day 1失利了， 看 d2吧！