AtCoder Beginner Contest 229_atcoder beginner contest 229 g - longest y

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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 long

ll 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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