又来 vp 了一场比赛\(\dots\dots\)
AtCoder Beginner Contest 200 vp记
Problem A
这道题不会有人要解析吧
Code
#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
int n;
signed main(){
n=read();
out(n/100+(n%100!=0));
return 0;
}
Problem B
暴力模拟即可
Code
#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
int n,k;
signed main(){
n=read(),k=read();
rep(i,k){
if(n%200==0)n/=200;
else n=n*1000+200;
}
out(n);
return 0;
}
Problem C
数学题，只要 \(a_i \equiv a_j\pmod{200}\)，那么\((a_i-a_j)\bmod200=0\)
所以可以开个数组统计同余即可
Code
#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
int n,sum,ans;
int a[200005],num[205];
signed main(){
n=read();
rep(i,n){
a[i]=read();
sum+=a[i];
num[a[i]%200]++;
}
// num[0]++;
repe(i,0,200){
ans=ans+(num[i]-1)*num[i]/2;
}
out(ans);
return 0;
}
Problem D
人类智慧题，可以发现，当我们有 201 个序列时，就必定有两个序列同余，又知 \(2^8=256 \ge 200\)，我们就可以将 n 缩小到 8，然后状压枚举。
Code
#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
int n;
const int N=205;
int a[N];
int v[300];
void print(int id){
int cnt=0;
rep(i,n){
if(id&(1<<i-1))++cnt;
}
cout<<cnt<<' ';
rep(i,n){
if(id&(1<<i-1))cout<<i<<' ';
}
puts("");
}
signed main(){
n=read();
rep(i,n)a[i]=read();
int m=min(n,8ll);
for(int i=1;i<(1<<m);i++){
int sum=0;
rep(j,n){
if(i&(1<<j-1))sum+=a[j],sum%=200;
}
if(v[sum]){
puts("Yes");
print(v[sum]);
print(i);
exit(0);
}
v[sum]=i;
}
puts("No");
return 0;
}
Problem E
对于这道题目，我们可以先算出第 k 个蛋糕是在和为多少的序列中，然后再算出是在美丽值的值，最后确定美味程度。
我们可以令 \(dp[i][j]\) 表示在和为 \(i\) 的情况下确定 \(j\) 个元素的方案数，不难想出，我们要确定第 k 个蛋糕所在的三元组之和，要找到的就是第一个 \(sum\) 使得 $$\sum_{i=1}^{sum}dp[i][3]>k$$ 第一个数等后面的同理。
这道题目整个的思路都是顺其自然的，写代码时需要注意些细节即可。
Code
#include<bits/stdc++.h>
#define int long long
#define repe(i,l,r) for(int (i)=l;(i)<=r;(i)++)
#define rep(i,n) for(int (i)=1;(i)<=n;(i)++)
#define FOR(i,r,l) for(int (i)=r;(i)>=l;(i)--)
#define INF 0x3f3f3f
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define ALL(v) (v).begin(),(v).end()
#define rsort(v) sort(ALL(v),greater<int>())
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
template <typename T>void die(T s){cout<<s<<endl;exit(0);}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template <typename T>void chkmax(T& a,T b){if(a<b)a=b;return;}
template <typename T>void chkmin(T& a,T b){if(a>b)a=b;return;}
int dp[3000005][4];
int sum[3000005][4];
int n,k,num,fi,se;
signed main(){
n=read(),k=read();
rep(i,n)dp[i][1]=1,sum[i][1]=i;
repe(i,2,2*n){
dp[i][2]=sum[min(i-1,n)][1]-sum[max(i-n,1ll)-1][1];
sum[i][2]=sum[i-1][2]+dp[i][2];
}
repe(i,3,3*n){
dp[i][3]=sum[min(i-1,2*n)][2]-sum[max(i-n,2ll)-1][2];
sum[i][3]=sum[i-1][3]+dp[i][3];
}
for(num=3;num<=3*n;num++){
if(k>dp[num][3])k-=dp[num][3];
else break;
}
for(fi=1;fi<=num-2;fi++){
if(k>dp[num-fi][2])k-=dp[num-fi][2];
else break;
}
for(se=1;se<=num-1-fi;se++){
if(num-fi-se>=1&&num-fi-se<=n&&k)--k;
if(!k)break;
}
cout<<fi<<' '<<se<<' '<<num-fi-se<<endl;
return 0;
}