Codeforces Round #577 (Div. 2) 题解

题解 比赛-Codeforces
题目链接 编辑文章

A.Important Exam

题意

有 $N$ 个人考 $M$ 道题 ,给出每个人每道题的答案,求如何安排每道题的正确答案,使得所有人获得的分数总和最大。

$N,M\le 1000$ 。

题解

真理掌握在大多数人手中。
#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

char s[1005];
int n,m,cnt[1005][26],v[1005];

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for (int j=1;j<=m;j++) cnt[j][s[j]-'A']++;
    }
    for (int i=1;i<=m;i++) v[i]=read();
    int ans=0;
    for (int i=1;i<=m;i++)
    {
        int mx=0;
        for (int j=0;j<26;j++) mx=max(mx,cnt[i][j]);
        ans+=mx*v[i];
    }
    return !printf("%d",ans);
}

B.Zero Array

题意

有一个长度为 $N$ 的序列,每次可以选择两个数 $-1$ ,问能否全部减为 $0$ 。

$N\le 10^5$ 。

题解

如果总和为奇数,显然无解。

然后可以大胆猜想,只要不存在一个数使得其它数加起来都 $<$ 它,那么就是有解的。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,s[100005];

signed main()
{
    n=read();
    long long sum=0;
    for (int i=1;i<=n;i++) s[i]=read(),sum+=s[i];
    if (sum&1) return 0&puts("NO");
    sort(s+1,s+n+1);
    if (sum-s[n]<s[n]) return 0&puts("NO");
    return 0&puts("YES");
}

C.Maximum Median

题意

一个长度为 $N$ 的数列,每次操作可以选择一个数 $+1$ ,一共可以进行 $K$ 次操作。问操作完后中位数最大是多少?

$N\le 200000 \ , \ K\le 10^9$ 。

题解

给中位数之前的数加是没有意义的,所以先排一遍序找到中位数。

接下来的过程可以理解成找到中位数 $m$ 后面的一个数 $x$,把 $[m,x]$ 的所有数都变成 $x$ 。可以枚举找到最大的 $x$ 。

$K$ 可能还能剩下,那么就把 $K$ 平均分给 $[m,x]$ 的每个数。我最开始平均分的 $[m,N]$ WA了无数次

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

ll n,m,k,s[200005];

signed main()
{
    n=read(); k=read();
    for (ll i=1;i<=n;i++) s[i]=read();
    sort(s+1,s+n+1);
    m=(n>>1)+1;
    ll ans=s[m],lasti=m;
    for (int i=m+1;i<=n;i++)
    {
        if ((s[i]-s[i-1])*(i-m)<=k)
        {
            k-=(s[i]-s[i-1])*(i-m);
            ans=s[i];
            lasti=i;
        }
        else break;
    }
    return !printf("%lld",ans+k/(lasti-m+1));
}

D.Treasure Hunting

题意

有一个$n\times m$的矩阵,行的标号从 $1$ 到 $n$ ,列的标号从 $1$ 到 $m$ ,矩阵中共有 $k$ 个宝藏,第 $i$ 个宝藏的位置为 $(r_i,c_i)$ 。有 $q$ 个安全的列,第 $i$ 个安全的列的编号是 $b_i$ 。

从 $(1,1)$ 出发。可以自由的向左向右走;只有安全列可以向上走;不能向下走。问至少要多少步才能收集所有宝藏。

题解

用 $f[i][0/1]$ 表示到第 $i$ 行,取完所有宝藏后在 左/右边 的最小步数。

可以发现最优情况一定是从离 另一侧 最近的两个安全通道上来(左右两个),所以二分查找一下即可。

注意如果当前行没有宝藏就直接上去,但要继承上一行 $l[i],r[i]$ 的值。初值处理也需要注意。

还有只需要取完宝藏,不一定要走完。所以先得到最大的 $r_i$ ,搜索到那一层即可。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const ll N=200005;
ll n,m,k,q,x,y,l[N],r[N],s[N],f[N][2];

signed main()
{
    memset(l,0x3f,sizeof(l));
    n=read(); m=read(); k=read(); q=read();
    ll maxX=0;
    for (ll i=1;i<=k;i++)
    {
        x=read(); y=read();
        maxX=max(maxX,x);
        l[x]=min(l[x],y);
        r[x]=max(r[x],y);
    }
    for (ll i=1;i<=q;i++) s[i]=read();
    sort(s+1,s+q+1);
    if (r[1])
    {
        f[1][0]=r[1]*2-1-l[1];
        f[1][1]=r[1]-1;
    }
    else l[1]=r[1]=1;
    for (ll i=2;i<=n;i++)
    {
        if (!r[i])
        {
            f[i][0]=f[i-1][0]+1;
            f[i][1]=f[i-1][1]+1;
            l[i]=l[i-1];
            r[i]=r[i-1];
            continue;
        }
        ll L=*(upper_bound(s+1,s+q+1,r[i])-1),R=*lower_bound(s+1,s+q+1,r[i]); //右侧最近的通道
        f[i][0]=1e18;
        if (L)
        {
            f[i][0]=min(f[i][0],f[i-1][1]+abs(r[i-1]-L)+abs(r[i]-L));
            f[i][0]=min(f[i][0],f[i-1][0]+abs(l[i-1]-L)+abs(r[i]-L));
        }
        if (R)
        {
            f[i][0]=min(f[i][0],f[i-1][1]+abs(r[i-1]-R)+abs(r[i]-R));
            f[i][0]=min(f[i][0],f[i-1][0]+abs(l[i-1]-R)+abs(r[i]-R));
        }
        f[i][0]+=r[i]-l[i]+1; //还有向上的一步以及从右到左
        L=*(upper_bound(s+1,s+q+1,l[i])-1),R=*lower_bound(s+1,s+q+1,l[i]);
        f[i][1]=1e18;
        if (L)
        {
            f[i][1]=min(f[i][1],f[i-1][0]+abs(l[i-1]-L)+abs(l[i]-L));
            f[i][1]=min(f[i][1],f[i-1][1]+abs(r[i-1]-L)+abs(l[i]-L));
        }
        if (R)
        {
            f[i][1]=min(f[i][1],f[i-1][0]+abs(l[i-1]-R)+abs(l[i]-R));
            f[i][1]=min(f[i][1],f[i-1][1]+abs(r[i-1]-R)+abs(l[i]-R));
        }
        f[i][1]+=r[i]-l[i]+1;
    }
    return !printf("%lld",min(f[maxX][0],f[maxX][1]));
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空