Atcoder 229
Atcoder 229
\(D.\)Longest X
题意
给定一个长度为\(N\)的字符串\(S\)，\(S\)中包含\(.\)和\(X\)两种字符，现在你可以将其中\(K\)个\(.\)替换成\(X\)，问最后可能构成的连续的\(X\)序列的长度最大是多少 \(1\le N,K \le 2\times 10^5\)
Sol
统计\(.\)个数的前缀和为\(sum[i]\)表示下标为\(i\)之前含有多少个\(.\)，那么我们可以枚举左端点，然后右端点依次递增，然后用前缀和\(O(1)\)求出\([l,r]\)之间有多少个\(.\)，判断是否小于\(K\)，让\(r\)一直递增直到大于\(K\)为止，很明显这里\(l,r\)都是单调递增的，因为假设\([l,r]\)是用掉了所有\(K\)区间，那么说明\([l,r]\)之间的\(.\)最少，\(X\)最多，当增加\(l\)时，\(X\)只可能变少，所以\(r\)要让答案更优就必须增大。
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=2e5+10;
int cnt[N];
int main()
{
string s;
int k;
cin>>s;
rd(k);
int n=s.size();
for(int i=0;i \(E.\)Graph Destruction
题意
给定\(N\)个点\(M\)条边的无向图，按顺序删除\(1,2, ...,N\)这\(N\)个点，问每删除一个点当前图有多少个连通块。
\(1\le N,M\le 2\times 10^5\)
Sol
一开始我的想法是以拓扑序的方式统计每个点的出度，但只过了一半的数据，查了半天查不出来。
正解是用并查集维护连通块，但并查集支持的的连边统计连通块，但我们要进行的操作是删边，因此从\(N\)号节点开始加入节点连边，注意在一开连边的时候只从小的点向大的点连边，因为逆序处理，大的点不会影响它前面小的点，因为小的点会比它先被删除。
从\(N\)开始加，此时连通块个数+1,然后遍历它指向的大的点，如果他们不再一个连通块里，那么总的连通块数-1,最后总的连通块个数就是此时第\(i\)个点对应的答案。
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N = 2e5+10, M = 2e5+10;
vectorE[N];
int f[N];
int find(int x)
{
return x==f[x]?x:f[x]=find(f[x]);
}
int main()
{
int n,m;
rd(n),rd(m);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
int u,v;
if(u>v) swap(u,v);
rd(u),rd(v);
if(u>v) swap(u,v);
if(u==v) continue;
E[u].pb(v);
}
int ans=0;
vectorres={0};
for(int u=n;u>=2;u--)
{
ans++;
for(auto v:E[u])
{
int fu=find(u),fv=find(v);
if(fu!=fv)
{
f[fu]=fv;
ans--;
}
}
res.pb(ans);
}
reverse(res.begin(),res.end());
for(auto x:res) cout< \(F.\)Make Bipartite
题意
给定\(N+1\)给点，从\(0\)到\(N\)开始编号，每个点\(i\)(\(1\le i\le N\))向\(0\)号点连边权为\(A_i\)的边，然后\(i\)号点向\(i+1\)号点连边权为\(B_i\)的边\(（N+1=1）\)，问如果把这个图变成二分图，最小需要删除的边的权重和是多少
\(1\le N\le 2\times10^5\) \(1\le A_i,B_i\le 10^9\)
Sol
进行二分染色，不妨固定\(0\)号点为白色(用\(0/1\)表示白色/黑色)
定义\(dp[i][j][k]\)表示当前染到了第\(i\)号点，当前\(i\)号点染色为\(j\)，\(1\)号点染色为\(k\)的最小边权和
初始\(dp[1][0][0]=A_i\)表示\(1\)号点染色为白色，说明\(1\)号点和\(0\)号点在一个点集里，那么它们之间就不能有边，于是要删去的边权为\(A_i\)
\(dp[1][1][1]=0\)表示\(1\)号点和\(0\)号点不在一个点集里，说明不需要删边，所以为\(0\)
转移：\(dp[i][j][k]=min(dp[i][j][k],dp[i-1][prej][k]+(j==0?A_i:0)+(prej==j?B_{i-1}:0))\)
第\(i\)个点由第\(i-1\)个点转移而来，如果第\(i\)个点染色为\(0\)，说明\(i\)号点和\(0\)在一个集合里，那么就要断开和\(0\)所连的边；
如果第\(i\)个染色\(j\)和第\(i-1\)个点的染色\(prej\)一样，说明\(i\)号点和\(i+1\)号点在一个点集里，要断开它们之间的边，答案要加上\(B_{i-1}\)
最后只需要检查一遍染完\(N\)点的所有集合就可以了
#include
#define ll long long
#define inf 1e18
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=2e5+10;
int A[N],B[N];
ll dp[N][2][2];
int main()
{
int n;
rd(n);
for(int i=1;i<=n;i++) rd(A[i]);
for(int i=1;i<=n;i++) rd(B[i]);
for(int i=1;i<=n;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
dp[i][j][k]=1e18;
dp[1][0][0]=A[1];
dp[1][1][1]=0;
for(int i=2;i<=n;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
for(int prej=0;prej<2;prej++)
dp[i][j][k]=min(dp[i][j][k],dp[i-1][prej][k]+(j==0?A[i]:0)+(j==prej?B[i-1]:0));
ll ans=1e18;
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
ans=min(ans,dp[n][j][k]+(j==k?B[n]:0));
cout< \(G.\) Longest Y
题意
给定一个长度为\(N\)的字符串\(S\)，\(S\)中包含\(.\)和\(Y\)两种字符，现在你可以进行\(K\)次操作，每次操作可以交换相邻的两个字符，问最后可能构成的连续的\(Y\)序列的长度最大是多少 \(2\le N,K \le 2\times 10^5\) \(1\le K\le 0^{12}\)
Sol
将所有\(Y\)的位置记录到一个数组\(B\)中
令\(B_i=B_i-i\)，那么将\(B_i+1\)对应于将原序列的位置和右边的字符交换，将\(B_i-1\)对应于将原序列的位置和左边的字符交换。
现在问题就是问进行\(K\)次加减运算最多可以令多少个\(B_i\)相同。
考虑吧长度为\(Len\)的区间变为一样的数最少需要几次操作，这是一个经典的问题
\(f(Len)=\sum_{i=t}^{min(Size(B),t+Len-1)}|B_t-x|\)，其中\(x\)为这个区间的中位数
因此可以枚举二分区间长度即可。如果操作次数小于\(k\)，说明区间长度还可以更大，反之区间长度就要变小
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=2e5+10;
int cnt;
ll k;
ll B[N],sum[N];
bool check(int len)
{
for(int l=1;l+len-1<=cnt;l++)
{
ll s=0;
int r=min(l+len-1,cnt);
int mid=l+r>>1;
s+=(mid-l+1ll)*B[mid]-(sum[mid]-sum[l-1]);
s+=(sum[r]-sum[mid-1])-(r-mid+1ll)*B[mid];
if(s<=k)return true;
}
return false;
}
int main()
{
string s;
cin>>s;
rd(k);
int n=s.size();
for(int i=0;i>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<