Zhy's Blog~
Codeforces Round #334
CF#334，终于正式参赛了一回(zhy)。难度一般，WA到爆炸，还好最后竟然还涨了几十分=_=，不至于太伤心→_→论刷低分号涨自信的重要性。
题意：类似于codeforces的算分机制，给出解题和hack情况，求最终得分。
解法： 公式都写的明明白白，不知道system test错掉的哥们是怎么搞的。
题意：N个物品，体积从小到大，一个背包中最多装两个物品，求用K个背包装所有物品，背包容量至少是多少。
解法：
贪心可解——设有n个物品是两两凑对的，那么这n个物品一定是体积最小的n个，且两两配对的方式是(1,n),(2,n-1)...剩下来的物品每个消耗一个背包。所以分配方案很明显n/2+N-n = K，求出n即可，接下来自行求最大值，复杂度O(N)。
二分答案可解——在[sn,sn+s(n-1)]这个区间内二分枚举最终的答案，然后O(N)地验证。至于验证细节，就是遵循能多装一个就再塞进去一个尽可能大的，还是有贪心的思想的，复杂度O(NlogN)。
贪心的优势在于这个题目里体积大小是排好序的，如果没有排序，那么和二分的复杂度并没有什么区别。
题意：01串，可选一段进行取反，求取反之后01间隔出现的子序列最长能有多长。
解法：看到很多dp的解法，不谈。考虑如下算法：
从左向右找到第一个00或11，靠右的位置为l；从右向左找到第一个00或11，靠左的位置为r；[l,r]取反，扫描一遍统计01子序列长度。复杂度O(N)
简单解释一下：
也就是这几种情况：
***000***
***111***
***00***11***
***11***00***
***00***00***
***11***11***
以最后一个为例： 左边的11表明——到第一个1的时候，最长的子序列肯定落脚到1（尾是1，但不一定是第一个1）； 所以此时将第二个1变为0是变废为宝的；同理右边的11也是如此，让第四个1之前一定落脚为0； 除了第二个和第三个1以外，取反的子串内部可取的01序列式不会受到任何影响的, 取反而已，无非是0101变成1010，但起点由第二个1取反后的0决定，终点由第三个1取反后的0决定。 当然，由于不影响内部，这个串当然是越长越好。所以l,r的取法如上所述。 能够这样操作的串结果会比原串增加2。
但这样是不全面的，博主本人也在此WA到死：
需要注意这种情况：
***00***
***11***
这里省略的串都是0101这样的，也就是说只有一组00或11，这个时候r = l-1
之前的算法没有处理这种情况，但考虑110,100,100101010这几个例子，都可以变为
101，101，101010101使结果增加1。
虽然取反的长度都不一样，但都是相当于r = N-1。所以原算法只需加上if（r<l） r = N-1;即可。
题意：求满足f(kx mod p) 同余 k*f(x) mod p的f映射的个数。其中f的定义域和值域都是0..p-1的整数，p是奇素数,k <p。
解法：博主数学渣，然而这个数论竟然还是一眼就有思路，所以应该还是比较简单的数论题吧。
首先，p是奇素数，k<p，于是决定了x和kx mod p的关系一定是一一对应的。从而其中一定有若干个环，比如：
p = 5,k = 4
x -> kx mod p
0 -> 0
1 -> 4
2 -> 3
3 -> 2
4 -> 1
共三个环{0},{1,4},{2,3}。
可以注意到环内的依赖关系，如f(1)=k*f(4)mod p，而f(4) = k*f(1)%p。很巧的是，k*f(x)%p和上面的情况如出一辙，也是有何kx%p一样的三个环，因此，f有以下几种情况。
f(0) = 0;
f(1) = 1,f(4) = (4) 或 f(1) = 4,f(4) = 1 或 f(1) = 2, f(4) = 3 或 f(1) = 3,f(4) = 2 或 f(1) = f(4) = 0;
f(2) = 1,f(3) = (4) 或 f(2) = 4,f(3) = 1 或 f(2) = 2, f(3) = 3 或 f(2) = 3,f(3) = 2 或 f(2) = f(3) = 0;
共1*5*5 = 25种组合。 于是，问题的解法就比较清晰了——dfs统计出kx%p的所有环，形成数组loocnt，其中loopcnt[i]表示长为i的环有多少个，然后基本的公式就是：
ans = ∏(i*loopcnt[i]+1)^loopcnt[i];
此处未计算f(0)，因为正常情况下f(0) = 0，只有一种情况，无需考虑。当然还有一些事必须要考虑清楚：
k = 0的时候，公式只能限制f(0) = 0，其他都没有限制，所以此时ans = p^(p-1)。
k = 1的时候，公式什么也限制不了，ans = p^p，不过之前的公式也是可以算的，只不过要考虑f(0)的取值可能性为p种，而不是1种了。
题意：两人互取石子，N堆。对于每堆，有两种操作可选。1.每次操作可以取一个；2.如果当前堆是偶数个石子n，可以将其折半后复制为K份，也就是K堆n/2个石子。不能操作者为输。
解法：比较传统的博弈论题目，利用SG函数解决。先推算前几个sg值观察规律。
假如K是偶数，那么可以注意到第2种方法得到的子问题一定是先手输，有因前几个sg值分别为feven = {0,1,2,0,1}，此时对于f[i]，如果i是奇数，影响它的只有f[i-1]，而如果i是偶数，影响它的是f[i-1]和一个必定会得到的0，所以依次推下去会发现sg值就是0,1,0,1...这样反复进行下去了。这是K为偶数时操作2的性质导致。
K为奇数是时，影响f[i]的因素就没有那么单纯了，如果i是奇数，当然还是只有第一种操作可选，即只受f[i-1]影响；如果i是偶数，那么f[i]由f[i-1]和f[i/2]来决定。又由于fodd={0,1,0,1,2,0,2,0,1,0...}，可见i>=4时，奇数的sg值都是0，偶数都>0，可以通过数学归纳法证明。当然，偶数的sg值不一定是1。因为奇数的sg值都是0，所以求解偶数的sg值时只要递归求解f(n/2)就行了。
n堆分开求sg值，然后通过异或操作求解最终的sg值。
Copyright © 2015-2016 zhyack. All Rights Reserved.
如对文章有任何疑问，请移步问题聚集区一览~