M. Flipping Cards

M. Flipping Cards

签到， 二分可选的最大中位数，把大于该中位数的视为1，小于该位的视为0， 每次check dp下最大能取到的比该为数字大的次数，大于 n / 2 + 1则状态可达, 其中dp状态0表示还未进入，1表示正在翻转中，2表示此前已经翻转过

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
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<i64> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }

    auto ck = [&](int mid) -> bool {
        vector dp(n + 1, vector<int> (4));
        bool is = 0;
        int maxp = 0;
        for (int i = 1; i <= n; i++) {
            bool x = (a[i] >= mid);
            bool y = (b[i] >= mid);


            dp[i][0] = dp[i - 1][0] + x;
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + y;
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + x;
        }

        maxp = max({dp[n][0], dp[n][1], dp[n][2]});
        if (n / 2 + 1 <= maxp) {
            return true;
        }
        return false;
    };

    i64 l = 1, r = 1e9 + 7;
    while (l <= r) {
        i64 mid = l + ((r - l) >> 1);
        if ((ck(mid))) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << r << '\n';

    return 0;
}

G. Hard Brackets Problem

G. Hard Brackets Problem

简单字符串题目

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
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    string s;
    cin >> s;

    stack<int> stk;
    vector<char> ans;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            stk.push(1);
            ans.push_back('(');
        } else {
            if (stk.empty()) {
            
            } else {
                stk.pop();
            }
            ans.push_back(')');
        }
    }   

    if (!stk.empty()) {
        cout << "impossible" << '\n';
    } else {
        for (auto x : ans) {
            cout << x;
        }
        cout << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

K. Randias Permutation Task

K. Randias Permutation Task

给出m个长度位n的排列，从1 - m操作A ∘ B,求总的排列总数

注意到n * m <= 180, 取大概坏的情况， n = m = sqrt(180), 总数不会很大，直接set暴力模拟过去，从1到n维护两个set， 一个是到达i之前的可能排列，一个是到了i，并操作i后的可能排列，从1 - m更新即可

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
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector a(m + 1, vector<int> (n + 1));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }

    set<vector<int>> st;
    st.insert(a[1]);
    set<vector<int>> nst;

    vector<int> np(n + 1);
    auto f = [&](vector<int> p, int pos) -> vector<int> {
        for (int i = 1; i <= n; i++) {
            np[i] = p[a[pos][i]];
        }
        return np;
    };

    for (int i = 2; i <= m; i++) {
        for (auto ar : st) {
            vector<int> c = f(ar, i);
            nst.insert(c);
        }
        st.insert(a[i]);
        for (auto x : nst) {
            st.insert(x);
        }
    }

    // for (auto x : st) {
    //     for (int i = 1; i <= n; i++) {
    //         cout << x[i] << " \n"[i == n];
    //     }
    // }
    cout << st.size() << '\n';

    return 0;
}

B. The Game

B. The Game

给出两个mutiset A， B，每次操作可以选择A的一个元素x, 操作x = x + 1同时删除一个元素，求问能不能把A变成B并输出所有步骤

考虑A变成B最后必然是m个匹配，先把A和B排序， 算出A最大m位的和sa和B所有m位的和sb，所需要的操作数是sb - sa，则A中最后需要大小为m + (sb - sa) 可直接到达B状态，注意这里不能直接对于最大的m位开始操作，因为A集合的大小可能巨大，会有很多冗余操作，需要把冗余的数字删除，删除过程中可能出现最后留下的数字过大，大到超过m个最大位的情况。

应当将A拆为两个部分， 一个最大的m位数字A1_Set，一个是除了m位的其他数字A2_Set，我们的目的就变成了将A2_set元素个数变成(sb - sa),即现在需要的操作次数， 每次对最小的数字进行操作，用两个小根堆存储两个部分的集合，动态维护当前A所需要的集合总大小和最大的m位数字，当sb < sa或者最大m位数字的最小值大于B【0】的时候无解，否则模拟输出答案, 注意开longlong，因为这个WA on 46, 且找了1小时不知道为什么，，

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
#define int long long
constexpr int inf = 1e9 + 7;
void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    ranges::sort(a);
    ranges::sort(b);

    int sb = std::accumulate(b.begin(), b.end(), 0LL);
    int sa{};

    priority_queue<int, vector<int>, greater<int>> p, q;
    vector<int> ans;

    for (int i = 0; i < m; i++) {
        int j = n - i - 1;
        sa += a[j];
        p.push(a[j]);

        if (sa > sb) {
            cout << -1 << '\n';
            return;
        } 
    }

    int ned = 0;
    for (int i = 0; i < m; i++) {
        int j = n - i - 1;
        int k = m - i - 1;
        if (a[j] > b[k]) {
            cout << -1 << '\n';
            return;
        }

        ned += b[k] - a[j];
    }

    if (n - m < ned) {
        cout << -1 << '\n';
        return;
    }

    for (int i = 0; i <= n - m - 1; i++) {
        q.push(a[i]);
    }

    while (q.size() > ned) {
        int x = q.top();
        q.pop();

        ans.push_back(x);
        x++;    

        if (x > p.top()) {
            sa -= p.top();
            sa += x;

            ned -= x - p.top();
            if (sa > sb) {
                cout << -1 << '\n';
                return;
            }

            int H = p.top();
            p.pop();

            p.push(x);
            x = H;
        }

        q.push(x);
        q.pop();
    }

    deque<int> dq;
    while (!p.empty()) {
        dq.push_back(p.top());
        p.pop();
    }

    while (!b.empty()) {
        int x = b.back();
        b.pop_back();
        if (dq.empty()) {
            cout << -1 << '\n';
            return;
        }

        int y = dq.back();
        dq.pop_back();

        if (x == y) {
            continue;
        } 

        while (y < x) {
            ans.push_back(y);
            y++;

            if (q.empty()) {
                if (dq.empty()) {
                    cout << -1 << '\n';
                    return;
                }
                dq.pop_front();
            } else {
                q.pop();
            }
        }
    }

    cout << ans.size() << '\n';
    for (auto x : ans) {
        cout << x << " ";
    }
    cout << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

H. Sweet Sugar

H. Sweet Sugar

树形dp， 因为元素都是0， 1， 2组成，那么考虑一个节点的为根的子树，如果没有1， 那么他的可达为 0, 2, 4 …., 即子树内2的倍数权值，如果出现了1，那么他的可达状态为1, 3, 5 ……, 同时附带被1分割的偶数块或者两个相连的偶数块权值和，想到这里即不能简单维护一个奇数偶数状态，使用树形dp，分别表示当前子树能到的最大奇数和和最大偶数和，因为权值为2的子树或节点总是能够直接剪掉且不影响主干，那么改子树能到达的状态就是1, 3, 5 ….最大奇数sum 以及 2, 4…. 最大偶数和， dp之后对于该子树如果可以取到K， 则切断它和父亲联系并更新答案，此贪心策略总是最优

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
constexpr int inf = -1e9;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<vector<int>> e(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        e[u].push_back(v);
        e[v].push_back(u);
    }

    vector dp(n + 1, vector<int>(2, inf));
    int ans = 0;

    auto dfs = [&](auto self, int u, int fa) -> void {
        dp[u][0] = dp[u][1] = inf;
        dp[u][a[u] & 1] = a[u];

        for (auto v : e[u]) {
            if (v == fa) continue;

            self(self, v, u);

            int x0 = dp[u][0], x1 = dp[u][1];
            int y0 = dp[v][0], y1 = dp[v][1];

            int n0 = inf, n1 = inf;

            n0 = max(n0, x0);
            n1 = max(n1, x1);

            if (x0 != inf && y0 != inf) n0 = max(n0, x0 + y0);
            if (x0 != inf && y1 != inf) n1 = max(n1, x0 + y1);
            if (x1 != inf && y0 != inf) n1 = max(n1, x1 + y0);
            if (x1 != inf && y1 != inf) n0 = max(n0, x1 + y1);

            dp[u][0] = n0;
            dp[u][1] = n1;
        }

        if (dp[u][k & 1] >= k) {
            ans++;
            dp[u][0] = dp[u][1] = inf; 
        }
    };

    dfs(dfs, 1, 0);

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }
    
    return 0;
}