A题
简单的模拟一下即可
void solve(){
ll a,b,c;
cin>>n>>a>>b>>c;
ll cnt=n/a;
n%=a;
cnt+=n/b;
n%=b;
cnt+=n/c;
cout<<cnt;
}
B题
找到最大值和最小值的均值,但是有可能最大值和最小值相加是一个奇数,所以我是分成两个来考虑(min+max)/2和(max+min+1)/2,代码看起来有点复杂,但是思路挺简单的。
void solve(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
ma=max(ma,a[i]);
mi=min(mi,a[i]);
}
ll ans=(ma+mi)/2,ans1=(mi+ma+1)/2;
ll cnt=0,cnt1=0,cnt2=0,cnt3=0;
for(int i=0;i<n;i++){
if(a[i]>ans) cnt=max(cnt,a[i]-ans);
else cnt1=max(cnt1,ans-a[i]);
if(a[i]>ans1) cnt2=max(cnt2,a[i]-ans1);
else cnt3=max(cnt3,ans1-a[i]);
}
if(cnt+cnt1>cnt2+cnt3) cout<<cnt+cnt1<<' '<<ans;
else cout<<cnt2+cnt3<<' '<<ans1;
}
C题
从头开始遍历,千万不能从尾开始遍历,因为后面的操作不能完全覆盖前面的操作,比如两次都是操作一,并且都是同一列,由题可得第二次操作是没用的。思路:对于操作一,如果这个列是第一次操作的话是可以直接操作的,也就是从头到尾遍历行,如果在前面被操作过了,那么我们就只要改变哪些被铲除的哪些格子就行了(使用set可以完成,而且可以防止他重复对同一个格子使用操作二,达到去重的效果);对于操作二,我们只要看这个格子有没有植物,有植物的话就异或他自己(因为a^a=0),并且把这个格子的行号存入对应的set中去,没有植物不需要操作。
unsigned seed;
unsigned rnd(){
unsigned ret=seed;
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return ret;
}
void solve(){
cin>>n>>m>>k>>seed;
unsigned op,j,x,a,b;
ll ans=0;
int r[205]={0},tu[20005][205]={0};
set<int> s[m+1];//s[j]表示第j行有没有被铲除的植物
while(k--){
op=rnd()%2+1;
if(op==1){
j=rnd()%m+1;x=rnd()%(n*m)+1;
if(r[j]==0){
for(int i=1;i<=n;i++){
ans^=x*((i-1)*m+j);
tu[i][j]=x;
}
r[j]=1;
}
else if(s[j].size()!=0){
for(auto t:s[j]){
ans^=x*((t-1)*m+j);
tu[t][j]=x;
}
s[j].clear();
}
}
else{
a=rnd()%n+1;b=rnd()%m+1;
if(tu[a][b]!=0) ans^=tu[a][b]*((a-1)*m+b),tu[a][b]=0,s[b].insert(a);
}
}
cout<<ans;
}
E题
只要理解好题目就很简单,度数就是代码他可以连接的最大边数,而已一个n个点的图,最少有n-1条边才可以连通, 所以只要找出最小的n-1条边就可以了
struct xx{
ll a,d;
bool operator<(const xx &t)const{
return a<t.a;
}
}eg[N];
void solve(){
cin>>n;
for(int i=0;i<n;i++) cin>>eg[i].a;
for(int i=0;i<n;i++) cin>>eg[i].d;
sort(eg,eg+n);
ll res=0,cnt=0;
for(int i=0;i<n;i++){
//cout<<eg[i].a<<' '<<eg[i].d<<'\n';
if(cnt+eg[i].d<=n-1) res+=eg[i].a*eg[i].d,cnt+=eg[i].d;
else {res+=eg[i].a*(n-1-cnt);break;}
}
cout<<res;
}