晨亦训计划总结

26-4-14

T1 树状数组优化 DP

T2 势能线段树板子

T3 发现题目中的式子是个关于的单调函数，于是可以二分，式子是个简单数数。

26-4-16

T1 分块题，注意一个性质，求区间模答案可以转化成次前缀。

T2 DP，重点是要按排序，有点反直觉。表示以开头的折射线路，开头的下一步向左/右的方案数。

转移蛮神奇的：

nmf(i, 1, n)
{
    ref(j, i - 1, 1)
    {
        if (a[j].second < a[i].second)
        {
            f[i][0] += f[j][1] + 1;
            f[i][0] %= mod;
        }
        else
        {
            f[j][1] += f[i][0] + 1;
            f[j][1] %= mod;
        }
    }
}

T3 猎奇结论题，结论我不会证。

26-4-22

这场 T1 太简单被毙掉了，T2 是高维莫队板板题，T3 其实不难，第一问几遍 DFS 求每个点子树内外直径即可，第二问随便找一个合法边暴力找两棵子树直径中点即可。

26-4-24

T1，二分答案，然后要找前大，nth_element 秒了。

T2，糖，将所有条件转化成或者的形式，方便求解，然后修改拍到 DFS 序上用两棵树状数组维护，一棵处理奇数深度修改，一棵处理偶数深度修改。

T3，麻烦数数题，思路就是固定两边，然后另外两边用数据结构维护，但这题有横/纵坐标相同的点，所以只能在值域上枚举两条边界，然后枚举处理这两条边界上点组成的区间，然后数数，纯一坨。

26-4-29

T1 可以发现每个点可达点是一个全为奇数/偶数的区间，题面要求求的就是最短路，而且所有边权均为，直接 BFS 求最短路，然后可以用两个 set 维护可达点，因为是 BFS 求最短路，不会重复访问同一个点，用过的点直接在 set 中删了即可。

T2 是神秘数数，首先是要注意到和的顺序不重要，简单理解，交换某两行不影响主视图，只交换左视图中的两行，即当前顺序下任意方案可以一一对应到交换中两个数后的一种方案，同理。归纳可得和的顺序不与答案无关。

然后是当且仅当中的最大值与中的最大值相等时有合法方案。

然后就是容斥和超绝数数。

放个网上的 Sol，内有详细数数过程。

T3 是超绝神秘 DP。

题解。