2023年7月30日发(作者：)

NOI2021联合省选A卷题解即将退役选⼿还是简单写下题解Day1T1 卡牌游戏据说有O(n)做法先⼆分答案，然后枚举最⼩值是来⾃A还是来⾃B这样我们需要反转⼀段前缀以及⼀段后缀，处理个B的前后缀最⼤/⼩值就能判断从⼩往⼤枚举可以双指针做到O(n)check时间复杂度O(nlogA_i)T2 矩阵游戏⼀道类似的题⼀道类似的题传统的做法是枚举矩阵的a_{11}然后设出每⾏和每列的第⼀个数差分约束建图，或者是搜索但是这道题好像做不了，原因是值域太⼤我们考虑先确定⼀个不考虑值域限制的矩阵然后调整它那么你的操作就是交替给每⼀⾏/列执⾏++--的操作于是你会发现你的每⼀个格⼦也是⼀个形如L leq a_i pm b_j leq R的形式考虑反转所有奇数的⾏和偶数的列那么每个格⼦都可以变成L leq a_i - b_j leq R的形式直接差分约束即可juruo不会写spfa导致T成傻⼦，学了dalao的写法双端队列才过认为n，m同阶，时间复杂度O(n^3)T3 图函数不难想到考虑每个点的贡献⼀个点u能对v geq u产⽣贡献当且仅当u和编号⽐它⼤的点构成的导出⼦图中u和v在同⼀个环上于是就有⼀个每个点每张图都跑⼀次tarjan的优秀做法时间复杂度O(nm^2)这个做法看起来没法优化我们考虑这其实只要求⼀个环⽽不需要知道SCC于是我们考虑直接对每个点u考虑他能和v成环当且仅当图中存在⼀条u->v的路径和v->u的路径只经过编号geq u的点这好像是废话但是这样就可以做了考虑这条路径的贡献其实就是路径上编号最⼩的边，编号在这之前的图都可以满⾜条件不难发现只需要对每个点dijkstra跑个最短路就可以计算贡献但是这样看起来是O(nmlogm)的，貌似过不了考虑⼀个更easy的想法我们只需每次加⼊⼀个边的时候扩展u所在的连通块这样每个点/边只需被加⼊⼀次时间复杂度O(nm)注意卡常Day2T1 宝⽯树上跳等差数列⼀类的东西不难想到倍增预处理出f/g两个倍增数组，表⽰每个点向上第⼀个点权是这个点点权的前驱/后继的点于是对于⼀个询问s->ts->lca的这段可以考虑⽤g直接O(logn)处理lca->t的这段好像不好搞只能先⼆分答案，然后⽤f从t跳上去判断是否可⾏这个是O(log^2n)的我们发现不管是预处理倍增数组还是处理询问都需要访问⼀个点祖先上最近的某⼀种颜⾊的位置不难想到把询问离线，开⼀个桶在树上扫3遍即可时间复杂度O(nlogn+qlog^2n)T2 滚榜不难想到O(n!*n)的做法即枚举所有排列那么可以扫⼀遍出b_i-b_{i-1}的最⼩值，做个前缀和判断是否leq m即可考虑优化成状压dp不难想到设状态f[S][i][j][k]表⽰当前选了S中的点，最后⼀个是i，当前最后⼀个b_i是j，当前所有b的总和是k的⽅案总数发现时间复杂度O(2^nn^2m^2)甚⾄跑不过阶乘算法不难想到j和k可以合在⼀起，考虑每⼀个差分即b_i-b_{i-1}的贡献是独⽴的于是状态简化为f[S][i][j]表⽰当前选了S中的点，最后⼀个是i，当前所有差分的贡献总和是j的⽅案总数时间复杂度O(2^nn^2m)⽤计算器⼀算5e8，还有很多空状态，⽤刷表dp跑得飞快T3 ⽀配不难得到⽀配树的O(nm)建法即暴⼒算出每⼀个点⽀配哪些点于是我们就得到了⼀个每次询问重构⽀配树的O(nmq)算法考虑每次直接在⽀配树上搞我们发现加边只会让点的⽀配集减⼩并且若⼀个点的⽀配集减⼩，那么它的⼦树的⽀配集也会减⼩于是不能难发现⼀个点，若它祖先的⽀配集都没被改变，那么它的⽀配集⾥⼀定删去了⽀配树上它的⽗亲那么考虑加⼊x->y会影响哪些点u，使它的⽀配集⾥删去了它的⽗亲，然后再dfs⼀遍即可算出答案⾸先，y需要能够不经过u⽀配树上的⽗亲⽽到达u这个可以枚举每个点，在反图中删去它的⽗亲来预处理其次，x和u的lca不能是u的⽗亲这⼀点只需判断fa[u]是否⽀配x即可于是我们就在O(nm)预处理，单次O(n)处理询问的复杂度内解决了这个问题总时间复杂度O(n(m+q))Processing math: 0%