cf 刷题杂记（1）

Codeforces Round 969 (Div. 2)

之前某篇题解一语成谶掉分了，赶在正式开学前打回蓝名 QwQ

C. Dora and C++ (C)

卡了很久才想起来裴蜀定理，期间还写了个假做法，不好评价。

由 \(ax + by = k\times gcd(a, b)\) 有解，可以将序列中任意两个数的差减小至 \(gcd(a, b)\) 以下。从相对性角度考虑，令 \(c_i\mod gcd(a, b)\) 后重新排序，则 \(ans = c_n' - c_1'\)；再贪心地从首项开始加上 \(gcd\)，有 \(ans = min(ans, c_i' + gcd - c_{i + 1})\).

D. Iris and Game on the Tree (D)

妙妙博弈题，写的比C题还快一点，果然我更擅长猜结论，基础还是太不扎实了

观察发现规律：任意字符串的权重只与其首尾字符有关，首尾字符相同则权重为 \(0\)，反之为 \(1\)；因此整棵树的权重只与根节点和叶子节点有关。当根节点值确定时，最优操作显然容易判断，而根节点不确定时，设叶子节点中已经确定的值数量为 \(cnt_0,cnt_1\)，当二者不相等时，先手先行确定根节点更加有利；而 \(cnt_0 = cnt_1\) 时，若叶子节点剩余问号数量为奇数，确定根节点会导致步数落后，因此双方都会尽可能地先填中间节点的值、将确定根节点的步骤留给对方，考虑奇偶即可。