A. Important Exam

水题

#include#include<string.h>#include#includeusing 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){        scanf("%s",a[i]);     }     for (int i=0;i){        scanf("%d",&b[i]);     }     for (int i=0;i){        int sum[5]={0,0,0,0,0};        for (int j=0;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){        ans+=(long long)pre[i]*b[i];     }     printf("%lldn",ans);  }  return 0;}

B. Zero Array

这道题就非常难受了

题意就是说，你有一个序列，你每次可以选择两个数，使得这两个数的值减小1。

最开始不知道为啥，脑子短路了，我发现只要把最大的减去最小的，然后用剩下的去减次小的，用剩下的继续减去

而且找不到反例，后面同学讨论一波，同学提出了一个2,2,2的样例，瞬间把我的结论推翻了。

后面也发现了我的结论的不正确，因为我每次把最大的减去次大的，那么不可避免的产生了一个新的数，这个数的大小我们没法判断，如果这个值过小，但是后面还有一个比这个值大的数。其实就不正确的。

其实你可以这样想，既然要求有没有可能，我们的顺序最优秀的，我们发现，其实每次把最高的降到次高的即可。这样我们保证一定是最有效的。但是有两个特殊情况，一个是数的总和是奇数那么无论怎么样

都会剩下一个。还有就是最高的太高了，用其他的所有都不能降到0，特判这两种情况即可

#include#include#include<string.h>#include#define LL long longusing 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("YESn");      }else {        printf("NOn");      }   }   return 0;}

C. Maximum Median

每次对一个数+1，一共可以进行K次，问最大中位数是多少。

二分答案即可

#include#include#include<string.h>#include#include#define LL long longusing 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("%lldn",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#include#include<string.h>#include#include#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#define mp make_pairusing 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("%lldn",min(dp[j][0],dp[j][1]));  }  return 0;}