Memphis's Blog

刷水严重。。不能这样了。。

屯题是不是会比较有压迫感。。

counter:

50

3787: Gty的文艺妹子序列：gty教你分块系列。。。没什么好说的吧。。分个块各种数据维护一下。

1416: [NOI2006]神奇的口袋：网上证明很多，两个性质

1.只要满足[tex]x_i>x_{i-1}[/tex]，[tex]x_i[/tex]的取值不影响答案。

2.[tex]y_i[/tex]序列的顺序任意交换也不影响答案。

性质2这里用不上，性质1就可以了，另外还有高精度。

3761: Zhenhuan：乍一眼水题，仔细想想不对劲。。想通了也挺水的。。

分奇偶讨论，设答案为[tex]ans[/tex]。

若[tex]n[/tex]为偶数，则对于[tex]a_i[/tex]，若[tex]i[/tex]为奇数，则使用[tex]1\sim a_i[/tex]，若[tex]i[/tex]为偶数，则使用[tex]ans-a_i+1 \sim ans[/tex]，这样使用显然最优，所以答案是相邻和的最大值。

若[tex]n[/tex]为奇数，最后一位和第一位按照上述方法会产生冲突，先按照上述方法取得[tex]ans[/tex]最小值。

第一位使用[tex]1\sim a_1[/tex]，第二位使用[tex]a_1+1\sim a_1+a_2[/tex]，对于第[tex]i[/tex]位，若[tex]i[/tex]为奇数，尽量往大的使用必然最优，偶数相反，若与前一位产生冲突，则跨越该冲突部分特殊计算，若不产生冲突，易证后面都不会冲突，所以保留跨越冲突部分的位置就可以了，外面套一个二分即可。

3759: Hungergame：无脑博弈问题，判断是否有子集xor为0。。

3751: [NOIP2014]解方程：没什么好说的。。考场上想不出来就是弱。。

3749: [POI2015]Łasuchy：枚举1号食物的状态，状态分为四种，在食物左边的人吃或不吃，在食物右边的人吃或不吃，用二进制表示就是00、01、10、11，然后判断一圈回来看是否可行。

3720: Gty的妹子树：玩烂的东西。。带插入区间K极值的做法可以搬过来。。由于是棵树，那就可以块状树。。感觉好烦。。搜了下题解发现不裂块能过。。那就不裂块把。。这样就方便很多。。

3680: 吊打XXX：温习了一下爬山。。。说实话爬山用来乱搞效果都蛮不错的。。

3722: PA2014 Final Budowa：枚举第一个游说的节点，然后check一下是否可行就好了。。证明如下，若当前状态获胜，则敌方要扳平必然需要在一个我方获胜节点花费一个代价，由题目条件可知一个点的下属是奇数个，所以若状态为平局，则必然还至少有一个空节点，我方只需要在该空节点花费代价即可，状态平局和为负同理可证。

3670: [Noi2014]动物园：填坑。先做一遍kmp，然后做一遍类似kmp的匹配，如果长度大于[tex]\lfloor \frac{i}{2}\rfloor[/tex]就往回跳，可以证明正确性。。自己找几个例子试试就好了。

3669: [Noi2014]魔法森林：填坑。LCT速度变慢了。。30min+才码出。。

3671: [Noi2014]随机数生成器：填坑。

3678: wangxz与OJ：T T。。

2109&2535：[Noi2010]Plane 航空管制：其实还算是蛮简单的拓扑排序，对于第一问，把边反向拓扑排序，对于第二问，枚举节点，删除该节点，做第一问直到队列为空即为答案。

3045: 电话线路：最短路。。我怎么又在刷水了。。

3620: 似乎在梦中见过的样子：kmp n次就好了。。为何[tex]O(n^2)[/tex]的复杂度开15000。。一开始题目看错了也是醉。

3629: [JLOI2014]聪明的燕姿：爆搜。。把约数和表示出来，把S一个一个拆约数暴力dfs就可以了。

3796: Mushroom追妹纸：很显然可以二分，那就二分+hash。。一开始拼命wa。。不知为何。。后来发现hash被卡了。。我可是双关键字hash啊。。。orz蘑队。。快去解决hash killer3

3798: 特殊的质数：分段打表，[tex]n~mod~4=1~or~n=2~(n~is~prime)[/tex]即为答案。证明不会。此题为分段打表练手题。。

3799: 字符串重组：没什么好说的。。

3789: 扫雪车：上下限最大流get

3790: 神奇项链：manacher+后缀min dp。

3606: [Sdoi2013]Insider：线段树套平衡树+射线法什么的。。出题人卡的一手好splay，query的时候都要splay才能过。。还记得当场同步赛做的时候码出了只过了两个点，当时我还想我一定是写挂了什么地方。。现在想想没准是被卡splay。。醉了。。

3682: Phorni：后缀平衡树

3791: 作业：果然是傻啊T T。。。K次操作后最多分成2*K-1段，然后就直接DP

3600: 没有人的算术：替罪羊树好像很爽的样子？曾经亲测替罪羊树艹treap速度n倍，写写也好方便。。我要成为替罪羊树选手。。

3792: 跑步：边当点做矩阵乘法。。我会告诉你我这么长时间没写矩乘导致写错了么T T。。

3797: Ural 1745 Yet Another Answer：把一个括号序列缩成 )))((( 的形式，设左部分的右括号为l，右部分的左括号r，删去的括号长度为v，先按照r>=l在前，r<l在后为第一关键字，这样可以保证左括号先递增，然后第一部分按照l递增排序，可以YY正确性，如果小的l都无法与之前匹配，那么大的l就更不必谈了，第二部分同理，按照r递减排序，然后做dp即可。

[tex]f_{i,j}=max\{f_{i-1,j},f_{i-1,j-a_i.l+a_i.r}+a_i.v+a_i.l*2\}(j-a_i.l>=0)[/tex]

3601: 一个人的数论：将狼踩尽的blog写的非常详细，证明那个式子是个d+1次多项式在杜教的在某篇论文里有证明。

3439: Kpm的MC密码：网上全是主席树维护dfs序？为什么我感觉每个点上挂个链表就没了？

3516: 国王奇遇记加强版：题解一大拨。。

3806: Neerc2011 Dictionary Size：字母树前缀后缀搞一下。

3681: Arietta：可持久化线段树优化网络流

3809: Gty的二逼妹子序列：莫队+块状数组。。除了这个小技巧外什么都没有了。。

2466: [中山市选2009]树：异或方程组。。没什么好说的。。在补知识点QAQ。。

1923: [Sdoi2010]外星千足虫：异或方程组。。bitset压位。。

2115: [Wc2011] Xor：异或方程组。。问题可以转化为任意一条简单路径和所有简单环的最大xor子集。

3813: 奇数国：压位一下就好了。。

2822: [AHOI2012]树屋阶梯：卡特兰数。

2322: [BeiJing2011]梦想封印：类似2115的做法，先考虑静态做法，现在可以到所有点，那么跑一棵xor生成树，生成树上所有点的dx代表1号点到x点xor和，每一条非树边代表了一个简单环，把简单环压入异或方程组消元，不等价的简单环最多只有w个，w为number的位数，设有s个，考虑1号点到每个点的方案，那就是所有不等价简单环的子集即[tex]2^s[/tex]个，到这里我们可能会单纯的把[tex]2^s*n-1[/tex]记为答案，但是有些节点是等价的，表现在异或方程组中就是消元后是否相等，最坏情况下不等价的节点数是[tex]2^{w-s}[/tex]级别的，但是条件是树边全是构造的大值，非树边所代表的简单环是构造的小值，然而我们的生成树是随机跑的，所以远远到不了这个级别。设不等价的节点数为t，答案就是[tex]2^s*t-1[/tex]。现在扩展到动态加边做法，生成树显然是可以扩展的，然后每次加点都判一次有多少不等价的节点，然后就没了。。判等价我用了map。。用hash会快很多。。

upd.2015.1.13：后来发现链就可以卡掉这种做法，可以改进一下，只有当加入了一条有效的非树边对所有点的简单路径判不等价节点，有效非树边只有[tex]w[/tex]条，这样复杂度就有保证了。

2460: [BeiJing2011]元素：排个序做异或方程组。。没什么好说的。。

2844: albus就是要第一个出场：网上有题解。。那就不多说了。。

3812: 主旋律：十分鬼畜的容斥+压位+枚举子集DP，代码很短。。写起来欲仙欲死。。

3823: 定情信物：比较有趣的题目，很容易找到一个[tex]O(n^2)[/tex]的递推式，[tex]f_{i,j}[/tex]表示i维下的j维元素有几个，递推式就是[tex]f_{i,j}=f_{i-1,j}*2+f_{i-1,j-1}[/tex]，表现在现实意义上就是第j维的某个元素经过拖动一分为二，第j-1维拖动轨迹成为第j维，其实画出来就是一个竖直转移带乘二的权的杨辉三角。[tex]O(n)[/tex]递推式就比较有趣了，通过上面这个递推式推出得到前几项的通项公式，观察通项公式即可得出递推式。[tex]f_i=\frac{f_{i-1}*(n-i+1)}{2i}[/tex]，线性逆元就不说了，但是有问题，逆元可以不存在= =。。。那我只要再保存一个数字里有多少p就可以了，有p就是0。

2426: [HAOI2010]工厂选址：贪心。

3106: [cqoi2013]棋盘游戏：记忆化搜索。

3609: [Heoi2014]人人尽说江南好：公式题。。

2282: [Sdoi2011]消防：直径上跑一下就好了。

3505: [Cqoi2014]数三角形：题解一大波。。我就不说了。

第一次屯题完结。。感觉棒(he)棒(he)的(da)