牛客周赛 Round 57 ABCDFG
A题：小红喜欢1
题意
输出1所在的位置
思路
无
代码
#include <bits/stdc++.h>
using namespace std;
int main() {for (int i = 1; i <= 5; i ++ ) {int x; cin >> x;if (x) cout << i << endl;}return 0;
}B题：小红的树切割
题意
对于一个树，每个节点有一种颜色，你可以删去若干条边以形成森林，使得每棵树相邻节点颜色不同，问最小的操作次数
思路
如果给定边的两个节点颜色一样那么就必须删去这条边
代码
#include <bits/stdc++.h>
using namespace std;
int main() {int n; cin >> n;string s; cin >> s;s = ' ' + s;int ans = 0;for (int i = 1; i < n; i ++ ) {int a, b; cin >> a >> b;if (s[a] == s[b]) ans += 1;}cout << ans << endl;return 0;
}C题：小红的双好数（easy）
题意
问是否存在k1和k2能将n以k1和k2两种进制的表示下，每一位不超过1
思路
二进制下肯定是不会超过1的，而剩下那个我们只需取它本身即可
在2的情况下失效，在1的情况下我们可以使用2和3
代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {LL n; cin >> n;if (n == 1) {cout << "YES" << endl;cout << 2 << ' ' << 3 << endl;}else {if (n == 2) cout << "NO" << endl;else {cout << "YES" << endl;cout << 2 << ' ' << n << endl;}}return 0;
}D题：小红的线段
题意
将2n个点两两组合形成n条线段，构造出与已知直线相交的线段最多的方案
思路
一开始可以分成三类
1:在直线上方
2:在直线下方
3:在直线上
其中在直线上下方的点可以和下上方或者直线上的点连线与直线相交
而在直线上的可以自己和自己就能形成一条与直线相交的线段
所以我们贪心地来
可以先将上方和下方匹配完
再将剩下的与在直线上的匹配
最后自己跟自己匹配
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
using PII = pair<int, int>;
signed main() {int n, k, b; cin >> n >> k >> b;queue<int> q[3];for (int i = 1; i <= 2 * n; i ++ ) {int x, y; cin >> x >> y;int cur = k * x + b;if (cur > y) q[0].push(i);else if (cur == y) q[2].push(i);else q[1].push(i);}vector<PII> ans;while (q[0].size() && q[1].size()) {ans.push_back({q[0].front(), q[1].front()});q[0].pop(), q[1].pop();}while (q[0].size() && q[2].size()) {ans.push_back({q[0].front(), q[2].front()});q[0].pop(), q[2].pop();}while (q[2].size() && q[1].size()) {ans.push_back({q[2].front(), q[1].front()});q[2].pop(), q[1].pop();}while (q[2].size() >= 2) {int t1 = q[2].front();q[2].pop();int t2 = q[2].front();q[2].pop();ans.push_back({t1, t2});}vector<int> no;for (int i = 0; i < 3; i ++ ) {if (q[i].size()) {while (q[i].size()) {no.push_back(q[i].front());q[i].pop();}}}cout << ans.size() << endl;for (auto [x, y] : ans) {cout << x << ' ' << y << " Y" << endl;}for (int i = 0; i < no.size(); i += 2) {cout << no[i] << ' ' << no[i + 1] << " N" << endl;}return 0;
}F题：小红的数组操作
思路
线段树模版题
我用了map来维护每个数组的最小值
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
struct node {int l, r;int v;
}tr[N << 2];
int minv[N];
void pushup(int u) {tr[u].v = min(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r) {tr[u] = {l, r};if (l == r) tr[u] = {l, r, minv[l]};else {int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}
}
int query(int u, int l, int r) {if (tr[u]. l >= l && tr[u].r <= r) return tr[u].v;int mid = tr[u].l + tr[u].r >> 1;int val = 1e9 + 7;if (l <= mid) val = query(u << 1, l, r);if (r > mid) val = min(val, query(u << 1 | 1, l, r));return val;
}
void modify(int u, int x, int val) {if (tr[u].l == x && tr[u].r == x) tr[u].v = val;else {int mid = tr[u].l + tr[u].r >> 1;if (x <= mid) modify(u << 1, x, val);else modify(u << 1 | 1, x, val);pushup(u);}
}
int main() {int n; cin >> n;vector<vector<int>> a(n + 1);vector<map<int, int>> b(n + 1);vector<int> num(n + 1);for (int i = 1; i <= n; i ++ ) {cin >> num[i];int mn = (int)1e9 + 7;for (int j = 1; j <= num[i]; j ++ ) {int x; cin >> x;mn = min(mn, x);b[i][x] += 1;a[i].push_back(x);}minv[i] = mn;}build(1, 1, n);int q; cin >> q;while (q -- ) {int op; cin >> op;if (op == 1) {int i, j, val; cin >> i >> j >> val;j -= 1;b[i][a[i][j]] -= 1;if (b[i][a[i][j]] == 0) b[i].erase(a[i][j]);b[i][val] += 1;a[i][j] = val;auto t = b[i].begin();modify(1, i, t->first);}else {int i; cin >> i;cout << query(1, 1, i) << endl;}}return 0;
}G题：小红的双排列构造
思路
构造题
首先无法构造的是n=1的情况，它已经定了
然后我们分类讨论k的情况
除了k=0外
对于n==4
我们可以看到
1 2 3 4 1 2 3 4 --k=5
1 2 3 4 2 1 3 4 --k=4
1 2 3 4 3 2 1 4 --k=3
1 2 3 4 4 3 2 1 --k=2
对于k==1
1 1 2 3 4 2 3 4即可
再讨论k=0的情况，在此不过多赘述
代码
#include <bits/stdc++.h>
using namespace std;
int main() {int n, k; cin >> n >> k;if (n == 1) {if (k != 2) cout << -1 << endl;else cout << 1 << ' ' << 1 << endl;}else {if (k == n + 1) {for (int i = 1; i <= 2; i ++ ) {for (int j = 1; j <= n; j ++ ) {cout << j << ' ';}}}else if (k == 0) {if (n == 2) cout << -1 << endl;else {for (int i = 1; i <= n; i ++ ) cout << i << ' ' << i << endl;}}else if (k == 1) {cout << 1 << ' ';for (int i = 1; i <= n; i ++ ) cout << i << ' ';for (int i = 2; i <= n; i ++ ) cout << i << ' ';}else {for (int i = 1; i <= n; i ++ ) cout << i << ' ';for (int i = n - k + 2; i >= 1; i -- ) cout << i << ' ';for (int i = n - k + 3; i <= n; i ++ ) cout << i << ' ';}}return 0;
}