先挖个坑。

以下是吐槽时间

原以为自己实力还行，结果省队集训3次考挂让我明白了什么- -

说白了还是自己太弱了2333 既然弱那NOI当然是滚粗咯

[UPDATE 7/12 16:00] 12号校内训练又被immortalCO和lightning虐成垫底了，一道CF的图象识别题居然不知道有给样例，完全不会搞，最后高二神犇immortalCO、lightning，高一神犇dick32165401都A了这题，我高一蒟蒻WAer（我真的除了WA不会别的了）WA了59个点。。。被暴踩。。。【手动垫底去了】（对着样例随便调下参就A了，日了狗了）整场研究第2题，然而第1题是个std才200b的水题。。。居然没时间想了。。。我好弱啊。。。

要是在NOI可能连Ag都没有了

[UPDATE 7/12 16:50] 刚去推了下第一题……卧槽真的比第二题简单不知道多少倍，半个小时就推出来了，而且确实好写不用拍交到CF上直接A了……我干嘛自己作死不想第一题啊！【我是sb

CF690A2口胡

http://www.codeforces.com/problemset/problem/690/A2

考试的时候脑补了下 $n=1,2,3,4$ 没啥规律，以为是道不可做题就扔了= =事实证明这题相当简单

假设有 $k$ 个物品分给 $n$ 个人，显然 $n\le 2$ 时第 $n$ 个人自己同意就能获得全部 $k$ 个，$n=3$ 时要让一个人同意就得给 $1$ 一个，$n=4$ 时要让一个人同意就给给 $2$ 一个（如果要给 $1$ 就得给两个，不划算），类推得到 $n=3,5,...,2k+1$ 时要给 $1,3,...,n-2$ 各一个，$n=4,6,...,2k+2$ 时要给 $2,4,...,n-2$ 各一个。

其实是我考试的时候手工列完表然后瞎以为答案是 $\frac{n}{2}$ 后来被自己叉了就觉得答案很复杂不可做

事实告诉我们要坚持下去啊！【要从被坑的经历中吸取教训

当 $n=2k+3$ 时，显然没办法让自己以外 $k+1$ 个人同意，于是只能死，类似的 $k$ 继续增加也只能死，但是这个情况会发生改变：编号在 $2k+2$ 以后的人为了活会同意，所以每次如果让前 $2k+2$ 人中的 $k$ 个同意（由 $n=2k+2$ 时的唯一情况可知这显然可行），那么就有 $n-(2k+2)+k$ 人同意了，只要 $2[n-(2k+2)+k]=n$ 即 $n=2k+4$ 就不会死了。

如果 $n=2k+m$ 不会死，那么下一个满足 $2[n-(2k+m)+k]=n$ 的 $n=2k+2m$，所以结论是条件为 $n\le 2k+2$ 或存在正整数 $t$，$n=2k+2^t$。

那么 $n$ 是奇数显然只能满足前者了，$k$ 的最小值为 $\frac{n-1}{2}$，$n$ 是偶数就可以是后者，要使 $k=\frac{n}{2}-2^{t-1}$ 最大，就要 $t$ 最大，取 $n$ 的二进制最高位减掉除以 $2$ 就是答案。

CF690E2口胡

http://www.codeforces.com/problemset/problem/690/E2

一道拼图的AI题，一开始觉得不可做，想了想觉得关键在于哪些边界接在一起比较合适。

对图像的 $k$ 个部分中的每两个 $i,j$，计算 $j$ 放在 $i$ 下方的不和谐程度 $w(i,j)$，不和谐程度越小的放置方法越优，那么就可以建立 $k$ 个点的有向图，从 $i$ 到 $j$ 的边权等于不和谐程度 $w(i,j)$，用状压DP求最小权哈密顿路径即可。

然后我被卡在了设计权函数上……我是把两个边界的灰度求差的平方然后加起来，然后发现被干扰了就取靠近边界的 $6\times 6$ 矩阵的灰度和来作差……效果极差无比……由于自己傻逼以为题目说的样例文件是一堆图片并不知道有 in 和 out 就不懂怎么调参（我还sb直接把图拿出来手工模拟做了一半弃疗了根本做不下去）最后脸滚键盘弄了个 $6$ 的常数……然后狂WA……全校只有我一个人没AC囧

事实上改成 $3\times 3$、$1\times 6$ 都能AC，效果比 $6\times 6$ 不知道好到哪里去了，大概是由于噪点并不是特别多，没必要用太大的矩阵模糊否则反而误差更大吧= =更重要的是要认真找样例文件，这种题不调参绝对是RP游戏

[UPDATE 7/12 20:30] 卧槽紫荆花之恋居然有人写了不到1KB就A了……好可怕……

[UPDATE 7/12 22:00] 看了下今天NOIP福建夏令营的题，有一题我居然不会做= =我真该补一补NOIP知识了

[UPDATE 7/13 11:00] BZOJ最后一页后面的题简直不可做，没有一题想得出来，我好弱。（orz SHUXK）

[UPDATE 7/13 20:00] lightning太强啦！出了一道神题！我搞了好久还只是接近AC=-=

研究UER2的B题【信息的交换】终于研究出来了……真是一道好题啊，研究了估计有一个月了才做出来【要是在考场上绝对10分滚粗了，UER2我去打肯定要挂】，中间绕了好多弯路掉了好几次坑，写完以后没过样例以为哪里错了……还好调出来了没问题2333

UOJ114口胡

http://uoj.ac/problem/114

很神的题。

对于一个图 $G$，考虑构出的序列是啥（这个一开始就卡了挺久），发现DFS过程实际上是按编号从小到大构了个DFS树 $T$，至于树上是按什么顺序呢……手动模拟了各种情况，发现如果从 $i$ 开始，每次令 $i=a_i$，所经过的 $i$ 的序列是 $T$ 按编号从大到小的DFS序（正好相反）。

然后考虑有多少个图具有这样的性质（这个卡了更久），即已知 $T$ 按编号从大到小顺序的DFS序 $L$ 还原图的方案数。一开始想的是DFS的过程记下当前DFS到了哪个结点，即 $f(i)$ 表示当前已经确定 $L_1,...,L_i$，确定剩下结点的连边情况的方案数，然而这做不了!0=0!因为一个点可以往祖先连边，而且连边条件还是它要比祖先的子节点大，如果把链上的情况记在状态里面就指数级了6666

又是纠结了很长时间，事实告诉我们研究DP的时候正、反都得考虑一发，考虑DFS树的反向边不要在子节点考虑而要在父节点考虑。

$f(i,j)$ 表示序列区间 $L_i,...,L_j$ 构树的方案数，这一步考虑根节点往子节点的连边，转移时枚举编号最大的子节点为根的子树区间 $[l,r]$，区间内有 $k$ 个比 $L_i$ 大的，就乘上 $2^k$。这样状态就真的只和区间有关了。

最后用一个区间DP完美地解决了这个问题，复杂度只要 $O(n^3)$。

我比较弱都想不出题，偶尔能想出一题都非常爽

[UPDATE 7/13 22:40] 这个月Codechef的题好丧做不动，算了就弃疗吧

[UPDATE 7/14 13:20] 今天校内训练又被immortalCO虐了 第一题一眼看出下界流，可是居然要输出方案烦。。。于是不会了最后骗分骗了20。第二题细节题，写完以后拍WA了原来是暴力写错了（幸好发现及时）。。。第三题好丧不会做写了个暴力弃疗（居然还多过了两个点）。。。最后发现immortalCO第一题100，lightning第一题50。。。我20分就尴尬了

[UPDATE 7/14 13:40] 原先分值有问题……重测以后分数和immortalCO一样……

[UPDATE 7/15 23:00] 今天学校专题讨论，讲了省队集训总结和一些知识点

【我的省队集训总结简直变成了Day2吐槽总结2333（一天挂两题的悲惨日子）

【我的知识点部分几乎是NOIP知识点归纳，讲的都是并查集、链表、队列、栈这些东西，然后翻出了一堆NOIP级别的题……和immortalCO、lightning的相比我真是弱爆了

【然后讲的时候immortalCO叫我接电话。。。居然是爸爸打进来的。。。然后后面又有录像直接拍给学弟看。。。真是无比尴尬啊 尼玛

我发现我被NOI2013 D1T2卡了将近一个月

剩下的看考前刷题记（下）