AtCoder Beginner Contest 222 个人题解
比赛链接：AtCoder Beginner Contest 222
A题 Four Digits
题目大意：
给你一个不超过四位的数，补充前导零
思路解析：
printf()
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
printf("%04d",n);
}
B题 Failing Grade
题目大意：
给出 $n$ 个学生的分数和及格分数，输出不及格的人数
思路解析：
模拟
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,p;
cin>>n>>p;
for(int i=1;i<=n;i++){
int op;
cin>>op;
if(op<p)ans++;
}
cout<<ans<<endl;
}
C题 Swiss-System Tournament
题目大意：
$2*n$ 个人两两猜拳，一共玩 $m$ 轮，给出每个人在轮中的抉择，而且每一轮都是当前的排位第一与第二比赛，第三与第四比赛，以此类推
输出最终的排位名次
思路解析：
模拟
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=500;
char a[maxn][maxn];
struct node{
int p,rk;
}b[maxn];
bool cmp(node x,node y){
if(x.rk==y.rk)return x.p<y.p;
return x.rk>y.rk;
}
int sum[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n*2;i++){
b[i].p=i;
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int k=1;k<=m;k++){
memset(sum,0,sizeof sum);
for(int i=1;i<=n*2;i+=2){
if(a[b[i].p][k]=='G'&&a[b[i+1].p][k]=='C')sum[b[i].p]++;
if(a[b[i].p][k]=='G'&&a[b[i+1].p][k]=='P')sum[b[i+1].p]++;
if(a[b[i].p][k]=='C'&&a[b[i+1].p][k]=='G')sum[b[i+1].p]++;
if(a[b[i].p][k]=='C'&&a[b[i+1].p][k]=='P')sum[b[i].p]++;
if(a[b[i].p][k]=='P'&&a[b[i+1].p][k]=='C')sum[b[i+1].p]++;
if(a[b[i].p][k]=='P'&&a[b[i+1].p][k]=='G')sum[b[i].p]++;
}
for(int i=1;i<=n*2;i++){
b[i].rk+=sum[b[i].p];
}
sort(b+1,b+n*2+1,cmp);
}
for(int i=1;i<=2*n;i++){
cout<<b[i].p<<endl;
}
}
D题 Between Two Arrays
题目大意：
给出等长的 $a$ 序列和 $b$ 序列，其中 $b_i>=a_i$ ,另外我们需要找到 $c$ 序列，使得 $a_i<=c_i<=b_i$ ，求 $c$ 序列的方案数
思路解析：
很明显的 $dp$ ，定义 $dp[i][j]$ 为 $c$ 序列前 $i$ 个，最后一位不大于 $j$ 的方案数，然后我们考虑转移方程，对于当前第 $i$ 个数，它可以由当前位比它小的数叠加过来，即 $dp[i][j]+=dp[i][j-1]$ ，另外一部分可以由上一位的最大数累加过来，但是上一位的当前数不能大于当前位的数，即 $dp[i][j]+=dp[i-1][min(j,b[i-1])]$
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=3005;
const int mod=998244353;
ll dp[maxn][maxn];
int a[maxn],b[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=a[1];i<=b[1];i++){
dp[1][i]=i-a[1]+1;
}
for(int i=2;i<=n;i++){
for(int j=a[i];j<=b[i];j++){
dp[i][j]+=dp[i][j-1]+dp[i-1][min(j,b[i-1])];
dp[i][j]%=mod;
}
}
cout<<dp[n][b[n]]<<endl;
}
