The 2nd Universal Cup. Stage 17: Jinan
为了参加省赛打的模拟。
打了八个题，稳稳金牌。
E. I Just Want... One More...
考虑如何计数，因此考虑方案的等价条件。
一条边满足要求，当且仅当原图存在一种最大匹配，使得这条边的两个顶点都不在匹配中。
而上述条件，实际上等价于两个顶点各自满足：存在一种最大匹配，使得这个点不在匹配中。
证明考虑广义 Hall 定理。
于是我们只需要判断二分图匹配的非必经点即可。实际上跑出最大流后，我们从源点出发走剩余流量不为 \(0\) 的边（包含反向边），可以走到的左部点是非必经点；从汇点出发走剩余流量为 \(0\) 的边，可以走到的右部点也是非必经点，与前者同理，相当于对称。前者这样的根据是，如果这个点向汇点连一条容量为 \(1\) 的边，那么一定可以使最大流 \(+1\)，因此原本的匹配中可以没有它。
因此分别求出左部和右部中的非必经点数量，再乘起来即可。
但是实际上可以直接考虑网络流增广路理解，过程几乎一摸一样，但是不需要广义 Hall 定理，我又想复杂了 qwq。
L. Ticket to Ride
考虑设计 dp 转移式 \(f(i,j)\) 表示前 \(i\) 条线已经考虑完成，其中有 \(j\) 条线没有被覆盖。
我们可以依次枚举 \(j\)，做如下 DP 转移：
\[f(i,j)=\max\left\{f(i-1,j-1),\{f(i',j) + w(i',i)\mid i' < i\}\right\} \]如果正在考虑 \(i\) 位置，记 \(m_t\) 表示 \(1\) 到 \(t\) 之间的能作为 \(i'\) 的最优选择。这个 \(m_t\) 一定是随着 \(t\) 变大单调不降的。
每次以 \(j\) 作为 \(r\) 枚举奖励区间的 \(l\)，将 \(1\) 到 \(l-1\) 的贡献加上奖励权值，更新 \(m\) 即可，很明显因为 \(m\) 中每一段都指向一个位置考虑是否最大，这中间不会有段的分裂，只有合并。
以段为单位看，势能分析知段的合并和更新次数为 \(O(n)\)。
具体可以使用并查集加链表，更新 \(f(1,j)\cdots f(n,j)\) 的时间复杂度为 \(O(n\alpha (n))\) ，总时间复杂度为 \(O(n^2\alpha (n)+nm)\)。
M. Almost Convex
其他的不用说，考虑对于两个特殊点和一个点集，在点集中选择一个点与两个特殊点构成三角形，且三角形内部不包含点集中的其他点，问点集中有多少个这样的点。
实际上考虑这个点与两个特殊点构成的两个角，一个点满足要求等价于它的两个角度不存在偏序大于另外一个点的两个角度的情况。
The 2nd Universal Cup. Stage 22: Hangzhou
为了准备省赛打的模拟。
打了 6 个 题，大概是银牌线。
B. Festival Decorating
把每个颜色的位置的补集放在在 bitset 上，可以得到一个空间和事件复杂度均为 \(O(\frac{n^2}{w})\) 的显然方法，但是空间过不去，因此考虑优化空间复杂度。
考虑对于出现次数 \(>\sqrt n\) 的颜色开 bitset，而出现次数 \(\le\sqrt n\) 的情况直接在每次遇到的时候暴力求出，这样时间复杂度为 \(O(\frac{n^2}w+\frac{n\sqrt n}{w})=O(\frac{n^2}{w})\)，而空间复杂度为 \(O(\frac{n\sqrt n}w)\)。
C. Yet Another Shortest Path Query
易知平面图的边数不超过 \(3n-6\)，因此度数最小的点的度数一定不超过 \(5\)，我们做 \(n\) 次操作，每次操作把当前图中度数最小的点删去。
记 \(t(v)\) 表示 \(v\) 点删除的时间。我们把无向边 \((u,v)\) 拆成两条有向边，不妨设 \(t(u) < t(v)\)，则 L 类边为 \(u\to v\)，R 类边为 \(v\to u\)。
显然一个点只能作为最多 \(5\) 条 L 边的起点，\(5\) 条 R 边的终点。
发现边数 \(k\le 3\) 的要求可以是询问变为分类讨论。
- 依次经过：L 或 R，显然可做。
- 依次经过：LR 或 RL 或 LL 或 RR，显然也可做。
- 依次经过：LLR 或 LRL 或 LLL 或 LRR，枚举第一个 L 边，转换成 \(5\) 个子问题。
- 依次经过：LRR 或 RLR 或 LLR 或 RRR，枚举最后一个 R 边，转换成 \(5\) 个子问题。
没有其他的情况，因此将问题离线。注意时间和空间限制，因此必须要做到精妙的实现，目前这份提交是 QOJ 最优解。
E. Period of a String
没什么可说的，重在实现。
H. Sugar Sweet II
注意到将事件的 \(b_i\) 按 \(b_i\to i\) 建出图，发现是一个外向基环树森林。如果只有树的情况，实际上要分类讨论。
设 \(p_u\) 表示 \(u\) 点在事件 \((u,b_u)\) 发生时满足条件的概率。记 \(v\) 为 \(u\) 深度最大的祖先（可以是自己），使得 \(p_u=1\)，即直接有 \(a_u<a_{b_u}\)，这时应有：
\[p_u=\frac{p_v}{(dep_u-dep_v+1)!} \]因为从 \(v\) 到 \(u\) 的所有点对应的事件必须按照从 \(v\) 到 \(u\) 的相对顺序发生，概率为 \(\frac{1}{(dep_u-dep_v+1)!}\)。
考虑在基环树上，则是找到到他距离最近的 \(v\)，dfs 即可。
K. Card Game
考虑一个答案的函数 \(ans(l,r)\)，实际上应该有：
\[ans(l,r)= \begin{cases} ans(l+1,r)+1 & r < next(l) \\ ans(next(l)+1,r) & r \ge next(l) \end{cases} \]因为要离线，因此这个可以使用主席树的合并和永久化标记来实现。
The 2024 Sichuan Provincial Collegiate Programming Contest
省赛的题目真的纯降智，感觉我们的准备一点用都没有。
最后作为打星队伍做了 9 题，获得了第 7 名。
剩下没做的题目是 BDI，感觉都很可惜。
以下是我想出的题目。
A. Reverse Pairs Coloring
考虑没有 \(a_i>a_j\) 的限制，则，并把每一行行内连通的块看成一个点，则网格图从上往下构成了一棵树。考虑 \(a_i>a_j\) 的要求实际上是把树上的一些点砍掉，我们可以倒着扫，遇到砍掉的部分把这部分结算计入答案即可。但是因为前面也有砍掉的部分，因此需要用树状数组记录砍掉部分会有多少点结算。
F. Isoball: 2D Version
相当于判断一条射线是否与矩形有交。
G. Function Query
可以利用 trie 找到两个最大的 \(i\)，分别满足 \((a\oplus x_i)<b\) 和 \((a\oplus x_i)>b\)，这两个中间较小的那个就是答案。
等于的情况要特殊判断。
J. Roman Numberals
简单数位 DP 即可，以当前位为 \(1\) 往前记 \(1000\)。
L. Beef Tripe in Soup Pot?
签到题。
标签：ac,06,Submission,复杂度,2024,做做,frac,考虑,QOJ From： https://www.cnblogs.com/imcaigou/p/18249252