主要是利用了斐波那契数列对mod1e9+9时二次剩余的性质。说起来这个性质也是很奇葩，只见过两次应用这个题目的情况，一个是这个题一个是/cf.
二次剩余的定义是 当存在某个x使得x^2 \equiv d(mod p)成立时，称“d是模p的二次剩余”，当对任意不成立时，称“ d是模 p的二次非剩余”
而对于斐波那契数列有更具体的性质：
继续阅读“[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci”
[区间DP][双DP][×] UVA 1579&Gym 10128H Matryoshka
紫书DP课后题最后一题了，也算是把这一部分做完了吧。
这个题，在uva上的数据太水了，导致很多网上的题解代码是错误的。在gym10128H这里会wa。这些题解大多是用一个简单的贪心策略处理分段，然后用区间dp处理分出来的段落。但是实际上分段也需要用一个dp，比如数据 1 2 4 3 1 2，用简单的贪心分段就会把4 3分到前面那一段，这样的出来结果是5（当把1 2 放进4 3里的时候4和3都要打开），但是如果把4 3分到后面的1 2里答案是4，是更优的解。
先讲简单的部分：分好段之后的区间dp。这个就是普通的区间dp $$dp(l,r)=min(dp(l,i)+dp(i+1,r)+cost(l,i,i+1,r)),i\in[l,r)$$其中 \[dp(l,r)\]表示
[l,r]之间的套娃组装成1个所需要的最小花费, 继续阅读“[区间DP][双DP][×] UVA 1579&Gym 10128H Matryoshka”
[CF][二分check][贪心][×] codeforces 1132D Stressful Training
昨晚肝这一场是真的赔了，傻不拉几的C低级失误wa了一发，出完发现大家都会F然后跑去看了20min没头绪，折回去搞这个D，到最后也没过。。。感觉复杂度没错却一直tle，一直弄到两点受不了了睡觉去了，今早上课困得一批。
下午睡醒之后一直tle on test 27，给跪了好吧，疯狂卡常数真的有意思？最后把multiset改成priority_queue过了，真的服了，到目前为止52组数据吧，最狠的一组达到了2979ms，差21ms超时呵呵呵呵呵呵。。。
继续阅读“[CF][二分check][贪心][×] codeforces 1132D Stressful Training”
[线段树+][LCA][dfs序][二分查找][×] codeforces 1062E
http://codeforces.com/contest/1062/problem/E
这题两个难点，第一个是如何快速找到一堆不一定在一起的节点的公共LCA，第二个是如何确定这一堆节点中需要剔除哪一个。
可以先想一下，设原集合的lca为p1，可以取得最优答案的点为x，其他点为vi，那么x一定不在lca(所有的vi)这个点的子树上。这时候，任意一个vi和x的lca都是p1。这时假如维护一个S[l,r]表示[l,r]的公共LCA，根据上面说的性质，这个S序列一定存在一个断点，从这个点开始所有的S==p1,这样的话就可以利用二分查找找到这个断点，可以确定这个断点一定是候选答案之一。另外一个在二分的过程中其实是所有的lca都是基于最左边那个点积累过来的，所以除了分界点之外另外一个可能影响到答案的就是最左边这个点。到这里就算是找到了唯二可能影响答案的点，只需要对他们分别验证就可以了。从dalao的代码里学到了lca也可以作为线段树维护的变量。。。 继续阅读“[线段树+][LCA][dfs序][二分查找][×] codeforces 1062E”
[DP][二分][经典][×] UVA 1443 Garlands
没做出来看题解的时候就在想出题人是怎么搞出来的。。。这个做法emm
最大值最小化肯定要想二分，但是二分后这题目怎么check是个技术活。我最悲催的是理解错了题目意思，以为这些珠子（不管是什么吧我感觉是珠子）可以互换位置。实际上是不可以换的emm所以说看题还是要好好搞明白。
然后说说这个check，这个一开始有点迷，因为它本身是dp那一章的题，但是二分的check一般都是判断一个可行性，那加了这个二分出来的答案的约束怎么判断可行性？首先可以确定一般dp不会说去dp那种“区间上的最大值”之类的东西，他要做一定是一个量化的东西去求最优解。这里的话可以想象一下，如果用了比m更少的段就可以满足要求那么就可以继续进行下去？这样的话必须保证段数和最紧的上限是一个正比的关系！但是算一算可以发现并没有这种正比关系，一般这时候就放弃用二分的方法了，但是这个题最精彩的地方就在于他的奇偶性，由于题目本身一直在要求“半段”，所以可以利用奇偶性来保证正比单调，具体可以看这位dalao的博客
[排序][贪心][动态单调性数据结构][x] codeforces 1061D TV Shows
http://codeforces.com/contest/1061/problem/D
嗯。。。又是这种一维的区间最优化策略问题了。。。似乎已经感觉到了套路。。。（赛场上贪心有感觉就直接上了
这种题一般是先排序（以左端点或者右端点）搞出来一个顺序，然后在这个顺序的基础上逐个考虑。考察到某一段时候一般需要做决策，然后这时候可以根据具体题目来看是贪心决策还是dp，如果直觉是贪心（毕竟真正证明有时候确实不好弄），那一般决策都跟满足条件的极端值有关，比如在这里就是如果存在能合并的点（如果连最基本的两段合并后小于各买一台电视机都不满足那一定不能合并），那么一定是和这段左边最靠近他的一个点合并。具体证明可以分情况讨论，一般真的证明的时候就是得考虑，如果不这么合并，计算出来的结果和原来的结果对比，一般要考虑之后的seg的影响，在考虑的时候可以分情况讨论（反正我一般有直觉就上233
然后在实现的时候，有时候没有头绪可以想想STL！（想起了ccpc网络赛被set支配的恐惧），这个东西有时候真的有妙用，它既保持了单调的性质（可以用来贪心）又有着动态维护的特性（贪心的动态调整）。
wa点又是精度，嗯万年精度，这次竟然LL也炸了，而且是因为add的两个参数本身可以达到LL，然后一加给爆了。。。。我去
[CF][尺取][减少重复计算] codeforces 1043D Mysterious Crime
emmm第一感觉好像后缀数组之类的结构，但是这个每个元素是个整数，而字符串处理中每个元素都是一个长度为1的字符，，，所以很难把他等同于字符串来处理。但是直接理解的话，要求的话一定是找到一个排列，然后考虑他的每个子段，然后再在其他所有的排列中去找有没有这个子段，直接裸暴力的话n^3*10，肯定不行，但是想一下如果仅仅是考虑所有的子段就一定是不小于n^2的了，所以起码要在这里进行优化。然后由字符串的性质就可以知道一个长度为i的串如果满足要求的话，那么他的所有子串也都是满足要求的这些子串可以不用再计算了，发现了这个之后怎么去实施这个想法？考虑以每个下标i为开始的最长子串，这里如果用暴力的方法每次从i开始递增， 然后在与其他串判断，则当然仍然是n^3的，但是可以发现与其他串判断这个过程其实有很多重复的判断，假如已经知道了i到i+k个存在的话，判断第i+k+1个时候只需要把这一个数字去和其他的串中对应的数字比较是否全部相等就可以了，这样的话把复杂度降到了n^2*10，但是仍然不够，再考虑之前说的，枚举字段中的重复假设已经知道以i开始的到i+k个数字满足要求，那么在算以i+1开始的子段的时候，可以直接从第i+1+k+1个数字开始，也就是说中间的那些都不用再考虑了，因为这些信息已经在算第i个的时候计算过了。所需要保存的只有每个序列中数字i出现的位置而已。