0201测试
0201 测试
T1
比较奇怪的题目。
手玩出 \(n=3\) 的情况，发现是当且仅当看到其他人帽子颜色相同时猜与其相反的颜色。
然后我们发现对于一种能猜对的情况，一定可以构造出一种会猜错的情况——将猜了的那些翻转即可。
然后为啥 \(n=3\) 的时候能做到 \(75\%\) 的正确率，是因为
000 111 这两种情况各自对应了 3 种猜错的情况。
于是我们考虑建图，将 \(2^n\) 个点每个点向二进制位恰好翻转一位的点连边。
图是一个 Hypercube（超立方体），虽然这暂时并没有什么卵用。
逆向考虑一种策略在图上会是怎样的。对于猜对的点，至少有一个相邻的点是猜错的 Case，而一个猜错的点最多对应 \(n\) 个猜对的点，这告诉我们正确率的上界是 \(\dfrac{n}{n+1}\)。而对于 \(n=3\) 的构造方案显然取到了上界。
发现这道题的 \(n=2^k-1\)，所以我们可能取到上界（Case 总数是分母的倍数）。取到上界，在图上就是存在一个大小为 \(\dfrac{2^n}{n+1}\) 的支配集。
换句话说，我们需要给一张图黑白染色，满足白色点最多，且每个白点必须连一个黑点，这个问题比较麻烦，不存在多项式做法，考虑图的特殊性质——Hypercube，这也许能够帮助我们构造出能够取到上界的情况。
我们需要选 Hypercube 中的一些点，能够取到上界。在 Hypercube 中的黑点在各个维度上变换后都是白点，考虑用异或的性质去构造。令第 \(i\) 个维度的权值为 \(i\)，维度权值异或和（如果该维坐标为 \(1\) 则异或，否则不异或）为 \(0\) 的点为黑点，其它为白点，这样的构造是满足条件的。
无向图 \(G(V,E)\) 的支配集是一个点集 \(S\)，记 \(F(u)\) 表示与 \(u\) 点有连边的点集，\(S\) 满足 \(\forall s_1,s_2(s_1\ne s_2)\in S,F(s_1)\bigcap F(s_2)=\emptyset\) 且 \(\bigcup\limits_{s\in S} F(s)=V - S\)。
为什么要考虑建图并将点向二进制位差异为 \(1\) 的点连边：这样建图之后确实能够让问题更加形象（也是受到手玩 \(3\) 的启发）。建图则是因为同一种策略正确的情况和不正确的情况的对应关系。
为什么要考虑用异或的性质构造：连边的形式是每一维变换，需要满足变换后不同，又恰好是 \(2^k-1\) 个维度，它们的异或和为 \(0\)。异或运算具有高度的对称性
T2
中规中矩的组合题。
发现如果横向或竖向有贯穿的一行或者一列，那么这些贯穿的行都是连在一起的，不妨考虑有若干列贯穿，枚举贯穿的区间 \([l,r]\)。
乘上贯穿的方案数 \((n+1)^{len}\) 后剩下的答案是两个类似问题乘起来，问题还是各个方向箭头把矩阵覆盖满，只不过只有上下左三个方向，且已知左边的某一个箭头把矩阵分成了两半。不妨枚举那个把矩阵分成两边的箭头的位置，剩下的只有两个方向了，是简单的组合问题。注意其中有分开的两半有一半左边不能贯穿，如果可以贯穿那么所有左边贯穿的箭头会被算重。
考虑没有贯穿的情况，记左边箭头最长为 \(s_1\)，右边最长为 \(s_2\)，上边下边 \(s_3,s_4\)。
如果纵向贯穿，则有 \(s_1+s_2<m\)，横向贯穿则是 \(s_3+s_4<n\)。这两种情况的答案单独计算。
下面的讨论请记住 \(s_1+s_2\ge m,s_3+s_4\ge n\)。
考虑 \(s_1+s_2>m\) 的情况，且，则一定能找到一个分界点，上下分别取到 \(s_1\) 和 \(s_2\)，此时必有 \(s_3+s_4=n\)。大概是这个图（不能同时满足 \(s_1+s_2>m\) 且 \(s_3+s_4>n\)）：
这种情况可以枚举某一条红线头的位置，注意靠上那条红线可以从左边来也可以从右边来，所以要乘 2。暴力枚举另一条红线交到的位置。剩下的四个问题独立，都是两个方向填矩阵的情况，基本组合问题。复杂度 \(O(n^3)\)
发现确定第一条红线的行之后移动列时，答案是一个固定值乘上一个前缀和的形式，可以做到均摊 \(O(1)\)。对于绿线也需要将矩阵转置一下计算。
最后剩下一种情况 \(s_1+s_2=m\) 且 \(s_3+s_4=n\)。
只能是这样的：
枚举左上角的位置计算即可，注意要算两遍，因为左上角位置既可以是横着过来的也可以是竖着过来的。
T3
有趣的数据结构题
一种暴力
维护每个数作为其中一个端点时的答案。
一个修改会对两个区间的答案造成影响。考虑如果维护这个影响。
赛时一直以为这是不可做的，实际上问题等价于维护 \(n\) 个编号连续的集合，操作是对于一段编号连续的区间都加入一个数，查询是查询全局 集合权值 + 集合中最大值 的最大值。
用线段树维护一段区间的集合，线段树上一个节点做集合操作时，这个节点代表的所有集合都具有同样的元素，因此直接取集合权值的最大值加上元素最大值即可。
解决问题的核心是将一个点的贡献/操作拆到了多个位置/多个部分，以便于对于不同的位置各自处理，这是一个非常重要的思想。
在本题中，将同一个点的贡献拆到了线段树上的多个部分，而一个线段树上的节点可以包括多个点，也便于对它们同时操作。
倍增并查集也是这个思路。倍增并查集拆分的是操作本身，将一个顺序无关操作分多步完成，多个操作的同一步可以一起做。
正解1
很神仙的一个想法是考虑按 \(k\) 将序列分块，然后块内是好做的，直接线段树维护。块间最多跨一个块。所以要统计块间的答案。
然后需要选 \(y\le x+k\) 使得 \(a_x+a_y\) 最大，然后令 \(b_i=a_{i+k}\)，变成 \(b_y+a_x\) 最大且 \(y\le x\)。
又变回了块内问题。这个问题如果在序列上是不好做的，因为额外有 \(y\ge x-k\) 的限制。但是分块统计的方式去掉了这个限制。
开一棵线段树来做这个问题，每个节点维护在这个这个节点 \(a_i,b_i\) 各自的最大值和答案，修改 \(a_i,b_i\) 时在各自的位置修改并上传答案即可。
一个问题如果能够简单的分治解决，套上线段树并记录分治过程之后就可以支持修改操作。
正解2
考虑取到答案的点的性质，由于答案由两个点构成，我们枚举了任意一个点都能得到答案，所以只需要考虑较大的那个点的性质。它满足它是区间 \([i-k,i+k]\) 中的最大值，称满足这样性质的点是好点。
我们只考虑好点的答案，于是做单点修改时只会修改常数个好点的答案，也只会有常数个好点变成不好的点或者不好的点变成好点。
好点的答案容易用线段树查询，好点答案最大值容易用 set 维护，时间复杂度 \(O((n+q)\log n)\)。
线段树需要写 zkw 以卡常。