The Third Test/The Last Test
死亡回放 比赛时间线
- 在 8:30 之前直接把
T2 造城墙的程序给写了（感谢老师透题 - 8:30 因为 ftp 炸了比赛缩水 15\text{min}
- 8:45 ftp 恢复，测试开始
- 开考看了眼
T1 黑白染色，不太会，跳到T3 炸鸡 - yee，这不就是个裸的二分答案吗？
- 约 9:10 写完第一版代码，小样例都没问题但大样例死的干干净净
- 意识到复杂度不对，开始想办法优化
- 约 9:40 想到了优化的办法并写了第二版，大样例从炸完变成了 2\text{s} 勉强跑出来
- 约 10:10 开始各种的加快读，终于放弃去打
T1 黑白染色 - 看出第一题是个数学题，果断选择暴力
懒得推式子 - 本来想打最暴力的做法，想了想觉得这玩意又臭又长，开始想办法优化
- 约 10:40 想出了一个蛮对的做法
- 约 11:20 小样例能过但是大样例爆栈了，就想着当个暴力骗分了
- 此时看到
T4 骑士与国王，感觉很疲惫就打了个骗分代码 —— 全场最错误的选择！ - 然后开始着手优化
T3 炸鸡 - 此时旁边的 zyx 问我我
T3 炸鸡复杂度 - 然后他说他的大样例跑不过但是跑得飞快
- 我就给他讲了一种很对的贪心思路，他顺利过掉了这题
- 此时我突然悟了！我知道我为什么复杂度没问题但是炸了！
- 约 11:50 我兴奋地准备改我的代码！此时有个
byd踩了一脚电源线！ - 电脑
tmd全部重启了！！！！！！！ - 老师还没多给时间！
于是他过了，我挂了 qwq
死因分析 错误点分析
- 那个
byd给电源线干炸了！ T2 造城墙懒了一下少了一个特判然后挂了两个点！T4 骑士与国王没有去打暴力！
死亡证明 成绩
遗书 各题错误思路 & 正解
T1 黑白染色
给定一个 n\times m 的矩阵，现在要在上面放一些点
使得这个矩阵的每一个 n\times n 的子方阵都有恰好k个点
求方案数对 10^9+7 取模。两个方案不同当且仅当某个位置是否放置点的状态是不同的。
输入格式：
从文件 discolour.in 中读入数据
输入共一行，三个整数 n,m,k .
输出格式：
输出到文件 discolour.out 中。
输出共一行，输出一个整数。
输入样例：
5 6 1
输出样例：
45
输入样例：
3 23 4
输出样例：
501309660
对于20%的数据，n<=2,m<=10
对于40%的数据，n<=5,m<=200
对于60%的数据，n<=10,m<=10000
对于另外20%的数据，k<=5
对于100%的数据，n<=100,m<=10^18,0<=k<=n^2
错误思路
-
可以发现当第一个 n\times n 的点选好之后，后面每一列的点数就确定了
-
然后就先暴力枚举第一个 n\times n 的矩阵的每一列的点数，然后一个一个用组合数计算最终答案
-
这样会爆栈，可以拿
Runtime Error 40#include<bits/stdc++.h> #define ll long long #define int ll using namespace std; const int maxn = 100005, P = 1e9 + 7; int n,m,k,a[maxn],C[105][maxn]; ll ans; void dfs(int pos,int tot,ll sum) { if (pos > m && tot == k) { ans = (ans + sum) % P; return ; } if (pos <= n && tot > k) return ; if (pos > n && tot != k) return ; if (pos <= n) for (int i = 0;i <= k - tot;i ++) { a[pos] = i; dfs(pos + 1,tot + i,(sum * C[n][i]) % P); } else { tot -= a[pos - n], a[pos] = k - tot; dfs(pos + 1,k,(sum * C[n][k - tot]) % P); } } signed main() { freopen("discolour.in","r",stdin); freopen("discolour.out","w",stdout); scanf("%lld%lld%lld",&n,&m,&k); C[0][0] = 1; for (int i = 1;i <= n;i ++) C[i][0] = C[i][i] = 1; for (int i = 1;i <= n;i ++) for (int j = 1;j <= k;j ++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P; if (n > m) { putchar('0'); return 0; } dfs(1,0,1); printf("%lld",ans); }
正解
-
需要推一下式子，具体看代码吧
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 105; const int P = 1e9 + 7; ll C[maxn][maxn], f[maxn][maxn * maxn], g[maxn][maxn], m; int n,k; inline ll qp(ll x, ll y) { ll ans = 1; while (y) { if (y & 1) ans = ans * x % P; x = x * x % P; y >>= 1; } return ans; } int main() { // freopen("discolour.in", "r", stdin); // freopen("discolour.out", "w", stdout); scanf("%d%lld%d", &n, &m, &k); f[0][0] = C[0][0] = 1; for (int i = 1;i <= 100;i ++) { C[i][0] = 1; for (int j = 1;j <= i;j ++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P; } for (int i = 1;i <= n;i ++) for(int j = 0;j <= n;j ++) g[i][j] = qp(C[n][j], (m - (ll)i) / (ll)n + 1); for (int i = 1;i <= n;i ++) for(int j = 0;j <= min(k, i * n);j ++) for (int t = 0;t <= min(j,n);t ++) f[i][j] = (f[i][j] + f[i - 1][j - t] * g[i][t]) % P; printf("%lld\n", f[n][k]); return 0; }
T2 造城墙
题目描述
小A要建造一个长为N高为M的墙，现在每一列只有最下方有若干砖头。
小A只有1*2一种形状的砖头（可以横着或者竖着），给出每一列下方的砖头数量。
问小A还能否建造出一个完整的墙。
输入格式
从文件 wall.in 中读入数据。
第一行一个数T表示数据组数。
每组数据第一行两个数N,M
之后N行每行一个[0,M]之间的整数表示这个位置的高度
输出格式
输出到文件 wall.out 中。
对于每组数据输出possible（如果可行），否则输出impossible。
输入样例
2
6 3 1 0 1 1 0 1
6 2 1 0 1 1 0 1
输出样例
possible
impossible
数据规模
对于40%的数据，保证m<=5
对于另外20%的数据，保证n,m<=100
对于100%的数据，保证n<=100000,m<=1000000,T<=10
数据很弱，欢迎骗分
错误思路
-
我们有一个构造策略：能摆竖着的就摆竖着的
-
对于每一列，如果这一列的空格子是奇数就说明需要从前后两列中选一列借一个格子摆一条横着的
-
这个画一画图就知道了
-
所以我们记录一个 tot 表示当前有几个格子需要借格子来放下一个横着的砖块，如果当前的空格子数减去 tot 是奇数（即把格子借给前一列，自己也需要借）则 tot=tot + 1
-
否则 tot = tot - 1 （即可以容纳下前一列需要借的格子）
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int n,m,a[maxn],tot,T; bool ok; int main() { freopen("wall.in","r",stdin); freopen("wall.out","w",stdout); scanf("%d",&T); while (T --) { scanf("%d%d",&n,&m); tot = 0, ok = true; for (int i = 1;i <= n;i ++) scanf("%d",&a[i]); for (int i = 1;i <= n;i ++) { a[i] = m - a[i]; if (a[i] - tot < 0) { ok = false; break; } if ((a[i] - tot) & 1) tot ++; else tot --; if (tot > m) { ok = false; break; } } if (tot == 0 && ok) printf("possible\n"); else printf("impossible\n"); } return 0; }
正解
-
就是加个小特判就能
WA 80\toAC 100#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int n,m,a[maxn],tot,T; bool ok; int main() { freopen("wall.in","r",stdin); freopen("wall.out","w",stdout); scanf("%d",&T); while (T --) { scanf("%d%d",&n,&m); tot = 0, ok = true; for (int i = 1;i <= n;i ++) scanf("%d",&a[i]); for (int i = 1;i <= n;i ++) { a[i] = m - a[i]; if (tot == 0 && !(a[i] & 1)) continue; // 特判没有需要借的情况 if (a[i] - tot < 0) { ok = false; break; } if ((a[i] - tot) & 1) tot ++; else tot --; if (tot > m) { ok = false; break; } } if (tot == 0 && ok) printf("possible\n"); else printf("impossible\n"); } return 0; }
T3 炸鸡
题面描述
肯德基的网红产品炸鸡需要油锅进行生产，这个厨房内，每个锅可以花费x的时间产出一份炸鸡，之后花费z的时间洗锅换油并可以重新投入生产。每个炸鸡产出之后可以放置至多y的时间否则必须扔掉。
一共会有n个时刻。在第 t_i 个时刻厨房会得到一个订单，要求$a_i$份炸鸡，给出所有的 a_i ，请问厨房最少需要多少个锅才可以满足所有的订单。 n≤5000 $t_i,a_i$≤10^9 x,y,z≤10^9 你可以在0时刻以前就开始准备煎饼 同时保证y<x，即每份炸鸡可保存时间不超过制作时间
输入格式
从文件 chicken.in 中读入数据。
输入第一行四个数n,x,y,z，之后每行两个数t**i,a**i
输出格式
输出到文件 chicken.out 中。
输出一行表示需要的锅的最小数量
样例输入
6 100 40 70 10 1 100 2 210 3 320 4 440 5 560 6
样例输出
11
数据规模
对于10%的数据，保证n<=10
对于50%的数据，保证n<=200
对于80%的数据，保证n<=2000
对于100%的数据，保证n<=5000
错误思路
-
一眼二分 + 堆
-
用堆记录每个锅当前要在哪个时刻才可以继续用
-
最开始我把所有的锅逐个扔进堆里就炸了
-
后来想到可以把同时刻的锅合在一起扔
-
然后就写完了
#include<bits/stdc++.h> #define type pair<int,int> #define mk make_pair #define int long long using namespace std; const int maxn = 5005; int n,x,y,z,ans; int t[maxn],a[maxn],aa[maxn]; int read() { char c = getchar(); int res = 0; while (c < '0' && c > '9') c = getchar(); while (c >= '0' && c <= '9') res = (res << 1) + (res << 3) + (c ^ 48), c = getchar(); return res; } bool check(int m) { priority_queue<type,vector<type>,greater<type> > q; q.push(mk(-1e18,m)); for (int i = 1,now;i <= n;i ++) { now = aa[i]; while (now > 0 && !q.empty()) { type g = q.top(); if (g.first + x > t[i] && now > 0) break; q.pop(); if (now < g.second) { q.push(mk(g.first,g.second - now)); q.push(mk(max(t[i] - y + z,g.first + x + z),now)); now = 0; } else { q.push(mk(max(t[i] - y + z,g.first + x + z),g.second)); now -= g.second; } } if (now > 0) return false; } return true; } signed main() { freopen("chicken.in","r",stdin); freopen("chicken.out","w",stdout); n = read(), x = read(), y = read(), z = read(); int l = 0,r = 0; for (int i = 1;i <= n;i ++) { t[i] = read(), aa[i] = read(); r += aa[i]; } while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) ans = mid, r = mid - 1; else l = mid + 1; } printf("%lld",ans); }
正解
-
也是稍微改一下就能
TLE 60\toAC 100 -
zyx 过了，我挂了#include<bits/stdc++.h> #define type pair<int,int> #define mk make_pair #define int long long using namespace std; const int maxn = 5005; int n,x,y,z,ans; int t[maxn],a[maxn],aa[maxn]; int read() { char c = getchar(); int res = 0; while (c < '0' && c > '9') c = getchar(); while (c >= '0' && c <= '9') res = (res << 1) + (res << 3) + (c ^ 48), c = getchar(); return res; } bool check(int m) { priority_queue<type,vector<type>,greater<type> > q; q.push(mk(-1e18,m)); for (int i = 1,now;i <= n;i ++) { now = aa[i]; while (now > 0 && !q.empty()) { type g = q.top(); if (g.first > t[i] + y && now > 0) break; q.pop(); // 因为每份炸鸡都有 y 的保质期，所以限制可以放宽 if (now < g.second) { q.push(mk(g.first,g.second - now)); // 没有用过的 now = 0; } else now -= g.second; } if (now > 0) return false; q.push(mk(t[i] + x + z,aa[i])); // TLE的原因就是我把很多用时相同的分成了好几部分扔进了队列里 } return true; } signed main() { freopen("chicken.in","r",stdin); freopen("chicken.out","w",stdout); n = read(), x = read(), y = read(), z = read(); int l = 0,r = 0; for (int i = 1;i <= n;i ++) { t[i] = read(), aa[i] = read(); r += aa[i]; } while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) ans = mid, r = mid - 1; else l = mid + 1; } printf("%lld",ans); }
T4 国王与骑士
题目描述
王国中有n个骑士和k个俱乐部。并不是每个骑士都在俱乐部中。
俱乐部的影响力有着严格的高低关系，第一个俱乐部有k1个骑士，影响力最大；第二个俱乐部有k2个骑士，影响力次大，以此类推。
现在国王准备给这n个骑士一个排名，但作为大臣你知道如果第一个俱乐部中的k1个骑士处在最后k1个位置，则作为最强的俱乐部他们会开始造反。同理如果第一个和第二个俱乐部中的k1+k2个骑士处在最后k1+k2个位置，他们也会联合起来造反。需要注意的是，如果只有k2这些骑士在最后k2这些位置是不会出现问题的，因为他们俱乐部的影响力不够反抗国王。依次类推，如果前m个俱乐部的k1+…+k**m个骑士全部在最后k1+…+k**m 个位置，也会发生造反。
现在你想知道，有多少种可能的排名不会发生造反。
输入格式
从文件 king.in 中读入数据。
每组数据第一行两个数n,k，表示骑士的数量和俱乐部的数量。
之后的k行每行一个整数，表示影响力第一到第k的俱乐部的骑士数量。
输出格式
输出到文件 king.out 中。
输出可能的方案数，对1000000007取模。
输入样例
3 0
输出样例
6
输入样例
5 1
4
输出样例
96
输入样例
4 2
2
1
输出样例
16
输入样例
20 5
3
7
1
2
2
输出样例
221500273
数据规模
对于20%的数据，保证n<=10
对于40%的数据，保证n<=20
对于另外20%的数据，保证k<=10
对于100%的数据，保证n<=1000000,k<=5000
错误思路
-
当时不知道为什么脑子炸了就没去打暴力
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6 + 5, P = 1e9 + 7; int n,m,a[maxn],b[maxn],ans = 1; signed main() { freopen("king.in","r",stdin); freopen("king.out","w",stdout); scanf("%lld%lld",&n,&m); for (int i = 1;i <= m;i ++) scanf("%lld",&a[i]); for (int i = 1;i <= n;i ++) ans = (ans * i) % P; printf("%lld",ans); }
正解
-
也是个数学题，用容斥解决
#include<bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2000000; const ll maxm = 6000; const ll P = 1000000007; ll n, k, a[maxn], sum[maxm], fac[maxn]; ll tim(ll x, ll y) { return (x * y) % P; } ll add(ll x, ll y) { return (P - y + x) % P; } ll f[maxm]; // f[i] is #perms of [1..a[i]] where *all* clans are needed for x revolt int main() { freopen("king.in","r",stdin); freopen("king.out","w",stdout); scanf("%lld%lld",&n,&k); for(int i = 1; i <= k; i++) cin >> a[i]; fac[0] = 1; for(int i = 1; i <= n; i++) fac[i] = tim(fac[i-1], i); for(int i = 1; i <= k; i++) sum[i] = sum[i - 1] + a[i]; ll ans = fac[n]; for(int i = 1; i <= k; i++) { f[i] = fac[sum[i]]; for(int j = 1; j < i; j++) f[i] = add(f[i], tim(f[j], fac[sum[i] - sum[j]])); ans = add(ans, tim(f[i], fac[n - sum[i]])); } printf("%lld",ans); return 0; }
葬礼 总结
-
总体来说这场打的还不错，拿了 rank\ 8
-
但是很多能拿的分都没拿到