9.3集训

Posted on Edited on In

第一道题 江南乐 是一道博弈论的题目，学长讲了。

multi-nim

将数量为m的一堆划分为i堆，将会划分出$m i \(堆个数为m的堆，和\)m - m i i\(堆个数为\)m+1$的堆

枚举i，求出划分为i堆的sg函数，效率很低，考虑优化

根据的异或的性质可以得到，偶数个同样的数异或起来，等于没有异或

因此如果他是奇数，我们才去异或

并且应用到整除分块，\(\dfrac m {\dfrac m i}\) 为\(\dfrac m i\)值相同的\(i\)的最大值

！！！注意：优化find,是用此时的x标记后继状态, 找mex时寻找具有这个标记的x的后继状态.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (sg[x] != -1) return sg[x];
if (x < f) return sg[x] = 0;
sg[x] = 0; int i, j, res;
for (i = 2; i <= x; i = x / (x / i) + 1)
{
    for (j = i; j <= min(i + 1, x); ++ j)
    {
        res = 0;
        if ((x % j) & 1) res = res ^ yhm_find(x / j + 1);
        if ((j - x % j) & 1) res = res ^ yhm_find(x / j);
        s[res] = x;
    }
}
while (s[sg[x]] == x) ++ sg[x];
return sg[x];

第二道是ddp"动态 DP"&动态树分治

动态dp&动态树分治

考虑思路：

  • 在树上搞出dp
  • 转移到序列上
  • 再搬回树上观察修改点所带来的影响
  • 考虑优化，树剖跳轻儿子保证复杂度\(O(logn)\)
  • 于是考虑通过矩阵来优化新构造出的dp转移方程式

其中下面这一局是树剖最经典的语句：\(query(dfn[x], end[top[x]], 1, n, 1)\)

——把树弄到了序列上

第三道是MET-Meteors（整体二分）

考虑整体二分的思路来源

对于这道题，我们当然可以二分做，但是二分做复杂度过于高

考虑对整体二分

显然，对值域进行二分看起来是一个不错的选择

于是我们选择对值域进行二分

然后验证的时候，和正常二分无太大思想的差异

但是在递归去求解子区间的时候，需要注意，用线段树或者树状数组来维护，因为是log的

其中如果发现左半区间无解，往右半区间递归的时候

应该减去在左半区间已经达到的答案

！！！注意：在修改之后，要进行复原