D - Longest X

题意：

给定一个只由$X$和$‘.’$组成的字符串,现在可以把任意位置上的$‘.’$改成$X$，问最多改$K$次，由连续的$X$组成的字符串的最长长度
这个题的思路与下面的$F$类似，所以放在前面做引导。

思路：

直接二分区间长度，然后看对应区间内，修改最多$K$次，能否全部都变成$X$即可，也可以双指针，来做这个题

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define ll long long
char s[N];
ll sum[N];
int len;
int k;
struct node {int id;int dis;
} pos[N];
bool check(int x) {for (int i = 1; i + x - 1 <= len; i++) {int j = i + x - 1;if (sum[j] - sum[i - 1] + k >= x) {return 1;}}return 0;
}
int main() {cin >> s + 1 >> k;len = strlen(s + 1);ll num = 0;for (int i = 1; i <= len; i++) {if (s[i] == 'X') {sum[i] = ++num;} else {sum[i] = sum[i - 1];}}if (len - sum[len] <= k) {printf("%d\n", len);return 0;}int l = 0, r = len;while (l < r) {int mid = (l + r + 1) >> 1;if (check(mid)) {l = mid;} else {r = mid - 1;}}cout << l << endl;
}

E - Graph Destruction

题意：

$N$个点$M$条边的无向图，现在问每次按照顺序(1,2…n)删除一个点，问图中剩下的连通块的数量是多少？

思路：

直接反着进行这个操作，每次往图中加入一个点，每加入一个点之前，先判断图中连通块的数量，每次新加进来的一个点，如果能跟已有的点形成一个连通块的话，数量$-1$

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;vector<int> g[N];
int n, m;
int fa[N];
int res;
int ans[N];
int find(int x) {if (x != fa[x]) fa[x] = find(fa[x]);return fa[x];
}void Union(int a, int b) {a = find(a), b = find(b);if (a != b) {res--;fa[a] = b;}
}
int main() {for (int i = 1; i < N; i++) {fa[i] = i;}cin >> n >> m;for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);}for (int i = n; i >= 1; i--) {ans[i] = res++;for (int j = 0; j < g[i].size(); j++) {int to = g[i][j];if (to > i) {Union(to, i);}}}for (int i = 1; i <= n; i++) {cout << ans[i] << endl;}
}

F - Make Bipartite

题意：

给定一个$N+1$个点的图，$0,1,2....N$
$0$号点在中间， $1,2,3,4...N$与$0$直接相连，$a_i$代表$i$号点与$0$点相连的边权，$b_i$代表$i$点与$i+1$号点直接相连的边权，$N+1$代表$1$号点，此时形成一个网状的图，问现在删除一些边，使得图变成一个二分图，问删除边的边权和最小是多少？

思路：

因为要构造二分图，所以就可以认为图中的点，分为黑白$01$两组，下面用$0$代表黑，$1$代表白
此时设$0$点为黑色,如果设为白色是一样的，镜像而已。
那么此时其他点就需要考虑所有情况
设$dp(i,j,k)$代表从$1$染色染到$i$，$i$的颜色是$j$，$1$的颜色是$k$
起始状态
$dp(1,0,0)=a_1$，因为$1$号与$0$号都是黑色，所以需要断开边$a_1$
$dp(1,1,1)=0$,因为$1$与$0$不同色，不同断开边
那么此时$dp(i,1,0)=min(dp(i-1,1,0)+b_{i-1},dp(i-1,0,0))$
$dp(i,1,1)=min(dp(i-1,1,1)+b_{i-1}+dp(i-1,0,1))$
$dp(i,0,1)=min(dp(i-1,0,1)+a_i+b_{i-1},dp(i-1,1,1)+a_i)$
$dp(i,0,0)=min(dp(i-1,0,0)+a_i+b_{i-1},dp(i-1,1,0)+a_i)$
状态方程的转移，就是看当前点与上一个点的相连状态和$0$点的项链状态
因为$N$与$1$还相连，所以最后取答案时两者颜色相同时注意取$b_n$即可
最终在$dp(n,1,1)+b_n,dp(n,0,0)+b[n],dp(n,1,0),dp(n,0,1)$中选最小的即可。

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
ll dp[N][2][2];
ll a[N], b[N];
int n;int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {cin >> b[i];}memset(dp, 0x3f, sizeof(dp));dp[1][0][0] = a[1];dp[1][1][1] = 0;for (int i = 2; i <= n; i++) {dp[i][1][0] = min({dp[i - 1][0][0], dp[i - 1][1][0] + b[i - 1]});dp[i][1][1] = min({dp[i - 1][0][1], dp[i - 1][1][1] + b[i - 1]});dp[i][0][1] = min({dp[i - 1][1][1] + a[i], dp[i - 1][0][1] + b[i - 1] + a[i]});dp[i][0][0] = min({dp[i - 1][1][0] + a[i], dp[i - 1][0][0] + b[i - 1] + a[i]});}ll res = 1e18;for (int i = 0; i <= 1; i++) {for (int j = 0; j <= 1; j++) {if(i==j) {res=min(res,dp[n][i][j]+b[n]);} else {res=min(res,dp[n][i][j]);}}}cout << res << endl;
}

G - Longest Y

题意：

给定一个仅有$Y$和$‘.’$组成的字符串，现在可以进行最多$K$次操作，可以进行的操作就是可以将相邻的字符交换位置，问最后能形成的由连续的$Y$组成的字符串长度是多长

思路：

把每个$Y$的位置记录下来形成一个$A$数组，例如样例一的$A=[1,2,6,8,10]$，现在再令$B$数组为$A_i-i$，即$B=[0,0,3,4,5]$，两个字符如果相邻的话，就代表它在$B$数组中的数字是一样的，因为每次只能交换相邻的字符，所以对于$B$数组来说就是只能对其中的元素$+1$（代表与右边的字符交换）或者$-1$（代表与左边的字符交换）
此时问题转换为了，最多进行$K$次$+1或-1$操作，最多能使几个数字变得相同 (问题1)

解决问题$1$，可以先解决最多进行$K$次操作，能否使得长度为$X$的数组内的元素都变成一样的数 (问题2)

解决问题2之前，考虑要想把长度为$X$的数组内的元素都变成同一个元素，所需要的最小次数是多少（问题3），这就是一个经典的问题了，可以转换为一个函数
$f(x)=\sum _{i=t}^{t+X-1}|B_i-x|$
是这个函数最小，那么$x$只需要取这个范围内的中位数即可，即$B_{t+X/2}$，此时$f(x)$最小,此时解决了问题三，就可以二分枚举区间长度，然后看这个区间内的元素进行$K$次操作后，能否都变成相同的数字。
此时问题就变得和$D$类似，可以用二分或者双指针解决了

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define ll long longll a[N], b[N];
ll sum[N];
char s[N];
ll k;
int len;
int num;bool check(int x) {for (int l = 1; l + x - 1 <= num; l++) {int r = min(x + l - 1, num);int mid = (l + r) / 2;ll all = b[mid] * (mid - l + 1ll) - (sum[mid] - sum[l - 1]);all += (sum[r] - sum[mid - 1]) - b[mid] * (r - mid + 1);if (all <= k) {return 1;}}return 0;
}
int main() {cin >> s + 1 >> k;len = strlen(s + 1);for (int i = 1; i <= len; i++) {if (s[i] == 'Y') {a[++num] = i;}}for (int i = 1; i <= num; i++) {b[i] = a[i] - i;}sort(b + 1, b + num + 1);for (int i = 1; i <= num; i++) {sum[i] = sum[i - 1] + b[i];}int l = 0, r = N;while (l < r) {int mid = l + r + 1 >> 1;if (check(mid)) {l = mid;} else {r = mid - 1;}}cout << l << endl;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
int b[maxn], sum[maxn];
int a[maxn];
string s;
int n, m, k, ans = 0;
int get(int l, int r) {int all = 0;int mid = (l + r) / 2;all = b[mid] * (mid - l + 1) - (sum[mid] - sum[l - 1]);all += (sum[r] - sum[mid - 1]) - b[mid] * (r - mid + 1);return all;
}
signed main() {cin >> s >> k;int n = s.size();for (int i = 0; i < n; ++i)if (s[i] == 'Y') {a[++m]=i;}for (int i = 1; i <= m; ++i) b[i] = a[i] - i;for (int i = 1; i <= m; ++i) sum[i] = sum[i - 1] + b[i];int i = 1;for (int j = 1; j <= m; ++j) {while (i <= j && get(i, j) > k) i++;ans = max(j - i + 1, ans);}cout << ans;return 0;
}

To be continued
如果你有任何建议或者批评和补充，请留言指出，不胜感激