P8271 [USACO22OPEN] COW Operations S

题目描述

Bessie 找到了一个长度不超过 $2\cdot 10^5$ 且仅包含字符 ‘C’，‘O’ 和 ‘W’ 的字符串 $s$。她想知道是否可以使用以下操作将该字符串变为单个字母 ‘C’（她最喜欢的字母）：

1. 选择两个相邻相等的字母并将其删除。

2. 选择一个字母，将其替换为另外两个字母的任一排列。

求出这个字符串本身的答案对 Bessie 而言并不足够，所以她想要知道 $s$ 的 $Q$（$1\le Q\le 2\cdot 10^5$）个子串的答案。

输入格式

输入的第一行包含 $s$。

第二行包含 $Q$。

以下 $Q$ 行每行包含两个整数 $l$ 和 $r$（$1\le l\le r\le |s|$，其中 $|s|$ 表示 $s$ 的长度）。

输出格式

输出一个长为 $Q$ 的字符串，如果第 $i$ 个子串可以被转变则第 $i$ 个字符为 ‘Y’，否则为 ‘N’。

输入输出样例 #1

输入 #1

COW
6
1 1
1 2
1 3
2 2
2 3
3 3

输出 #1

YNNNYN

说明/提示

【样例解释】

第一个询问的答案是「是」，因为 s 的第一个字符已经等于 ‘C’。

第五个询问的答案是「是」，因为 s 的第二到第三个字符组成的子串 OW 可以通过两步操作变为 ‘C’：

   OW
-> CWW
-> C

这个样例字符串 COW 的其他子串均不能被转变为 ‘C’。

【测试点性质】

• 测试点 2-4 满足 $|s|\le 5000$ 以及 $Q\le 5000$。
• 测试点 5-11 没有额外限制。

C++实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN(2e5+5);
int sum[MAXN][3];
int c['~'];
int main()
{
    c['C']=0;c['O']=1;c['W']=2;
    string s;cin>>s;
    for (int i{1};i<=s.size();++i)
    {
        for (int j{0};j<3;++j) 
			sum[i][j]+=sum[i-1][j];
        ++sum[i][c[s[i-1]]];
    }
    int T;cin>>T;
    while (T--)
    {
        int l,r;scanf("%d %d",&l,&r);
        int z[3];
        for (int i{0};i<3;++i)
            z[i]=sum[r][i]-sum[l-1][i]&1;
        printf("%c",!(z[1]^z[2])&&(z[0]^z[1])?'Y':'N');
    }
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容