Codeforces Round #589 (Div. 2) 题解

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

我是傻逼,赛后D题加了一行就过了。。。

A.Distinct Digits

题意

给出 $l,r(\le 10^5)$ ,求 $x\in [l,r]$ ,要求 $x$ 各数位均不同。

题解

数据范围小,直接暴力判断。

#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 l,r,cur[10];

inline bool check(int x)
{
    int j=0;
    while (x)
    {
        cur[++j]=x%10;
        x/=10;
        for (int k=1;k<j;k++) if (cur[j]==cur[k]) return 0;
    }
    return 1;
}

signed main()
{
    l=read(); r=read();
    for (int i=l;i<=r;i++)
    {
        if (check(i))
        {
            printf("%d",i);
            return 0;
        }
    }
    return 0&puts("-1");
}

B.Filling the Grid

题意

有个 $n\times m(n,m\le 1000)$ 的矩形,每个格子可以被涂成黑/白两色。给出两个数组 $r$ 和 $c$ ,$r_i$ 表示从第 $i$ 行第 $1$ 列开始有连续多少个黑色格子,$c_i$ 表示第 $i$ 列第 $1$ 行开始。问满足 $r,c$ 的涂色方案有多少种。

题解

按题意膜你,对于每一行,前 $r_i$ 个涂成黑色,第 $r_i+1$ 个涂成白色。列同理,不过涂的时候需要判断一下是否矛盾。最后如果还剩 $x$ 个格子没涂那答案就是 $2^x$ 。

#include<bits/stdc++.h>
#define ha 1000000007

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,r[1005],c[1005],mp[1005][1005];

signed main()
{
    memset(mp,-1,sizeof(mp));
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        r[i]=read();
        for (int j=1;j<=r[i];j++) mp[i][j]=1;
        mp[i][r[i]+1]=0;
    }
    for (int i=1;i<=m;i++)
    {
        c[i]=read();
        for (int j=1;j<=c[i];j++)
        {
            if (mp[j][i]==0) return 0&puts("0"); //矛盾
            mp[j][i]=1;
        }
        if (mp[c[i]+1][i]==1) return 0&puts("0");
        mp[c[i]+1][i]=0;
    }
    int ans=1;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
    {
        if (mp[i][j]!=-1) continue;
        ans=ans*2%ha;
    }
    printf("%d",ans);
    return 0;
}

C.Primes and Multiplication

题意

题解

可以发现答案就是

$$\prod \forall prime(x)^{\sum_{i=1}^n \frac{i}{prime(x)} \ (i\equiv 0\pmod {prime(x)})}$$

计算 $\sum_{i=1}^n \frac{i}{prime(x)} \ (i\equiv 0\pmod {prime(x)})$ 可以让 $n$ 不断的除 $prime(x)$ ,将商累加起来。

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

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

bool ss[100005];
ll x,n,cnt,ans=1,zs[100005],c[100005],ccnt;

inline void getPrime()
{
    memset(ss,1,sizeof(ss));
    ss[0]=ss[1]=0;
    for (ll i=2;i*i<=x;i++)
    {
        if (ss[i]) zs[++cnt]=i;
        for (ll j=1;j<=cnt && zs[j]*i*zs[j]*i<=x;j++)
        {
            ss[zs[j]*i]=0;
            if (i%zs[j]==0) break;
        }
    }
}

inline ll qpow(ll x,ll y)
{
    ll ans=1;
    while (y)
    {
        if (y&1) ans=ans*x%ha;
        y>>=1;
        x=x*x%ha;
    }
    return ans;
}

signed main()
{
    x=read(); n=read();
    getPrime();
    for (ll i=1;i<=cnt;i++)
    {
        if (x%zs[i]) continue;
        c[++ccnt]=zs[i]; //分解质数
        while (x%zs[i]==0) x/=zs[i];
    }
    if (x>1) c[++ccnt]=x;
    for (ll i=1;i<=ccnt;i++)
    {
        ll n2=n,cur=0;
        while (n2) cur+=n2/=c[i]; //不断除当前质数
        ans=ans*qpow(c[i],cur)%ha;
    }
    printf("%lld",ans);
    return 0;
}

D.Complete Tripartite

题意

题解

可以发现不与 $x$ 直接相连的点一定和 $x$ 在同一集合。

那么就可以先把 $1$ 归到集合 $\text{①}$ ,然后遍历所有与 $1$ 相连的点,把他们标为集合 $\text{②}$ 。剩下的没有被标成 $\text{②}$ 的就一定在 $\text{①}$ 里。

再随便选一个 $\text{②}$ 中的节点,把与它相连且 $\notin \text{①}$ 的节点标成 $\text{③}$ 。

至此集合就划分完了,接下来只需要验证是否满足题意。

  1. 如果三种集合有一种的节点个数 $cnt[i]$ 为 $0$ ,那么无解。(我就是因为这个炸掉了
  2. 对于节点 $x$ ,遍历所有与它相连的节点 ,并记录三种集合的个数 $cur[i]$。如果 $x$ 所属的集合个数不为 $0$ ,或者其它集合的 $cnt[i]\neq cur[i]$ ,那么无解。
#include<bits/stdc++.h>
#define ha 1000000007

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

struct Edge {
    int next,to;
} edge[600005];
bool vis[100005];
int cnt,head[100005],n,m,a,b,col[100005],cnt2[4],cur[4];

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

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    col[1]=1; cnt2[1]=1;
    for (int i=head[1];i;i=edge[i].next) //从 1 开始,标记集合 ②
    {
        int y=edge[i].to;
        col[y]=2;
    }
    for (int i=1;i<=n;i++) if (!col[i]) col[i]=1,cnt2[1]++; //剩下的在 ①
    int st=2;
    for (;st<=n && col[st]!=2;st++); //找到一个 ② 中的节点
    for (int i=head[st];i;i=edge[i].next) //标记集合 ③
    {
        int y=edge[i].to;
        if (col[y]==1) continue;
        col[y]=3;
        cnt2[3]++;
    }
    cnt2[2]=n-cnt2[1]-cnt2[3];
    if (!cnt2[1] || !cnt2[2] || !cnt2[3]) return 0&puts("-1"); //无解情况 1
    for (int x=1;x<=n;x++)
    {
        memset(cur,0,sizeof(cur));
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            cur[col[y]]++;
        }
        for (int i=1;i<=3;i++)
        {
            if (col[x]==i && cur[i]) return 0&puts("-1");
            else if (col[x]!=i && cnt2[i]!=cur[i]) return 0&puts("-1"); //无解情况 2
        }
    }
    for (int i=1;i<=n;i++) printf("%d ",col[i]);
    return 0;
}

新评论

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