date: 2022-12-06
第一道AGC
这很可能是我的的最后几题之一了
[[This is a tag]]
赛时直接卡住，还好QY明智地提早开了unrated
先考虑一段区间，然后发现选一段区间进行转换等价于剩下的一部分进行转化
所以可以把询问区间看成一个循环，我们每次最多能够删两个交界处
有因为一共只有3种颜色，所以如果有4个及以上交界处，那么一定能够找到两个对称的边界，那么就是一定可以删掉两个边界
当交界处个数为3时，一定形如 ABC 所以答案一定为2
当交界处个数为2时，一定形如 AB 所以答案一定为1
交界处个数不可能为1
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,q,l,r,k[N];
char s[N];
int main(){
scanf("%d%d",&n,&q);
cin>>s+1;
for(int i=2;i<=n;i++){
k[i]=k[i-1];
if(s[i]!=s[i-1])k[i]++;
}
while(q--){
scanf("%d%d",&l,&r);
int x=k[r]-k[l]+(s[r]!=s[l]);
printf("%d\n",x/2+x%2);
}
}