E.Final Countdown
我愿称之为今年最傻逼的一次,思路很快想出来了,但是实现一直搞不对
观察发现答案是n的所有前i位数相加(如12345,那么ans=12345+1234+123+12+1)
要证明的话就是按照题目的Note那样算,(以12345为例,ans=(12345-1234-123-12-1)+21234+2123+212+21)
然后傻逼的事情就来了,这个n的位数是比较大的,我就想用高精度,然后梭哈,然后T..
把12345+1234+123+12+1用竖式列出来就很容易发现怎么做了.从后往前按每一位算就好了.
最终在还有六分钟结束的时候想出来,应该按每一位算,结果nm写按位算的时候写了bug.应该是jw = (ans+jw)/10,当时写的jw = ans/10.我怎么这么傻逼.
F.Feed Cats
比赛时这题完全没思路,赛后看b站解法是dp
当前状态和之前的状态容易转移.
记dp[i]是在位置i处放猫粮能喂养猫的最大数量.那么dp[i] = max(dp[j]) + w[i].其中 j < i 且需要满足条件:
j需要小于 所有那些包含点i的区间的左端点 (这样才能保证我们选点i时不会与以前的冲突)
那么如何得到包含点i的区间的最左端点?
我们可以直接从左向右遍历,当进入到一个区间的左端点时把左端点加入,当离开区间右端点时把左端点删除.
由于n比较小(1e6),所以我们可以直接记录m个区间在1~n这些点上的起始点和结束点,in[i]表示点i处的左端点们(是一个vector),out[i]表示以点i处的为右端点的区间的左端点(也是一个vector)
然后从左到右遍历点,把点i处若有左端点则加入,到了右端点就把那个左端点移除.
标签：1234,CF1932,端点,ans,区间,Div,12345,dp,927 From： https://www.cnblogs.com/oijueshi/p/18020638