牛客周赛Round 131

A ICPC Balloons

思路：
简单的 if-else 或者是 swich-case。果然我只有碰到这种简单题才能想到多解。
代码：

void solve()
{
    char c;
    cin>>c;
    if(c=='A')cout<<"red";
    else if(c=='B')cout<<"orange";
    else if(c=='C')cout<<"blue";
    else if(c=='D')cout<<"green";
}

B String Covering

思路：
可以发现，单个 1 是染不出来的。
代码：

void solve()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    bool flag=true;
    int i=0;
    while(i<n){
        if(s[i]=='1'){
            int j=i;
            while(j<n&&s[j]=='1')j++;
            if(j-i==1){
                flag=false;
                break;
            }
            i=j;
        }else i++;
    }
    if(flag)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

C Get The Sequence

思路：
遍历 a[i] 如果 a[i]>=b[pos] 那么 pos++ 否则就找下一个 a 来匹配。不匹配的 a 可以直接删除。
代码：

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<int>a(n);
    vector<int>b(m);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<m;i++)
    {
        cin>>b[i];
    }
    int j=0;
    for(int i=0;i<n&&j<m;i++)
    {
        if(a[i]>=b[j]){
            j++;
        }
    }
    if(j==m)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

D Longest Subsequence

思路：
要求最长子序列，我们可以用 dp[x] 来记录以 x 结尾的最长子序列的长度，它只能从 dp[x-1] 或 dp[x+1] 上演变过来。
所以 dp[x]=max(dp[x],max(dp[x-1],dp[x+1])+1)。
代码：

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    vector<int> dp(n+5,0);
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int m=max(dp[a[i]+1],dp[a[i]-1])+1;
        dp[a[i]]=max(m,dp[a[i]]);
        ans=max(ans,dp[a[i]]);
    }
    cout<<ans<<endl;
}

E Eat The Candy

思路：
对每一个盒子都计算它所能达到的最大值，最后取所有盒子的最大值。
对于每个位置计算：从左边能搬多少糖到 i、从右边能搬多少糖到 i。
代码：

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    vector<int> b(n),c(n);
    int now=a[0];
    for(int i=0;i<n-1;i++)
    {
        b[i+1]=b[i]+min(a[i+1],now);
        now=a[i+1]-min(a[i+1],now);
    }
    now=a[n-1];
    for(int i=n-1;i>=1;i--)
    {
        c[i-1]=c[i]+min(now,a[i-1]);
        now=a[i-1]-min(a[i-1],now);
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int m=a[i];
        if(i)m+=b[i-1];
        if(i!=n-1)m+=c[i+1];
        ans=max(ans,m);
    }
    cout<<ans<<endl;
}

F Bracket Coloring

思路：
括号匹配想到用栈。每一对括号考虑其前后是否相同。
代码：

const int MOD=998244353;
void solve()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ans=1;
    vector<int> st;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='('){
            if(i==0||s[i-1]==')')//如果是新的括号组的开始
                st.push_back(1);
            else st.push_back(0);//连续左括号中的一个
        }else{
            if(st.size()==1){//栈大小为1当前匹配的是最外层括号
                ans=ans*2%MOD;
            }else if(st.back()==1){//栈顶为1，这对括号独立
                //序列中两个相邻位置的括号字符相同（同为 ‘(’或同为‘)’），则它们的颜色不能相同。
                if(i==s.size()-1||s[i+1]=='(')
                    ans=ans*2%MOD;
            }
            st.pop_back();
        }
    }
    cout<<ans<<endl;
}