[POI2015]ODW
喵锟讲过。分块。
N>=blo,那就暴力倍增往上跳。O(N/blo*logN)
N<blo，预处理，f[i][j]表示，i往上跳，每次跳j步，到根节点为止，权值和。O(N*blo)（预处理复杂度）
平衡一下：N/blo*logN=N*blo
blo=sqrt(NlogN)
由于上去到lca再下去，
细节比较多。
[POI2009]KAM-Pebbles
阶梯型nim游戏的变形。
阶梯型nim游戏：高度单调的阶梯。每次只能把a[i]中选择x个，放到a[i-1]中，或者把a[1]中扔掉若干个。问有无先手必胜策略。
等价于对奇数堆做nim游戏。
第一次先手，就把奇数堆按照必胜策略移动。偶数堆不管，当做垃圾桶。
如果后手移动奇数堆到偶数堆，就按照奇数堆必胜策略移动。
反之，就把后手移动过来x的奇数堆再往前移动x个。对于奇数堆的状态不变。早晚会把偶数堆移动完。
所以，等价。
这个题的话，保证单调不减，设c[i]=a[i]-a[i-1],c[1]=a[1]，
那么，每次只能找一个c[i]>0的拿走x，相当于：c[i]->c[i]-x,c[i+1]->c[i+1]+x
所以，就是一个倒着做的阶梯型nim游戏了。
从后往前每隔一个异或一下。即可。
[POI2007]ODW-Weights
性质题。
关键点：任何两个砝码都有一个特征，他们的中总有一个的重量是另外一个的整数倍，当然他们也可能相等。
所以，从小到大排序，种类一共最多只有log1e9=30个。
由于只能用这些，所以就考虑用这些砝码重量将容器承重进制拆分。
然后再合并起来。代表这个位置的空间一共有多少个。
然后大力贪心。
肯定先放重量小的砝码，因为贡献都是1
肯定先占用自己的空间。因为更大的空间占据了，大的砝码就可能没地方了。并且小的空间不能为大砝码所用。小砝码不用就浪费了。
所以，交换空间一定不优。
如果自己的空间不够了，肯定要找大的空间借。因为贡献都是1，所以把这个种类的砝码放完一定不劣。
就把大的空间借一份拆出来成若干的小份空间继续供小砝码使用。
由于贪心正确。
所以，不够了就停止。
突破口：进制拆分。把所有的容器空间一起考虑，并不是单单先填一个容器。一切以放完最小的砝码为主，。。
[POI2006]PAL-Palindromes
我的想法比较简单：
按照长度sort，
然后对每个字符串跑一遍manacher
开始循环所有的字符串S。
之前的都比当前的S长度小，所以，回文中心一定在当前S中。
把扫过的字符串加入hash表。
循环当前字符串的每个位置i。如果p[i]==i，然后把i后面的hash取出来，看之前hash表中有多少个。
其实可以用trie树。
发现都是回文串，所以si+sj是回文串当且仅当si是sj的循环节。
si显然也是sj的前缀。放trie上就可以直接查找了。
对于O(1)判断si是sj的循环节：
hash(sj)*p^leni+hash(si)=hash(si)*p^lenj+hash(sj)
证明方法类似kmp的循环节证明。
[POI2008]BBB-BBB
给定一个由+1和−1构成的长度为n的序列，提供两种操作：
1.将某一位取反，花销为x
2.将最后一位移动到第一位，花销为y
要求最终p+sumn=q，且p+sumi≥0(1≤i≤n)，求最小花销
sumi为1-i的前缀和
发现，对于最优解，一定可以分成两步完成：先进行若干移位，再进行若干取反。
移位不好处理。就枚举移位多少。
先要满足p+sumi>=0
选择最小的minsum，不断+2，象征把-1变成+1，直到sumi>=-p，只要找到minsum，可以O(1)判断。次数设为now。
其实是不断把位置最靠前的-1变成+1
然后处理sumn=q-p
计算差距，然后直接变化即可。次数是：now+abs(q-p-sumn-now)/2
如果需要变的话，那么意义是：变-1：把最靠前的-1变成+1，变+1：最靠后的+1变成-1。
由于题目满足一定存在解，所以，其实对每个移位的次数，都存在解。
由于-1都是最靠前变成+1，+1都是最靠后变成-1，所以最后一定是合法的。
至于minsum，可以用单调队列优化，或者预处理前缀min
https://www.luogu.org/blog/user9168/solution-p3470
[POI2009]SLO-Elephants
比较显然的是，可以分成若干个环。
然后环上要进行转换。
len长的环每个点一定都要动。然后需要一个“搬运工”
显然，贪心可知，这个“搬运工”一定是环上代价最小的。让它走len-1次。
但是WA
因为，还可以找环外面借搬运工。
找最小的x，和环上最小的y交换。然后x带着环上剩下的开始转圈。再把x和y换回来。
由于x是所有的点中代价最小的，所以不存在把x换进来，换出去的时候顺便换换别的。
总之，只有以上两种方式。（第二种我漏了）