Codeforces Round #584 题解

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

感冒了没打,亏死了,后来补的。

为了节约时间,洛谷上有较好翻译的我就直接贴链接了,懒得自己写了。

A.Paint the Numbers

题意

题解

每次找最小的数然后把后面的筛完就行了。

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

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    sort(s+1,s+n+1);
    for (int i=1;i<=n;i++)
    {
        if (!s[i]) continue;
        ans++;
        for (int j=i+1;j<=n;j++) if (s[j]%s[i]==0) s[j]=0;
    }
    return !printf("%d",ans);
}

B.Koala and Lights

题意

有 $n(n\le 100)$ 个灯泡,给出每个灯泡最初的状态,第 $i$ 个灯泡从第 $b_i(b_i\le 5)$ 秒开始改变状态,每 $a_i(a_i\le 5)$ 秒改变一次。问最多能同时亮几个灯泡?

题解

可以发现周期最多为 ${5!}=120$ ,还有个 $b_i$ 那就枚举 $125$ 秒即可得到答案。

#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,a,b;
char s[105];
bool f[105][126];

signed main()
{
    n=read();
    scanf("%s",s+1);
    for (int i=1;i<=n;i++)
    {
        a=read(); b=read(); s[i]-='0';
        for (int j=1;j<=b;j++) f[i][j]=s[i];
        for (int j=b+1,k=1,cur=s[i]^1;j<=125;j++,k++)
        {
            if (k>a) cur^=1,k-=a;
            f[i][j]=cur;
        }
    }
    int ans=0;
    for (int i=1;i<=125;i++)
    {
        int cnt=0;
        for (int j=1;j<=n;j++) cnt+=f[j][i];
        ans=max(ans,cnt);
    }
    return !printf("%d",ans);
}

C.Paint the Digits

题意

有 $n(n\le 2\times 10^5)$ 个 $[0,9]$ 的数,要把它们染成 $1$ 和 $2$ 。要求把染 $1$ 的从左到右排列,然后把染 $2$ 从左到右排,这样形成一个单调不降序列。

求一种合法的染色方法。如果无解输出 - 。多组数据,$\sum n \le 2\times 10^5$ 。

题解

如果确定了染 $2$ 的最小值 $x$,那么怎么染色就很清楚了。$> x$ 的染 $2$ ,$< x$ 的染 $1$ ,$=x$ 的尽量染 $2$ ,如果不行则染 $1$ 。

最开始我以为数字的范围为 $10^9$(感冒了脑子糊的) ,于是就口胡的排序后二分 $x$ 。但如果是 $[0,9]$ 就可以直接枚举了。

#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;
bool f[200005];
char s[200005];

inline bool check(int mid)
{
    memset(f,0,sizeof(f));
    int max1=0,max2=mid;
    for (int i=1;i<=n;i++)
    {
        if (s[i]<mid)
        {
            if (s[i]<max1) return 0;
            max1=s[i];
        }
        else if (s[i]>mid)
        {
            if (s[i]<max2) return 0;
            f[i]=1;
            max2=s[i];
        }
        else
        {
            if (s[i]>=max2) f[i]=1;
            else max1=s[i];
        }
    }
    return 1;
}

signed main()
{
    t=read();
    while (t--)
    {
        n=read();
        scanf("%s",s+1);
        for (int i=1;i<=n;i++) s[i]-='0';
        bool flag=0;
        for (int i=0;i<=9;i++) if (check(i)) { flag=1; break; }
        if (!flag) { puts("-"); continue; }
        for (int i=1;i<=n;i++) printf("%d",f[i]+1);
        puts("");
    }
    return 0;
}

D.Cow and Snacks

题意

题解

可以发现答案和顺序没有关系。。。

所以可以拿个并查集把吃过的并在一起,如果某个人喜欢的两种已经被合并了那么答案 ++

#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,k,x,y,ans,fa[200005];

int getfa(int x) { return x==fa[x] ? x : fa[x]=getfa(fa[x]); }

signed main()
{
    n=read(); k=read();
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1;i<=k;i++)
    {
        x=read(); y=read();
        int gfx=getfa(x),gfy=getfa(y);
        if (gfx==gfy) ans++;
        fa[gfx]=gfy;
    }
    return !printf("%d",ans);
}

新评论

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