NEERC 17 K
题意
有一个序列 \(\{a[i]\}\) ，满足 \(\sum\limits_{j=1}^{i-1}a_j<a_i\) ， \(\sum{a_i}<2^{64}\) ，以及一个奇数 \(r\)
现在给出序列 \(\{b[i]\}\) ，其中 \(b[i]=a[i]*r\ mod\ 2^{64}\)
再给出一个整数 \(s\) ，求一些 \(b_i\) 使其和 mod \(2^{64}\) 为 \(s\)
保证有解
\(1\leq n \leq 64\) ， \(1\leq b_i,r\leq 2^{64}\)
题解
一种方法是 meet in the middle ，复杂度为 \(O(2^{\frac{n}{2}})\)
另一种方法是枚举 \(a_1\) ，解出 \(r\)
由题意得 \(a_i>2a_{i-1}\) ，因此 \(a_1\leq2^{64-n}\)
又因为 \(2\nmid r\) ， \(a_1\) 与 \(b_1\) 的 lowbit 应当相同，设为 \(k\)
则只能解出 \(mod\ 2^{64-k}\) 意义下的 \(r\) ，还需要枚举前 \(k\) 位
但 \(2^k\mid a_1\) ，\(a_1\leq 2^{64-n}\) ，因此枚举 \(a_1\) 仅需枚举 \(2^{64-n-k}\) 次，总复杂度仍为 \(O(2^{64-n})\)
解 \(r\) 时直接推 \(mod\ 2^k\) 意义下的逆元，不要用exgcd
以 \(42\) 为阈值分治两种算法，即可通过此题
WF2014 K
题意
给定一个大小为 \(n\) 的环和 \(k\) 条线段，使用最少的线段覆盖环。
\(n,k\leq 10^6\)
题解
直接倍增，令 \(f[i][j]\) 为 \(i\) 之前有线段覆盖的点能到达的最远点，注意一些 \(\pm1\) 的细节
WF2019 B
题意
你要修一座拱桥。桥面的高度为 \(h\) 。给定 \(n\) 个地形坐标 \((x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\) ，将其相邻连接就是地面。
你需要修若干条柱子，只能在给定的点对应的横坐标处修，在第 \(i\) 个点处修的柱子的高度为 \(h−x——i\) 。第 \(1\) 个和第 \(n\) 个点处必须修柱子。
你还需要在修的柱子之间造拱，拱是一个半圆形，直径为两个柱子的距离，恰好和桥面相切。
拱不能和地面相交，可以相切。
假设你修了 \(k\) 条柱子，高度为 \(h_1,h_2,\dots,h_k\) ，修了 \(k-1\) 个拱，直径为 \(d_1,d_2,\dots,d_{k−1}\) 。
给定参数 \(\alpha,\beta\) ，要求最小化代价： \(\alpha*\sum\limits_{i=1}^k{h_i}+\beta*\sum\limits_{i=1}^{k-1}{(h_{i+1}-h_i)^2}\)
无合法方案输出 impossible 。 \(n\leq 10^4\) 。
题解
显然可以DP，需要做到 \(O(1)\) 的判断一段区间内的点是否都在某个圆内。
设现在我们由 \(f_i\) 向后转移，新的拱半径为 \(r\) ，则新的拱圆心为 \((x_i+r,h-r)\)。
这样一个点 \((x_j,y_j)\) 在圆内的条件为 \((x_j-x_i-r)^2+(y_j-h+r)^2\leq r^2\)
整理得 \(r^2-2(x_i-x_j+y_j-h)r+(x_i-x_j)^2+(y_j-h)^2\leq 0\)
可以解得 \(r_1\leq r\leq r_2\) 。
因为拱是一个半圆，所以当 \(y_j\leq h-r_1\) 时只需要 \(r\leq r2\) 。
枚举 \(j\) 时维护 \(r\) 的范围即可。
WF2019 G
题意
有一棵 \(n+1\) 个点的树，每条边上有一个大写字母，每个点所代表的字符串是由其到根节点的边上字母依次排列。
有 \(k\) 个询问，每次给定一个字符串 \(S\) ，求有多少个非根节点代表的字符串以 \(S\) 为前缀。
\(n,k,\sum{\abs{S}}\leq 10^5\)
题解
这个描述很奇怪。。。首先把所有询问串都反过来，这样这棵树就是一个 trie ，询问就变成了询问多少个串的后缀是 \(S\) 。
对于所有询问串建 AC 自动机，把这棵 trie 放在上面跑，AC 自动机上沿途所有经过的结点点权 \(+1\)
询问的答案就是 fail 树上的字数点权和
NEERC, Northern 2016-17 J
题意
有一种语言，只有一种变量 ? ，其值在 \([0,255]\) 内随机，有六种操作
+ - * / min max 。
支持进行宏定义。
给定一个结果 \(c\) ，你只能进行宏定义并写出一个表达式，使得此表达式的值等于 \(c\) 的概率不小于 \(\dfrac{1}{2}\) 。
宏定义与表达式的总长度不超过 \(256\) 。
题解
如果需要 \(0\) ，依照样例输出
? / ? / ? 。
否则，用 \(1\) 拼出 \(2,4,8,16,32,64,128\) 即可获得所有数。
我们需要七个数都正确的概率大于 \(\dfrac{1}{2}\) ，即需要 \(1\) 正确的概率不小于 \(\dfrac{1}{2}^\frac{1}{7}\approx 90.6\%\) 。
考虑将许多个 \(?\) 取
max ，使其大概率为 \(255\)
，然后将两个 \(255\) 相除。
则需要每个 \(255\) 正确的概率不小于 \((90.6\%)^\frac{1}{2}\approx 95.2\%\) 。
取一个 ? 取到 \(255\)
的概率是 \(\dfrac{1}{256}\) 。
所以要保证这个正确概率需要取\(\log_{\frac{255}{256}}(1-0.952)\approx776\) 次。
依靠宏定义使每层套多个上一层 max
即可在规定长度内通过。
事实上，可以使正确率超过 \(1-10^{-10}\) 。
##NEERC, Northern 2016-17 G
题意
有棵 \(n\) 个点的树形供水网络，每个叶子是一座房子，根节点是水源。
有个黑帮占据了一些房子，需要切断尽量少的供水管道使黑帮的水源中断，在此基础上使平民房子受影响尽可能少。
一开始黑帮没有占据任何房子，有 \(q\) 次操作每次向一个房子加入或移除黑帮，然后询问以上的两个值。
\(n,q\leq 10^5\)
题解
第一问的答案即为根节点有黑帮的儿子数量，很好维护。
显然切断的是根的每个儿子子树内点的 lca
，求出这个容易维护第二问答案。
维护集合 lca
的最简便方法是在插入/删除点时到根节点链修改，定义节点的偏序以点权为第一关键字，以深度为第二关键字，则答案即为子树最大值。
树剖即可。
NEERC, Northern 2016-17 E
题意
有一篇长为 \(l\) 的文章，和一个
\(n\times m\)
的网格图。网格图上每个格子为 . 或 X。
你需要从文字中选一段子串，然后选择网格图上的任意一个点 \((x,y)\) 作为起点，在阅读这段文字时，遇到
l,r,u,d
字符时，分别使你当前所在的位置往左、右、上、下移动一格。最终恰好画出网格图中
X 画出的图形。
问是否可行，如果可行输出你选的子串区间。
\(l\leq 10^5,n\times m\leq 10^5\)
题解
即一段字串画出的图形和网格图上的图形形状相同。
只有两个图形 X 的个数相等且两个方向上
max-min 相等才有可能。
双指针，转化为 \(O(l)\) 次判断两个图形是否完全一致。
因为 \(n\times m\leq 10^5\) ，必然又一边小于 \(\sqrt{10^5}\) ，将这一边逐行 \(hash\) 判断即可。
注意细节。