Codeforces Round #581 (div. 2) 题解

补的，这真是一场神仙Round。

A.BowWow and the Timetable

题意

题解

可以发现一般情况下答案只与最高位有关，但如果是刚好 $4^x$ 的话就需要看后面有没有 $1$ ，如果没有那答案要 $-1$ 。

#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,ans;
char s[105];

signed main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    reverse(s+1,s+n+1);
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        if (s[i]=='1')
        {
            ans=max(ans,(i+1)>>1);
            if (n&1 && i==n && !cnt) ans--;
            cnt++;
        }
    }
    return !printf("%d",ans);
}

B.Mislove Has Lost an Array

题意

题解

贪心。最小的情况就是加到 $l$ ，剩下全为 $1$ ；最大就加到 $r$ ，剩下全为 $2^{r-1}$ 。

#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,l,r;

signed main()
{
    n=read(); l=read(); r=read();
    int ans=0,cur=1;
    for (int i=1;i<=l;i++) ans+=cur,cur<<=1;
    printf("%d ",ans+n-l);
    ans=0,cur=1;
    for (int i=1;i<=r;i++) ans+=cur,cur<<=1;
    cur>>=1;
    return !printf("%d",ans+(n-r)*cur);
}

C.Anna, Svyatoslav and Maps

题意

简单的说就是固定最少的点，使得任意固定的两点之间最短路径之一是原路径。

题解

可以先用 $\text{Floyd}$ 跑出两两之间的最短路。

首先固定起点 $P_1$ 。然后从 $i=3$ 开始遍历 $P_i$ ，如果固定的最后一个点 $P_{last} \rightarrow P_i \le P_{last+1}\rightarrow P_i$ ，那么就固定 $P_{i-1}$ ，同时更新 $last=i-1$。

#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,m,dis[105][105],p[1000005],ans[1000005],acnt;

signed main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        char ch[105]; scanf("%s",ch+1);
        for (int j=1;j<=n;j++) dis[i][j]=(i==j) ? 0 : (ch[j]=='1') ? 1 : 1e9;
    }
    m=read();
    for (int i=1;i<=m;i++) p[i]=read();
    for (int k=1;k<=n;k++)
    {
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                if (dis[i][k]+dis[k][j]>=dis[i][j]) continue;
                dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    ans[++acnt]=p[1];
    int cnt=1; //cnt就是 Plast->Pi 的距离
    for (int i=3;i<=m;i++)
    {
        if (dis[ans[acnt]][p[i]]>cnt) cnt++;
        else ans[++acnt]=p[i-1],cnt=1;
    }
    ans[++acnt]=p[m];
    printf("%d\n",acnt);
    for (int i=1;i<=acnt;i++) printf("%d ",ans[i]);
    return 0;
}

D.Kirk and a Binary String

题意

题解

可以发现一定是把原序列中的 $1$ 变成 $0$ ，那么题目就变成了选一些 $1\rightarrow 0$ 。

当一个数是 $1$ 时，它只能连接后面的 $1$ ；变 $0$ 后就能连 $0$ 了，所以只要它后面 $0$ 的个数 $\le$ $1$ 的个数，那么就可以选它。

至于以它为终点的区间，因为它前面连续的 $1$ 也会随之被删掉，所以它们之间的不降序列个数不变。

#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;
char s[100005];

signed main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    int sum=0; //0与1个数的差
    for (int i=n;i;i--)
    {
        if (s[i]=='0') sum++;
        else if (sum) sum--;
        else s[i]='0';
    }
    return !printf("%s",s+1);
}