$CSP$ $2019$ $Day2$ 模拟考试 题解报告

目录

\(CSP\) \(2019\) \(Day2\) 模拟考试 题解报告

得分情况

\(T1\) \(100\ Pts\) (做过)

\(T2\) \(8\ Pts\)

\(T3\) \(0\ Pts\)

总分: \(108\ Pts\)

考试过程

\(T1\) 开始做 先把 \(84\) 的写完 跑路

看了一下 \(T2\) 看到小数据 写了个爆搜 感觉是 \(dp\) 但是没写

转 \(T3\) 想写暴力写不出来 看到一个链的特殊情况 推了一个假结论 满二叉树的情况推不出来 跑路

回 \(T1\) 把剩下分的写完 转 \(T2\) \(dp\) 推假 凄惨爆蛋

题解

\(T1\) Emiya 家今天的饭

容斥

答案为 每行选一个数的方案数减去每行选一个 有一行超过总数的一半的方案数

一定只有一列超过总数的一半 直接枚举 设为 \(p\)

状态 \(f_{i, j, k}\) 表示前 \(i\) 行 当前枚举列选择了 \(j\) 个数 其他列选择了 \(k\) 个数的方案数

\(g_{i, j}\) 表示前 \(i\) 行选 \(j\) 个的方案数

设 \(s_i = \sum_{j = 1}^m a_{i, j}\)

转移 $$f_{i, j, k} = \sum_{j = 0}^i \sum_{k = 0}^i \left(f_{i - 1, j, k} + f_{i - 1, j - 1, k} \times a_{i, p} + f_{i - 1, j, k - 1} \times \left(s_i - a_{i, p}\right)\right)$$

其中 \(j + k \leq i\)

\[g_{i, j} = \sum_{j = 0}^i \left(g_{i - 1, j} + g_{i - 1, j - 1} \times s_i\right) \]

答案为 $$\sum_{j = 1}^n g_{n, j} - \sum_{p = 1}^m \sum_{j = 0}^n \sum_{k = 0}^{j - 1} f_{n, j, k}$$

对 \(p\) 直接在循环内统计 同样 \(j + k \leq n\)

显然 复杂度 \(O(mn^3)\) 可以通过 \(84\ Pts\)

这一部分的代码

/*
  Time: 5.16
  Worker: Blank_space
  Source: P5664 [CSP-S2019] Emiya 家今天的饭
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#define int long long
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
int n, m, a[110][2021], g[110][110], s[110], f[110][110][110], sum, ans;
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/

/*----------------------------------------函数*/
signed main() {
	n = read(); m = read(); g[0][0] = 1; f[0][0][0] = 1;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) a[i][j] = read(), s[i] += a[i][j];
	for(int i = 1; i <= n; i++) for(int j = 0; j <= i; j++) g[i][j] = (g[i][j] + g[i - 1][j] + (j > 0) * s[i] * g[i - 1][j - 1]) % mod;
	for(int j = 1; j <= n; j++) ans = (ans + g[n][j]) % mod;
	for(int p = 1; p <= m; p++, memset(f, 0, sizeof f), f[0][0][0] = 1)
	{
		for(int i = 1; i <= n; i++) for(int j = 0; j <= i; j++) for(int k = 0; k + j <= i; k++)
			f[i][j][k] = (f[i][j][k] + f[i - 1][j][k] + a[i][p] * (j > 0) * f[i - 1][j - 1][k] % mod + (s[i] - a[i][p]) * (k > 0) * f[i - 1][j][k - 1] % mod) % mod;
		for(int j = 0; j <= n; j++) for(int k = 0; k + j <= n && k < j; k++) sum = (sum + f[n][j][k]) % mod;
	}
	printf("%lld", (ans - sum + mod) % mod);
	return 0;
}

考虑优化

对于 \(f\) 的转移 与 \(j\) 与 \(k\) 的大小无关 设 \(f_{i, j}\) 表示前 \(i\) 行 当前列比其他列多 \(j\) 个的方案数

转移 $$f_{i, j} = \sum_{j = n - i}^{n + i}\left(f_{i - 1, j} + f_{i - 1, j - 1} \times a_{i, p} + f_{i - 1, j + 1} \times \left(s_i - a_{i, p}\right)\right)$$

复杂度 \(O(mn^2)\) 可以通过

代码

/*
  Time: 5.28
  Worker: Blank_space
  Source:
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#define int long long
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
int n, m, a[110][2021], s[110], g[110][2021], f[110][210], ans, sum;
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/

/*----------------------------------------函数*/
signed main() {
	freopen("meal.in","r",stdin);
	freopen("meal.out","w",stdout);

    n = read(); m = read(); g[0][0] = 1; f[0][n] = 1;//防止越界 
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) a[i][j] = read(), s[i] = (s[i] + a[i][j]) % mod;
    for(int i = 1; i <= n; i++) for(int j = 0; j <= i; j++) g[i][j] = (g[i][j] + g[i - 1][j] + (j > 0) * g[i - 1][j - 1] * s[i] % mod) % mod;
    for(int j = 1; j <= n; j++) ans = (ans + g[n][j]) % mod;
    for(int p = 1; p <= m; p++, memset(f, 0, sizeof f), f[0][n] = 1) 
    {
    	for(int i = 1; i <= n; i++) for(int j = n - i; j <= n + i; j++)
    		f[i][j] = (f[i][j] + f[i - 1][j] + (j > 0) * f[i - 1][j - 1] * a[i][p] % mod + f[i - 1][j + 1] * (s[i] - a[i][p]) % mod) % mod;
    	for(int j = n + 1; j <= n << 1; j++) sum = (sum + f[n][j]) % mod;
    }
    printf("%lld", (ans - sum + mod) % mod);
    
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
2 3
1 0 1
0 1 1

3 3
1 2 3
4 5 0
6 0 0


*/

\(T2\) 划分

\(ps\) : 赛后 一旁的 \(zxs\) 表示这不就是个数的划分的加强版 不随便写一个 \(dp\) 就有六十多分 闻言 我只能在一边疯狂膜拜

其实做的时候看了一下第三个样例 我就感觉这题不对劲 高精一如既往的恶心

由完全平方公式: \(\left(a + b\right)^2 \geq a^2 + b^2\) 所以多分段一定会更优

状态: \(f_i\) 表示以 \(i\) 结尾 前面分为若干段(一定是尽量多分)的最小代价

以 \(s\) 数组表示前缀和 转移的同时维护一个 \(g\) 数组 记录上一个转移的位置

转移: \(f_i = \min\{f_j + (s_i - s_j)^2 \}\)

转移的条件是 \(s_i - s_j \geq s_j - s_{g_j}\) 且 \(f_j + (s_i - s_j)^2 < f_i\)

通过枚举 \(j\) 每次转移是 \(O(n)\) 的

总复杂度 \(O(n^2)\)

期望得分 \(64\ Pts\)

实际得分 \(64\ Pts\)

考虑优化

观察转移条件: \(s_i - s_j \geq s_j - s_{g_j}\)

移项: \(s_i \geq 2s_j - s_{g_j}\)

那么如果有 \(j\) 与 \(k\) 两个决策点 都可以转移到 \(i\) 若是 \(k \leq j\) 因为分段越多答案越优 所以 \(k\) 这个点就没有用了 这样就可以通过单调队列进行优化

当一个元素的下一个元素仍然满足 \(\geq s_i\) 这一条件时 那么这个元素就可以出队了

当有一个新的决策点时 维护队列单调递增

这样可以将转移优化到 \(O(1)\)

总时间复杂度 \(O(n)\)

期望得分 \(100\ Pts\)

实际得分 \(88\ Pts\)

后三个数据点的数据过大 炸掉了 \(long\ long\)

代码

/*
  Time: 5.28
  Worker: Blank_space
  Source:
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#define int long long
/*--------------------------------------头文件*/
const int M = 1e8;
const int B = 1e5 + 7;
const int D = 1e7 + 7;
const int mod = 1 << 30;
const int INF = 1e18;
/*------------------------------------常量定义*/
int m, n, type, a[D << 2], s[D << 2], ans = INF, f[D << 2], g[D << 2], q[D << 2], l, r;
int _p[B], _l[B], _r[B], b[D << 2];
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int x) {if(x > 9) print(x / 10); putchar(x % 10 ^ 48);}
/*----------------------------------------快读*/

/*----------------------------------------函数*/
signed main() {
//	freopen("partition.in","r",stdin);
//	freopen("partition.out","w",stdout);

    n = read(); type = read();
    if(type == 0) for(int i = 1; i <= n; i++) s[i] = s[i - 1] + read();
    else {
    	int x = read(), y = read(), z = read(); b[1] = read(), b[2] = read(), m = read();
    	for(int i = 1; i <= m; i++) _p[i] = read(), _l[i] = read(), _r[i] = read();
    	for(int i = 3; i <= n; i++) b[i] = (b[i - 1] * x + b[i - 2] * y + z) % mod;
    	for(int j = 1; j <= m; j++) for(int i = _p[j - 1] + 1; i <= _p[j]; i++) a[i] = (b[i] % (_r[j] - _l[j] + 1)) + _l[j], s[i] = s[i - 1] + a[i];
    }
    memset(f, 63, sizeof f); f[0] = 0; g[0] = 0; q[l = r = 0] = 0;
    for(int i = 1; i <= n; i++)
    {
    	while(l < r && s[i] - s[q[l + 1]] >= s[q[l + 1]] - s[g[q[l + 1]]]) l++;
    	f[i] = f[q[l]] + (s[i] - s[q[l]]) * (s[i] - s[q[l]]); g[i] = q[l];
    	while(l < r && 2 * s[q[r]] - s[g[q[r]]] >= 2 * s[i] - s[g[i]]) r--;
		q[++r] = i;
    }
    print(f[n]);
    
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

可以直接开 \(\_\_int128\) 强过 时间复杂度是不变的

也可以选择写高精

\(\_\_128\) \(AC\) 代码

/*
  Time: 5.30
  Worker: Blank_space
  Source:
*/
/*--------------------------------------------*/
#include<cstdio>
#include<iostream>
#define int long long
#define ll __int128
/*--------------------------------------头文件*/
const int M = 1e8;
const int B = 1e5 + 7;
const int D = 1e7 + 7;
const int mod = 1 << 30;
const int INF = 1e18;
/*------------------------------------常量定义*/
int m, n, _p, type, s[D << 2], g[D << 2], q[D << 2], l, r, tmp;
ll ans = 0;
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(ll x) {if(x > 9) print(x / 10); putchar(x % 10 ^ 48);}
/*----------------------------------------快读*/

/*----------------------------------------函数*/
signed main() {
//	freopen("partition.in","r",stdin);
//	freopen("partition.out","w",stdout);

    n = read(); type = read();
    if(type == 0) for(int i = 1; i <= n; i++) s[i] = s[i - 1] + read();
    else {
    	int x = read(), y = read(), z = read(), b1 = read(), b2 = read(), m = read();
    	for(int j = 1; j <= m; j++)
    	{
    		int p = read(), _l = read(), _r = read();
    		for(int i = _p + 1; i <= p; i++)
    			if(i == 1) s[i] = b1 % (_r - _l + 1) + _l;
    			else s[i] = b2 % (_r - _l + 1) + _l, tmp = (b2 * x + b1 * y + z) % mod, b1 = b2, b2 = tmp;
    		_p = p;
    	}
    	for(int i = 1; i <= n; i++) s[i] += s[i - 1];
    }
    q[l = r = 0] = 0;
    for(int i = 1; i <= n; i++)
    {
    	while(l < r && s[i] - s[q[l + 1]] >= s[q[l + 1]] - s[g[q[l + 1]]]) l++;
    	g[i] = q[l];
    	while(l < r && 2 * s[q[r]] - s[g[q[r]]] >= 2 * s[i] - s[g[i]]) r--;
		q[++r] = i;
    }
    for(int i = n; i; i = g[i]) ans += (ll)(s[i] - s[g[i]]) * (s[i] - s[g[i]]);
    print(ans);
    
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

高精度比较恶心 这个题卡时间还卡空间

自己写完后调了接近半个小时 改了很多地方 但是由于常数过大 不开 \(O2\) 的情况下依然只有 \(88\ Pts\) 吸氧可以过

不知道题解里面有没有用高精过的代码 大多数都是直接用 \(\_\_128\) 水过去了

高精代码

/*
  Time: 5.30
  Worker: Blank_space
  Source:
*/
/*--------------------------------------------*/
#include<cstdio>
#define ll long long
#define Max(x, y) ((x) > (y) ? (x) : (y))
/*--------------------------------------头文件*/
const int M = 1e8;
const int B = 1e5 + 7;
const int D = 1e7 + 7;
const int mod = (1 << 30) - 1;
const int INF = 1e18;
/*------------------------------------常量定义*/
int m, n, _p, type, g[D << 2], q[D << 2], l, r, tmp;
ll s[D << 2];
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void W(ll x) {if(x > 9) W(x / 10); putchar(x % 10 ^ 48);}
/*----------------------------------------快读*/
struct node {
	ll a[6];
	int len;
	node() {for(int i = 0; i <= 5; i++) a[i] = 0; len = 1;}
	void print() {
		printf("%lld", a[len]);
		for(int i = len - 1; i; i--) printf("%08lld", a[i]);
		puts("");
	}
} ans;
node operator + (node x, ll y) {
	for(int i = 1; i <= 5 && y; i++)
	{
		x.a[i] += y % M; y /= M;
		y += x.a[i] / M; x.a[i] %= M;
	}
	while(x.a[x.len + 1]) x.len++;
	return x;
}
node operator * (node x, node y) {
	node z; z.len = x.len + y.len;
	for(int i = 1; i <= x.len; i++) for(int j = 1; j <= y.len; j++)
		z.a[i + j - 1] += x.a[i] * y.a[j];
	for(int i = 1; i <= z.len; i++) z.a[i + 1] += z.a[i] / M, z.a[i] %= M;
	while(!z.a[z.len] && z.len > 1) z.len--;
	return z;
}
node operator & (node x, node y) {
	node z; z.len = Max(x.len, y.len); ll t = 0;
	for(int i = 1; i <= z.len; i++)
	{
		z.a[i] = x.a[i] + y.a[i] + t;
		t = z.a[i] / M; z.a[i] %= M;
	}
	if(t) z.a[++z.len] = t;
	return z;
}
/*----------------------------------------函数*/
signed main() {
//	freopen("partition.in","r",stdin);
//	freopen("partition.out","w",stdout);

    n = read(); type = read();
    if(type == 0) for(int i = 1; i <= n; i++) s[i] = s[i - 1] + read();
    else {
    	int x = read(), y = read(), z = read(), b1 = read(), b2 = read(), m = read();
    	for(int j = 1; j <= m; j++)
    	{
    		int p = read(), _l = read(), _r = read();
    		for(int i = _p + 1; i <= p; i++)
    			if(i == 1) s[i] = b1 % (_r - _l + 1) + _l;
    			else s[i] = b2 % (_r - _l + 1) + _l, tmp = (b2 * x + b1 * y + z) & mod, b1 = b2, b2 = tmp;
    		_p = p;
    	}
    	for(int i = 1; i <= n; i++) s[i] += s[i - 1];
    }
    q[l = r = 0] = 0;
    for(int i = 1; i <= n; i++)
    {
    	while(l < r && s[i] - s[q[l + 1]] >= s[q[l + 1]] - s[g[q[l + 1]]]) l++;
    	g[i] = q[l];
    	while(l < r && 2 * s[q[r]] - s[g[q[r]]] >= 2 * s[i] - s[g[i]]) r--;
		q[++r] = i;
    }
    for(int i = n; i; i = g[i])
	{
		node d;
		d = d + (s[i] - s[g[i]]);
		ans = d * d & ans;
	}
    ans.print();
    
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

\(T3\) 树的重心

上一篇:Educational Codeforces Round 110


下一篇:topsort习题1