\(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;
}