投资公司转让_搭建web服务器_网络推广专员是干什么的_最新新闻热点话题

牛客周赛 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;
}