"Wei Lai Cup" 2022 Niuke summer multi school training camp 5
K Headphones
General idea of the topic
There are N pairs of headphones, and Yasa takes out exactly k pairs. NIO should take out at least how many headphones, which can be more than Yasa takes out. There are a pair of headphones on the left and right. Yasa takes out a pair of headphones, and NIO takes them one by one.
Solution
See code.
code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 5; int n, k; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while (cin >> n >> k) { if ((n - k) * 2 <= n) cout << -1 << endl; else cout << n + 1 << endl; } }
C Bit Transmission
General idea of the topic
There is a string composed of 01. For some positions, ask whether it is 1, ask 3n times, and ask at least once, and the answer returned is wrong. Ask whether these query results can uniquely determine the string.
Solution
See code.
code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 5; int n, x; string s; int yes[maxn], no[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= 3 * n; i++) { cin >> x >> s; if (s == "YES") yes[x]++; else no[x]++; } s = ""; bool ok = 1; for (int i = 0; i < n; i++) { if (no[i] && yes[i]) { if (ok) ok = 0; else { cout << -1 << endl; return 0; } if (yes[i] == 1 && no[i] == 1) { cout << -1 << endl; return 0; } else if (no[i] == 1) { s += "1"; } else if (yes[i] == 1) { s += "0"; } else { cout << -1 << endl; return 0; } } else { if (no[i]) s += "0"; else s += "1"; } } cout << s << endl; return 0; }
B Watches
General idea of the topic
Given the price of n items, if you choose k items, the cost of purchasing the ith item is ai+k*i. Ask how many items you can buy at most (the ith item is the ith item in the original sequence).
Solution
Two points + greed, determine whether you can choose k items, and the total cost does not exceed M yuan.
code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 5; int n, m; int a[maxn], b[maxn]; bool checked(int k) { int ans = 0; for (int i = 1; i <= n; i++) b[i] = a[i] + k * i; sort(b + 1, b + 1 + n); for (int i = 1; i <= k; i++) { ans += b[i]; if (ans > m) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while (cin >> n >> m) { for (int i = 1; i <= n; i++) cin >> a[i]; int l = 0, r = n, mid, ans; while (l <= r) { mid = (l + r) >> 1; if (checked(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans << endl; } }
A Don't Starve
General idea of the topic
Given that n points have food (each point can be eaten many times), each point has a coordinate. The rule for walking is that each step must be strictly shorter than the previous step. Ask how many times you can eat food under the optimal scheme.
Solution
First, list all the edges, then sort them from large to small, and then enumerate the edges with the same length each time.
f[i] is defined as the maximum food obtained at the arrival point I in the current state.
code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e3 + 5; const int Max = 0x3f3f3f3f; int n; int x[maxn], y[maxn]; struct Edge { int u, v, dis; Edge(int u = 0, int v = 0, int dis = 0) : u(u), v(v), dis(dis) {} bool operator<(const Edge &a) const { return dis > a.dis; } }; vector<Edge> e; int f[maxn], g[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(f, -Max, sizeof f); cin >> n; for (int i = 1; i <= n; i++) cin >> x[i] >> y[i]; for (int i = 0; i <= n; i++) { for (int j = 1; j <= n; j++) if (i != j) e.push_back(Edge(i, j, pow(x[j] - x[i], 2) + pow(y[j] - y[i], 2))); } sort(e.begin(), e.end()); f[0] = 0; for (int i = 0, j = 0; i < e.size(); i = j) { vector<Edge> v; for (; j < e.size() && e[i].dis == e[j].dis; j++) v.push_back(e[j]); for (auto e : v) g[e.v] = -Max; for (auto e : v) g[e.v] = max(g[e.v], f[e.u] + 1); for (auto e : v) f[e.v] = max(f[e.v], g[e.v]); } cout << *max_element(f, f + n + 1) << endl; return 0; }
H Cutting Papers
General idea of the topic
An inequality is given, and the area of the closed region formed by this inequality and the circle centered on the center of the closed region are combined.
Solution
Draw the closed region according to the inequality, and directly calculate the union of the circle and the closed region.
code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e3 + 5; const int pi = acos(-1); double n; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; cout << fixed << setprecision(10) << n * n * (4 - pi) / 8 << endl; return 0; }