Codeforces Round #604 (Div. 2)

A - Beautiful String

题意:
用'a','b','c'替代'？'，使得替换后的字符串相邻的字符不同。
思路:
贪心，首先判断原字符串是否有相邻非'?’字符相同。
对于每个'?'，考虑这个位置前后的字符，取'a','b','c'第一个没有出现过的字符。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+200;

char s[maxn];

int main()
{
    int T;scanf("%d",&T);    
    while(T--)
    {
        scanf("%s",&s);
        int len=strlen(s);
        int flag=0;
        for(int i=0;i<len-1;i++) if(s[i]!='?'&&s[i+1]!='?'&&s[i]==s[i+1]) flag=1;
        if(flag==1){printf("-1\n");continue;}
        for(int i=0;i<len;i++)
        {
            int vis[3]={0,0,0};
            if(s[i-1]!='?'&&i!=0) vis[s[i-1]-'a']=1;
            if(s[i+1]!='?'&&i!=len-1) vis[s[i+1]-'a']=1;
            if(s[i]=='?') 
            {
                for(int j=0;j<3;j++) 
                {
                    if(vis[j]==0)
                    {
                        s[i]='a'+j;
                        break;
                    }
                }
            }

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

}

B - Beautiful Numbers

思路：
排序，模拟，贪心。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e6+200;

struct Coke{
    int id,v;
}a[maxn];

bool cmp(Coke c,Coke d)
{
    return c.v<d.v;
}
int ans[maxn];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].v);
            a[i].id=i;
        }
        sort(a+1,a+1+n,cmp);
        int mi=a[1].id,mx=a[1].id;
        for(int i=1;i<=n;i++)
        {
            mi=min(mi,a[i].id);
            mx=max(mx,a[i].id);
            if(mx-mi+1==i) ans[i]=1;
            else ans[i]=0;
        }
        for(int i=1;i<=n;i++) printf("%d",ans[i]);
        printf("\n");
    }


}

C - Beautiful Regional Contest

思路：
贪心，模拟。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+200;
int a[maxn],b[maxn];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);a[n+1]=-1;
        int tot=0;
        for(int i=1,now=1;i<=n;i++)
        {
            if(a[i]!=a[i+1]) b[++tot]=i-now+1,now=i+1;
        }
        for(int i=1;i<=tot;i++) b[i]+=b[i-1];
        int cnt;
        for(int i=1;i<=tot;i++)
        {
            if(b[i]*2>n) {cnt=i-1;break;}
        }
        if(cnt<3)    {printf("0 0 0\n");continue;}
        int mx=-1,flag=0;
        for(int i=2;i<cnt;i++)
        {
            mx=min(b[cnt]-b[i],b[i]-b[1]);
            if(b[1]<mx)
            {
                printf("%d %d %d\n",b[1],b[i]-b[1],b[cnt]-b[i]);
                flag=1;
                break;
            }
        }
        if(!flag) printf("0 0 0\n");
    }    
}

D - Beautiful Sequence

题意：
给你a,b,c,d个0，1，2，3.问是否能组成左右间隔为1的序列，如果不行输出"NO";否则输出"YES"，并输出任意可行的方案.
思路:
（比赛的时候想麻烦了，用了好多特判过的，很容易漏掉一些情况。）
其实这题贪心即可，因为相邻的数只隔1，所以下一次选择的数，肯定在i-1或i+1的位置，所以你可以采取的策略是先尽量把前面的取完，再去取后面的。
关于策略的正确性，你可以这样考虑，第0号位置肯定要通过第1号位置消除，这里会遇到一个问题，例如1，1，1，1与1，2，1，1，你要考虑的是起始位置在哪里，因为0->1->0与1->0->1这个过程有所区别，所以你要考虑两个初始位置。
此外将起始位置放在个数为0的时候没有意义，因此你在开始时要选择第一个个数不为空的位置。
代码:

#include<bits/stdc++.h>
using namespace std;

vector<int> ans;
int a[4];

bool dfs(int now)
{
    int b[4],flag=1;for(int i=0;i<4;i++) b[i]=a[i];
    b[now]--;
    while((b[0]||b[1]||b[2]||b[3])&&flag)
    {
        if(now!=0&&b[now-1]) ans.push_back(now-1),b[now-1]--,now--;
        else if(now!=3&&b[now+1]) ans.push_back(now+1),b[now+1]--,now++;
        else flag=0; 
    }
    return flag;
}

int main()
{
    for(int i=0;i<4;i++) scanf("%d",&a[i]);
    int now=0;while(!a[now]) now++;
    ans.push_back(now);
    if(dfs(now))
    {
        printf("YES\n");
        for(auto it:ans) printf("%d ",it);
        printf("\n");
        return 0;
    }
    ans.clear();
    ans.push_back(now+1);
    if(dfs(now+1))
    {
        printf("YES\n");
        for(auto it:ans) printf("%d ",it);
        printf("\n");
        return 0;
    }
    printf("NO\n");
}

E - Beautiful Mirrors

题意：
有n天，每天快乐的概率为 $\frac{p_{i}}{100}$ ,否则回到第一天,求到第n天的期望值。
思路：
推公式： $dp[i]=(dp[i-1]+1)*\frac{p_{i}}{100}+(dp[i-1]+1+dp[i])*(1-\frac{p_{i}}{100})$

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=2e5+200;
ll dp[maxn],p[maxn];
ll mod=998244353;

ll quickpow(ll a,ll b){
    if(b<0)  return 0;
    ll ret=1;
    a%=mod;
    while(b){
        if(b & 1 ) ret = ( ret *a ) % mod;
        b>>=1;
        a = (a * a)% mod;
    }
    return ret;
}
ll inv(ll a){
    return quickpow(a,mod-2);
}


int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
    for(int i=1;i<=n;i++) dp[i]=100*inv(p[i])%mod,dp[i]=dp[i]*(dp[i-1]+1),dp[i]%=mod;
    printf("%lld\n",dp[n]);
}