CSP-S模拟赛二总结（实际难度大于CSP-S）

T1

很简短，也很好做，第一题直接场切。

我的方法

首先要明确一件事：就是如果选了 $a_{x,y}$，那么就必然要选 $a_{y,x}$，所以第一步就在 $a_{x,y}$ 的基础上加上 $a_{y,x}$。

然后我们把每个数看做一个点，任意两个点之间都建一条边（假想的），那么选集合就相当于在跑团，而每条边的权值就是 $a$，然后就把最大团问题改编一下就行了。

代码：

#include<bits/stdc++.h>
#define int long long
#define code using
#define by namespace
#define plh std
code by plh;
int c,t,n,ed,ans,a[26][26],vis[26];
void dfs(int x,int l)
{if(x>n){ans=max(ans,l);return;}int t=0;for(int i=1;i<x;i++){if(vis[i]){t+=a[i][x];}}vis[x]=1;dfs(x+1,l+t);vis[x]=0;dfs(x+1,l);
}
signed main()
{
//	freopen("party.in","r",stdin);
//	freopen("party.out","w",stdout);cin>>c>>t;while(t--){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<i;j++){int t=a[j][i]+a[i][j];a[i][j]=a[j][i]=t;ans=max(a[i][j],ans);}}dfs(1,0);cout<<ans<<endl;ans=-2e6;}return 0;
}

正解

看到 $n\le 20$，你想到了什么？

看这里。

对了，状压 DP 啊！（虽然我在比赛的时候忘了还有 lowbit 这个东西然后写出了一个 $O(2^n{n}^2)$ 的状压……）

首先定义状态：这一目了然了嘛，就是 $d{p}_s$（$s$ 表示当前的状态），其中 $1$ 表示这个数被选进集合了，$0$ 表示没有。

接着就是写状态转移方程，如果我们直接转移，那就会是 $O(2^n{n}^2)$（外层枚举状态 $O(n^2)$，中间枚举加入集合的点 $O(n)$，内层枚举集合内原本所含有的数与新的数所能构成的距离和 $O(n)$），明显只要是个正常的状压都会 TLE 的好吧，于是我们考虑优化。因为 $O(2^n)$ 是肯定没法优化的，因此考虑优化一个 $O(n)$。

明显，中间那一层枚举要加入的点可以直接优化成 $O(1)$，因为枚举这一层实际上就是在找一个基准来计算，而这个基准又是随机的，因此我们可以直接固定下来：固定成 $\mathrm{lowbit}(s)$（不知道 $\mathrm{lowbit}$ 的同学自己去找资料看看）。于是时间复杂度就被我们优化成了 $O(2^{n}n)$。

但是简单一算就会发现：按照这个时间复杂度写时间复杂度就飙升到 $200000000$ 左右了！还是过不了，于是再考虑优化。

我们先写出当前的状态转移方程：

$$d{p}_s=d{p}_{s\oplus \mathrm{lowbit}(s)}+a$$

后面那个 $a$ 就表示 $\mathrm{lowbit}(s)$ 到每个点的距离和。

很明显，要想再优化，就要把这个 $a$ 预处理出来。

那有没有一种办法，让我们能预处理出 $a$ 呢？啊，有的兄弟，有的。

我们设一个新的 DP：$su{m}_s$，表示在 $s$ 这个状态下 $\mathrm{lowbit}(s)$ 到 $s$ 中的每一个点的距离和，于是我们就可以把这个状态转移方程改进一下：

$$d{p}_s=d{p}_{s\oplus \mathrm{lowbit}(s)}+su{m}_s$$

现在就诞生了一个新的问题：$su{m}_s$ 怎么求？

如果直接求，我们会发现时间复杂度来到了 $O(2^{n}n)$（外面枚举状态，里面枚举 $\mathrm{lowbit}(s)$ 到每个点的距离和），仔细观察容易发现：这个 DP 所需要的循环和上面的 DP 所需要的循环很类似。那我们就采用相同的方法：把动点固定成定点。而 $\mathrm{lowbit}(s)$ 已经被用过了，因此我们换个特殊点：最大的点。我们记做 $\mathrm{upbit}(s)$ 吧。

于是我们就可以写出状态转移方程：

$$su{m}_s=su{m}_{s\oplus \mathrm{upbit}(s)}+g_{\mathrm{lowbit}(s),\mathrm{upbit}(s)}$$

其中 $g$ 表示题中输入的那个数组。

然后就可以快乐的写代码了！

我绝对不会告诉你我没写。

T2

考试时：不是 $k\le 120$ 是什么鬼！？还有那个 $n\le 10^{36}$ 是什么！？这是要弄死人的节奏吗！？

为了您能更好的理解这道题是如何被一步一步想出来的，我们一个数据点一个数据点的讲：

Subtask 1

很简单，翻译下来就是 $x-y=n$，令 $y=1$，于是 $x=n+1$，然后直接输出即可。注意题目中说了 $x,y\le 10^{36}$。

Subtask 2

翻译一下就是 $x^2-y^2=(x+y)(x-y)=n$，现在设 $a=x+y,b=x-y$，则 $x=\frac{a+b}{2},y=\frac{a-b}{2}$，变形一下就是 $a+b=2x,a-b=2y$，因为 $x,y\in \mathbb{Z}$，所以 $2x,2y$ 都是偶数，因此 $a+b,a-b$ 都是偶数，而 $a+b,a-b$ 都是偶数的情况只有两种：

1. $a,b$ 都是奇数。
2. $a,b$ 都是 $4$ 的偶数。

当 $a,b$ 都是奇数时

那么 $ab=n$ 也是一个奇数，这时设 $b=1,a=n$ 可知：$x=\frac{n+1}{2},y=\frac{n-1}{2}$。

当 $a,b$ 都是偶数时

那么 $ab=n$ 就是 $4$ 的倍数，这时设 $b=2,a=\frac{n}{2}$ 可知：$x=\frac{\frac{n}{2}+2}{2},y=\frac{\frac{n}{2}-2}{2}$。

注意：当 $n=1$ 或 $n=4$ 时，不存在两个不同的数 $x,y$ 使得 $x^2-y^2=n$。

Subtask 3

详见 Cubes。

Subtask 4

显然，$x,y\le 10^6$，而 $x^k-y^k$ 具有单调性，双指针一下即可。

Subtask 5

显然在送分，当 $k\ge 3$ 时，$x,y\le 10^{\frac{16}{3}}<10^8$，直接按照 Subtask 4 暴力即可。

Subtask 6

思考一下 Cubes 的做法，就很容易发现这个点的解法：二分。因为特殊性质中给了 $x-y=1$，于是 $x=y+1$，原式就可以被转化为 $(y+1{)}^k-y^k=n$，然后不难证明这个函数是具有单调性的，然后二分 $y$ 即可。

正解

在 Subtask 6 的基础上再深挖：首先我们知道这个式子：

$$x^k-y^k=(x-y)\sum _{i=0}^{k-1}{x}^{k-i-1}{y}^i=(x-y)(x^{k-1}+x^{k-2}y+x^{k-3}{y}^2\cdots +x{y}^{k-2}+y^{k-1})$$

而这个式子等于 $n$，即是说：

$$(x-y)\sum _{i=0}^{k-1}{x}^{k-i-1}{y}^i=n$$

在 Subtask 6 里面说了一个关键信息：$x-y=1$。那这里我们能不能强制性的让 $x-y$ 等于某个数，或者换种方法来说：枚举 $x-y$ 等于多少。

我们来思考一下枚举 $x-y$ 所需要的时间复杂度是多少。因为 $x^k-y^k$ 是一个 $k$ 次式，而 $x-y$ 是一个一次式，所以 $x-y$ 的次数就是 $x^k-y^k$ 的 $\frac{1}{k}$，或者说，是 $n$ 的 $\frac{1}{k}$。

因此我们可知这个式子：$x-y\le n^{\frac{1}{k}}$。

因为题目中有这个条件：$n\le \min (10^{6k},10^{36})$，因此 $n$ 再大也大不过 $10^{6k}$，所以 $n\le 10^{6k}$，所以 $x-y\le n^{\frac{1}{k}}\le 10^{\frac{6k}{k}}=10^6$，诶，可以过！

另一方面：因为 $x-y$ 乘上后面那么大一堆东西等于 $n$，所以它还是 $n$ 的因数。

确定了 $x-y$，然后就可以二分了。

注意：$x^k-y^k$ 不能直接算，因为有可能 $x^k>10^{36},y^k>10^{36}$，但 $x^k-y^k\le 10^{36}$，因此要先转化成上面那个一大坨式子（因为那个式子是两个数相乘，结果只会变大不会变小），再计算它的值。

还有就是中间计算要时刻关注数的大小是否超出了 $10^{36}$，反正细节很多，也很难写。

代码：

#include<bits/stdc++.h>
#define int long long
#define _ __int128
#define code using
#define by namespace
#define plh std
code by plh;
by Plh
{_ read(){_ z = 0, f = 1;char c = getchar();while(c < '0'||c > '9'){if(c == '-') f=-1;c = getchar();}while(c >= '0'&&c <= '9'){z = z * 10 + c - '0';c = getchar();}return z * f;}void write(_ x){if(x < 0){putchar('-');x = -x;}int a[46], top = 0;while(x){a[top++] = x % 10;x /= 10;}while(top) putchar(char(a[--top] + '0'));}
}
code by Plh;
const _ INF = (_)(1e18) * (_)(1e18);
_ k, n, c, t;
bool check(_ x, _ y)
{if(INF / x < y) return true;return false;
}
_ mulcheck(_ x, _ y)
{if(INF / x >= y) return x * y;return INF;
}
_ qpow(_ x, _ y)
{_ z = 1;bool fl = false;while(y){if(y & 1){if(fl||check(z, x)) return INF;else z *= x;}if(check(x, x)) fl=true;else x *= x;y >>= 1;}return z;
}
_ up()
{_ l = 1, r = qpow(10, 36 / k + 1), mid;while(l <= r){mid = l + r >> 1;if(qpow(mid, k)>n) r = mid - 1;else l= mid + 1;}return r + 1;
}
_ calc(_ x, _ y, _ z)
{_ xx = 1, yy = 1, sum = 0;for(int i = 1;i < k;i++){if(check(xx, x)) return INF;else xx *= x;}for(int i = 0;i < k;i++){if(mulcheck(xx, yy) == INF) return INF;sum += mulcheck(xx, yy);if(i == k - 1) break;xx /= x;if(check(yy, y)) return INF;else yy *= y;}if(mulcheck(sum, x - y) == INF) return INF;return mulcheck(sum, x - y);
}
void solve()
{k = read(), n = read();if(k == 1){if(n == INF) puts("-1 -1");else write(n + 1), putchar(' '), write(1), putchar('\n');return;}if(k == 2){if(n == 1||n == 4) puts("-1 -1");else if(n & 1) write((n + 1) >> 1), putchar(' '), write((n - 1) >> 1), putchar('\n');else if((n & 3) == 0) write(((n >> 1) + 2) >> 1), putchar(' '), write(((n >> 1) - 2) >> 1), putchar('\n');else puts("-1 -1");return;}_ m = up();for(int i = 1;i <= m;i++){if(n % i) continue;_ l = 1, r = qpow(10, 36 / (k - 1) + 1), mid, t;while(l <= r){mid = l + r >> 1;t = calc(mid + i, mid, k);if(t == n){write(mid + i),putchar(' '), write(mid), putchar('\n');return;}if(t > n) r = mid - 1;else l = mid + 1;}}puts("-1 -1");return;
}
signed main()
{c = read(), t = read();while(t--) solve();return 0;
}

总之，考试时把 $k=1$ 和 $k=2$ 时的情况写出来了，结果因为 INF 的问题直接爆 0（因为我当时是直接写的 INF=1e36，谁知道它会炸掉啊！！！）。

T3

一道典型的 DP。

说句实话：它不告诉我是 DP，我还真看不出来这是道 DP。

一看题：”最多 $m$ 个杯，最多操作 $w$ 次“。一看到这句话，贪心、二分、DP 中选一个。

贪心肯定不行，因为你找不到贪心策略。二分肯定不行，因为没有单调性。因此这题是 DP。（好牵强的理由……）

首先定义状态：设 $d{p}_{i,j}$ 表示在还剩 $i$ 个玻璃杯、还可以操作 $j$ 的情况下所能测出来的最大楼层，于是就可以写出状态转移方程：

$$d{p}_{i,j}=d{p}_{i-1,j-1}+d{p}_{i,j-1}+1$$

我解释一下：假设我从第 $now$ 层扔了个玻璃杯，如果玻璃杯没碎，那就还剩 $i$ 个玻璃杯、$j-1$ 次操作，而这样我们也得到了 $x>now$ 这个结论（$x$ 的定义和题目中的一样），说明在 $now$ 层上面最多就有 $d{p}_{i,j-1}$ 层。如果玻璃杯碎了，那就还剩 $i-1$ 个玻璃杯、$j-1$ 次操作，同样我们得到了 $x<now$ 这个结论，说明在 $now$ 层下面最多有 $d{p}_{i,j-1}$ 层，再加上 $now$ 这一层可以得到上述状态转移方程。

图示：

但是请注意数据范围：$m\le 10^7,w\le 10^7$。

现在考虑优化。

仔细观察这个状态转移方程：$d{p}_{i,j}=d{p}_{i-1,j-1}+d{p}_{i,j-1}+1$，你有没有觉得有点眼熟？如果没有，请看这个状态转移方程：

$$d{p}_{i,j}=d{p}_{i-1,j-1}+d{p}_{i-1,j}$$

如果到这个份上你都还没看出来，可以选择回炉重造了。

很明显：杨辉三角啊！

由上可推出：$d{p}_{i,j}={\sum }_{k=1}^i{C}_j^k$，证明太简单，这里就不证了。（我绝对不会告诉你我没看懂证明。）

实在想看证明的同学就看一下题解上的证明：

（至少我没看懂……我觉得他应该就是假设它成立了，然后推出来了这样下去后面都成立，就成立了，原版应该是数学归纳法，但题解作者应该太懒了。）

于是就可以快乐的敲代码了。

注意：题目中要对 $998244353$ 取模，而组合计数中有除数，所以还需要提前求一下阶乘逆元。

代码：

#include<bits/stdc++.h>
#define int long long
#define code using
#define by namespace
#define plh std
code by plh;
const int mod=998244353;
int c,t,m,w,ans,fac[10000006],bfac[10000006];
int qpow(int x,int y)
{if(y==0){return 1;}int t=qpow(x,y>>1);if(y&1){return t*t%mod*x%mod;}else{return t*t%mod;}
}
int C(int x,int y)
{if(x<0||y<0||y<x){return 0;}return fac[y]%mod*bfac[y-x]%mod*bfac[x]%mod;
}
signed main()
{fac[0]=1;for(int i=1;i<=10000000;i++){fac[i]=fac[i-1]*i%mod;}bfac[10000000]=qpow(fac[10000000],mod-2);for(int i=9999999;i>=0;i--){bfac[i]=bfac[i+1]*(i+1)%mod;}cin>>c>>t;while(t--){cin>>m>>w;for(int i=1;i<=m;i++){ans=(ans+C(i,w))%mod;}cout<<ans<<endl;ans=0;}return 0;
}

T4

水题，但阴间实现。

首先一看两个水池能互相合并，猜都猜得到是并查集，因此我用一种极其简单的思路写了一个并查集：首先往这个坑所在的大坑里到水，如果要往外溢，就看往哪溢，然后一直模拟就行了。

代码：

#include<bits/stdc++.h>
#define int long long
#define code using
#define by namespace
#define plh std
#define INF	0x3f3f3f3f3f3f3f3f
code by plh;
const int N = 1e6 + 6;
const int mod = 998244353;
int n, q, h[N], wid[N], siz[N], mx[N], inv[N], fa[N];
int find(int x)
{if(x == fa[x]) return x;return fa[x] = find(fa[x]);
}
bool fill(int x, int &y)
{if((mx[x] * wid[x] - siz[x]) >= y){siz[x] += y;y = 0;return 0;}else{y -= (mx[x] * wid[x] - siz[x]);siz[x] = mx[x] * wid[x];return 1;}
}
void merge(int x, int y)
{if(x > y) swap(x,y);int fx = find(x), fy = find(y);if(fx != fy){fa[fy] = fx;wid[fx] += wid[fy];siz[fx] += siz[fy];h[fx] = h[fy];mx[fx] = min(h[fx - 1], h[fx]);}
}
void solve()
{int ans = 0;cin>>n>>q;for(int i = 1;i < n;i++) cin>>h[i];h[0] = h[n] = INF;for(int i = 1;i <= n;i++) fa[i] = i, wid[i] = 1, mx[i] = min(h[i-1], h[i]), siz[i] = 0;while(q--){int op;cin>>op;if(op == 1){int pos, num;cin>>pos>>num;int now = pos;now = find(now);while(num){
//				cout<<num<<'\n';
//				for(int i = 1;i <= n;i++) cout<<siz[i]<<" ";
//				cout<<'\n';if(!fill(now, num)) break;while(h[now - 1] <= h[now]&&num&&fill(now, num)){
//					for(int i = 1;i <= n;i++) cout<<siz[i]<<" ";
//					cout<<'\n';int left = now - 1;left = find(left);if(fill(left, num)){if(mx[left] == mx[now]) merge(left, now);else now = left;}else break;}while(h[now - 1] > h[now]&&num&&fill(now, num)){int right = now + wid[now];right = find(right);if(fill(right, num)){if(mx[now] == mx[right]) merge(now, right);else now = right;}else break;}}
//			for(int i = 1;i <= n;i++) cout<<siz[i]<<" ";
//			cout<<'\n';}else{int pos;cin>>pos;pos = find(pos);ans ^= (siz[pos] % mod * inv[wid[pos]] % mod);}}cout<<ans<<'\n';
}
signed main()
{inv[0] = inv[1] = 1;for(int i = 2;i < N;i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;int c, t;cin>>c>>t;while(t--) solve();return 0;
}
/*
0 1
5 7
1 3 4 2
1 1 3
2 2
1 2 8
2 2
1 5 5
2 4
2 5
*/

然后完美的 TLE 了……

原因：仔细一算时间复杂度：$O(qn\alpha (n))$，其中这个 $\alpha (n)$ 是个常数，但是很明显这个常数极大。因为我是一位一位移的，所以耗时自然很大。

那既然问题出在了移动这里，那我们就用一个数组记录下当前这个水槽能到的最远的水槽在哪。然后这个题就 AC 了……

注意：细节很多，而且代码很难写，注意看注释。

#include<bits/stdc++.h>
#define int long long
#define code using
#define by namespace
#define plh std
#define INF	LONG_LONG_MAX
code by plh;
by fastio
{int read(){int z = 0, f = 1;char c = getchar();while(c < '0'||c > '9'){if(c == '-') f = -1;c = getchar();}while(c >= '0'&&c <= '9'){z = z * 10 + c - '0';c = getchar();}return z * f;}void write(int x){if(x < 0){putchar('-');x=-x;}int top = 0,a[16];while(x){a[top++] = x % 10;x /= 10;}while(top) putchar(char(a[--top] + '0'));}
}
code by fastio;
const int N = 1e6 + 6;
const int mod = 998244353;
int n, q, pos, num, op, ans, now, tmp, tag, h[N], wid[N], siz[N], mx[N], inv[N], lft[N], rgt[N], fa[N];
int find(int x, int *fa)
{if(x == fa[x]) return x;return fa[x] = find(fa[x], fa);
}
bool cmp(int x, int y)
{if(y == INF) return false;//高度无限，根本填不满x = find(x, fa);return siz[x] >= wid[x] * y;//我的水量是否大于等于最大水量
}
void merge(int x, int y)
{if(x > y) swap(x,y);//以小的为根if(x < 1||x > n||y < 1||y > n) return;//是否满足条件x = find(x, fa), y = find(y, fa);if(x == y||x + wid[x] != y||!wid[x]||!wid[y]) return;//这两个点已经连在一起？两个点不相邻？已经有一个点连到其他连通块中了？if(!cmp(x, h[y - 1])||!cmp(y,h[y - 1])) return;//两边的水还没满了？fa[y] = x, wid[x] += wid[y], siz[x] += siz[y];//合并 if(min(h[x - 1], h[x + wid[x] - 1]) == INF) mx[x] = INF;else mx[x] = min(h[x - 1], h[x + wid[x] - 1]) * wid[x];siz[y] = wid[y] = mx[y] = 0;return;
}
bool fill(int x, int &y)
{x = find(x, fa), tmp = x + wid[x];if(!y||siz[x] == mx[x]) return false;if(mx[x] - siz[x] <= y)//如果倒不完 {y -= mx[x] - siz[x];//先倒 siz[x] = mx[x];merge(x, x - 1);//然后看看左右有没有和自己一样满了的可以合并 merge(x, tmp);}else siz[x] += y, y = 0;//反之直接倒 return y&&siz[x] != mx[x];//如果有水且还能倒就继续倒 
}
void solve()
{ans = 0;n = read(), q = read();for(int i = 1;i < n;i++) h[i] = read();h[0] = h[n] = INF;for(int i = 1;i <= n;i++) lft[i] = rgt[i] = fa[i] = i, wid[i] = 1, mx[i] = min(h[i - 1], h[i]), siz[i] = 0;while(q--){op=read();if(op == 1){pos = read(), num = read();while(num){now = pos;while(fill(now, num));//尽可能的往里面倒水while(cmp(now, h[now - 1])&&num)//倒过了但还有水且我已经倒满了，则先尽可能往左边倒{if(lft[now] == now) lft[now] = now - 1, now--;//如果我都被倒满了但我原本没往左溢，那我现在就可以往左溢了并记录下来我往左溢到了哪else now = find(now, lft);//否则找我可以向左最远可以溢到哪if(now < 1) break;//跑出去了，也就是跑到最左边了while(fill(now, num));//继续在最左边加水}tag = h[now - 1];now = pos;while(fill(now, num));//尽可能的往里面倒水while(cmp(now, h[now])&&!cmp(now, tag)&&num)//倒过了但还有水且我已经倒满了且我最左边的高度比最右边的高度高，则再往右倒{if(rgt[now] == now) rgt[now] = now + 1, now++;//如果我都被倒满了但我原本没往右溢，那我现在就可以往右溢了并记录下来我往右溢到了哪else now = find(now, rgt);//否则找我可以向右最远可以溢到哪if(now > n) break;//跑出去了，也就是跑到最右边了while(fill(now, num));//继续在最右边加水}}}else{pos = read();find(pos, fa);ans ^= (siz[fa[pos]] % mod * inv[wid[fa[pos]]] % mod);}}if(ans == 0) putchar('0');write(ans);putchar('\n');return;
}
signed main()
{inv[0] = inv[1] = 1;for(int i = 2;i <= 1000000;i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;int c, t;c=read(), t=read();while(t--) solve();return 0;
}
/*
0 1
5 7
1 3 4 2
1 1 3
2 2
1 2 8
2 2
1 5 5
2 4
2 5
*/

总结

• T1：打卡题，很容易想到正解。
• T2：简单题，但阴间实现，而且代码很难写，细节特别多。
• T3：有难度，主要是完全看不出来是个 DP，还有就是结论很难想到。
• T4：简单题，但阴间实现，代码难写，细节多。

上周考的题，到昨天才改完，代码实在是太难写了，还希望各位能点个赞，谢谢。