当前位置: 首页 > article >正文

牛客周赛 Round 85

牛客周赛 Round 85

在这里插入图片描述

A-小紫的均势博弈

题意:

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

思路:

奇数小红胜,偶数小紫胜 奇数小红胜,偶数小紫胜 奇数小红胜,偶数小紫胜

Code:

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

B-小紫的劣势博弈

题意:

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

小红的目的是令 x 尽可能小,小紫是令 x 尽可能大,双方最优操作,求 x 最终的值 小红的目的是令x尽可能小,小紫是令x尽可能大,双方最优操作,求x最终的值 小红的目的是令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, 小紫可以选择全是1的连续子串全部变成0 给定01字符串,小红可以选择全是0的连续子串全部变成1,小紫可以选择全是1的连续子串全部变成0

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

思路:

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

统计一下 010 和 101 连续子串的数量,均不大于 1 即可操作成功,否则失败 统计一下010和101连续子串的数量,均不大于1即可操作成功,否则失败 统计一下010101连续子串的数量,均不大于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 串,小红先手操作可以删除该串的一个非空前缀,小紫后操作可以删除一个后缀 ( 可以为空 ) 给定01串,小红先手操作可以删除该串的一个非空前缀,小紫后操作可以删除一个后缀(可以为空) 给定01串,小红先手操作可以删除该串的一个非空前缀,小紫后操作可以删除一个后缀(可以为空)

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

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

思路:

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

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 条线段,当前所有线段为红色,现在至少选择一条线段染成紫色,是否可以使得不存在两条红色线段相交 数轴上n条线段,当前所有线段为红色,现在至少选择一条线段染成紫色,是否可以使得不存在两条红色线段相交 数轴上n条线段,当前所有线段为红色,现在至少选择一条线段染成紫色,是否可以使得不存在两条红色线段相交

思路:

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

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

如何判断是否相交 如何判断是否相交 如何判断是否相交

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

若当前左边界大于 a b 数组的最右边界,则直接加入,最后 a b 数组中的线段为两种染色方案,随意输出其一即可 若当前左边界大于ab数组的最右边界,则直接加入,最后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 个节点染成紫色,使得最大红色联通块最小 n个节点组成树,n-1条边,当前所有节点均为红色,现在需要将其中k个节点染成紫色,使得最大红色联通块最小 n个节点组成树,n1条边,当前所有节点均为红色,现在需要将其中k个节点染成紫色,使得最大红色联通块最小

思路:

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

二分当前最大联通块大小 m i d 二分当前最大联通块大小mid 二分当前最大联通块大小mid

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

最终需要更改的节点个数小于等于 k 个即可完成当前联通块的染色 最终需要更改的节点个数小于等于k个即可完成当前联通块的染色 最终需要更改的节点个数小于等于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;
} 

http://www.kler.cn/a/589374.html

相关文章:

  • ElementUI 表格中插入图片缩略图,鼠标悬停显示大图
  • 电脑型号与尺寸
  • Leetcode Hot 100 200.岛屿数量
  • 【Agent】OpenManus-Flow-BaseFlow详细分析
  • element-ui progress 组件源码分享
  • 蓝牙技术联盟中国实体成立!华为、小米发声支持本土化战略
  • 实战ansible-playbook
  • 《C#上位机开发从门外到门内》3-3:基于USB的设备管理系统
  • MCP 开放协议
  • Visual Studio里的“公共语言运行时支持”各选项的作用是什么,分别适用于哪些场景?
  • 基于CPLD+MCU的3U机箱数字量输入采集板DI,主要针对标准DC110V开关量信号进行采集处理
  • LINUX驱动学习之IIC驱动-----以AP3216C为例
  • ZED X系列双目3D相机的耐用性与创新设计解析
  • 基于python+django+vue.js开发的停车管理系统运行-期末作业
  • 基于Python的tkinter开发的一个工具,解析图片文件名并将数据自动化导出为Excel文件
  • Spring 原生启动过程
  • Jenkins 快讯
  • A - 整数的简单问题/A - A Simple Problem with Integers
  • Linux centos7误删/boot拯救方法
  • 【系统架构设计师】操作系统 - 文件管理 ③ ( 树形目录结构 | 文件属性 | 绝对路径 与 相对路径 )