A. Equation
签到。
B. Modulo Equality
因为\(n\)比较小,直接枚举循环排列然后check即可。
C. Long Beautiful Integer
题意:
给出一个长度为\(n,n\leq 2e5\)的十进制数\(x\)。
然后要找到一个最小的数\(y\),满足\(y\geq x\)且\(y_i=y_{i+k},i\leq n-k\)。
思路:
对于\(x\)来说,若第一次出现\(x_i\not ={x_{i+k}}\)的位置满足\(x_i>x_{i+k}\),那么直接显然\(x_{i+k}=x_i\)。
然后有这样一个性质:
- 若当前为第\(i\)个位置,并且\(x_i\)增大,那么\(i+1\)~\(n\)的位置上面的值都可以随便填。
这个较为显然。所以在上面说的情况,因为\(x_{i+k}\)增大了,那么后面直接等于前面相应位置即可。
如果第一次出现的为\(x_i<x_{i+k}\),我们就需要另外考虑。
显然我们只需要在\(1\)~\(k\)的位置找一个值进行增大,因为对应位置必须相等,若在后面增大的话,前面的也会跟着增大。并且因为要求\(y\)最小,所以我们从\(k\)往前来进行增大,若某个位置增加,那么后面的都可以等于前面的。
为什么说是从后往前呢?不是只选一个位置增大就行了么?
因为要考虑\(8999\cdots\)这种需要进位的情况。
细节见代码:
D. Domino for Young
题意:
给出\(n\)列高度为\(a_i\)的格子,类似于下面:
现在要用\(1\times 2\)的多米诺骨牌来填充。问最多可以放置多少个这样的多米诺骨牌。
思路:
我们直接将给出的图黑白染色,那么答案就是
\[min(黑色格子数量,白色格子数量)\]
至于为啥,我也不清楚= =