Codeforces Educational Round 34划水报告

本文主要是介绍Codeforces Educational Round 34划水报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A到E题
A. Hungry Student Problem
题意:给n个数，问这些数能不能拆成 $3*x+7*y(x>=0,y>=0)$ 的形式
直接暴力枚举3的倍数计算

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=100000+10;
int A[maxn];
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n;scanf("%d",&n);int x;for(int i=1;i<=n;i++){scanf("%d",&x);int ok=0;for(int j=0;j<=x/3;j++)if((x-3*j)%7==0)ok=1;if(ok)puts("YES");else puts("NO");}
return 0;
}

B. The Modcrab
题意:一个人打怪，每回合可以嗑药或攻击,每回合也会受到怪物伤害,问保证存活的情况下,最少几回合打完,并输出每回合策略.(这个人是先手,也就是先手打死怪物就结束了,不会受到怪物攻击)
贪心,能打就打，不能就嗑药

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=200000+10;
int ans[maxn];
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int A,B,C,D,E;cin>>A>>B>>C>>D>>E;//cout<<A<<' '<<B<<' '<<C<<' '<<D<<' '<<E<<endl;int cnt=0;while(D>0){cnt++;//printf("%d\n",D);A-=E,D-=B;if(D>0&&A<=0){D+=B;A+=C;ans[cnt]=2;}else if(D<=0||A>0){ans[cnt]=1;}}printf("%d\n",cnt);for(int i=1;i<=cnt;i++){if(ans[i]==1)puts("STRIKE");else puts("HEAL");}
return 0;
}

C. Boxes Packing
给一些立方体盒子,边长严格小于这个盒子的盒子可以放在这个盒子里，且只能放一个，问最少剩多少盒子
贪心
显然如果两个盒子都能放，肯定先放边长长的,因为可能再把其他较小的盒子再放到它里面
排过序之后合并就行了
时间复杂度O(n^2)

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100000+10;
int A[maxn];
int vis[maxn];
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n;scanf("%d",&n);int x;for(int i=1;i<=n;i++)scanf("%d",&A[i]);sort(A+1,A+n+1);int cnt=0;for(int i=1;i<=n;i++){if(vis[i])continue;cnt++;vis[i]=1;int nw=A[i];for(int j=i+1;j<=n;j++)if(!vis[j]&&A[j]>nw){vis[j]=1;nw=A[j];}}printf("%d\n",cnt);
return 0;
}

D. Almost Difference
题意:
定义贡献
给你一列数A[i],求 $\sum_{i=1}^{n}\sum_{j=i}^{n}d(A[i],A[j])$
如果贡献只有上半部分的话对于 $i$ 贡献即为 $\sum_{j=i}^nA[j]-A[i]*(n-i+1)$
考虑多算的,即 $A[i]+1$ 和 $A[i]-1$ 的负贡献,为 $\sum_{j=i}^n([A[j]==A[i]+1]|[A[j]==A[i]-1])*(A[j]-A[i])$
即贡献要减去 $A[i]+1$ 的个数加 $A[i]-1$ 的个数
离散化后开个桶统计
答案会超过 $10^18$ ,用long double存,最后保留小数点输出

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
using namespace std;
const int maxn=200000+10;
int A[maxn];
int hsh[maxn];
int B[maxn];
int cnt[maxn];
int tt;
int bs(int x){int l=1,r=tt;while(l+1<r){int mid=(l+r)>>1;if(hsh[mid]>=x)r=mid;else l=mid;}if(hsh[l]==x)return l;return r;
}
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&A[i]),B[i]=A[i];sort(B+1,B+n+1);hsh[++tt]=B[1];for(int i=2;i<=n;i++)if(B[i]!=B[i-1])hsh[++tt]=B[i];long double tot=0;long long sum=0;for(int i=n;i>=1;i--){int t=bs(A[i]);cnt[t]++;sum+=A[i];long long res=sum-(long long)A[i]*(n-i+1);if(t!=1)if(hsh[t-1]==hsh[t]-1)res+=cnt[t-1];if(t!=tt)if(hsh[t+1]==hsh[t]+1)res-=cnt[t+1];tot+=res;}cout << setiosflags(ios::fixed) << setprecision(0) << tot;
return 0;
}

E. Swapping Characters
题意:
给你一些字符串，问是否存在一个字符串，使得将这个字符串中交换两个字符的位置能否表示这些字符串
考虑如果能表示,那交换第一个字符串的两个字符的位置，在将得到的字符串交换两个字符的位置一定能表示所有字符串
暴力枚举交换的位置，在O(k)匹配
如果两个字符串不同的位置个数>4那么一定不能
如果两个字符串字母组成不同，那么一定不能

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char A[2510][5010];
int dif[2510][10];
int cnt[2510];
int num[30];
int tmp[30];
int hv[2510];
inline int judge(int x,int y,int z){int clt=0;int hvx=0,hvy=0;for(int i=1;i<=cnt[z];i++){if(dif[z][i]==x)hvx=1;if(dif[z][i]==y)hvy=1;}if(!hvx&&!hvy){clt+=(A[1][y]!=A[z][x]);clt+=(A[1][x]!=A[z][y]);}if(hvx&&!hvy){clt-=(A[1][y]==A[z][x]);clt+=(A[1][x]!=A[z][y]);}if(hvy&&!hvx){clt-=(A[1][x]==A[z][y]);clt+=(A[1][y]!=A[z][x]);}if(hvy&&hvx){clt-=(A[1][x]==A[z][y]);clt-=(A[1][y]==A[z][x]);}return cnt[z]+clt;
}
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int k,n;scanf("%d %d",&k,&n);for(int i=1;i<=k;i++){memset(tmp,0,sizeof(tmp));for(int j=1;j<=n;j++){cin>>A[i][j];if(i==1)num[A[i][j]-'a']++;else tmp[A[i][j]-'a']++;}int ok=1;if(i!=1){for(int j=0;j<26;j++){if(tmp[j]!=num[j])ok=0;if(tmp[j]>1)hv[i]=1;}if(!ok){puts("-1");return 0;}}}for(int i=2;i<=k;i++){for(int j=1;j<=n;j++)if(A[1][j]!=A[i][j])dif[i][++cnt[i]]=j;if(cnt[i]>4){puts("-1");return 0;}}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){int ok=1;for(int l=2;l<=k;l++){if(judge(i,j,l)>2||(judge(i,j,l)==0&&!hv[l]))ok=0;}if(ok){swap(A[1][i],A[1][j]);for(int l=1;l<=n;l++)printf("%c",A[1][l]);return 0;}}puts("-1");
return 0;
}