20210628模拟赛解题报告
写在前面
期望得分：\(100+100+20 \sim 100 = 220 \sim 300pts\)
实际得分：\(100+0+30 = 130pts\) （因为教师机上的 lemon 不能用 lower_bound，这太傻逼了）
实际得分：\(100+100+30=230pts\) （换了台能用的机子，结果 2e8 没跑过去，这太傻逼了）
洛谷得分：\(100+100+100=300pts\) （把数据点扔洛谷上，啪的一下就过了，我 AK 了？！）
T1 是个树剖求 LCA 的板子， 10min 切掉，然后花了 10min 想了几种很怪的情况特判了；
然后开 T2，一眼是期望，用了 10min 想到一个不错的思路，感觉很可做，20min 写出来了，过了样例，稍微算了一下没爆 longlong 就扔掉看 T3 了。
T3 一眼以为是一个数位 DP，教练的题怎么天天考数位DP，设了个五维的状态 \(f_{i,j,x,y,k}\)，发现连 \(20\%\) 的数据都开不下，并且不会转移。然后就弃了发呆。中间上撤锁吃了顿饭，感觉思路如泉水般涌现。回来稍微完善了一下就码出来了，感觉自己阿克了，找 KnightL 的暴力拍了一下，发现 \(n\&1=1\) 时被 Hack 了，并且在本地机子和极限数据下代码跑了 5s+，感觉要凉。经过一阵紧张的调码环节后发现是自己式子推错了，改过了被 Hack 的部分过了，但在极限数据下依旧跑的很慢mmp。
题目扔这儿，有兴趣的可以爆切了：T1,T2,T3
题解写的太拉了，所以我成为了新的题解 /cy
题解
T1
可以利用 dfs 序来求解，如果 \(a\) 是 \(b\) 的祖先，当且仅当 \(dfn_a \le dfn_b < dfn_a + siz_a\)，预处理 \(O(n)\)，查询 \(O(1)\)。
也可以使用树剖求 LCA 去判断两个点之间的关系，时间复杂度 \(O(n \log n)\)。
也可以倍增求 LCA，需要 \(O(n \log n)\) 的预处理，不过查询的复杂度都是 \(O(\log n)\)。
反正随便过啦
/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"< T2
考虑固定 \(A\) 序列，然后随便安排 \(B\) 的位置，显然这依旧是合法的。方案数是全排列的方案数 \(n!\) 。
发现全排列不好枚举，考虑计算所有可能下 \(a_i\) 与 \(b_j\) 的对决次数。
固定这两个位置，其他的随便枚举，所以对决次数为 \((n-1)!\)，所以这两个人对 \(A\) 队分数的贡献为 \(\frac{(a_i - b_j)^2}{n} [a_i > b_j]\)。
然后枚举所有 \(a_i\) 与所有 \(b_j\) 对决就是答案
\(B\) 队同理。所以：
\[ansa = \sum_{i=1}^{n}\sum_{j=1 \&\& a_i > b_j}^n \frac{(a_i - b_j)^2}{n} \]\[ansb = \sum_{i=1}^{n}\sum_{j=1 \&\& b_i > a_j}^n \frac{(b_i - a_j)^2}{n} \]这样的复杂度是 \(O(n^2)\)，显然过不掉。
发现排序对答案没有影响，所以先对两个数组排序。
用 \(lower\_bound\) 找到第一个比 \(a_i\) 大的点的位置 \(x\)，答案变为
\[ansa = \sum_{i=1}^{n}\sum_{j=1}^x \frac{(a_i - b_j)^2}{n} \]然后把平方差拆开，发现可以预处理前缀和，前缀平方和。然后每个元素就可以 \(O(1)\) 算了。
总时间复杂度 \(O(n \log n)\) ，瓶颈在二分那，不过也能过了。
发现两个队都是单调的，所以每次二分找的位置一定是单调增的，可以用个指针，指针只会向右移动，所以复杂度是 \(O(n)\) 的。
为了避免精度问题，可以最后除以 \(n\)，算一下开 longlong 是不会爆的。
代码是使用 \(lower\_bound\) 的版本。
/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"< T3
可以设个五维的状态 \(f_{i,j,x,y,k}\) 分别表示 当前位数，上一次填的数，总和，前 \(n\) 个数的和，奇数位的和 然后数位 DP。发现空间在 \(20 \%\) 的数据下都开不下，笑死。
考虑换个思路，设 \(f_{i,j}\) 表示填了 \(i\) 位，总和为 \(j\) 的方案数。
如何求 \(f_{i,j}\)？
把它当做一个 01背包 ，一共 \(|S|\) 件物品选 \(n\) 次（为什么只需要算到 \(n\) 到后面就自然明白）。
初始化 \(|S|\) 中的每个元素 \(x\) 选一次都是 \(1\)，即 \(f_{1,x} = 1\)。
考虑只有前 \(n\) 个数和后 \(n\) 个数和相同的情况。利用乘法原理，总方案数为：
\[\sum_{x=0}^{Max}f_{n,x}^2 \]其中 \(Max\) 表示所填的数的和的上限。
在考虑第二个限制，发现和第一个限制一样都是填两次 \(n\) 个数，然后两次和相同，只不过填的位置换了换。
所以在上面的基础上 \(\times 2\) 即可。
同时满足的情况重复计算了，考虑如何筛去。同时考虑两个条件的性质应该不难想。
设 \(k = n / 2\) 表示前面 \(n\) 个数中有几个偶数位，设 \(x\) 表示前 \(n\) 个数中的偶数位和为 \(x\)，设前 \(n\) 数总和为 \(s\)。其方案数可以用 \(f_{k,x}\) 表示。
那么，前 \(n\) 个数中有 \(n-k\) 个奇数位，奇数位的和为 \(k-x\)，方案数为 \(f_{n-k,s-x}\)
同理，后 \(n\) 个数中奇数位的情况应当与前 \(n\) 个数中偶数位的情况相同，后 \(n\) 个数中偶数位的情况应当与前 \(n\) 个数中奇数位的情况相同，方案数分别为 \(f_{k,x},f_{n-k,s-x}\)。
利用乘法原理，要减去的总的贡献为
\[\sum_{s=0}^{Max}\sum_{x=0}^{s} f_{k,x}^2 \times f_{n-k,s-x}^2 \]极限情况下复杂度为 \(O(10^8)\)，正常评测机是可以过的，但学校的古董机过不去。
我们发现，前 \(n\) 个数奇数位填的数只和后 \(n\) 个数偶数位填的数相关。与另外两个无关。所以考虑把两部分先单独算出来在用乘法原理。
设 \(Max1,Max0\) 分别表示前 \(n\) 个数奇数位填的最大位数和和偶数位填的最大位数和。
要减去的总的方案数为
\[(\sum_{x=0}^{Max0}f_{k,x}^2) \times (\sum_{y=0}^{Max1} f_{n-k,y}) \]减去即可。
复杂度为 \(O(Max0+Max1)\)。你会发现预处理极限情况下依旧是 \(O(10^8)\)
/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"<> s + 1;
int len = strlen(s + 1);
for(int i = 1; i <= len; ++i) {
stc[++sc] = s[i] - '0'; // 其实这个行为挺傻逼的
f[1][stc[sc]] = 1;
}
if(n == 1) {
cout<= 0; --k) {
for(int j = 1; j <= sc; ++j) {
f[i][k] = f[i][k] + f[i-1][k - stc[j]];
if(f[i][k] > mod) f[i][k] -= mod;
}
}
}
for(int i = 0; i <= Max; ++i) {
Ans = Ans + f[n][i] * f[n][i] % mod;
if(Ans > mod) Ans -= mod;
}
Ans = Ans * 2 % mod;
// cout<