abc229 总结（区间最长连续字符 图的联通分量计数）

D - Longest X 前缀和+双指针

大意：一个字符串由"X"和"."组成，给定n次操作机会，每一次可以将一个"."变成"X".

求最长连续的"X"的个数

思路：
前缀和统计"."的个数，然后双指针跑一下，在操作次数大于等于区间内的"."的个数的情况下尽可能更新区间长度，然后取最值就可以了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll N=2e5+10;
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
ll dir[][4]={
   {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
ll n,m;
ll cnt[N];
char s[N];
ll a,b;
void solve()
{
    cin>>(s);
    cin>>n;
    ll ans=0;
    ll len=strlen(s);
    //cnt[0]=(s[0]=='.');
    for(int i=0;i<len;++i)
    {
    	if(s[i]=='.') cnt[i+1]=cnt[i]+1;
    	else cnt[i+1]=cnt[i];
	}
	//for(int i=0;i<len;++i) cout<<cnt[i]<<' ';
	for(int l=0,r=0;l<len;++l)
	{
		while(r<len&&cnt[r+1]-cnt[l]<=n)
		{
			r++;
		}
		ans=max(ans,(ll)r-l);
	}
	cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

G - Longest Y

G跟D是很像的两个题，所以我想先讲G

大意：
同样也是一个字符串，问题跟D也一样，但是G题的操作变成了只能交换相邻两个位置的字符，这是两题唯一的区别。

思路：

官方题解的思路很巧妙：

如果s[i]=='Y'，b[++cnt]=i-cnt;
令数组b的元素值等于各个Y元素的位置减去其位序（是第几个Y）。

如果是两个连续的Y，它们的位置连续加1，位序也连续加1，那么二者的b[i]值就会相等

那么问题就转化成了：

有一个数字b，每一次操作可以将b里面的元素+1或者-1，然后问最多能使b中由多少个元素相等。

仔细观察b的构造过程，可以发现b中的元素是不减的，即它们具有单调性，那么我们就可以考虑而二分。

二分对象自然是最大能得到的相等元素的区间长度，那么judge(x)函数的内容就是能否在k次操作内将一个长度为x的区间统一为一个值。

为了做到这一点，最优策略一定是将两边的元素向中间的元素靠拢，那么judge的判断就是

其中mid为区间的中点 。

左边的式子是可以优化的，用前缀和预处理一下，然后分别算一下式子左右部分的贡献就可以了

左边的贡献：sum1=(mid-l+1)*b[mid]-(sum[mid]-sum[l-1])

右边的贡献：sum2=sum[r]-sum[mid-1]-b[mid]*(r-mid+1)

很简单的一个小学数学

然后我们就可以快乐ac啦

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll N=2e5+10;
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
string s;
ll n;
ll b[N];
ll cnt=0;
ll sum[N];//b的前缀和 
bool judge(ll x)
{
	for(int l=1;l+x-1<=cnt;++l)
	{
		ll r=l+x-1;//左右界
		ll mid=l+r>>1;//极值点
		ll s1=(mid-l+1)*b[mid]-(sum[mid]-sum[l-1]);
		ll s2=(sum[r]-sum[mid-1])-(r-mid+1)*b[mid];
		if(s1+s2<=n) return 1;
	}
	return 0;
}
void solve()
{
    cin>>(s);
    cin>>n;
    for(int i=0;i<s.size();++i)
    {
    	if(s[i]=='Y')
		{
			b[++cnt]=i+1-cnt; 
		 } 
	}
	for(int i=1;i<=cnt;++i)
	{
		sum[i]=sum[i-1]+b[i];
	}
	ll l=0,r=cnt;
	while(l<=r)
	{
		ll mid=l+r>>1;
		if(judge(mid)) l=mid+1;
		else r=mid-1;
	}
	cout<<l-1<<endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

E - Graph Destruction

大意：
有一张图，从1到n开始删顶点，每次将与该顶点相连的所有边都去掉，并输出当前情况下图的联通块数。

思路：
要计算联通块数，就会想到并查集，但是并查集能实现的操作只有加，而题目是减，所以要考虑逆向思维。

倒着统计集合。从大到小遍历到i点时，先更新连通块数量+1，它的边一定都是连向较大的点的，如果二者在一个集合里，那么联通块的数量就减1，否则让二者放到一个集合里。

code：
 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll N=2e5+10;
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
ll dir[][4]={
   {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
ll n,m;
ll a,b;
ll fa[N];
vector<ll> vt[N];
ll vis[N];
ll ans[N];
ll find(ll x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void solve()
{
    cin>>n>>m;
    ll cnt=0;
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i)
    {
    	cin>>a>>b;
    	vt[a].push_back(b);
	}
	ll sd=0;
	for(int i=n;i;--i)
	{
		sd++;
		for(ll k:vt[i])
		{
			ll fx=find(i);ll fy=find(k);
			if(fx!=fy)
			{
				sd--;
				fa[fx]=fy;
			}
		}
		ans[i]=sd;
	}
	for(int i=2;i<=n;++i) cout<<ans[i]<<endl;
	cout<<0;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}