2024.3 总结

倒叙总结。

link [tag: 构造，数论]

正着做很困难，正难则反，现在考虑一个数 \(a_x\) 能否作为结尾，显然要满足 \(F(x)=lcm\{a_i|i\neq x\}\) 的 \(F(x)\) 不是 \(a_x\) 的倍数。

在考虑不断取到最后一个数的过程中，\(F(x)\) 显然不会上升，可以使用任意顺序的意思。

现在还有一个问题，\(F(x)\) 会爆 long long，我们要转换的考虑（这个问题解决办法其实好像不少的。\(a_j\) 对 \(a_x\) 的影响部分其实只有 \(\gcd(a_x,a_j)\)，我们再对这部分取 \(lcm\)，如果等于 \(a_x\) 就是不行，不然的话显然......？

link [tag: 博弈论]

考虑最后两个数为 \(a,b\)，选手和为 \(x,y\)，那么应该有怎么取都是这个 b 赢（好奇怪。

那么有 \(x+a\equiv y+b\pmod m\) 和 \(x+b\equiv y+a\pmod m\)，于是得到 \(2a\equiv 2b\pmod m\)，是时候对着这个发呆了！？？首先 \(a=b\) 没什么问题哒 qwq

这个 \(2\) 的实质上是什么呢？手玩之后发现可以对 \(m\) 进行分讨。

• 若 \(2|m\)，所以 1 的余数被不要了，一个循环节变成了 0,2,4... & 0,2,4...，这时候 \(2x\) 和 \(2(x+\frac{m}{2})\) 同余啦。

• 若 \(2|m\)，循环节仅仅是顺序改变。

首先相等的对去掉，如果 \(2|m\) 就再按照第二种规则凑对，特判凑成奇数对不合法。然后是，如果能配队完就合法。

哦还要构造对应的先手必胜的方案！按照匹配选完，到了最后一定是最开始说的那个局面，就可以 win 了。

link [tag: dfn，树状数组，离线]

唐，感觉做法很多。直接 stack 处理祖先，然后变成子树里面数 \(dep_i=x\) 的个数，这个 dsu on tree 啊什么的就能做。也可以直接离线按照不同深处分别处理，对应的点贡献 +1，然后查询对应深度询问的子树和，再清掉 +1 的贡献即可。

link [tag: 树形 dp]

考虑反着走，处理出每个点合法的一群蚂蚁的上下界，对于每个叶子，在原序列中二分有多少个合法的蚂蚁群即可。

link [tag: 贪心，主席树]

假设集合 \(S=\{a_{p_1},...,a_{p_d}\}\) 可以表示出 \([1,x]\)，此时答案就是 \(x+1\) 了。我们考虑新加入一个 \(a'\) 带来的影响。

• \(a'\leq x+1\)，此时可以表示的区间扩张到了 \([1,x+a']\)。

• \(a'>x+1\)，根本就，无法产生影响嘛 /fad

那很朴素的，假设现在我们的区间是 \([1,x]\)，我们将所有没有加入的第一类数加入 \(S\)，额那不就变成所有 \(a_i\leq x+1\) 的 \(a_i\) 和了嘛......？第一类数中加入了的跟 \(S\) 等价呀。

就这样加，知道某一次加前加后的 \(x\) 相等就是答案了。

in fact，这样子加的 \(x+1\) 有一个倍增复杂度就差不多是 \(log\) 的了，不需要再继续优化。具体而言，我们考虑一个最 poor 的加法的 x 的变化是 1,3,6,11,19,... 这个形式的。

link [tag: 贪心，排序]

呜呜呜怎么是套路 /lh

首先 \(b_i\gets a_i-b_i,c_i\gets c_i-a_i\)，然后变成了强制选 \(a\)，然后 \(y\) 个换成 \(b\)，\(z\) 个换成 \(c\)。

考虑两个人 \(i,j\) 一个选 \(b\) 一个选 \(c\) 的时候 \(i\) 什么时候贡献更好，那么是 \(b_i+c_j>b_j+c_i\) 即 \(b_i-c_i>b_j-c_j\)。

我们按照 \(b_i-c_j\) 降序排序，那么一定存在一个分界点，使得左边只有选 \(b\) 的，右边只有选 \(c\) 的情况下去到最好答案。这个很好反证（

然后就是前后分别处理一下，用堆做出前若干大的和，再枚举分界点取 \(\max\)。

link [tag: 数数]

我觉得这个题可以蓝的？？？

考虑一个数前面的逆序数为 \(a_i\)，当且仅当 \(a_i>k\) 时 \(a_i\) 会向前移动并且减，所有考虑最终序列中 \(a_i=k\) 的位置，可以往后移的种类是 \(n-i+1\)，这个累乘一下就是答案了。