2024.3.19abc晚训题解

本文主要是介绍2024.3.19abc晚训题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我发现还是有部分同学打完晚训不去补题，时间上的安排要自己调整，还有七个月参加CSP，每天少做一点，七个月比其他同学少做了多少？比赛时也会力不从心，留下遗憾。
3.19晚训链接VJ3.19abc晚训
视频讲解链接
我个人认为一般这种题目看文字题解就能懂…同学们要提升自己的理解能力自学能力
A题
等差数列的公式是A[i]=A[1]+(i-1)D 其中A[1]是首项，D是公差所以说直接枚举即可

#include <bits/stdc++.h>
using namespace std;
int main()
{int a,b,c;cin>>a>>b>>c;for(int i=a;i<=b;i=i+c){cout<<i<<" ";}	return 0;
}

B题

#include <bits/stdc++.h>
using namespace std;
int A[200];
int main()
{	int len=0;int q;cin>>q;while(q--){int op,x;cin>>op>>x;if(op==1){A[++len]=x;	}else{cout<<A[len-x+1]<<'\n';}}return 0;
}

C题解题思路
这题很明显要用到分而治之的思想，因为你的X可以被拆分，拆分以后还可能继续拆…
那么我们就直接写个函数f(x) 然后很明显f(x)可以被拆成两个新的f()，注意控制一下什么时候结束。
但还有一个问题，N最大10¹⁷ 每次拆一半，最坏的情况是要拆出50多层，我们画一下图就很容易知道每一层要处理的f(x)是上一层的2倍，那么就会爆炸程序。但是本题涉及到的f(待处理) 重复出现了很多次，所以说可以用存储数据的方式，把每个f(待处理) 的值算出来以后，存起来，当其他分支情况再遇到它时就可以直接查询出答案，而不是再向下搜索一遍。这个叫记忆化。

#include <bits/stdc++.h>
using namespace std;
long long int ans=0;
map<long long int,long long int >v;
long long int dfs(long long int x){if(x<2)return 0*1ll;if(v[x]){return v[x];}else{if(x%2){return v[x]+=x+dfs(x/2)+dfs(x/2+1);}else{return v[x]+=x+2*dfs(x/2);}}
}
int main()
{	long long int x;cin>>x;cout<<dfs(x);return 0;
}

D题解题思路
倒着枚举字符串，遇到.以后顺着输出

#include <bits/stdc++.h>
using namespace std;
char s[200];
int main()
{	cin>>s+1;int n=strlen(s+1);int last=1;for(int i=n;i>=1;i--){if(s[i]=='.'){last=i+1;break;}}for(int i=last;i<=n;i++){cout<<s[i];}return 0;
}

E题解题思路
本题特别的点就是网格图是环形，第一行跟最后一行相通，第一列跟最后一列相通。做这个题还需要明确当前这个人所面朝的方向在哪，定义一个变量记录即可

#include<bits/stdc++.h>
using namespace std;
char s[102][102];
int main() {int h,w;cin>>h>>w;for(int i=0; i<h; i++) {for(int j=0; j<w; j++) {s[i][j]='.';}}int q;cin>>q;int x,y;x=0;y=0;int op=0;//朝向  上while(q--) {if(s[x][y]=='.') {s[x][y]='#';op=(op+1)%4;if(op==0) {x=(x-1+h)%h;} else if(op==1) {y=(y+1)%w;} else if(op==2) {x=(x+1)%h;} else if(op==3) {y=(y-1+w)%w;}} else {s[x][y]='.';op=(op-1+4)%4;if(op==0) {x=(x-1+h)%h;} else if(op==1) {y=(y+1)%w;} else if(op==2) {x=(x+1)%h;} else if(op==3) {y=(y-1+w)%w;}}}for(int i=0; i<h; i++) {for(int j=0; j<w; j++) {cout<<s[i][j];}cout<<'\n';}return 0;
}

F题解题思路
我们可以假设一开始车上人数是0
然后开始前i个上下车，也就是A[i]的前缀和
如果为负，说明一开始车上0人是不科学的，那么要补齐，补到当前这个前缀和的负数变为0
所以说修改以后我们第i次上下车后，车上总人数就又是0人了，控制在一个刚刚好的边界，最终就能保证车上人数最小

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;long long int ans=0;long long int s=0;for(int i=1;i<=n;i++){int x;cin>>x;s=s+x;if(s<0){ans=ans-s;s=0;}}cout<<s;return 0;
}

G题解题思路
观察1 N 2N 3N 4N 5N 6N …XN 整除N的必定是N的倍数
那么每N个数里面会产生N-1个不整除的
我们可以计算K里面有多少个N-1，那么在数字列表里面就对应多少个N
然后把余数算上去，就得到答案了。注意当K整除N-1时，答案需要-1 ，因为会刚好落在N的倍数上

#include<bits/stdc++.h>
using namespace std;
int main() {int p; cin>>p;while(p--){int n,k; cin>>n>>k;int x=k%(n-1),xx=k/(n-1);if(k<n) cout<<k<<endl;else if(k==n) cout<<n+1<<endl;else if(x) cout<<xx*n+x<<endl;else cout<<xx*n-1<<endl;}return 0;
}

H题解题思路
本题思维量不大，但对程序实现能力有有一定要求
我们可以定义出左右指针LR来控制Alice/Bob接下来吃的位置
定义op=0或1控制当前是谁吃
定义eat_L/eat_R表示吃的总数
定义pre_L/pre_R表示上一轮吃的数量
定义now_L/now_R表示当前这一轮吃的数量
定义ans=0表示总的玩的步骤数
那么就很好办了
写个while循环，一直玩，一直吃，吃一个以后判断要不要让给第二个人吃

#include<bits/stdc++.h>
using namespace std;
int A[8005];
int main() {int t;cin>>t;while(t--) {int n;cin>>n;for(int i=1; i<=n; i++) {cin>>A[i];}int L=1;int R=n;int eatL=0;int eatR=0;int last_L=0;int last_R=0;int cur_L=0;int cur_R=0;int ans=1;int op=0;//当前是谁吃  0  就是L吃   1R的那个人吃int sum=n;/*		总体逻辑就是ans=1  Alice的第一步是必定执行的吃了一段以后，判断能不能让给对方吃(前提是还有剩下没吃的糖果) 则ans++其余的就正常初始化  或者 变化  */ while(true) {if(sum==0)break;if(op==0) {eatL+=A[L];//总数cur_L+=A[L];//这一轮吃的sum--;L++;if(cur_L>last_R) {if(sum!=0)ans++;//交换op=(op+1)%2;last_L=cur_L;cur_L=0;continue;}continue;} else {eatR+=A[R];cur_R+=A[R];R--;sum--;if(last_L<cur_R) {if(sum!=0)ans++;//交换op=(op+1)%2;last_R=cur_R;cur_R=0;continue;}continue;}}cout<<ans<<" "<<eatL<<" "<<eatR<<'\n';}return 0;
}