【解题报告】2022牛客寒假算法基础集训营1
-
2022牛客寒假算法基础集训营1 由于题目难度有些偏基础,太基础的今后就不细讲了。 话不多说,开冲!
-
由于字符超过 上限了,删了一些简单的内容,可以在CSDN端查看完整内容
A:九小时九个人九扇门
题意 | 简单
- 经典 999 游戏,之前就看过极限脱出系列的攻略全流程了...(咳咳
数字根:一个数字的各个位数字和,如果该和不是一位数,继续操作,直到一位数字,就是这个数字的数字根
比如
87->(8+7=15)15->(1+5=6)6
所以87的数字根为6
- 有 个人,给定每个人的数字 选出一些人的集合,求集合的数字根为 的集合选法,取模 集合的数字根:为集合的所有元素的和的数字根
思路 | 数学 + dp
- 容易猜想或者得到,设 表示 的数字根,那么有:
还有一些性质:
这些都可以由上面 式推导出来。 如果让我证明的话,感觉不大好证,我会用反证法,先假设 式成立 然后我能得到 也是同时成立的,并且这个和数字根的定义相同 所以原 成立
- 不管怎么样,我们可以利用这个 设 表示考虑完前 个数字,数字根为 的方案数,然后转移即可。 随便计算数字根,用定义法 还是递归法 都行
代码
- 时间复杂度: 空间复杂度:滚动数组了一下,
const int st = 0;
int cnt[15][2];
int cal(int a){ // 你当然可以写 return (x-1) % 9 + 1 更快速得到数字根
if(a < 10)return a;
return cal(cal(a / 10) + a % 10);
}
int main()
{
cnt[0][st] = 1;
int n;cin >> n;
for(int i = 1;i <= n;++i){
int t;cin >> t;
for(int j = 0;j < 10;++j){
int aim = cal(j + t);
cnt[aim][st^1] = (cnt[aim][st^1] + cnt[j][st]) % MOD;
}
for(int j = 0;j < 10;++j){
cnt[j][st] = (cnt[j][st] + cnt[j][st^1]) % MOD;
cnt[j][st^1] = 0;
}
}
for(int i = 1;i < 10;++i){
cout << cnt[i][st] << ' ';
}
return 0;
}
B:炸鸡块君与FIFA22
题意 | 中等
- 给定一个长度为 的字符串 ,和 个询问
字符串只包含三种字符:
- 表示赢,加一分。
- 表示输,扣一分。如果扣分前分数是三的倍数,则不扣分
- 表示平局,分数不变。
- 每组询问给定 ,表示初始分数为 ,经历 之后的分数为多少
思路 | 数据结构 + 简单同余
- 容易想到,快速计算分数肯定要用能分治的数据结构。我这里使用倍增表。 倍增表就是:
它比线段树要内存小,更快,但是无法修改操作。同样要求操作满足结合律。
- 这里想到,分数是三的倍数扣分不记录,则按分数取余 分别记录,就变成 想好转移。
- 容易得到整段的分数等于左边段的分数加上右边段的分数 这个时候 变成了什么呢?当然就是 ,注意分数可能有负,所以要这么处理。
- 然后是查询。查询就是把 分成不同个 的段,来让查询复杂度达到 级别,具体可以看代码
代码
- 时间复杂度:
int dp[MAX][22][3];
int p2[22]; // 预处理 2^p
int main()
{
p2[0] = 1;
for(int i = 1;i <= 20;++i)
p2[i] = p2[i-1] * 2;
int n,q;cin >> n >> q;
string ss;
cin >> ss;
ss = " " + ss;
for(int i = 1;i <= n;++i){
for(int j = 0;j < 3;++j){ // 计算 dp 初值
dp[i][0][j] = 0;
if(ss[i] == 'W')dp[i][0][j]++;
else if(ss[i] == 'L' && j != 0)dp[i][0][j]--;
}
}
for(int i = 1;i <= 20;++i) // 预处理转移 dp
for(int p = 1;p <= n;++p){
if(p + p2[i] - 1 > n)break;
for(int j = 0;j < 3;++j){
int f1 = dp[p][i-1][j];
int f2 = dp[p+p2[i-1]][i-1][((j+f1)%3+3)%3];
dp[p][i][j] = f1 + f2;
}
}
for(int i = 1;i <= q;++i){
int l,r,s;
cin >> l >> r >> s;
int delta = 0;
int now = s % 3;
for(int j = 20;j >= 0;--j){ // 查询
if(l + p2[j] - 1 <= r){
delta += dp[l][j][now];
now = (now + dp[l][j][now] % 3 + 3) % 3;
l += p2[j];
}
}
cout << s + delta << '\n';
}
return 0;
}
D:牛牛做数论
题意 | 中等
思路 | 数论
- 欧拉函数是积性函数,可以写成 所以得到
- 那么最大值,就是 中最大的质数取到的值 最小值,就是范围之内最多、尽量小的质数的乘积,暴力检查前 个质数即可。
E:炸鸡块君的高中回忆
- 签到题 先特判,再做下述操作: 操作1:花两步,校园里人少掉 。 操作2:花一步,校园里人少掉 ,但是只能做一次。
- 设操作1 做了 次,答案就是最小的 ,满足:
答案就是
F:中位数切分
题意 | 中等
- 把长度为 的序列划分成最多份,满足每份的中位数 。若长度为偶数,中位数取中间的左边那个数字。
思路 | 数据结构 + dp
- 划分满足无后效性,想到 ,则设: 表示考虑玩前 个元素,最多划分的段数
- 看到中位数,想到把元素变化。若 ,即为 ,否则记为 这样,序列的中位数 转化为序列的和
- 想 的转移,如下:
- 元素和,想到前缀和。我们用 数组记录前缀和,于是后面就变成了:
由于 是固定的,我们移动元素位置,得到:
- 于是,右边就变成了求区间最小值,线段树搞定。 最后答案当然就是
- 注意到, 数组是可以为负数的,所以我们每个位置的元素增加一个增量 即可。 还注意到,有些位置的分隔是不可行的,因为求的是区间最大值,用 做初始化。
代码
- 时间复杂度:
#define ls (p<<1)
#define rs (p<<1|1)
#define md ((l+r)>>1)
const int O = 1e5+2;
const int U = 2e5+4;
int tree[MAX*4];
inline void push_up(int p){
tree[p] = max(tree[ls],tree[rs]);
}
inline void build(int p,int l,int r){
if(l == r){
tree[p] = -1;
return;
}
build(ls,l,md);
build(rs,md+1,r);
push_up(p);
}
inline void add(int p,int l,int r,int k){
tree[p] = k;
}
inline void update(int p,int l,int r,int ux,int uy,int k){
if(ux <= l && uy >= r){
add(p,l,r,k);
return;
}
if(ux <= md)update(ls,l,md,ux,uy,k);
if(uy > md)update(rs,md+1,r,ux,uy,k);
push_up(p);
}
inline int query(int p,int l,int r,int qx,int qy){
int res = -1;
if(qx <= l && r <= qy)return tree[p];
if(qx <= md)res = max(res,query(ls,l,md,qx,qy));
if(qy > md)res = max(res,query(rs,md+1,r,qx,qy));
return res;
}
int pre[100050];
int main()
{
int T;
scanf("%d",&T);
while(T--){
int n,m;scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i){
int t;scanf("%d",&t);
if(t >= m)t = 1;
else t = -1;
pre[i] = pre[i-1] + t;
}
build(1,1,U);
update(1,1,U,O,O,0);
int ans = -1;
for(int i = 1;i <= n;++i){
int dpj = query(1,1,U,1,O + pre[i] - 1);
if(dpj != -1){
int dpi = dpj + 1;
if(i == n)ans = dpi;
update(1,1,U,O + pre[i],O + pre[i],dpi);
}
}
printf("%d\n",ans);
}
return 0;
}
G:ACM is all you need
题意 | 中偏难
- 给定一维函数上 个整数点 定义 表示满足
- 变化,表示让所有的值 变成 ,其中 是自己选择的一个整数 求经过一次变化, 的最小值是多少
思路 | 思维 + 差分
- 首先,每个点都加 当然不影响 ,我们把变化看做 看到几何意义,就是这个函数上的每个点距离 的直线的距离。 我们可以当做把这个函数沿着某个 向上翻折,但是这样对整体答案不好考虑。
- 我们只考虑单独一个位置。 由于 只和当前位置与前后两个相邻位置有影响。 且仔细分析,我们只用关注增减情况即可,只有四种抽象情况:
- 因为如果存在 或者 ,这个点变化前和变化后当然都不会是 接下来,我们分析当 处于什么情况下, 的变化值 我们记录成一个段 ,表示 时候, 的变化值为 当然, 可以是正无穷,我们使用一个正大值 表示。(为什么 不用负大值记录,可以仔细想想)
- 于是问题就变成,给定许多个段,求处于哪个位置, 是最小的 我们只要对段排序,位置肯定是某个端点处的位置。 这个时候我们可能会想到,退出某个段, 的影响就没了,应该把 退回,这样就写成滑动窗口了,我们可以用简单差分:再累加一个 的段把影响去掉即可。
代码
- 时间复杂度:
int aa[MAX];
int cnt;
struct node{
ll L,R;
int delta;
bool operator<(const node &ND)const{
if(L != ND.L)return L < ND.L;
return R < ND.R;
}
}seg[2 * MAX];
int main()
{
int T = read();
while(T--){
int n = read();
for(int i = 1;i <= n;++i){
aa[i] = read();
}
int ans1 = 0;
cnt = 0;
for(int i = 2;i <= n-1;++i){
if(aa[i] == aa[i-1] || aa[i] == aa[i+1])continue;
ll L,R,D;
if(aa[i-1] < aa[i] && aa[i] < aa[i+1]){
L = (aa[i] + aa[i-1]) / 2 + 1;
R = (aa[i] + aa[i+1] + 1) / 2 - 1;
D = 1;
cnt++;
seg[cnt].L = L;
seg[cnt].R = R;
seg[cnt].delta = D;
cnt++;
seg[cnt].L = R+1;
seg[cnt].R = INF;
seg[cnt].delta = -D;
}else if(aa[i-1] < aa[i] && aa[i] > aa[i+1]){
int L1 = (aa[i] + aa[i-1]) / 2 + 1;
int L2 = (aa[i] + aa[i+1]) / 2 + 1;
L = max(L1,L2);
R = INF;
D = 1;
cnt++;
seg[cnt].L = L;
seg[cnt].R = R;
seg[cnt].delta = D;
}else if(aa[i-1] > aa[i] && aa[i] > aa[i+1]){
L = (aa[i] + aa[i+1]) / 2 + 1;
R = (aa[i] + aa[i-1] + 1) / 2 - 1;
D = 1;
cnt++;
seg[cnt].L = L;
seg[cnt].R = R;
seg[cnt].delta = D;
cnt++;
seg[cnt].L = R+1;
seg[cnt].R = INF;
seg[cnt].delta = -D;
}else{
ans1++;
int L1 = (aa[i] + aa[i-1] + 1) / 2;
int L2 = (aa[i] + aa[i+1] + 1) / 2;
L = min(L1,L2);
R = INF;
D = -1;
cnt++;
seg[cnt].L = L;
seg[cnt].R = R;
seg[cnt].delta = D;
}
}
sort(seg+1,seg+1+cnt);
int ans = ans1;
int delta = 0;
for(int i = 1;i <= cnt;++i){
delta += seg[i].delta;
if(i == cnt || (seg[i].L != seg[i+1].L))ans = min(ans,ans1+delta); // 可以想想为什么要这个if
}
cout << ans << '\n';
}
return 0;
}
H:牛牛看云
题意 | 简单偏中等
- 给定 ,求
思路 | 思维
- 第一个想法, 右侧的 中, 是一个常量,我们可以想做:
其中 可以转化成这 个点到某个点 之间的距离和,但是貌似挺复杂的,我们有更简单的方法
- 第二个想法,我们利用好 的值域比较小,我们可以把题目化成:
其中 表示有多少对 ,满足 满足 我们可以记 表示 个数字中有多少个数字为
- 怎么算呢,如果 ,合法对数明显为 如果 ,合法对数也明显为
I:B站与各唱各的
题意 | 中等
- 组样例,每组给定 表示有 个人, 句歌词。每个人可以选择每句歌词唱不唱,不能与他人沟通。 若某句歌词被所有人唱了,或者所有人都没唱,那么这句是失败的,否则是成功的。 每个人都十分聪明,求唱成功的句的期望取模
思路 | 数学
- 我们随便想一想,容易得到一个策略:每个人对每句随机选择 唱与不唱,那么策略是最优的。 每句假设是独立的。如果每个人采取这样的策略,那么唱失败的概率只有 容易得到,答案即为:
J:小朋友做游戏
- 签到。考虑选 个吵的, 个不吵的,满足 且 选吵的 个,只要选幸福度最高的 个吵的即可。做一个排序然后一个前缀和即可。
K:冒险公社 (天了噜,简单题没人做?)
题意 | 简单
- 个岛,每个岛为 三色之一
思路 | 简单dp
- 发现,第 个预测和 的所有岛都没有关系,明显符合 dp 的无后效性 答案求的是绿色岛的最大值。 发现和每个岛的颜色有关,直接设 表示走完前 个岛,其中岛 的颜色分别为 ,合法方案中绿色岛最多的值
- 然后考虑转移,每次多走一格岛,明显转移是从 转移到 什么时候转移呢?合法转移,看这个位置的罗盘预测是否满足即可
代码
- 时间复杂度:
/**
0 1 2
R G B
*/
int dp[MAX][3][3][3];
int main()
{
int n;cin >> n;
string ss;cin >> ss;
for(int i = 2;i < n;++i)
for(int i1 = 0;i1 < 3;++i1)
for(int i2 = 0;i2 < 3;++i2)
for(int i3 = 0;i3 < 3;++i3)
dp[i][i1][i2][i3] = -1;
for(int i = 0;i < 3;++i)
for(int i2 = 0;i2 < 3;++i2)
for(int i3 = 0;i3 < 3;++i3){
dp[1][i][i2][i3] = 0;
if(i == 1)dp[1][i][i2][i3]++;
if(i2 == 1)dp[1][i][i2][i3]++;
}
int ans = -1;
for(int i = 2;i < n;++i)
for(int i1 = 0;i1 < 3;++i1)
for(int i2 = 0;i2 < 3;++i2)
for(int i3 = 0;i3 < 3;++i3)
for(int i4 = 0;i4 < 3;++i4)
if(dp[i-1][i2][i3][i4] != -1){
int pre = dp[i-1][i2][i3][i4];
int R = 0,G = 0;
if(i1 == 0)R++;
else if(i1 == 1)G++;
if(i2 == 0)R++;
else if(i2 == 1)G++;
if(i3 == 0)R++;
else if(i3 == 1)G++;
int now = 0;
if(i1 == 1)now++;
if(ss[i] == 'G' && G > R){
dp[i][i1][i2][i3] = max(dp[i][i1][i2][i3],pre + now);
}else if(ss[i] == 'R' && R > G){
dp[i][i1][i2][i3] = max(dp[i][i1][i2][i3],pre + now);
}else if(ss[i] == 'B' && R == G){
dp[i][i1][i2][i3] = max(dp[i][i1][i2][i3],pre + now);
}
if(i == n-1)ans = max(ans,dp[i][i1][i2][i3]);
}
cout << ans;
return 0;
}
L:牛牛学走路
- 签到