CF1569A Balanced Substring 题解

题目传送门

题意

给出 \(T\) 个长度为 \(n\) 且仅含 \(\texttt{a}\) , \(\texttt{b}\) 的字符串,对于每个字符串,输出任意的 \(l\) ,\(r\) ,表示字符串的第 \(l\) 个字符到第 \(r\) 中 \(\texttt{a}\) , \(\texttt{b}\) 字符的数量相同。

\(\texttt{SOLUTION}\)

记字符串为 \(s\) ,字符串中的第 \(x\) 个字符为 \(s_x\) 。

不难发现,如果字符串中存在 \(s_x \ne s_{x-1}\) ( \(2\le x\le n\) )那么直接输出 \(x-1\) , \(x\) 即可。

如果不存在任意一对 \(s_x \ne s_{x-1}\) ( \(2\le x\le n\) ),则字符串中只可能全为 \(\texttt{a}\) 或全为 \(\texttt{b}\) ,这样肯定无解。

于是……

就\(\texttt{AC}\)了。

\(\texttt{AC CODE}\)

#include<bits/stdc++.h>
using namespace std;
const int MAX=100010;
int read()
{
	int x=0; char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int n;
char str[MAX];
bool check()
{
	for(int i=2;i<=n;i++)
	{
		if(str[i]^str[i-1]) return printf("%d %d\n",i-1,i),1;
	}
	return 0;
}
int main()
{
	int t=read();
	while(t--)
	{
		scanf("%d%s",&n,str+1);
		if(!check()) puts("-1 -1");
	}
	return 0;
}

上一篇:洛谷P3147[USACO16OPEN]-262144 P


下一篇:循环卷积(离散化)