记录牛客训练营补题感悟。
题目链接
A 九小时九个人九扇门B 炸鸡块君与FIFA22C Baby's first attempt on CPUD 牛牛做数论E 炸鸡块君的高中回忆F 中位数切分G ACM is all you needH 牛牛看云I B站与各唱各的J 小朋友做游戏K 冒险公社L 牛牛学走路
A 九小时九个人九扇门题目大意：
01背包
分析
- 一个结论：一个数的数字根等于这个数对9取模的结果（特别的，取模为0则数字根为9）
【证明：】
一个四位数abcd, (abcd) % 9 = (a * 1000 + b * 100 + c * 10 + d) % 9 = (a % 9 + b % 9 + c % 9 + d % 9) = (a + b + c + d) % 9
#includeB 炸鸡块君与FIFA22using namespace std; const int N = 1e5 + 10, mod = 998244353; int f[N][9]; int main(void) { int n; scanf("%d", &n); f[0][0] = 1; int x; for(int i = 1; i <= n; i ++) { scanf("%d", &x); x %= 9; for(int j = 0; j < 9; j ++) { //要选x这个值 f[i][(j + x) % 9] = (f[i][(j + x) % 9] + f[i - 1][j]) % mod; //不选 f[i][j] = (f[i][j] + f[i - 1][j]) % mod; } } for(int i = 1; i < 9; i ++) cout << f[n][i] << " "; cout << f[n][0] - 1<< endl; //得减去初始化f[0][0] = 1，不能一个也不选 }
题目大意：
ST表
在此引用大佬的一篇ST表详解
思路
- 注意到起始分数若在%3意义下相等，则经历[푙, 푟]一段后分数的变
化量是一个定值；dp[푘] [푖] [푗]表示在初始分数为푘的情况
下经历了[푖, 푖 + 2^푗 − 1]一段儿游戏后分数的变化量假设预处理出了dp，则对于一次询问，可以先将其初始分数푠对3
取模，然后按照倍增的套路从푙跳若干个2的次幂跳到푟，跳的时
候要按照分数对3取模的结果来决定访问哪个dp值
#includeC Baby’s first attempt on CPUusing namespace std; typedef long long LL; const int N = 1e6 + 10; LL dp[3][N][21]; char str[N]; int main(void) { int n, q; scanf("%d%d", &n, &q); scanf("%s", str + 1); for(int j = 0; j <= 20; j ++) { for(int k = 1; k <= n; k ++) { if(j == 0) { if(str[k] == 'W') dp[0][k][j] = dp[1][k][j] = dp[2][k][j] = 1; else if(str[k] == 'D') dp[0][k][j] = dp[1][k][j] = dp[2][k][j] = 0; else{ dp[0][k][j] = 0; dp[1][k][j] = dp[2][k][j] = -1; } } else { int p1 = k, p2 = k + (1 << (j - 1)); if(p2 > n) { dp[0][p1][j] = dp[0][p1][j-1]; dp[1][p1][j] = dp[1][p1][j-1]; dp[2][p1][j] = dp[2][p1][j-1]; } else{ dp[0][p1][j] = dp[0][p1][j-1] + dp[((0 + dp[0][p1][j-1]) % 3 + 3) % 3][p2][j-1]; dp[1][p1][j] = dp[1][p1][j-1] + dp[((1 + dp[1][p1][j-1]) % 3 + 3) % 3][p2][j-1]; dp[2][p1][j] = dp[2][p1][j-1] + dp[((2 + dp[2][p1][j-1]) % 3 + 3) % 3][p2][j-1]; } } } } while(q --) { LL l, r, s; scanf("%lld%lld%lld", &l, &r, &s); while(l <= r) { LL j = 0; while(l + (1 << j) <= r + 1) j ++; j --; s += dp[s % 3][l][j]; l += (1 << j); } printf("%lldn", s); } }
题目大意：
当时比赛看着复杂，就没仔细读，感觉任务很庞大
其实，就是根据输入得到某些语句之间是冲突的，这些语句之间至少要有三个语句，问至少应该插入多少空语句？
读题、模拟
分析
- 样例解释 ----> 基本思路
第二句和第一句有冲突: 2->1 第三句和第一句有冲突:3->1 【1 0 0 0 2 3】 开一个数组存储插入后的结果，遍历原数组A，看B最后的几个语句是否和当前语句冲突，若有，B的末尾加空语句数组开的要大
代码细节
temp[i]表示和第i句有冲突的最近的是几
【假如第三句和第二句、第一句有冲突， 我们只需要处理第三句和第二句的冲突即可】
B数组中如果是1 2 3， 但第4句只和第二句冲突符合题意，该如何处理？
【此时B数组长度len = 3, 根据temp数组找到2的位置j，加3 - (len - j)个0，再加上4即可】
#includeD 牛牛做数论using namespace std; int a[110][5], b[1010], len; int temp[110]; // temp[i] 表示和i有冲突的最近的语句是谁 int main(void) { int n; cin >> n; for(int i = 1; i <= n; i ++) { temp[i] = 4; for(int j = 1; j <= 3; j ++) { cin >> a[i][j]; if(a[i][j]) temp[i] = min(temp[i], j); } } for(int i = 1; i <= n; i ++) { if(temp[i] != 4) { int j = len; //B数组长度 while(b[j] != i - temp[i]) j --; int add = 3 - (len - j); for(j = 1; j <= add; j ++) b[++ len] = 0; } b[++ len] = i; } cout << len - n << endl; return 0; }
题目大意：
打表/数论
分析
- 写一个暴力版本打表，发现规律公式
#includeE 炸鸡块君的高中回忆using namespace std; typedef long long LL; LL primes[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41}; LL n; bool isP(LL x) { if(x <= 3) return true; for(int i = 2; i * i <= x; i ++) { if(x % i == 0) return false; } return true; } int main(void) { int T; scanf("%d", &T); while(T --) { scanf("%lld", &n); LL temp = 1, i = 1; if(n == 1) { puts("-1"); continue; } while(temp * primes[i] <= n) { temp *= primes[i]; i ++; } printf("%lld ", temp); while(!isP(n)) { n --; } printf("%lldn", n); } }
题目大意：
n个人，只有m个人带了校园卡，于是他们想到了这样一个策略：先让m个人带校园卡进入学校，再派一个人带着所有m张校园卡出来，重复上述过程，直到所有人进入学校。
假设从外面进入学校和从校内出来到校外都需要花费一个单位的时间，求所有人都进入学校最少需要花费几个单位的时间。
签到题、思维
分析
- 最后一趟最多进去m个人，前面每趟最多m-1个人
2.详细见代码，注意向上取整、分母不为零（
#includeF 中位数切分using namespace std; int main(void) { int T; scanf("%d", &T); while(T --) { int a, b; scanf("%d%d", &a, &b); int ans; //最后一次进去b个，前几次进去b - 1个 if(a == 1 && b == 1) ans = 1; else if(a > 1 && b == 1) ans = -1; else{ int cnt = (a - b + b - 2) / (b - 1); //出来次数 ans = cnt * 2 + 1; } printf("%dn", ans); } }
题目大意：
给定一个长为n的数组a和一个整数m，你需要将其切成连续的若干段，使得每一段的中位数都大于等于m，求最多可以划分成多少段。
我们定义，偶数个数的中位数为中间两个数中较小的那一个，奇数个数的中位数就是正中间的数。如[2,3,1,5]的中位数为2，[2,3,1,2]的中位数为2，[3,5,9,7,11]的中位数为7。
两种写法
法一：数学分析(简单写法)
AC代码如下：
#includeusing namespace std; const int N = 1e5 + 10; int a[N]; int main(void) { int T; scanf("%d", &T); while(T --) { int n, m, x; scanf("%d%d", &n, &m); int cnt1 = 0, cnt2 = 0; while(n --) { scanf("%d", &x); if(x >= m) cnt1 ++; else cnt2 ++; } if(cnt1 > cnt2) printf("%dn", cnt1 - cnt2); else printf("-1n"); } }
法二：树状数组、前缀和、离散化、DP（复杂做法）
- 状态表示：dp[i]表示对于前i个数字，最后一段以a[i]结尾，最多可以分为多少段。则O(n ^ 2)的状态转移为：
dp[i] = max(dp[j] + 1); j < i && med(a[j + 1]…a[i]) >= m.优化：
（1）前缀和： >=m的a[i] = 1, < m的a[i] = -1, 并对其求前缀和S[]
（2)在前缀和上开一个维护最大值的树状数组，每次即求所有S[i] - S[j] > 0的j当中最大的dp[j]
（3）还是有一些问题（为什么前缀和数组 <= 0直接跳过？），没看明白二分那里的写法，请大佬们指点，解决后更新在此处。呜呜呜
G ACM is all you need
题目大意：
题目大意：给出一个数组，求：
注意: 0 <= a[i] <= 1000 我是没注意到。
分析
开一个cnt数组, cnt[i]表示i出现了多少次
枚举ai, aj：【等差数列求出方法数】
（1）若ai == aj: cnt[ai] = n
假设第一个数的位置 <= 第二个数的位置
相当于从n个数中选俩数字，可以重复。假设我们第一个数选择了第一个位置的数，第二个数有n中选法… 第一个数选择最后一个位置的数时，有1中选法。所以一共是(n + 1) * n / 2种
（2）ai != aj时， 即是cnt[ai] * cnt[aj]种
注意cnt数组也要开long long， 相乘会爆int
#includeI B站与各唱各的using namespace std; const int N = 1010; long long cnt[N]; int main(void) { int n; scanf("%d", &n); int x; while(n --) { scanf("%d", &x); cnt[x] ++; } long long ans = 0; for(int i = 0; i <= 1000; i ++) { for(int j = i; j <= 1000; j ++) { if(i == j) ans += 1ll * abs(i + j - 1000) * (cnt[i] * (cnt[j] + 1) / 2); else ans += 1ll * abs(i + j - 1000) * (cnt[i] * cnt[j]); } } cout << ans << endl; return 0; }
题目大意：对于一首m句的歌曲，n个人选择唱或不唱（n个人不能进行交流， ），某一句歌词所有人都没唱或同时被所有人都唱了，则认为这句唱失败了。他们的目标是让成功唱出的句子数尽可能多，希望求期望成功的句子数量对10^9 + 7取模的结果。
逆元、数学
分析
n个人地位等价，策略完全一样，唱的概率都为pi
对于某一句失败的概率：(pi) ^ n + (1 - pi) ^ n, pi = 1/2时取得最小值
对于m句成功的概率: m * (2 ^ n - 2) / (2 ^ n)
#includeJ 小朋友做游戏using namespace std; const int mod = 1e9 + 7; typedef long long LL; LL mul(LL a, LL b) { int ans = 1; while(b) { if(b & 1) { ans = (ans * a) % mod; } a = (a * a) % mod; b >>= 1; } return ans; } int main(void) { int T; scanf("%d", &T); while(T--) { LL n, m; scanf("%lld%lld", &n, &m); LL n2 = mul(2, n) % mod; printf("%dn", (m * (n2 - 2) % mod * mul(n2, mod - 2) % mod + mod) % mod); } }
题目大意：给出A个安静的小朋友，B个闹腾的小朋友。每个小朋友都有一个幸福度，两个闹腾的小朋友不能在一块。恰好选出n个人做游戏的幸福度最大是多少？
分析
- 本题难度不大，但我一开始敲的代码还得调试建议使用思路简单，代码复杂度不高的：
亮点： 前缀和优化，枚举更新答案
【人脑判断多（易出错）还不如写的让机器明白点】
#includeK 冒险公社using namespace std; int a[200010]; int b[200010]; int sum1[200010]; int sum2[200010]; bool cmp(int a, int b) { return a >= b; } int main(void) { int T; scanf("%d", &T); while(T --) { int A, B, n; scanf("%d%d%d", &A, &B, &n); // vector a(A + 1); //vector b(B + 1); for(int i = 1; i <= A; i ++) scanf("%d", &a[i]); for(int i = 1; i <= B; i ++) scanf("%d", &b[i]); //a[0] = 0, b[0] = 0; if(A < (n + 1) / 2){ puts("-1"); continue; } sort(a + 1, a + 1 + A, cmp); sort(b + 1, b + 1 + B, cmp); for(int i = 1; i <= A; i ++) sum1[i] = sum1[i - 1] + a[i]; for(int j = 1; j <= B; j ++) sum2[j] = sum2[j - 1] + b[j]; int ans = -1; for(int i = 0; i <= A; i ++) { int j = n - i; if(j > n / 2 || j > B || j < 0) continue; ans = max(ans, sum1[i] + sum2[j]); } printf("%lldn", ans); } }
题目大意：
岛屿有三种类型，分别为象征财富的绿岛（用G表示）、象征敌人的红岛（用R表示）与象征灾难的黑岛（用B表示）。
玩家手中还有一个可以预测岛屿颜色的罗盘，该罗盘也可以发出绿色（G）、红色（R）、黑色（B）三种颜色，其预测的规则是：玩家在第i(3≤i)座岛屿上时，若i、i-1、i-2三座岛中绿岛数量多于红岛则发绿光、若红岛数量多于绿岛则发红光、若两者数量相等则发黑光。
现在，给定罗盘对某一张游戏地图的全部预测结果，请你告诉渴望财富的炸鸡块君，这张地图最多有多少个绿岛。
DP
分清楚合法情况，更新dp数组
#includeL 牛牛学走路using namespace std; const int N = 1e5 + 10; int n; int dp[N][3][3][3]; string s; int main(void) { cin >> n >> s; s = " " + s; memset(dp, -1, sizeof dp); //初始化i == 3时的情况 for(int i = 0; i < 3; i ++) { for(int j = 0; j < 3; j ++) { for(int k = 0; k < 3; k ++) { int G = (i == 0) + (j == 0) + (k == 0); int R = (i == 1) + (j == 1) + (k == 1); if(s[3] == 'G' && G > R) dp[3][i][j][k] = G; else if(s[3] == 'R' && R > G) dp[3][i][j][k] = G; else if(s[3] == 'B' && G == R) dp[3][i][j][k] = G; } } } for(int i = 4; i <= n; i ++) //当前为i { for(int a = 0; a < 3; a ++) { for(int b = 0; b < 3; b ++) { for(int c = 0; c < 3; c ++) { if(dp[i - 1][a][b][c] == -1) continue; int G = (a == 0) + (b == 0); int R = (a == 1) + (b == 1); for(int k = 0; k < 3; k ++)//当前这个岛屿可能是多少 { G += (k == 0); R += (k == 1); if(s[i] == 'G' && G > R || s[i] == 'R' && G < R || s[i] == 'B' && G == R) dp[i][k][a][b] = max(dp[i][k][a][b], dp[i - 1][a][b][c] + !k); G -= (k == 0); R -= (k == 1); } } } } } int res = -1; for(int a = 0; a < 3; a ++) { for(int b = 0; b < 3; b ++) { for(int c = 0; c < 3; c ++) { res = max(res, dp[n][a][b][c]); } } } printf("%dn", res); return 0; }
签到题，略
还有两道没补，明天一定。
