cf_934_div2

Destroying Bridges

A

题意

给定一个强连通图和最多减去的边数。从 1 结点出发，问如何使得访问的到的点最少。

解题思路

因为是强连通图，切断任意两点的联系，就是减去 n - 1条边，减去1和其他边的连边便可以实现无联通，也就是最优解。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10, inf = 1 << 30;

void solve() {
    int n, k;
    cin >> n >> k;
    if (k >= n - 1) {
        cout << 1 << endl;
    } else {
        cout << n << endl;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

Equal XOR

B

题意

给定一个长度为2*n的数组，数组元素由1~n组成，每个数出现两次。

现在要找到以 n 为划分的连个区间中长度为2 * k的异或和相同的子集。

解题思路

每个数只有两种情况：分别在两个数组中，或者在一个数组中出现了2次。

与0异或值不变，关键就是控制两边的异或值：

1. 优先塞进在一边出现两次的数，保证不影响异或值
2. 然后赛两边都出现的数，保证两边异或的值相同。

严格的证明：不会，反正是guess，以后也不想太多了

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10, inf = 1 << 30;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    vector<int> mp(n + 1);
    vector<int> o(n + 1);
    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
        o[a[i]] ++ ;
        if (o[a[i]] == 2) {
            mp[a[i]] = 1;
        }
    }
    vector<int> oo(n + 1);
    for (int i = 0; i < n; i ++ ) {
        cin >> b[i];
        oo[b[i]] ++ ;
        if (oo[b[i]] == 2) {
            mp[b[i]] = 2;
        }
    }
    vector<int> l, r;
    for (int i = 1; i <= n; i ++ ) {
        if (mp[i]) {
            if (mp[i] == 1) {
                if (l.size() < k * 2) {
                    l.pb(i), l.pb(i);
                }
            } else {
                if (r.size() < k * 2) {
                    r.pb(i), r.pb(i);
                }
            }
        }
    }
    for (int i = 1; i <= n; i ++ ) {
        if (!mp[i]) {
            if (l.size() < k * 2) {
                l.pb(i);
            }
            if (r.size() < k * 2) {
                r.pb(i);
            }
        }
    }
    for (int i = 0; i < l.size(); i ++ ) {
        cout << l[i] << " \n"[i == l.size() - 1];
    }
    for (int i = 0; i < r.size(); i ++ ) {
        cout << r[i] << " \n"[i == r.size() - 1];
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

MEX Game 1

C

题意

给定一个长度为 n 的数组，元素都小于 n 。

A先手：选一个元素，放到一个集合中，然后删除

B：选一个元素，删除。

A要保证集合的MEX尽量大，B不希望。

解题思路

特殊的情况：出现一次的数，那么A只能拿一个.

如果一个数出现多次，其实可以演变成A后手，就是B拿哪个，A就哪哪个。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10, inf = 1 << 30;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> o(n + 1);
    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
        o[a[i]] ++ ;
    }
    int ans = 0;
    bool flag = 1;
    for (int i = 0; i <= n; i ++ ) {
        if (!o[i]) {
            break;
        } else if (o[i] == 1) {
            if (!flag) {
                break;
            }
            flag = 0;
        }
        ans = i + 1;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}