牛客周赛 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个整数元素和一个整数x为0
小红小紫先后进行操作
小红小紫先后进行操作
小红小紫先后进行操作
小红每次选择一个数加到
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 将连续的0或1的子串全部变成单独的,例如000111000−>010
统计一下 010 和 101 连续子串的数量,均不大于 1 即可操作成功,否则失败 统计一下010和101连续子串的数量,均不大于1即可操作成功,否则失败 统计一下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 串,小红先手操作可以删除该串的一个非空前缀,小紫后操作可以删除一个后缀 ( 可以为空 ) 给定01串,小红先手操作可以删除该串的一个非空前缀,小紫后操作可以删除一个后缀(可以为空) 给定01串,小红先手操作可以删除该串的一个非空前缀,小紫后操作可以删除一个后缀(可以为空)
若最终生成一个双生串则小紫获胜 若最终生成一个双生串则小紫获胜 若最终生成一个双生串则小紫获胜
小红分别对前缀 1 到 n 进行删除操作,小紫获胜的概率是多少 小红分别对前缀1到n进行删除操作,小紫获胜的概率是多少 小红分别对前缀1到n进行删除操作,小紫获胜的概率是多少
思路:
统计一下 0 和 1 前缀的数量,暴力判断删除后缀是否能满足条件即可 统计一下0和1前缀的数量,暴力判断删除后缀是否能满足条件即可 统计一下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 条线段,当前所有线段为红色,现在至少选择一条线段染成紫色,是否可以使得不存在两条红色线段相交 数轴上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个节点组成树,n−1条边,当前所有节点均为红色,现在需要将其中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;
}