Codeforces Round #692 (Div. 2)

${A. In-game Chat}$
按题意模拟

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+500;
int w[N];
int main()
{
    int T;
    scanf("%d",&T);
//    T=1;
    while(T--)
    {
        int n;
        scanf("%d",&n);
        string s;
        cin>>s;
        int i;
        for(i=n-1;i>=0;i--)
        {
            if(s[i]!=')') break;
        }
        int h=i+1;
        int q=n-h;
        if(h>=q) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
    return 0;
}

${B. Fair Numbers}$
往后暴力寻找答案,即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+500;
int w[N];bool vis[10];
bool ck(ll x)
{
    memset(vis,false,sizeof vis);
    ll num=x;
    while(x)
    {
        vis[x%10]=true;
        x/=10;
    }
    for(int i=1;i<=9;i++)
        if(vis[i])
        {
            if(num%i!=0)    return false;
        }
    return true;

}
int main()
{
    int T;
    scanf("%d",&T);
//    T=1;
    while(T--)
    {
        ll n;
        scanf("%lld",&n);
        while(!ck(n))    n++;
        printf("%lld\n",n);
    }
    return 0;
}

${C. Peaceful Rooks}$
对于一个环来说,它的拆开是需要n+1步的,因为第一步是要拆环,对于不在对角线上也不成环的环每次只需要1步,这里用dsu统计环的数量即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+500;
int fa[N],sz[N];
int vis[N];
int dsu(int u)
{
    if(u==fa[u])    return u;
    else            return fa[u]=dsu(fa[u]);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int ans=0;
        for(int i=1;i<=n;i++)    fa[i]=i,sz[i]=1,vis[i]=0;
        ans=m;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==y)    
            {
                ans--;continue;    
            }
            if(dsu(x)==dsu(y))    vis[dsu(x)]=1;
            else                sz[dsu(x)]++;
            fa[dsu(y)]=dsu(x);
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[dsu(i)]==1)        ans++,vis[dsu(i)]=2;
        }
        printf("%d\n",ans);
    }
    return 0;
}

${D. Grime Zoo}$
贪心即可,我们可以知道$填是连续的,对于每一段来说,我们肯定是在前面一段全填1/0,后面一段全填0/1.

${证明:}$ 假设我们还有一个更优的解法,那么我肯定是交换某个1/0..这样产生的结果(01/10串的数目)是不变的,所以发现只与0/1的数目有关.如此这种处理即是最好做的,因为它会严格的使得某种01/10偏大.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+500;
char s[N];
ll pre_zero[N],suf_zero[N],pre_one[N],suf_one[N],pre[N],suf[N];
ll ans_pzero[N],ans_fzero[N],ans_pone[N],ans_fone[N];
int main()
{
    scanf("%s",s+1);
    ll x,y;scanf("%lld%lld",&x,&y);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        pre_zero[i]=pre_zero[i-1];
        pre_one[i]=pre_one[i-1];
        pre[i]=pre[i-1];
        if(s[i]=='0')        pre_zero[i]++;
        else if(s[i]=='?')    pre[i]++;
        else                pre_one[i]++;
    }
    for(int i=n;i>=1;i--)
    {
        suf_one[i]=suf_one[i+1];
        suf_zero[i]=suf_zero[i+1];
        suf[i]=suf[i+1];
        if(s[i]=='0')        suf_zero[i]++;
        else if(s[i]=='?')    suf[i]++;
        else                suf_one[i]++;
    }
    //1.前面填0的答案.
    for(int i=1;i<=n;i++)
    {
        ans_pzero[i]=ans_pzero[i-1];
        if(s[i]=='0'||s[i]=='?')
        {
            ans_pzero[i]+=pre_one[i]*y;
        }
        else
        {
            ans_pzero[i]+=(pre_zero[i]+pre[i])*x;
        }
    }
    //2.前面填1的答案.
    for(int i=1;i<=n;i++)
    {
        ans_pone[i]=ans_pone[i-1];
        if(s[i]=='1'||s[i]=='?')
        {
            ans_pone[i]+=pre_zero[i]*x;
        }
        else
        {
            ans_pone[i]+=(pre_one[i]+pre[i])*y;
        }
    }
    //3.后面填0的答案.
    for(int i=n;i>=1;i--)
    {
        ans_fzero[i]=ans_fzero[i+1];
        if(s[i]=='0'||s[i]=='?')
        {
            ans_fzero[i]+=suf_one[i]*x;
        }
        else
        {
            ans_fzero[i]+=(suf_zero[i]+suf[i])*y;
        }
    }
    //4.后面填1的答案. 
    for(int i=n;i>=1;i--)
    {
        ans_fone[i]=ans_fone[i+1];
        if(s[i]=='1'||s[i]=='?')
        {
            ans_fone[i]+=suf_zero[i]*y;
        }
        else
        {
            ans_fone[i]+=(suf_one[i]+suf[i])*x;
        }
    }
    //5.统计答案.
    ll ans=2e18;
    for(int i=0;i<=n;i++)
    {
        ans=min(ans,ans_pzero[i]+ans_fone[i+1]+(pre_zero[i]+pre[i])*(suf_one[i+1]+suf[i+1])*x+(pre_one[i])*(suf_zero[i+1])*y);
        ans=min(ans,ans_pone[i]+ans_fzero[i+1]+(pre_one[i]+pre[i])*(suf_zero[i+1]+suf[i+1])*y+(pre_zero[i])*(suf_one[i+1])*x);
    }printf("%lld\n",ans);
    return 0;
}

${E. Poman Numbers}$
对于这题来说,我们手画一下可以发现:当n>=2时,n项为正,n-1项为负,其他可以任意符号.如此我们可以二进制贪心填充即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+500;
int num[30];
char s[N];
int main()
{
    ll n,T;
    scanf("%lld%lld",&n,&T);
    scanf("%s",s+1);
    for(int i=1;i<=n-2;i++)
    {
        num[s[i]-'a']++;
    }
    //第n个符号是正,n-1个符号是负. 
    ll now=(1ll<<(s[n]-'a'))-(1ll<<(s[n-1]-'a'));
    T-=now;
    for(ll i=25;i>=0;i--)
    {
        while(T>0&&num[i])    T-=(1ll<<i),num[i]--;
    }
    for(ll i=25;i>=0;i--)
    {
        while(T<=-(1ll<<i)&&num[i])    T+=(1ll<<i),num[i]--;
    }
    if(T)    { puts("NO"); return 0;}
    bool ans=false;
    now=0;
    //剩下的数凑完即可.
    for(ll i=25;i>=0;i--)
    {
        if((num[i]&1)&&now==0)    now+=(1ll<<i);
        else if(now!=0)
        {
            while(now>=(1ll<<i)&&num[i])    now-=(1ll<<i),num[i]--;
            if(num[i]&1)    now+=(1ll<<i);
        }
    }
    if(!now)    ans=true;
    if(ans)    puts("YES");
    else    puts("NO");
    return 0;
}
/*
4 7
adaa
*/

${F. The Thorny Path}$
待补.