传送门

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(黑色格子数量,白色格子数量)\]
至于为啥,我也不清楚= =

12-16 02:07
查看更多