记录牛客训练营补题感悟。
绿油油的，感到很欣慰，总是让人忍不住的继续加油。
题目链接
2022牛客寒假算法基础集训营1
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
这种结论还是很好证明的，但我没发现，以后还是得多想想有啥规律没 - 问题转化为： 从a数组中选择一些数字，使得其求和对9取模为0，1，2，3，4，5，6，7，8有多少种选法
#include <bits/stdc++.h>
using 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，不能一个也不选
}
B 炸鸡块君与FIFA22
题目大意：
ST表
在此引用大佬的一篇ST表详解
思路
- 注意到起始分数若在%3意义下相等，则经历[𝑙, 𝑟]一段后分数的变
化量是一个定值； dp[𝑘] [𝑖] [𝑗]表示在初始分数为𝑘的情况
下经历了[𝑖, 𝑖 + 2^𝑗 ? 1]一段儿游戏后分数的变化量- 假设预处理出了dp，则对于一次询问，可以先将其初始分数𝑠对3
取模，然后按照倍增的套路从𝑙跳若干个2的次幂跳到𝑟，跳的时
候要按照分数对3取模的结果来决定访问哪个dp值
#include <bits/stdc++.h>
using 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("%lld\n", s);
}
}
C Baby’s first attempt on CPU
题目大意：
当时比赛看着复杂，就没仔细读，感觉任务很庞大
其实，就是根据输入得到某些语句之间是冲突的，这些语句之间至少要有三个语句，问至少应该插入多少空语句？
读题、模拟
分析
- 样例解释 ----> 基本思路
第二句和第一句有冲突: 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即可】
#include <bits/stdc++.h>
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;
}
D 牛牛做数论
题目大意：
打表/数论
分析
- 写一个暴力版本打表，发现规律
- 公式
#include <bits/stdc++.h>
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("%lld\n", n);
}
}
E 炸鸡块君的高中回忆
题目大意：
n个人，只有m个人带了校园卡，于是他们想到了这样一个策略：先让m个人带校园卡进入学校，再派一个人带着所有m张校园卡出来，重复上述过程，直到所有人进入学校。
假设从外面进入学校和从校内出来到校外都需要花费一个单位的时间，求所有人都进入学校最少需要花费几个单位的时间。
签到题、思维
分析
- 最后一趟最多进去m个人，前面每趟最多m-1个人
2.详细见代码，注意向上取整、分母不为零（段错误两次。。）
#include <bits/stdc++.h>
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("%d\n", ans);
}
}
F 中位数切分
题目大意：
给定一个长为n的数组a和一个整数m，你需要将其切成连续的若干段，使得每一段的中位数都大于等于m，求最多可以划分成多少段。
我们定义，偶数个数的中位数为中间两个数中较小的那一个，奇数个数的中位数就是正中间的数。如[2,3,1,5]的中位数为2，[2,3,1,2]的中位数为2，[3,5,9,7,11]的中位数为7。
两种写法
法一：数学分析(简单写法)
AC代码如下：
#include <bits/stdc++.h>
using 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("%d\n", cnt1 - cnt2);
else printf("-1\n");
}
}
法二：树状数组、前缀和、离散化、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
题目大意：
思维
分析
- |f[i] - b| 可以看成f[i]与b的高度差。可以发现b取一定值可以使f[i]不再是local num; 也可以使f[i]变成local num。例如下图，当b >= 5时，a[i]不再是local num
- 我们假设b = 0, 那么一开始是local num的f[i]的个数就记录下来了（代码中记为ans）。mp记录的就是这样的区间端点。mp[x] --表示b为x及以上时，会使原本不是local num的变成local num; mp[x] ++，表示当b为x及以下时，会使原本是的变成不是。
map会自动排序，最后我们相当于从最小区间端点开始枚举，取最大的res就是能最大减少res个local num。
注意端点取值，可以根据实际意义枚举间的的数值发现是向上还是向下还是+1取整，
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int n;
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &f[i]);
map<int, int> mp;
int ans = 0;
for(int i = 2; i < n; i ++)
{
if(f[i] == f[i - 1] || f[i] == f[i + 1]) continue;
if(f[i] < f[i - 1] && f[i] < f[i + 1])
{
ans ++;
mp[(f[i] + min(f[i - 1], f[i + 1]) + 1) / 2] ++;
}
else if(f[i] > f[i - 1] && f[i] > f[i + 1])
{
mp[(f[i] + max(f[i - 1], f[i + 1])) / 2 + 1] --;//f[i+1]=1, f[i-1]=3, f[i]=4,f[i]=5
}
else{
mp[(f[i] + min(f[i - 1], f[i + 1]))/ 2 + 1] --; //f[i]和第二大的中点以上是locl num
mp[(f[i] + max(f[i - 1], f[i + 1]) + 1) / 2] ++;
}
}
int res = 0, tot = 0;
for(auto &[k, v] : mp)
{
tot += v;
res = max(res, tot);
}
printf("%d\n", ans - res);
}
}
H 牛牛看云
题目大意：给出一个数组，求：
注意: 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
#include <bits/stdc++.h>
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;
}
I B站与各唱各的
题目大意：对于一首m句的歌曲，n个人选择唱或不唱（n个人不能进行交流， ），某一句歌词所有人都没唱或同时被所有人都唱了，则认为这句唱失败了。他们的目标是让成功唱出的句子数尽可能多，希望求期望成功的句子数量对10^9 + 7取模的结果。
逆元、数学
分析
n个人地位等价，策略完全一样，唱的概率都为pi
对于某一句失败的概率：(pi) ^ n + (1 - pi) ^ n, pi = 1/2时取得最小值
对于m句成功的概率: m * (2 ^ n - 2) / (2 ^ n)
#include <bits/stdc++.h>
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("%d\n", (m * (n2 - 2) % mod * mul(n2, mod - 2) % mod + mod) % mod);
}
}
J 小朋友做游戏
题目大意：给出A个安静的小朋友，B个闹腾的小朋友。每个小朋友都有一个幸福度，两个闹腾的小朋友不能在一块。恰好选出n个人做游戏的幸福度最大是多少？
分析
- 本题难度不大，但我一开始敲的代码还得调试
- 建议使用思路简单，代码复杂度不高的：
亮点：前缀和优化，枚举更新答案
【人脑判断多（易出错）还不如写的让机器明白点】
自己使用vector不知为何过不了一些样例，能用数组还是数组吧
#include <bits/stdc++.h>
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<int> a(A + 1);
//vector<int> 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("%lld\n", ans);
}
}
K 冒险公社
题目大意：
岛屿有三种类型，分别为象征财富的绿岛（用G表示）、象征敌人的红岛（用R表示）与象征灾难的黑岛（用B表示）。
玩家手中还有一个可以预测岛屿颜色的罗盘，该罗盘也可以发出绿色（G）、红色（R）、黑色（B）三种颜色，其预测的规则是：玩家在第i(3≤i)座岛屿上时，若i、i-1、i-2三座岛中绿岛数量多于红岛则发绿光、若红岛数量多于绿岛则发红光、若两者数量相等则发黑光。
现在，给定罗盘对某一张游戏地图的全部预测结果，请你告诉渴望财富的炸鸡块君，这张地图最多有多少个绿岛。
DP
分清楚合法情况，更新dp数组
#include <bits/stdc++.h>
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("%d\n", res);
return 0;
}
L 牛牛学走路
签到题，略
继续加油嗷！！！
