Educational Codeforces Round 72 题解

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

A.Creating a Character

题意

有 $T$ 组测试数据,每组测试数据有 $str, int, exp$ 三个参数,可将 $str, int$ 增加, 增加的总和严格等于 $exp$ , 求有多少种方案使得增加后 $str > int$ 。

$T\le 100 \ , \ str,int,exp\le 10^8$ 。

题解

可以算出增加后 $str$ 的最小值,然后给 $str$ 分配后答案即为剩余的 $exp+1$ 。注意如果 $str$ 已经满足答案就是 $exp+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 t,a,b,c;

signed main()
{
    t=read();
    while (t--)
    {
        a=read(); b=read(); c=read();
        int mina=((a+b+c)>>1)+1;
        if (mina>=a) printf("%d\n",max(0,c-mina+a+1));
        else printf("%d\n",c+1);
    }
    return 0;
}

B.Zmei Gorynich

题意

$T$ 组测试数据。一条恶龙有 $x$ 个头, 你有 $n$ 个技能,每个技能无限使用:每次砍掉 $d_i$ 个头,长出 $h_i$ 个头,(砍掉后头数小于等于 $0$ 时不再生长)。 问:最少使用多少次技能可以杀死恶龙,如果无法杀死,输出 -1

题解

显然应该先一直砍 $d_i-h_i$ 最大的,直到剩下的头数 $\le d_{max}$ 再一次性全部砍掉。

特殊情况需要提前考虑。

#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 t,n,x,d[105],h[105];

signed main()
{
    t=read();
    while (t--)
    {
        n=read(); x=read();
        int maxD=0,maxDelta=0;
        for (int i=1;i<=n;i++)
        {
            d[i]=read(); h[i]=read();
            maxD=max(maxD,d[i]);
            maxDelta=max(maxDelta,d[i]-h[i]);
        }
        if (x<=maxD) { puts("1"); continue; } //直接取完
        if (maxDelta<=0) { puts("-1"); continue; } //无解
        int ans=(x-maxD+maxDelta-1)/maxDelta;
        printf("%d\n",ans+1);
    }
    return 0;
}

C.The Number Of Good Substrings

题意

令 $f(x_2)=x_{10}$ ,$x_2$ 为 $x$ 的二进制,可以有前导 $0$ 。问一个二进制串中有多少个子串 $x$ 满足 $f(x)=len_x$ 。

二进制串长度 $\le 200000$ 。

题解

$2^{18}=262144$ ,所以一个以 $1$ 开头的子串最多 $18$ 位。

我最开始就直接从每一位开始枚举 $20$ 位,然后就 $WA$ 了。后来才发现有可能有多个前导 $0$ ,所以可以预处理出 $i$ 右边的第一个 $1$ 的位置 $nxt[i]$(可以是 $i$),然后从 $nxt[i]$ 开始枚举 $20$ 位即可。

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

const int N=200005;
int t,n,nxt[N];
char s[N];

signed main()
{
    t=read();
    while (t--)
    {
        int ans=0;
        scanf("%s",s+1);
        n=strlen(s+1);
        nxt[n+1]=n+1;
        for (int i=n;i;i--)
        {
            nxt[i]=nxt[i+1];
            if (s[i]=='1') nxt[i]=i;
        }
        for (int i=1;i<=n;i++)
        {
            int cur=0,maxj=min(n,nxt[i]+19);
            for (int j=nxt[i];j<=maxj;j++)
            {
                cur=cur<<1|(s[j]-'0');
                if (cur==j-i+1) ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

D. Coloring Edges

题意

请给一个 $N$ 点 $M$ 边的有向图着色,使得没有一个环只有一个颜色,您需要最小化使用颜色的数量。

$N,M\le 5000$ 。

题解

可以发现如果没有环就只用 $1$ 种颜色,否则 $2$ 种。

然后对于输入的每一条边 $a\rightarrow b$ ,都以 $b$ 为起点搜索,如果 $a$ 被访问过就说明成环了,就把 $a\rightarrow b$ 染色;否则连边 $a\rightarrow b$ 。

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

const int N=5005;
struct Edge {
    int next,to;
} edge[N];
bool vis[N],col[N];
int cnt,head[N],n,m,a,b,ans;

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x)
{
    vis[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (vis[y]) continue;
        dfs(y);
    }
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        memset(vis,0,sizeof(vis));
        dfs(b);
        if (vis[a]) ans=col[i]=1;
        else add(a,b);
    }
    printf("%d\n",ans+1);
    for (int i=1;i<=m;i++) printf("%d ",col[i]+1);
    return 0;
}

新评论

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