Wasserstein Distance

显然,有跨越的移动是没有意义的。因为相邻的移动和跨越的移动代价相同。

所以,我们从前往后,贪心地比较当前位,通过后一位来调整,计算代价即可。

 


合约数

预处理\(10000\)内所有数的合约数,时间复杂度\(O(n\sqrt{n})\)。

然后就是要处理所有子树里面出现数的情况,用 map 启发式合并就好了。

由于前一部分预处理脑抽了,所以自闭了。

 


序列变换

我们直接枚举第一种状态以后数列\(a\)的形态。

第一种操作的次数是固定的,我们从前往后依次贪心地当前位置应该填的数 swap 过来就好了。

那么第二次和第三次操作的次数其实也是固定的,我们选择两个数中的较大数,如果大于两倍,是奇数的话\(-1\),否则直接整除\(2\),显然,这样的次数是最少的。

于是我们的时间复杂度为\(O(T*n!*n*log_{2}a_i)\)。


数字游戏

处理起来很麻烦啊。。

但听说数据是假的?

 


小Y吃苹果

显然,每天分出两种情况,答案就是 \(2^n\) 。


1 + 2 = 3?

要使得 \(x\; xor\; 2x= 3x\),只需要没有产生进位,也就是在二进制下\(x\)没有连续的两位都为\(1\)。

用数位 dp 预处理,然后 dfs ,来计算\(\le mid\)的时候,有多少个满足要求的数。

直接二分就好了。


二数

从高位往低位找第一个奇数,考虑修改。

要么改大,要么改小。

考虑改大改小产生的代价,继续往后观察,如果后面是连续的\(4\),则改大改小等价,我们选择改小,否则,偏向哪边,就选该哪个。

当然如果第一个奇数为为\(9\),显然,只能改小,因为改大了代价会增大。

 


K序列

有一个很明显的提示是\(n*k\le 10^7\) 。

考虑 dp ,用 \(f[x]\) 表示余数为 \(x\) 的方案数,暴力转移即可。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注