I. Interesting Scoring Systems
J. Joyful Numbers
K. Königsberg Bridges
L. Long Grid Covering
签到题。
A. Adjacent Rooks
\(GF\) 大失败，\(dp\) 大胜利。
填排列一种很经典的 \(dp\) 是从小到大依次插入，这样能比较好处理相邻数之间的关系
所以设 \(f_{i,j,0/1}\) 表示到 \(i\) 有 \(j\) 个连续，\(i\) 和 \(i-1\) 是否相邻。
插入一个数分讨，可能使连续数 \(+1,-1\) 或不变。
B. Beautiful Permutation
打表构造？出题人坚持这是本场最难的题，严谨构造也不怎么看得懂。
直接推柿子可以发现：
\[\sum b \equiv \sum a- \sum i (mod \ \ 2) \\ \frac{n(n-1)}{2} \equiv n(n-1)(mod \ \ 2) \]所以 \(n \% 4=2/3\) 都无解，然后打表剩下都有解。
\(n \% 4\) 提醒我们可以考虑 4 个分成一组或分成 4 组，钦定前 \(n/4\) 个倒序然后看表，看有没有比较顺的答案。
下面是在 \(n=16,17\) 找出的比较合理的答案
//15 14 13 12 3 11 10 9 8 6 5 4 2 1 0 7
//16 15 14 13 4 12 11 10 9 7 6 5 3 2 1 0 8
if(n%4==0){
for(int i=0;i<n/4;i++) a[++tot]=n-1-i;
a[++tot]=n/4-1;
for(int i=0;i<n/4;i++) a[++tot]=n-1-i-n/4;
for(int i=0;i<n/4-1;i++) a[++tot]=n/2-2-i;
for(int i=0;i<n/4-1;i++) a[++tot]=n/4-2-i;
a[++tot]=n/2-1;
}
else{
for(int i=0;i<n/4;i++) a[++tot]=n-1-i;
a[++tot]=n/4;
for(int i=0;i<n/4;i++) a[++tot]=n-n/4-1-i;
for(int i=0;i<n/4-1;i++) a[++tot]=n/2-1-i;
for(int i=0;i<n/4-1;i++) a[++tot]=n/4-1-i;
a[++tot]=0; a[++tot]=n/2;
}
C. Cartesian MST
直接展开成 \(n*m\) 的网格，然后还是跑 \(kruskal\) ，每次加一条边相当于合并两行/两列，加的边数就是剩余列数/行数，直到最后缩到一个点。
复杂度 \(O((n+m)log(n+m))\)。
D. Display of Springs
回忆一下李超树的过程：对于每个节点找出中点最大的，然后标记永久化。
所以建树比较次数 \(O(nlogV)\) ，查询比较次数 \(O(logV)\)。
E. Even Intervals
\(5e4\) 可以离线还是 20s，莫队+权值线段树即可。
F. Friendship Circles
考虑要使圆包含 0 而不包含 \(x\) ，那么必须要满足圆心在 0 和 x 中垂线靠 0 这一侧。
所以直接半平面交，在交后的图形内任意一点做圆过 0 保证和其它点不会相交，所以只要看多少线构成这个交即可。
题解比较 nb，考虑圆反演：
首先如果有解那么肯定存在一个圆过两个点符合要求。对于 0 圆反演，那么这个圆就是一条直线，在圆内的靠外，圆外的靠内。
因为是个双射，所以我们可以通过圆反演之后的图形来做：如果有一个点可以，那么就是存在一条直线使得仅有这个点在直线外。
所以只有凸包上的点合法。
G. Game on a Tree
好像挺有意思的，留坑待填。