NOIP 模拟赛第七场
预估分数：\(100+30+50+20\)，实际分数：\(100+30+50+30\)，排名 \(4/15\)（or \(5/16\)）。
好消息：实际分数比预估分数还高。坏消息：T2 简单题，T4 部分暴力分和所有乱搞分都没拿到。
T1
题目大意：有一个 \(n \times m\) 的网格，每个网格上垂直放有 \(a_{i,j}\) 个立方体，但这些数未知。你会得到这个立体图从前面看第 \(i\) 列看到的立方体数 \(b_i\) 和从左面看第 \(i\) 列看到的立方体数 \(c_i\)，求\(\sum a_{i,j}\) 的最小值，无解输出 \(-1\)。\(n,m \le 3\times 10^5,a_i,b_i \le 10^9\)
思路分析：签到题。
首先我们判断无解的情况，就是 \(\max b_i \neq \max c_i\)，原因显然 ，因为最高的那个立方体不可能从左边看和从前面看对不上。至于必要性，就是考虑到 \(\max b_i = \max c_i\) 时我们显然有一种方案，就是在最高的那个位置建立坐标系，按照 \(x\) 轴第 \(i\) 列放置 \(b_i\) 个物体，\(y\) 轴第 \(i\) 列放置 \(c_i\) 个物体，就有了一种合法解。
但是这样放肯定是太多了，因为可能出现某个 \(b_i = c_j\)，只需一个高度为 \(b_i\) 的方块放在位置 \((i,j)\) 即可。故考虑优化。首先我们注意到 \(b_i,c_i\) 的顺序对答案无影响，所以我们钦定 \(b,c\) 单调不降。于是对于每一个 \(b_i\)，我们都找一个未放置的一列且满足 \(b_i = c_j\)，然后在位置 \((i,j)\) 放置高度为 \(b_i\) 的立方体。最后再累加第 \(j\) 列未放置物体的 \(c_j\) 就是答案。实现过程双指针维护即可。复杂度需要排序的一个 \(\log\)。
#include
#include
#define int long long
using namespace std;
int id,n,m,a[2000005],b[2000005],c[2000005],ans,l;
signed main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);freopen("count.in","r",stdin);freopen("count.out","w",stdout);cin >> id >> n >> m;for(int i = 1;i <= n;i ++)cin >> a[i];for(int i = 1;i <= m;i ++)cin >> b[i];sort(a + 1,a + n + 1);sort(b + 1,b + m + 1);if(a[n] != b[m]){cout << -1;return 0;}l = 1;for(int i = 1;i <= n;i ++){ans += a[i];while(l <= m && b[l] < a[i])l ++;if(b[l] == a[i]){c[l ++] = 1;continue ;}}for(int i = 1;i <= m;i ++)if(!c[i])ans += b[i];cout << ans;
}
T2
题目大意：你有 \(n\) 个硬币机，对第 \(i\) 个硬币机按 \(1,2,3\) 次可以分别得到 \(a_i,a_i + b_i,2 \times a_i + b_i\) 枚硬币，按 \(4\) 次及以上得到的硬币数和按 \(3\) 次得到的硬币数相同。对于 \(k = 0,1,...,m\)，请求出按 \(k\) 次硬币机得到的最多硬币数的异或和。\(n \le 10^5,m \le 10^6,a_i,b_i \le 10^9\)
思路分析：太吃脑电波了，考场上只写了暴力，但知道做法后就瞬间做出来了。
核心思想：考虑到有什么做法能够使之不产生依赖关系。所以不妨考虑拆点。
具体地，把一个硬币机拆成两个点。一个点占用空间 \(1\)，利益为 \(a_i\)；一个点占用空间 \(2\)，利益为 \(a_i + b_i\)。这样无论选这两个中的哪几个，都在原题面的约束下合法。于是这就变成了 \(2n\) 个互不依赖的点。首先注意到只有两种占用空间，所以我们先对 \(a_i\) 及 \(a_i + b_i\) 构建两个数组并分别从大到小排序。注意到暴力 dp 依然是 \(\mathcal{O}(n^2)\) 的，因此直接贪心即可。设使用 \(k - 1\) 次硬币机时，最优方案为放 \(l\) 个占用空间为 \(1\) 的点，\(r\) 个占用空间为 \(2\) 的点，那么使用 \(k\) 次硬币机时最优方案一定为放 \(l + 1\) 个占用空间为 \(1\) 的点，\(r\) 个占用空间为 \(2\) 的点或者放 \(l - 1\) 个占用空间为 \(1\) 的点，\(r + 1\) 个占用空间为 \(2\) 的点，两者取 \(\max\) 即可。于是我们就解决了这道题。
注意代码实现中我的 \(a\) 数组和 \(b\) 数组是反的。
#include
#include
#define int long long
using namespace std;
int n,m,a[300005],b[300005],l,r,ans,truans;
signed main()
{freopen("coin.in","r",stdin);freopen("coin.out","w",stdout);cin >> n >> m;for(int i = 1;i <= n;i ++)cin >> b[i];for(int i = 1;i <= n;i ++)cin >> a[i],a[i] += b[i];sort(a + 1,a + n + 1,greater());sort(b + 1,b + n + 1,greater());for(int i = 1;i <= m;i ++){if(l == n && r == n){truans ^= ans;continue ;}int maxx = 0,L = l,R = r;if(r < n && b[r + 1] > maxx)maxx = b[r + 1],L = l,R = r + 1;if(l < n && r && a[l + 1] - b[r] > maxx)maxx = a[l + 1] - b[r],L = l + 1,R = r - 1;l = L,r = R,ans += maxx;truans ^= ans;}cout << truans;
}
T3
题目大意：你有一个字符串 \(S,T_0\)，保证 \(|T_0| \ge |S|\)。
定义 \(T_i\) 等于 \(T_{a_{i,1}} + T_{a_{i,2}} + ... + T_{a_{i,k_i}} + D_i\)，其中 \(\sum k_i \le 10^6,k_i > 0,\sum |D_i| \le 2 \times 10^6,D_i > 0\)。
对于每个 \(i\) 求 \(S\) 在 \(T_i\) 中出现了多少次。
题目分析：这题真没看懂题解。题解有点难懂了吧。
首先 \(n \le 1000,\sum k_i \le 1000\) 的 \(50 \text{pts}\) 做法。
注意到实际拼接时增加的贡献就是拼接的前面那部分和末尾的那部分，于是直接对每个字符串记录它的前缀和后缀，长度记到 \(|S| - 1\) 即可。然后贡献可以用 KMP 直接求。注意答案还要加上不跨块内的贡献。这样空间和时间复杂度都是 \(\mathcal{O}(n^2)\) 的。下面代码还打了一个全为字符 \(0\) 的特殊性质，因此码量较长。
#include
#define int long long
using namespace std;
string qian[1000005],mo[1000005],s;
int n,nxt[2000005],k,pai;
unsigned int ans[2000005],xian[2000005];
int KMP(string A,string B)
{int N = A.size(),M = B.size(),da = 0;A = " " + A,B = " " + B;nxt[1] = 0;for(int i = 2,j = 0;i <= N;i ++){while(j && A[j + 1] != A[i])j = nxt[j];if(A[j + 1] == A[i])j ++;nxt[i] = j;}for(int i = 1,j = 0;i <= M;i ++){while(j && A[j + 1] != B[i])j = nxt[j];if(A[j + 1] == B[i])j ++;if(j == N){da ++;j = nxt[j];}}return da;
}
string lit;
void update(int i)
{if(qian[i].size() >= s.size())qian[i] = qian[i].substr(0,(int)s.size() - 1);if(mo[i].size() >= s.size())mo[i] = mo[i].substr((int)mo[i].size() - (int)s.size() + 1,(int)s.size() - 1);
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);freopen("string.in","r",stdin);freopen("string.out","w",stdout);//cout << KMP("aba","abaabababba") << " " << KMP("abaabcb","abaabaabcb") << '\n';cin >> n >> s >> mo[0];if(n <= 1000){ans[0] = KMP(s,mo[0]);qian[0] = mo[0];update(0);for(int i = 1;i <= n;i ++){cin >> k;for(int j = 0;j < k;j ++){cin >> pai;ans[i] += ans[pai];string ta = mo[i];ta += qian[pai];ans[i] += KMP(s,ta);mo[i] += mo[pai];qian[i] += qian[pai];update(i);}cin >> lit;qian[i] += lit,mo[i] += lit;ans[i] += KMP(s,mo[i]);update(i);cout << ans[i] << '\n';}return 0;}ans[0] = mo[0].size();xian[0] = (mo[0].size() >= s.size());for(int i = 1;i <= n;i ++){cin >> k;for(int j = 0;j < k;j ++)cin >> pai,ans[i] += ans[pai],xian[i] |= (xian[pai] | (ans[i] >= (unsigned int)s.size()));cin >> lit,ans[i] += (unsigned int)lit.size(),xian[i] |= (ans[i] >= (unsigned int)s.size());if(!xian[i])cout << "0\n";else cout << (unsigned int)(ans[i] - (unsigned int)s.size() + 1) << '\n';}
}
考虑观察性质。首先注意到每个字符串的前缀 \(|T_0|\) 位就等于 \(T_0\)。这是显然的，因为 \(k_i > 0\)。所以我们在算衔接两个字符串的贡献时，后面那个字符串的前缀一定是相同的。于是我们就只用考虑前面那个字符串的后缀加上 \(|T_0|\) 的前 \(|S| - 1\) 位时多造成的贡献。
但是到了这里依然不好求。这需要联想到一点：\(T_i\) 可贡献的后缀一定得是 \(S\) 的前缀，而 \(T_0\) 前缀是 \(S\) 的后缀都是可以求出来的（可以使用 Z 函数来求）。设这些 \(T_0\) 前缀构成集合 \(A\)，那么问题就变成了有几个 \(T_i\) 可贡献的后缀满足既得是 \(S\) 的前缀又要在集合 \(A\) 中。好了这里我就看不懂题解了，它说可以直接 KMP 计算贡献，但我寻思这不是还得 \(\mathcal{O}(n)\) 来计算吗。这到底咋算的。问 AI 也没看懂，但是似乎大家的更正也没更 T3（相同的原因），我就不计较了。
其实罪魁祸首应该是题解不贴代码。代码都没有我咋知道怎么实现啊。
为啥有人 O(n^2) 过了啊。
T4
题目大意：你有一个树高为 \(n\) 的满二叉树，你要往里面放 \(m\) 个点（点有编号，点可以重合），使得每一层都有至少 \(1\) 个点，求方案数对 \(10^9 + 7\) 取模的值。
这题数据范围有两种，一种是 \(n,m \le 2000\)，一种是 \(n \le 20,m = 1145141919\)。
考场上只想到了第二个数据范围的做法。介绍一下我的做法。
我们记 \(f_i\) 表示钦定 \(m\) 个点只在任意 \(i\) 层，且这 \(i\) 层都至少有一个点的方案数。
我们先不考虑后半句话，则 \(f_i = \sum j^m\)，其中 \(j\) 满足性质 \(\text{popcount}(j) = i\)。
然而这些方案中有一些是算重了的，所以我们要减去某个系数乘上 \(f_j\) 才能得到最终答案，其中 \(j < i\)。经过推理得出这个系数等于 \(\dbinom{n - j}{i - j}\)。其实这是根据范德蒙德卷积转化得来的，原本推出的是 \(\dfrac{\binom{n - 1}{i - 1} \times \binom{i - 1}{j - 1}}{\binom{n - 1}{j - 1}}\)。由于我忘记怎么推的了，所以这里先不说明，大家可以自行推导。
按道理来说这里是只有 20pts 的，但是我特判了 \(n > m\) 和 \(n = m\)，这两个情况各有 \(1\) 个点，于是就 \(30\text{pts}\) 了。
#include
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int n,m,f[20005],a[20005] = {0,1},fac[20005] = {1,1},ni[20005],fang[5000005];
int fpow(int x,int y)
{int z = 1;while(y){if(y & 1)z = z * x % mod;x = x * x % mod;y >>= 1;}return z;
}
int C(int x,int y)
{return fac[x] * ni[y] % mod * ni[x - y] % mod;
}
signed main()
{freopen("glass.in","r",stdin);freopen("glass.out","w",stdout);cin >> n >> m;if(n > m){cout << 0;return 0;}for(int i = 2;i <= n;i ++)a[i] = a[i - 1] * 2 % mod,fac[i] = fac[i - 1] * i % mod;if(n == m){int trans = 1;for(int i = 1;i <= n;i ++)trans = trans * a[i] % mod;cout << trans * fac[n] % mod << '\n';return 0;}for(int i = n;i >= 0;i --)ni[i] = fpow(fac[i],mod - 2);for(int i = 0;i < (1 << n);i ++)fang[i] = fpow(i,m);for(int i = 1;i <= n;i ++){for(int j = 0;j < (1 << n);j ++){if(__builtin_popcount(j) != i)continue ;f[i] = (f[i] + fang[j]) % mod;}for(int j = i - 1;j;j --){f[i] -= C(n - 1,i - 1) * C(i - 1,j - 1) % mod * fpow(C(n - 1,j - 1),mod - 2) % mod * f[j] % mod;f[i] %= mod;}f[i] = (f[i] + mod) % mod;}cout << f[n];
}
我们再来说一下 \(\mathcal{O}(nm^2)\) 做法。其实这个方法特别简单但是考场没想到。就是设 \(dp_{i,j}\) 表示考虑前 \(i\) 层放 \(j\) 个点且前 \(i\) 层每层都有点的方案数。转移就是枚举一个 \(k < j\)，然后 \(dp_{i,j}\) 获得 \(dp_{i - 1,k} \times (2^{i - 1})^{j - k} \times \dbinom{j}{k}\) 转移的贡献。\(\dbinom{i}{j}\) 是为了区分结点的先后关系，注意这里请勿写成 \(\dbinom{m - k}{j - k}\)，否则后面很难优化。
注意到此算法三层循环是跑不满的， \(j\) 从 \(i\) 枚举，\(k\) 又从 \(j - 1\) 倒序枚举。故本身其常数就很小。于是考虑乱搞。注意到 \(dp_{i,x}\) 只能通过 \(dp_{i - 1,y}\) 转移，且此时式子转移与 \(m\) 无关，于是我们可以提前做好打表，即先在本地暴力跑完所有 \(dp\) 值，然后令每个 \(i = 210t\)，直接将 \(dp_{i,j}\) 存储在程序里。这样我们后面 dp 时就可以直接令 \(i\) 从 \(\left\lfloor \dfrac{n}{210} \right\rfloor \times 210 + 1\) 开始 dp，于是常数又大幅减小，所以此时最劣复杂度已经来到了小常数 \(\mathcal{T}(210nm)\)，在劣质评测机下也能 700ms 通过。
此题确实是有 \(\mathcal{O}(nm \log m)\) 做法的，但我觉得上面做法真的很美妙啊。学到了学到了。
将两种做法拼一下即可 AC。由于源代码有 90KB，这里就将一些打表结果注释掉了。
#include
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int n,m,f[20005],a[20005] = {0,1},fac[20005] = {1,1},ni[20005],T[2005][2005],fang[5000005];
int dp_210[2005] = {/*打表结果*/};
int dp_420[2005] = {/*打表结果*/};
int dp_630[2005] = {/*打表结果*/};
int dp_840[2005] = {/*打表结果*/};
int dp_1050[2005] = {/*打表结果*/};
int dp_1260[2005] = {/*打表结果*/};
int dp_1470[2005] = {/*打表结果*/};
int dp_1680[2005] = {/*打表结果*/};
int dp_1890[2005] = {/*打表结果*/};
int fpow(int x,int y)
{int z = 1;while(y){if(y & 1)z = z * x % mod;x = x * x % mod;y >>= 1;}return z;
}
int C(int x,int y)
{return fac[x] * ni[y] % mod * ni[x - y] % mod;
}
int dp[2344][2344];
signed main()
{freopen("glass.in","r",stdin);freopen("glass.out","w",stdout);cin >> n >> m;if(n > m){cout << 0;return 0;}for(int i = 2;i <= min(max(n,m),10000LL);i ++)a[i] = a[i - 1] * 2 % mod,fac[i] = fac[i - 1] * i % mod;for(int i = min(max(n,m),10000LL);i >= 0;i --)ni[i] = fpow(fac[i],mod - 2);if(m <= 2000){for(int i = 210;i <= m;i ++)dp[210][i] = dp_210[i - 210];for(int i = 420;i <= m;i ++)dp[420][i] = dp_420[i - 420];for(int i = 630;i <= m;i ++)dp[630][i] = dp_630[i - 630];for(int i = 840;i <= m;i ++)dp[840][i] = dp_840[i - 840];for(int i = 1050;i <= m;i ++)dp[1050][i] = dp_1050[i - 1050];for(int i = 1260;i <= m;i ++)dp[1260][i] = dp_1260[i - 1260];for(int i = 1470;i <= m;i ++)dp[1470][i] = dp_1470[i - 1470];for(int i = 1680;i <= m;i ++)dp[1680][i] = dp_1680[i - 1680];for(int i = 1890;i <= m;i ++)dp[1890][i] = dp_1890[i - 1890];for(int i = 1;i <= n;i ++){T[i][0] = 1;for(int j = 1;j <= m;j ++)T[i][j] = T[i][j - 1] * a[i] % mod;}dp[0][0] = 1;for(int i = n / 210 * 210 + 1;i <= n;i ++)for(int j = i;j <= m;j ++){for(int k = j - 1;k >= i - 1;k --)dp[i][j] = (dp[i][j] + dp[i - 1][k] * T[i][j - k] % mod * C(j,k)) % mod;}cout << dp[n][m] % mod;return 0;}for(int i = 0;i < (1 << n);i ++)fang[i] = fpow(i,m);for(int i = 1;i <= n;i ++){for(int j = 0;j < (1 << n);j ++){if(__builtin_popcount(j) != i)continue ;f[i] = (f[i] + fang[j]) % mod;}for(int j = i - 1;j;j --){f[i] -= C(n - 1,i - 1) * C(i - 1,j - 1) % mod * fpow(C(n - 1,j - 1),mod - 2) % mod * f[j] % mod;f[i] %= mod;}f[i] = (f[i] + mod) % mod;}cout << f[n];
}