NOI备考小结

6.29 IOI 2021 day1

T1.candies

Des:

​ 给出 $n$ 个袋子，每个袋子有容量上限 $c[i]$ 。接下来 $m$ 次操作，每次给 $[l,r]$ 区间的袋子装入/取出 $v[i]$ 的糖果，对于每一个袋子，当无法装入/取出时停止。求最后每个袋子里有多少个糖果。 ​ ​ ($n,m\le2e5$)

Sum:

​ 这道题的思想和之前在 $XJ$ 集训的时候遇到的某道题的思路很像，通过转化即可求解。

Sol:

​ 类似于曾经在 $XJOI$ 上做过的某题，对于每一个袋子，当装入或者取出操作的程度大于容量 $c[i]$ ，此前的所有操作无意义，而当最后一次这种情况出现后，其后所有的操作都将有意义。这里我们就只用二分最大的后缀满足其最大/小子段和没有超过这个容量。对于每个袋子之间就离线按顺序转移。时间复杂度 $O(n\log^2n)$ ，二分最大子段和应该可以在线段树上二分，可以降到 $O(n\log n)$ 。

T2.keys

Des:

​ $n$ 个点 $m$ 条边的图，每个点有一把钥匙 $a[i]$ (可以相同)，每条需要持有某一种钥匙 $b[i]$ 才能通过。设 $p[i]$ 表示从 $i$ 号点能到达的点数，求 $p[i]$ 最小的点集。 ​ ​ ($n,m\le 3e5$)

Sum:

​ 本题只要求最小到达点数的点集，可能就意味无法求出所有 $p[i]$ ，基于此思想思考如何舍去一些点。并考虑使用高效的数据结构处理钥匙和边的关系。

Sol:

​ 考虑答案的形式，最后大概会形成一个拓扑图，每个点是一个点集，而拓扑图终止节点中点集最小的就是答案。考虑这个拓扑图的含义，每个点集能在拓扑图上到达的点数(拓扑图上点的权值为点集大小)就是点集内每一个点都能达的点数。一个强连通分量向外连边后就无意义了。那么，我们的任务就是缩点并判断哪些点集有意义。缩点用线段树合并加启发式合并完成(颜色用线段树合并，在颜色的线段树叶子节点上挂可以到达的点，这些点用启发式合并)，时空复杂度均为 $O(n\log n)$ 。

T3.parks

Des:

​ 平面上若干个偶点（坐标均为偶数），相邻距离为 $2$ 的点之间可以连边，同时连出的这条边必须被一个奇点匹配（坐标均为奇数，且在该边的两个偶点的八联通内）。请构造出一种连接方式，时图上任意偶点之间可以互相到达，且每条边有不同的奇点匹配。 ​ ​ ($n\le3e5$)

Sum:

​ 构造题的做题思路还不够清晰，没有严密的构造逻辑。

Sol:

​ 由于图是网格图，而匹配分横纵两种边，这就很自然地引导我们往二分图黑白染色上想。将那些奇数点按照黑白染色分别分给横纵两种边。这样，两种边就自然地被区分开了，剩下的问题就是将图联通。我们考虑顺序加点，从左往右从上往下(只要是固定顺序即可)。然后再判断它的每一条出边能否连出来，可以发现这样一定有解。假设待加入点的上层点和同层左边的点都在同一连通块中，若横边需要借下一层的点，那么直接借了保证连通，反之，我们就可以用纵边借接下来右边的点来保证与上面连通，因此一定会连通。时间复杂度 $O(n\log n)$ ，这里的 $O(\log n)$ 是 $map$ 存图的复杂度。

6.30 IOI 2021 day2

T1.dna

Des:

​ 给出两个字符串 $A,B$ ，接下来 $q$ 次询问，每次询问一个区间 $[l,r]$ ，求将 $A$ 在 $[l,r]$ 区间内的字符串通过最少的操作次数变为 $B$ 在 $[l,r]$ 区间内的字符串。

​ ($n,q\le 1e5$)

Sum:

​ 挺水一题，考场看错题了，整了好久才整明白。

Sol:

​ 每段区间无非就是在若干二元环和三元环中转，优先转二元环，再转三元环即可。时间复杂度 $O(n)$ 。

T2.dungeons

Des:

​ $n+1$ 个点，其中一个第 $n+1$ 个点是终点，每个点有个权值 $s[i]$ ，若到达 $i$ 时自己的权值 $w\ge s[i]$ ，那么当前权值 $w$ 加上 $s[i]$ 并进入 $wi$ ，反之，当前权值 $w$ 加上 $p[i]$ 并进入 $l[i]$ 。接下来 $q$ 次询问，求每次从位置 $x$ 以初始权值 $y$ 进入到终点时的权值。

​ ($n\le 4e5,q\le5e4$)

Sum:

​ 考场上觉得是倍增套倍增，完全想不明白就放了。

Sol:

​ 由于每次加上第一次未成功进入的 $s[i]$ 会使权值翻倍(可以成功进入的 $s[i]$ 直接倍增)，那么剩下来的操作就是在一个基环树上跳再从某一个 $s[i]$ 进入，这里预处理在基环树上的倍增，每次找到下一次进入的 $s[i]$ 。由于权值每次翻倍，所以可以在 $O(\log V)$ 次到达终点。时间复杂度 $O(q\log n\log V)$ 。

T3.registers

Des:

​ 给定 $m=100$ 个长度为 $b=2000$ 的寄存器，每一位上可以存一个比特，给出 $n$ 个长度为 $K$ 的 $a[i]$ ，仅用位运算和加法，若 $s=0$ 则求出 $a[i] $ 的最小值，若 $s=1$ 则将 $a[i]$ 排序，在 $q$ 次操作之内完成。

​ ($n\le 100,k\le 10,q\le 4000$)

Sum:

Sol:

7.1 NOIAC

T1.gcd

Des:

​ 给定 $n$ 个字符串 $a_i$ 和 $b$ 。接下来 $q$ 次询问，每次给出一个 $x$ 表示选定的 $a_i$ 集合，求将 $a_i$ 集合顺次拼接后与给出的 $b$ 区间 $[l,r]$ 求 $LCS$ 。

Sum:

​ 对折半搜索不够敏感，且对四边形不等式掌握的不到位。在考虑集合的时候时常会用到折半搜索。

Sol:

​ 设 $dp[x][i][j]$ 表示集合 $x$ 对于 $[l,r]$ 的LCS，前一维 $x$ 可以折半搜索，后面两维满足四边形不等式，具有决策单调性。

T2.hundred

Des:

​ 给定 $n$ 个人，每个人有初始积分 $a_i$ ，再给出 $m$ 中搏斗 $(x,y,z)$，表示 $x$ 被 $y$ 打败，$y$ 将获得 $z$ 的奖励以及 $x$ 所有积分，且若这是 $y$ 打赢的第 $s$ 场， $y$ 还将获得 $n-s+1$ 的奖励。保证 $m$ 连出的有向图无环。

​ 设 $X$ 表示最后所有人的总积分， $Y$ 表示未打赢过的人数，求出原图的子图满足每个人在搏斗中被打败就将离场，最大化 $\frac{X^k}{Y}$ 。

​ ($k\in {1,2} ,n\le 150,m\le 500$)

Sum:

​ 考场上写出来了 $k=1$ 的费用流，但是由于各种奇怪的错误，全挂了。事实上，若我直接枚举 $Y$ ，那么我就可以直接用 $k=1$ 的费用流来通过本题。本题可以非常好地套用费用流的原因就在于其额外积分刚好就是降序选择。

Sol:

​ 题目非常长，但仔细读题并分析清楚题意后就会发现事实上本题有用的信息不多。因为最终求所有人的积分和，所有人的初始权值显然无用，只是个常数，我们只关心整体的积分和。而每个点至多选择一个点进行选择，这就让我们考虑到二分图。关于每条边 $(x,y,z)$ 倒是非常好直接套用费用流，问题就在于额外的奖励，由于费用流会优先最大值，而额外积分的奖励机制也刚好就是降序，所以我们可以拆出若干条边，其权值为 $n,n-1,n-2…$ ，流量为 $1$ 。$\frac{X^k}{Y}$ 关于 $X+ky=0$ 有凸性，可以利用相关性质解题。更好的做法是，枚举 $Y$ 将每条边往额外汇点连权值 $\inf$ 边流量 $1$ 的边，最后再将额外汇点向原汇点连权值 $0$ 流量 $Y$ 的边。时间复杂度 $O(n^2m)$ 大概。

T3.years

Des:

​ 定义排列 $a$ 的一个上升子序列 $b$ 的权值 $\displaystyle \sum \ln (b_i-b_{i-1}+K)$ 。

​ 接下来 $q$ 次询问，每次给定 $K$ ，求最长上升子序列中权值最大值。

​ ($n\le 1e6,K\le 1e6,q\le 20$)

Sum:

​ 考场上有想到线性的做法，但是当时想的时候忽视了每个长度时加入的点是单调递减的，以为我的做法假了。

Sol:

​ 我们将各个长度的结尾点分开，可以发现每个值只会在一段时间内有效，然后就会被其后的某个点给击败，所以，每个点只会进一次出一次。问题就在于如何求每个点何时被打败，列出式子可以发现其值恰好就是求个 $exp$ ，但在弹点的时候会出现一定问题，可能是不是边缘的点被弹掉，那么，每次弹点的时候就把被弹点左右两个点拿出来 $exp$ 求出交点，判断后面的点什么时候被弹掉即可。时间复杂度 $O(qn)$ ，$exp$ 的常数巨大，只于 $O(qn\log V)$ 的做法我还没想明白。

7.2 Day1

T1.math

Des:

​ 设 $f_i$ 为长度为 $i$ 的错排数量，$g_i$ 为长度为 $i$ 的圆周排列个数。

​ 求 $\displaystyle \sum_i\sum_j \begin{Bmatrix} i \ j \ \end{Bmatrix} f_jg_j $ 。答案对 $998244353$ 取模。

​ $(n\le 1e5)$

Sum:

​ 考场上推出了最终式子，没有进一步放缩 $j$ 的范围，导致结果没办法化简。

Sol:

​ $f_j,g_j$ 无关，直接不管。我们把一列第二类斯特林数展开掏出来，可以发现结果就类似于求一列的答案：$\displaystyle s_i =\sum_k\frac{(-1)^k} {k!} \frac{\sum (i-k)^j}{i-k}$ 。直接 $NTT$ 求解。

T2.sequence

Des:

​ 给出序列 $a_i$ ，求其子序列满足 $\prod \binom{a_i}{a_{i+1}}$ 为奇数的个数。答案对 $998244353$ 取模。

​ ($n\le 1e5,a_i\le 1e5$)

Sum:

​ 对折半的思想不是很掌握，在处理这种集合类问题的时候，经常被卡思路。可见，在处理关于集合内问题时，应该多考虑是否可以拆分为无关的几份实现折半。

Sol:

T3.phi

Des:

​ 给定序列 $a_i$ ，接下来 $q$ 次询问，求 $\displaystyle \phi(\prod_{i=l}^ra_i)$ 。答案对 $998244353$ 取模。

​ ($n,q\le 2e5,a_i\le 1e6$)

Sum:

​ 考场上写了个莫队，时间复杂度 $O(n\sqrt n\log n)$，完全不可能过。不过，简单总结一下，对于某些加入和删除只在第一次出现有效的题中，我们通常需要考虑扫描线线段树。

Sol:

​ 每次询问的答案是区间权值之积乘上区间 $\displaystyle \prod \frac{p_i-1}{p_i}$ 。由于这里的质数只与是否出现有关，则我们可以将询问离线，从左往右扫描线，保证质数在它最后一次的出现位置产生贡献。询问的时候在线段树上询问区间积。时间复杂度 $O(n\log n\log V)$ 。