牛客周赛 Round 85

牛客周赛 Round 85

A-小紫的均势博弈

题意：

$n枚石子，小红和小紫轮流拿一个石子，小红先手$
$谁先不能拿谁输$

思路：

$奇数小红胜，偶数小紫胜$

Code：

void solve() {   
    int n; cin >> n;
    cout << (n & 1 ? "kou" : "yukari") << endl;
} 

B-小紫的劣势博弈

题意：

$n个整数元素和一个整数x为0$
$小红小紫先后进行操作$
$小红每次选择一个数加到x中$
$小紫每次选择一个数减到x中$

$小红的目的是令x尽可能小，小紫是令x尽可能大，双方最优操作，求x最终的值$

思路：

$每次取当前最小的元素轮流+-到x中即可$

Code:

void solve() {   
    int n; cin >> n;
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 0; i < n; i ++) {
        int x; cin >> x;
        q.push(x);
    }
    int ans = 0;
    int flag = 1;
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        if (flag) ans += t, flag = 0;
        else ans -= t, flag = 1;
    }
    cout << ans << endl;
} 

C-小紫的01串操作

题意：

$给定01字符串，小红可以选择全是0的连续子串全部变成1，小紫可以选择全是1的连续子串全部变成0$

$每人均可操作最多一次，顺序任意，是否可以将01串变成全部相同的字符串$

思路：

$将连续的0或1的子串全部变成单独的，例如000111000->010$

$统计一下010和101连续子串的数量，均不大于1即可操作成功，否则失败$

Code：

void solve() {   
    string s; cin >> s;
    string t = "";
    t += s[0];
    for (int i = 1; i < s.size(); i ++) {
        if (s[i] != s[i - 1]) t += s[i];
    } 
    if (t.size() <= 2) {
        cout << "Yes" << endl;
        return;
    }
    int x = 0, y = 0;
    for (int i = 1; i < t.size() - 1; i ++) {
        if (t[i - 1] == '0' && t[i] == '1' && t[i + 1] == '0') x ++;
        if (t[i - 1] == '1' && t[i] == '0' && t[i + 1] == '1') y ++;
    }
    if (x <= 1 || y <= 1) {
        cout << "Yes" << endl;
        return;
    }
    cout << "No" << endl;
} 

D-小紫的优势博弈

题意：

$定义双生串为字符串中每种字符出现次数均为偶数$

$给定01串，小红先手操作可以删除该串的一个非空前缀，小紫后操作可以删除一个后缀(可以为空)$

$若最终生成一个双生串则小紫获胜$

$小红分别对前缀1到n进行删除操作，小紫获胜的概率是多少$

思路：

$统计一下0和1前缀的数量，暴力判断删除后缀是否能满足条件即可$

Code：

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

    vector<int> p0(n + 1, 0), p1(n + 1, 0);
    for (int i = 0; i < n; i++) {
        p0[i + 1] = p0[i] + (s[i] == '0');
        p1[i + 1] = p1[i] + (s[i] == '1');
    }

    int win = 0;
    for (int i = 1; i <= n; i++) {  
        for (int j = 0; j <= n - i; j++) {  
            int cnt_0 = p0[n - j] - p0[i - 1];
            int cnt_1 = p1[n - j] - p1[i - 1];
            if (cnt_0 % 2 == 0 && cnt_1 % 2 == 0 && (cnt_0 || cnt_1) && i-1) {
                //cout << n - j << ' ' << i - 1 << endl;
                win++;
                break; 
            }
        }
    }
    printf("%.6f\n", (double)(win) / n);
} 

E-小紫的线段染色

题意：

$数轴上n条线段，当前所有线段为红色，现在至少选择一条线段染成紫色，是否可以使得不存在两条红色线段相交$

思路：

$首先优先按照左边界进行排序，其次按照右边界，均为从小到大排序，这样在之后的操作中可以保证左边界始终小于等于前一线段$

$之后将当前不相交的线段放到a数组中，若出现相交的线段则放到b数组中，若依然相交，直接输出-1$

$如何判断是否相交$

$按照之前的排序，我们无需额外处理左边界，只需要判断当前线段的左边界是否大于ab数组中的最右边界即可$

$若当前左边界大于ab数组的最右边界，则直接加入，最后ab数组中的线段为两种染色方案，随意输出其一即可$

Code：

struct three{
    int l, r, pos;
}v[N];

bool cmp(three a, three b) {
    if (a.l == b.l) return a.r < b.r;
    return a.l < b.l;
}

void solve() {   
    int n; cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> v[i].l >> v[i].r;
        v[i].pos = i;
    }
    sort(v + 1, v + n + 1, cmp);
    vector<int> a, b;
    int ra = -1, rb = -1;
    for (int i = 1; i <= n; i ++) {
        auto [l, r, pos] = v[i];
        if (l > ra) {
            a.push_back(pos);
            ra = r;
        } else if (l > rb) {
            b.push_back(pos);
            rb = r;
        } else {
            cout << "-1" << endl;
            return;
        }
    }
    sort(a.begin(), a.end());
    cout << a.size() << endl;
    for (auto t : a) cout << t << ' ';
    cout << endl;
} 

F-紫的树上染色

题意：

$n个节点组成树，n-1条边，当前所有节点均为红色，现在需要将其中k个节点染成紫色，使得最大红色联通块最小$

思路：

$求最小的最大值，经典的二分，标准的正解$

$二分当前最大联通块大小mid$

$dfs统计棵子树的大小，从叶节点开始向上递归，若当前子树大于mid，则将当前子树根节点染成紫色，向上递归的大小更改为0$

$最终需要更改的节点个数小于等于k个即可完成当前联通块的染色$

Code：

int n, k;
vector<int> g[N];
int st[N], cnt[N];
int sum;

int dfs(int x, int mid) {
    if (st[x]) return cnt[x];
    st[x] = 1, cnt[x] = 1;
    for (auto ne : g[x]) {
        if (st[ne]) continue;
        else cnt[x] += dfs(ne, mid);
    }
    if (cnt[x] > mid) {
        cnt[x] = 0;
        sum ++;
    }
    return cnt[x];
}

bool check(int x) {
    for (int i = 1; i <= n; i ++) st[i] = 0, cnt[i] = 0;
    sum = 0;
    dfs(1, x);
    return sum <= k;
}

void solve() {   
    cin >> n >> k;
    for (int i = 1; i < n; i ++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if (n - k <= 1) {
        cout << n - k << endl;
        return;
    } 
    int l = 1, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}