Preface
最近因为队友要准备预推免，很久没有一起训练过了；我个人也是把大部分精力都放在科研方面，算是挺久没写代码了
同时因为这场撞了本校预推免的原因，导致学校很多队伍被迫重组，但好在我们队没受影响堪堪凑齐了三个人
这场题还算符合我们队的口味吧，虽然因为大家都不会写代码了导致 dirt 很高而且写的很慢，最后压哨 8 题，没够到 9 题的及格线
但总体来说对很多题目想法都有，剩下没过的 B,H 都有思路；最后反正学校的 CCPC 名额也是打满了，只能说不粘锅了
PS：赛时代码后续待补……
A. 整点正方形计数2
队友开局写的，好像是个什么差分计数之类的东西，我题目都没看就过了
C. 造桥与砍树
为什么都知道用类普利姆的做法，我只会用公式克鲁斯卡尔
将所有数模 \(k\) 后排序，很容易对每个数 \(i\) 找到它的最优匹配数 \(mt_i\)；而一旦我们选择了 \((i,mt_i)\) 这条边后 \(i\) 的最优匹配数就会右移
考虑把每个数对应的匹配权值扔到堆里模拟克鲁斯卡尔的过程，并用并查集维护当前的联通关系，每次连边后把下一个最优匹配加入堆中即可
但这样做复杂度显然会爆炸，因为存在大量已经在一个集合内的匹配会导致端点的移动数量打到 \(O(n^2)\) 级别
一个显而易见的观察就是随着匹配点向右的移动，我们可以一次性跳过一段连续的位置，因此可以再用一个并查集来维护空位，即可保证总复杂度 \(O(n(\log n+\alpha(n))\)
PS：事实上这题利用类似的思路写类普利姆的做法很好写，只能说公式人是这样的
D. 通配符匹配
挺套路的 DP+KMP，但实现起来细节挺多，扔给队友写了
E. 看比赛回放
签到，因为败方赢了 \(l=m-\frac{n+1}{2}\) 局，因此最坏需要看 \(2k+1\) 局才能确定
F. 连线博弈
很公式的一个题，首先看到博弈就想到打表 SG 函数
（值得一提的是刚开始犯病了以为每个子问题是独立的线段模型，后面找了反例才发现是图连通块内部的模型）
不难发现状态只和连通块内的点数有关，因此转移为 \(SG(x)=\operatorname{mex}_{y=0}^{x-2} SG(y)\oplus SG(x-y)\)
然后这个 SG 函数的规律是在几百项之后有 \(34\) 的周期，这还是给队友打了值相同的下标差分值后才找到的规律，只能说是十分神秘
剩下的问题就是怎么划分连通块了，一个经典 trick 就是用 Hash
对于一条线段，给其两侧的点集分别异或上一个不同的随机数，最后值相同的点集即属于同一个连通块内
统计个数很容易用 map 离线处理
G. 序列与整数对
很套路的根号分治，对于询问 \((x,y)\)，令 \(l_x,l_y\) 分别表示 \(x,y\) 出现的次数
- \(\max(l_x,l_y)\le \sqrt n\)，此时直接 two pointers 扫一遍即可得出答案；
- \(l_x>\sqrt n\)，此时对应的 \(x\) 种类不超过 \(\sqrt n\)，在固定 \(x\) 的情况下可以对任意 \(y\) 正向 \(O(n)\) 扫一遍原序列得到答案；
- \(l_y>\sqrt n\)，此时对应的 \(y\) 种类不超过 \(\sqrt n\)，在固定 \(y\) 的情况下可以对任意 \(x\) 反向 \(O(n)\) 扫一遍原序列得到答案；
总复杂度 \(O((n+q)\sqrt n)\)
H. 教师
考虑一个 trivial 的 DP，令 \(f_{i,mask}\) 表示花费总时间为 \(i\)，已经确定最大值的课程状态为 \(mask\) 的最大收益
每次考虑一个新的老师时，我们只更新当前状态的补集的子集即可，因为这样一定会把最优解给算到
但 \(O(mT\times 3^n)\) 的复杂度无法通过，考虑利用 sosdp 的思路，每次直接枚举某个课是不是当前教师作为最大值，复杂度降为 \(O(mT\times n2^n)\)
#include<cstdio>
#include<iostream>
#include<cstring>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
int n,m,k,T,V[N][10005],f[N][1<<14],val[14];
signed main()
{scanf("%lld%lld%lld%lld",&n,&m,&k,&T);for (RI i=0;i<n;++i)for (RI j=0;j<=k;++j)scanf("%lld",&V[i][j]);for (RI mask=0;mask<(1<<n);++mask){int res=0;for (RI i=0;i<n;++i)if ((mask>>i)&1) res+=V[i][0];for (RI i=0;i<=T;++i)f[i][mask]=res;}while (m--){int h,t; scanf("%lld%lld",&h,&t);for (RI i=0;i<n;++i) val[i]=V[i][0];while (h--){int x,y; scanf("%lld%lld",&x,&y); --x;val[x]=max(val[x],V[x][y]);}for (RI i=T-t;i>=0;--i){static int g[1<<14];memcpy(g,f[i],sizeof(g));for (RI j=0;j<n;++j)for (RI mask=0;mask<(1<<n);++mask)if (((mask>>j)&1)==0)g[mask|(1<<j)]=max(g[mask|(1<<j)],g[mask]+val[j]);for (RI mask=0;mask<(1<<n);++mask)f[i+t][mask]=max(f[i+t][mask],g[mask]);}}for (RI i=1;i<=T;++i)printf("%lld\n",f[i][(1<<n)-1]);return 0;
}
K. 置换环
直接逆序构造 \(n,n-1,\dots,1\) 即为最优解
考虑证明，因为 \(n\) 次移动过程中每个点都会作为不动点恰好一次，而上述构造方法在每个点不是不动点时，能保证剩下的点均构成若干二元环，这一定是最优的
M. 并行计算
队友都是分布式并行计算高手，我题意都没看就早早过了这个题，最躺赢的一集
Postscript
本来以为这个学期能有很多时间训练冲个好成绩，现在看来大家都很忙估计又要开始摆烂模式，比赛权当旅游了