Codeforces Round #577 (Div 2)

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;
}

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;
}

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;
}

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