10.6

[NOI2013] 向量内积

首先判断是否为 \(2\) 的倍数，我们将每个向量点乘前面向量的前缀和，若最后答案的奇偶性与 \(i-1\) 的奇偶性相同，那么理想状况下是全一，当然也可能是出现偶数个零，但是如果最后答案奇偶性与 \(i-1\) 的奇偶性不同，那么一定至少存在一个向量与当前向量点乘为 \(0\) ，因为这是必要不充分条件，所以我们可以多次 \(shuffle\) 序列来判断。

判断是否为 \(3\) 的倍数，我们把上面的思路延续，容易发现 \(0^2\equiv0\pmod3,1^2\equiv1\pmod3,2^2\equiv1\pmod3\) ，我们成功把问题转化为 \(0/1\) 问题，所以维护前缀平方和就好。

[IOI2014] friend 朋友

从后往前处理，这样处理到当前 \(i\) 结点就不用考虑它与后面结点的连边。设 \(j=host_i\)
若只看 \(1\) 操作，只将 \(i\) 和 \(j\) 进行连边，那么就是一个朴素的树上最大独立集，此时我们 \(i\) 和 \(j\) 只能选一个，所以我们给答案先加上 \(w_i\) ，同时 \(w_j=max(w_j-w_i,0)\) ，这样方便反悔。
\(2\) 操作是将 \(i\) 和 \(j\) 的邻居连边，也就是说此时 \(i\) 和 \(j\) 的邻居完全相同，也就是说对 \(i\) 和 \(j\) 的限制也完全相同，所以 \(w_j=w_j+w_i\)。
\(3\) 操作对 \(i\) 和 \(j\) 的限制也完全相同，唯一多的就是 \(i\) 和 \(j\) 只能选一个，所以 \(w_j=\max(w_j,w_i)\) 。

abc374_f

感觉有用的点不是很多，于是把第二维即发货天数这个状态跟答案存成一个 \(pair\) 放进 \(set\) 里，每回保留有用的那几个就好了，复杂度未知。

abc134_f

把绝对值拆开，发现我们只需决定每个球放在它后面的盒子还是前面的盒子，每个盒子装后面的球还是前面的球，所以我们可以考虑 \(dp\) 。设 \(f_{i,j,k}\) 代表前 \(i\) 个数和盒子，有 \(j\) 个盒子为空，同时当前怪异度为 \(k\) 的方案数，然后思考如何如何从 \(i-1\) 转移到 \(i\)：

1. 第 \(i\) 个球和第 \(i\) 个盒子匹配，\(f_{i,j,k}+=f_{i-1,j,k}\)。
2. 第 \(i\) 个球和前面的盒子匹配，第 \(i\) 个盒子都和前面的球匹配，\(f_{i,j,k}+=f_{i-1,j+1,k-2i}\times(j+1)^2\)。
3. 一个和前面匹配，一个和后面匹配，\(f_{i,j,k}+=f_{i-1,j,k}\times 2j\)。
4. 两个都和后面匹配， \(f_{i,j,k}+=f_{i-1,j-1,k+2i}\) 。

然后就做完了。