[开发测试]Codeforces Round #738 (Div. 2)

Codeforces Round #738 (Div. 2)

A. Mocha and Math

题意

$t$组样例，给定一个长度为$n$的数组，可以对这个数组进行任意次操作，每次操作时选取一个区间$[l,r]$，对于所有$i\in [0,r?l]$，将这个区间内的$a_{l+i}$变为$a_{l+i}\&a_{r?i}$，最小化这个数组中的最大值，输出这个最大值。
$1\le t\le 100,1\le n\le 100,0\le a_i\le 10^9$

Solution

将$a_i$拆分为二进制，如果当前位对于所有的$a_i$来说都为1，则说明，无论如何选取区间，这一位上都不可能变为0，否则经过若干次变化后，这一位上最终都会变为0。

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
int t,n;
int a[105];
int main()
{
   scanf("%d",&t);
   while(t--)
   {
       scanf("%d",&n);
       memset(a,0,sizeof(a));
       for(int i=1;i<=n;i++)
       {
           int x;scanf("%d",&x);
           int cnt=0;
           while(x)
           {
               if(x%2)a[cnt]++;
               cnt++;
               x/=2;
           }
       }
       int res=0;
       for(int i=0;i<=32;i++)
       {
           if(a[i]==n)res+=(1<<i);
       }
       printf("%d\n",res);
   }
   return 0;
}

B. Mocha and Red and Blue

题意

$t$组样例，给定一个长度为$n$的字符串，包含字符‘？’，‘R’，‘B’，其中’?'代表黑色正方形，‘R’代表红色正方形，‘B’代表蓝色正方形，现在要求给黑色正方形染色，使得不完美性（相邻正方形为同一颜色的的对数）最少。
输出任意构造方案。
$1\le t\le 100,1\le n\le 100$

Solution

贪心，（bfs）
对一个黑色正方形涂色，对不完美性的贡献可能为0或1或2。
因此对一个不为黑色正方形的正方形旁边为黑色的正方形涂色是，只要与当前颜色不同即可。这样构造出来的方案是最优的。

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
int t,n;
char s[105];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%s",&n,s);
        queue<int>q;while(!q.empty())q.pop();
        for(int i=0;i<n;i++)if(s[i]!='?')q.push(i);
        if(!q.empty())
        {
            while(!q.empty())
            {
                int x=q.front();q.pop();
                if(x-1>=0&&s[x-1]=='?')
                {
                    s[x-1]=(s[x]=='R'?'B':'R');
                    q.push(x-1);
                }
                if(x+1<n&&s[x+1]=='?')
                {
                    s[x+1]=(s[x]=='R'?'B':'R');
                    q.push(x+1);
                }
            }
        }
        else
        {
            for(int i=0;i<n;i++)
            {
                if(i%2==0)s[i]='R';
                else s[i]='B';
            }
        }

        printf("%s\n",s);

    }
    return 0;
}

C - Mocha and Hiking

题意

$t$组样例，给了一个数字$n$，表示有$n+1$个点。
一个长度为$n$的数组$a$：
1.$a_i$为0，代表$i$到$n+1$有一条边。
2.$a_i$为1，代表$n+1$到$i$有一条边。
还有$n?1$条边，从$i$到$i+1$，$i\in [1,n?1]$
问是否有存在一条路径，在这条路径上，每个点都只经过一次。
若存在，输出这条路径；不存在，输出-1.
$1\le t\le 20,1\le n\le 10^4,0\le a_i\le 1$

Solution

1.如果$a_1=1$，可以构造出$n+1,1,2,3,?,n?1,n$这样的路径。
2.如果$a_n=0$，可以构造出$1,2,3,?,n?1,n,n+1$
3.如果$a_{i?1}=0\&\&a_i=1,?i\in [2,n]$，可以构造出$1,2,?,i,n+1,i+1,i+2,?,n?1,n$
4.否则输出-1（虽然这种情况好像不会出现，但还是写上了）

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
int t;
int n;
int a[100005];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        bool flag=false;
        if(a[n]==0)
        {
            for(int i=1;i<=n+1;i++)printf("%d ",i);
            printf("\n");
            continue;
        }
        else if(a[1]==1)
        {
            printf("%d ",n+1);
            for(int i=1;i<=n;i++)printf("%d ",i);
            printf("\n");
            continue;
        }
        for(int i=2;i<=n;i++)
        {
            if(a[i-1]==0&&a[i]!=0)flag=true;
        }
        if(!flag)printf("-1\n");
        else
        {
            printf("1 ");
            for(int i=2;i<=n;i++)
            {
                if(a[i-1]==0&&a[i]!=0)
                {
                    printf("%d ",n+1);
                    for(int j=i;j<=n;j++)
                        printf("%d ",j);
                    printf("\n");
                    break;
                }
                else printf("%d ",i);
            }
        }
    }
    return 0;
}

D1 - Mocha and Diana (Easy Version)

题意

给定节点个数$n$，边数分别为$m_1,m_2$的两处森林（无环），问还能往两个森林中加入多少条边，输出加入边的方案。
往两个森林中加边的条件是，加入这条边后，两个森林都不会产生环。

Solution

先将两个森林中的边通过并查集分别并起来，然后暴力枚举加入哪条边，如果能加入这条边，则把其放入答案，两个森林分别和这条边并起来。

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
int n,m1,m2;
int f1[1005];
int f2[1005];
int Find1(int x){return f1[x]==x?x:f1[x]=Find1(f1[x]);}
int Find2(int x){return f2[x]==x?x:f2[x]=Find2(f2[x]);}
vector<P>e;
int main()
{
    scanf("%d%d%d",&n,&m1,&m2);
    for(int i=1;i<=n;i++)f1[i]=f2[i]=i;
    for(int i=1;i<=m1;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        u=Find1(u);
        v=Find1(v);
        f1[u]=v;
    }
    for(int i=1;i<=m2;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        u=Find2(u);
        v=Find2(v);
        f2[u]=v;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int u1=Find1(i);
            int v1=Find1(j);
            int u2=Find2(i);
            int v2=Find2(j);
            if(u1!=v1&&u2!=v2)
            {
                f1[u1]=v1;
                f2[u2]=v2;
                e.push_back(P(i,j));
            }
        }
    }
    printf("%d\n",e.size());
    for(P p:e)printf("%d %d\n",p.first,p.second);
    return 0;
}
/*
1000
3
0 0 1
*/

D2 - Mocha and Diana (Hard Version)

题意

给定节点个数$n$，边数分别为$m_1,m_2$的两处森林（无环），问还能往两个森林中加入多少条边，输出加入边的方案。
往两个森林中加边的条件是，加入这条边后，两个森林都不会产生环。

Solution

正解是启发式合并。

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
int n,m1,m2;
int f1[100005];
int f2[100005];
int Find1(int x){return f1[x]==x?x:f1[x]=Find1(f1[x]);}
int Find2(int x){return f2[x]==x?x:f2[x]=Find2(f2[x]);}
vector<P>e;
int main()
{
    scanf("%d%d%d",&n,&m1,&m2);
    for(int i=1;i<=n;i++)f1[i]=f2[i]=i;
    for(int i=1;i<=m1;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        u=Find1(u);
        v=Find1(v);
        if(u<v)swap(u,v);
        f1[u]=v;
    }
    for(int i=1;i<=m2;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        u=Find2(u);
        v=Find2(v);
        if(u<v)swap(u,v);
        f2[u]=v;
    }
    for(int i=2;i<=n;i++)
    {
        int u=Find1(i);
        int v=Find2(i);
        if(u!=Find1(1)&&v!=Find2(1))
        {
            f1[u]=1;
            f2[v]=1;
            e.push_back(P(1,i));
        }
    }
    set<int>st1,st2;
    for(int i=2;i<=n;i++)
    {
        if(Find1(i)!=Find1(1))st1.insert(Find1(i));
        if(Find2(i)!=Find2(1))st2.insert(Find2(i));
    }
    //cout<<"?";
    for(auto u=st1.begin(),v=st2.begin();u!=st1.end()&&v!=st2.end();u++,v++)
    {
        e.push_back(P(*u,*v));
    }
    printf("%d\n",e.size());
    for(P p:e)printf("%d %d\n",p.first,p.second);
    return 0;
}
/*
1000
3
0 0 1
*/

E - Mocha and Stars

题意

问有多少个数组a满足以下条件：
$$\begin{gathered} 对于所有的i(1\le i\le n),a_i是[l_i,r_i]之间的整数 \\ \sum _{i=1}^n{a}_i\le m \\ gcd(a_1,a_2,?,a_n)=1 \end{gathered}$$
$m,n$题目中已经给出。
$1\le n\le 50,1\le m\le 10^5$

Solution

对于$gcd(a_1,a_2,?,a_n)=1$
$$\begin{gathered} \sum _{a_1=l_1}^{r_1}\sum _{a_2=l_2}^{r_2}?\sum _{a_n=l_n}^{r_n}[gcd(a_1,a_2,?,a_n)=1] \\ =\sum _{a_1=l_1}^{r_1}\sum _{a_2=l_2}^{r_2}?\sum _{a_n=l_n}^{r_n}\sum _{d|gcd(a_1,a_2,?,a_n)}\mu (d) \\ =\sum _{d=1}^m\mu (d)\sum _{a_1=?\frac{l_1}{d}?}^{?\frac{r_1}{d}?}\sum _{a_2=?\frac{l_2}{d}?}^{?\frac{r_2}{d}?}?\sum _{a_n=?\frac{l_n}{d}?}^{?\frac{r_n}{d}?}1 \end{gathered}$$
对于${\sum }_{i=1}^n{a}_i\le m$
可以通过背包dp来优化+前缀和
$$\begin{gathered} now\in [1,n]，表示表示当前处理到a_{now} \\ 记L为a_{now}的下边界，R为a_{now}的上边界 \\ sum[j]表示\sum _{i=1}^{now}{a}_i\le j的个数 \\ f[j]表示\sum _{i=1}^{now}{a}_i=j的个数 \\ 因此sum[j]=f[j]+(i?sum[j?1]:0)来维护前缀和 \\ f[j]=(j>=L?sum[j?L]:0)?(j>=R+1?sum[j?R?1]:0)这个表示有多少种和为j的方案 \\ 那么为什么f[j]是这样推过来的？？？拆成两个数更好理解一点 \\ (j?R)+R,(j?R+1)+R?1,(j?R+2)+R?2,?,(j?L)+L \\ 也就是相当于求这段区间f[j?R],f[j?R+1],?,f[j?L]的和。 \\ 这段之前已经记录过前缀和了,也就是(j>=L?sum[j?L]:0)?(j>=R+1?sum[j?R?1]:0) \end{gathered}$$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int N=1e5+5;
const int mod=998244353;
int n,m;
int l[N],r[N];
int prime[N],cnt=0;
int mu[N];
bool isprime[N];
int f[N];
int sum[N];
void initMu()
{
    mu[1]=1;
    for(int i=2;i<=m;i++)
    {
        if(!isprime[i])
        {
            mu[i]=-1;
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt&&1ll*i*prime[j]<=m;j++)
        {
            isprime[i*prime[j]]=true;
            if(i%prime[j])mu[i*prime[j]]=-mu[i];
            else break;
        }
    }
}
int calc(int d)
{
    int k=m/d;
    f[0]=1;
    for(int i=1;i<=k;i++)f[i]=0;
    for(int i=1;i<=n;i++)
    {
        int L=(l[i]+d-1)/d;
        int R=r[i]/d;
        if(L>R)return 0;
        for(int j=0;j<=k;j++)
        {
            sum[j]=f[j];
            if(j)sum[j]=(sum[j]+sum[j-1])%mod;
        }
        for(int j=0;j<=k;j++)
        {
            if(j-L>=0)f[j]=sum[j-L];
            else f[j]=0;
            if(j-R-1>=0)f[j]=(f[j]-sum[j-R-1]+mod)%mod;
        }
    }
    int ans=0;
    for(int i=1;i<=k;i++)ans=(ans+f[i])%mod;
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
    initMu();
    int res=0;
    for(int i=1;i<=m;i++)res=(res+1ll*mu[i]*calc(i)%mod+mod)%mod;
    printf("%d",res);
    return 0;
}