526互联

Educational Codeforces Round 159 (Rated for Div. 2)

发布时间 2023-12-05 00:15:05作者: xzm111

A - Binary Imbalance

如果全是 0 则显然输出 YES。对至少有一个 1 的情况，如果存在 0 则一定存在一个 0 和 1 挨在一起的位置，一直往这中间加 0 即可满足要求。

于是只要字符串包含 0 就是 YES，全 1 就是 NO。

Submission

B - Getting Points

一天的收益可以为 \(2t + l, t + l, l\) 三种，容易算出每种至多取多少天，贪心地从大往小取即可。

Submission

C - Insert and Equalize

把 \(a\) 从小到大排个序，先不考虑添加 \(a_{n+1}\)，设 \(g = \gcd(a_n - a_1, a_n - a_2, \dots, a_n - a_{n-1})\)，可以观察到一个合法的 \(x\) 一定满足 \(x \mid g\)。

若能通过 \(x\) 把所有数变成 \(a_n\)，则 \(\forall i: x \mid a_n - a_i\) 一定成立，这等价于 \(x \mid g\)。而对于一个 \(y \nmid g\)，\((a_n - a_i) \bmod y\) 的值不会随操作而改变，又因为 \(y \nmid g\)，则 \(\exist i: a_n - a_i \not\equiv 0 \pmod{y}\)，于是 \(y\) 不合法。

显然最小操作次数就是 \(\sum\limits_{i=1}^{n} \dfrac{a_n - a_i}{g}\)，即把所有数用 \(g\) 变成 \(a_n\)。新加一个数时，观察到加在 \(a_n + g\) 处不优于加在 \(a_1 - g\) 处，于是只考虑不改变最大值的添加方式。于是添加 \(a_{n+1}\) 带来的额外代价为 \(\dfrac{a_n - a_{n+1}}{g}\)，由于 \(a_{n+1} < a_n\)，于是最大化 \(a_{n+1}\) 即可。具体地：找到最大的 \(i\) 使得 \(a_i - g > a_{i-1}\)，此时 \(a_i - g\) 即为最优 的 \(a_{n+1}\)。

处理一组数据的时间复杂度为 \(O(n \log n)\)。

加快实现：C++17 起引入 std::gcd(_Mn __m, _Nn __n)，直接用即可（当然 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 也一样）。

这题有用 unordered_map 被 Hack 了的，原理在 这里，所以慎用 unordered 系列。

Submission

D - Robot Queries

好像有很简洁的做法，这里给出一种分治做法。

可以先处理出类似前后缀和的东西，即操作一段前缀后能到达的坐标，从终点逆操作一段后缀后能到达的坐标（不难发现，反转区间不会影响经过整个区间后坐标的变化量），此时可以先处理掉询问中没有被翻转的部分，翻转了的区间分治处理。

套路地分治，每次处理跨过分治中心的询问。利用跨过分治中心的性质，将要翻转的区间分成两半处理，容易发现，新的操作序列就是把左边一段翻转了放右边，右边一段翻转了放左边。于是也把询问拆成两个，右边的询问放左边的长度，左边的询问放右边的长度。

此时从分治中心向两边拓展，左右分别维护 正向移动/逆向移动 能到达的坐标集合，遇到拆分后询问时，先从预处理的 后/前 缀中找出找出走到反转区间 右/左 端点时的坐标，简单变换到以分治中心为原点的坐标系下，判断集合中是否存在需要的 \((\Delta x, \Delta y)\) 即可。

代码实现的时间复杂度是 \(O(n \log^2 n)\)，也不算慢。

这题好像也有用 unordered_map 被卡了的。

Submission

E - Collapsing Strings

容易把问题转化为：求对于每个 \((i,j)\)，\(s_i\) 后缀和 \(s_j\) 的前缀最多能匹配多少位，只要求总和。

稳定的做法就是用字典树维护所有的 \(s_i\)，并统计每个节点的子树中有多少个关键点（作为结尾的点）。然后再用每个 \(s_i\) 的反串去字典树上跑一遍统计答案。

空间更小的做法则是用哈希表维护每个 \(s_i\) 前缀或后缀的哈希，并枚举每个 \(s_i\) 的后缀或前缀来尝试匹配。然而因为 Open Hack，这种做法寄了一大片。

不过这并不能说明哈希是错的，只能说明寄了的哈希不合理。下面给出两类很容易被 Hack 的字符串哈希（多项式哈希）。

  • 自然溢出
  • 固定方式且模数乘积并没有大得变态

第一种是众所周知的寄，它本质上是对 \(2^{64}\) 取模，这个模数本身是不好的，因此无论你怎么搞（多种自然溢出一起做判据，随机 \(base\)，对字符做随机映射），只要还符合多项式哈希的形式，通过以下代码都能得到两个哈希值一样的串（对 __uint128_t 的自然溢出，只要稍微增大 \(n\) 的取值即可）：

string s; s.resize(1<<12);

s[0]='a'; int n=1;
for(int i=0;i<12;++i) {
    for(int j=0;j<n;++j) s[j+n]=((s[j]-'a')^1)+'a';
    n<<=1;
}

string ss[2];
for(int i=0;i<(1<<11);++i) ss[0]+=s[i];
for(int i=0;i<(1<<11);++i) ss[1]+=s[i+(1<<11)];

cout<<ss[0]<<"\n"<<ss[1]<<endl;

把它们放在合适的位置就可以构造出 Hack。

Example：自然溢出即使双哈希也寄。

第二种包括了常见的双哈希（取两个 \(10^9\) 级别的质数分别做），也包括了类似取一个 \(10^{18}\) 的质数的做法。在没有 Hack 的时候可以认为它们是正确的，因为造数据的时候并不知道你的哈希函数，那么它极大概率不会出错。但是有了 Open Hack 时，Hacker 可以得到你的哈希函数，根据生日悖论，只要 \(\sqrt{\prod mod}\) 级别个字符串，就能找到一对哈希值相同的串。常规做法这个值都是在 \(10^9\) 级别，通过对字典树随机拓展可以做到 \(O(1)\) 生成一个不同字符串，于是 Hacker 只需要把你的哈希函数提取出来，然后用几分钟的时间做这个随机构造就能卡掉。唯一的缺点是这样随机拓展的内存开销较大，可能需要申请超过 \(40 \text{GiB}\) 的内存才能爆破掉部分哈希，但只要限制一个大小并重复随机就可以解决这个问题，容易发现，串长的期望是 \(O(\sum \log mod)\) 级别的，也就是说，绝大部分的数据范围都能容纳 Hack 数据。

Example：双哈希，但是根号甚至不到 \(5 \times 10^8\)。

而能活过 Open Hack 的常规哈希（就是 Hacker 能在有限的时间内找到并看懂你的哈希函数的实现的哈希），要么是带随机的，要么是 \(\sqrt{\prod mod}\) 极大的。

也就是说，如果时间允许，那么三重甚至四重哈希能显著降低被叉的可能性，这本质上是在提升 \(\prod mod\)，即扩大哈希函数的值域。

时间不允许则可以引入随机成分，但注意：模数为质数是一个很好的性质，随机后仍然要保证所有模数为质数，否则它可能莫名其妙寄掉（参考自然溢出）。于是随机一般在 \(base\) 上做。随机的范围不能太小，不然可以用上面的方法把随机的值域中大半的 \(base\) 卡掉，然后 Hack 你。随机注意初始化种子，种子也一定不能是常量，不能是可预测的量（time(nullptr)，这点存疑，不知道有没有案例），可以用 chrono::steady_clock::now().time_since_epoch().count() （相对较高精度的时钟）或 random_device{}() （虽然 Windows 下不是真随机，但也是由系统产生的安全伪随机数），尽量别用 rand()，因为 CF 的机子是 Windows，RAND_MAX 只有 \(32767\)。

赛时以为字典树空间不够，写的 Hash 并且过了 System Test，代码其实还用了一个 unordered_map，但是并没有人卡（其实也不太好卡，主要是 map 实在跑不过去）。

Submission

F - Trees and XOR Queries Again

感觉比前两个简单，因为几年前有过 这题（这下真的是 “Again” 了）。浪费时间写 D 了，没看这题。

询问能否用异或表示，可以转化为询问路径上的点的异或线性基。于是做法类似，因为线性基是可以 \(O(\log^2 n)\) 合并的（就是暴力枚举一个中的元素，把它插进另一个里面），而且这东西显然有交换律和结合律，于是倍增维护即可。

由于毒瘤的 Hack，现在倍增要想 AC，必须在合并线性基时加上这么一个优化：插入时不枚举 \(x\) 的每一个二进制位，而是每次直接取 \(\lfloor \log_2 x \rfloor\)，显然复杂度没有优化，但是它就能过了。取 \(\lfloor \log_2 x \rfloor\) 可以用 __lg(x)，它的实现是（对 uint）：

inline _GLIBCXX_CONSTEXPR unsigned
  __lg(unsigned __n)
  { return (int)sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }

显然是个常数极小的 \(O(1)\)，事实证明它快于预处理 log 数组。

Submission