Codeforces Round #577 (Div 2)"/>
Codeforces Round #577 (Div 2)
A. Important Exam
水题
#include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> using namespace std; const int maxx = 1005; char a[maxx][maxx]; int pre[maxx]; int b[maxx]; int main(){int n,m;while(~scanf("%d%d",&n,&m)){for (int i=0;i<n;i++){scanf("%s",a[i]);}for (int i=0;i<m;i++){scanf("%d",&b[i]);}for (int i=0;i<m;i++){int sum[5]={0,0,0,0,0};for (int j=0;j<n;j++){if (a[j][i]=='A'){sum[0]++;}else if (a[j][i]=='B'){sum[1]++;}else if (a[j][i]=='C'){sum[2]++;}else if (a[j][i]=='D'){sum[3]++;}else {sum[4]++;}}int maxx=0;for (int i=0;i<=4;i++){maxx=max(maxx,sum[i]);}pre[i]=maxx;}long long ans=0;for (int i=0;i<m;i++){ans+=(long long)pre[i]*b[i];}printf("%lld\n",ans);}return 0; }View Code
B. Zero Array
这道题就非常难受了
题意就是说,你有一个序列,你每次可以选择两个数,使得这两个数的值减小1。
最开始不知道为啥,脑子短路了,我发现只要把最大的减去最小的,然后用剩下的去减次小的,用剩下的继续减去
而且找不到反例,后面同学讨论一波,同学提出了一个2,2,2的样例,瞬间把我的结论推翻了。
后面也发现了我的结论的不正确,因为我每次把最大的减去次大的,那么不可避免的产生了一个新的数,这个数的大小我们没法判断,如果这个值过小,但是后面还有一个比这个值大的数。其实就不正确的。
其实你可以这样想,既然要求有没有可能,我们的顺序最优秀的,我们发现,其实每次把最高的降到次高的即可。这样我们保证一定是最有效的。但是有两个特殊情况,一个是数的总和是奇数那么无论怎么样
都会剩下一个。还有就是最高的太高了,用其他的所有都不能降到0,特判这两种情况即可
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define LL long long using namespace std; const int maxx = 1e5+9; int a[maxx]; LL sum; int main(){int n;while(~scanf("%d",&n)){sum=0;for (int i=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];}sort(a+1,a+1+n);if (sum%2==0 && sum-a[n]>=a[n]){printf("YES\n");}else {printf("NO\n");}}return 0; }View Code
C. Maximum Median
每次对一个数+1,一共可以进行K次,问最大中位数是多少。
二分答案即可
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #define LL long long using namespace std; const int maxx = 200005; LL a[maxx]; LL n,k; bool check(LL x){LL ans=0;for (int i=(n+1)/2;i<=n;i++){if (a[i]<x){ans=(LL)ans+x-a[i];}}if (ans<=k)return true;else return false; } int main(){while(~scanf("%lld%lld",&n,&k)){for (int i=1;i<=n;i++){scanf("%lld",&a[i]);}sort(a+1,a+1+n);LL l=a[(n+1)/2],r=3e9;LL ans=l;while(l<=r){LL mid=(l+r)/2;if (check(mid)){ans=mid;l=mid+1;}else {r=mid-1;}}printf("%lld\n",ans);}return 0; }View Code
D. Treasure Hunting
好题啊,这个题真的很秀,当时没看到这个题,后面看别人的代码+题解,懂了
题目意思是,给一些的坐标点,坐标点上会有宝藏,你可以在每一行中随意移动,并在指定的列中往下移动,问如何移动能收集所有的宝藏,同时使得移动的步数最少
你可以发现以下结论
1.我们在每一层搜集完了所有的宝藏后,应该尽快往下一层走。搜集完所有的时刻,一定是在某一个边界位置,可能是左边界,也有可能是右边界
2.我们每次下到新的一层,一定是从边界位置开始(因为那个时候刚好收集完成),向左走,找到最近的向下走的通道,或者向右走,找到最近向下走的通道
3.我们到达新的一层后,需要判断是否这一层有宝藏
4.如果有宝藏,我们需要考虑,是先往左走搜集完左边的,然后再向右走收集到最右边的,还是先向右走搜集完右边的,然后向左走搜集完最左边的
有了这个,我们的DP就非常好写了
转移方程为
dp[i][0]表示收集完第i层,最后在最左边
dp[i][1]表示收集完第i层,最后在最右边
用trans()计算从第j层边界到i层边界,水平移动的步数。
那么转移方程可以写为:
dp[1][0]=abs(maxn[1][1]-1)+abs(maxn[1][1]-maxn[1][0]);//从起点开始,走到最右边,再走回来dp[1][1]=abs(maxn[1][1]-1);//从起点开始,走到最右边dp[i][0]=min(dp[i][0],dp[j][0]+trans(j,0,i,0)+i-j);dp[i][0]=min(dp[i][0],dp[j][1]+trans(j,1,i,0)+i-j);dp[i][1]=min(dp[i][1],dp[j][0]+trans(j,0,i,1)+i-j);dp[i][1]=min(dp[i][1],dp[j][1]+trans(j,1,i,1)+i-j);
前两个都是计算初始值
四个分别表示
从第j层左边界最后到第i层左边边界,搜集完第i层所需要的步数
从第j层左边界最后到第j层右边边界,搜集完第i层所需要的步数
从第j层右边界最后到第j层左边边界,搜集完第i层所需要的步数
从第j层右边界最后到第j层右边边界,搜集完第i层所需要的步数
最后在找边界的从左右两边找到最近的通道,用二分查找即可。
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<vector> #define LL long long #define rep(i,j,k) for(int i=j;i<=k;i++) #define per(i,j,k) for(int i=j;i>=k;i--) #define pb push_back #define pii pair<int,int> #define mp make_pair using namespace std; using namespace std; const int maxx = 2e5+10; const int INF = 1e9; LL maxn[maxx][2]; LL dp[maxx][2]; int n,m,k,q; int b[maxx]; LL trans(int u,int du,int v,int dv){int p=lower_bound(b+1,b+1+q,maxn[u][du])-b;LL rt=INF;//找到第一个小于maxn[u][du]if(p<=q){rt=abs(maxn[u][du]-b[p])+abs(maxn[v][dv^1]-b[p])+abs(maxn[v][dv]-maxn[v][dv^1]);//我们找到abs(maxn[u][du]-b[p])+abs(maxn[v][dv^1]-b[p])+abs(maxn[v][dv]-maxn[v][dv^1])了一条路后,水平消耗的路程,应该是出发点的通路的距离,以及到达目的层后,目标方向的反向的最远距离,以及目标防方向的最远距离 }p=upper_bound(b+1,b+1+q,maxn[u][du])-b-1;if(p){rt=min(rt,abs(maxn[u][du]-b[p])+abs(maxn[v][dv^1]-b[p])+abs(maxn[v][dv]-maxn[v][dv^1]));}return rt; } int main(){while(~scanf("%d%d%d%d",&n,&m,&k,&q)){rep(i,1,n){maxn[i][0]=INF;maxn[i][1]=-INF;}LL x,y;rep(i,1,k){scanf("%lld%lld",&x,&y);maxn[x][0]=min(maxn[x][0],y);maxn[x][1]=max(maxn[x][1],y);}maxn[1][0]=1;maxn[1][1]=max(maxn[1][1],1LL);rep(i,1,q){scanf("%d",&b[i]);}sort(b+1,b+1+q);memset(dp,0x3f,sizeof(dp));dp[1][0]=abs(maxn[1][1]-1)+abs(maxn[1][1]-maxn[1][0]);//从起点开始,走到最右边,再走回来dp[1][1]=abs(maxn[1][1]-1);//从起点开始,走到最右边int j=1;rep(i,2,n){if (maxn[i][0]==INF)continue;dp[i][0]=min(dp[i][0],dp[j][0]+trans(j,0,i,0)+i-j);dp[i][0]=min(dp[i][0],dp[j][1]+trans(j,1,i,0)+i-j);dp[i][1]=min(dp[i][1],dp[j][0]+trans(j,0,i,1)+i-j);dp[i][1]=min(dp[i][1],dp[j][1]+trans(j,1,i,1)+i-j);j=i;}printf("%lld\n",min(dp[j][0],dp[j][1]));}return 0; }
转载于:.html
更多推荐
Codeforces Round #577 (Div 2)
发布评论