部分题目课上讲过，就不解释了。
A – Registration system
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
map<string, int> mp;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
if (mp.count(s)) {
cout << s << mp[s]++ << "\n";
} else {
cout << "OK\n";
mp[s] = 1;
}
}
return 0;
}B – Boxes Packing
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
map<int, int> mp;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
mp[x]++;
}
int res = 0;
for (auto i : mp) {
res = max(i.second, res);
}
cout << res << "\n";
return 0;
}C – Glass Carving
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
multiset<int> h, v, x, y;
h.insert(m);
v.insert(n);
x.insert(0), x.insert(m);
y.insert(0), y.insert(n);
for (int i = 0; i < k; i++) {
char op;
int p;
cin >> op >> p;
if (op == 'H') {
auto l = x.upper_bound(p);
auto r = l--;
h.erase(h.find(*r - *l));
h.insert(*r - p);
h.insert(p - *l);
x.insert(p);
} else {
auto l = y.upper_bound(p);
auto r = l--;
v.erase(v.find(*r - *l));
v.insert(*r - p);
v.insert(p - *l);
y.insert(p);
}
cout << 1LL * *h.rbegin() * *v.rbegin() << "\n";
}
return 0;
}D – Anton and Lines
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
constexpr db eps = 1e-7;
db f(db k, db b, db x) {
return k * x + b;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, x1, x2;
cin >> n >> x1 >> x2;
vector<pair<int, int> > p(n);
for (auto& i : p) {
cin >> i.first >> i.second;
}
vector<pair<db, int> > left, right;
for (int i = 0; i < n; i++) {
int k = p[i].first, b = p[i].second;
left.push_back({ f(k, b, x1 + eps), i });
right.push_back({ f(k, b, x2 - eps), i });
}
sort(left.begin(), left.end());
sort(right.begin(), right.end());
for (int i = 0; i < n; i++) {
if (left[i].second != right[i].second) {
cout << "YES\n";
return 0;
}
}
cout << "NO\n";
return 0;
}E – 卡布列克圆舞曲
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
while (cin >> n) {
map<int, int> mp;
for (int t = 1;;t++) {
vector<int> a;
int m = n;
if (mp.count(m)) {
vector<pair<int, int>> p;
for (auto i : mp) {
p.push_back({ i.second,i.first });
}
sort(p.begin(), p.end());
int ok = 0;
for (auto [x, y] : p) {
if (y == m) {
ok = 1;
}
if (ok) {
cout << y << " ";
}
}
break;
}
mp[n] = t;
while (m) {
a.push_back(m % 10);
m /= 10;
}
sort(a.begin(), a.end());
int maxv = 0, minv = 0;
for (auto i : a) {
minv *= 10;
minv += i;
}
reverse(a.begin(), a.end());
for (auto i : a) {
maxv *= 10;
maxv += i;
}
n = maxv - minv;
}
cout << "\n";
}
return 0;
}F – [NOIP2017 提高组] 奶酪
#include <bits/stdc++.h>
using namespace std;
struct point {
int x, y, z, s;
point(int x_ = 0, int y_ = 0, int z_ = 0) :x(x_), y(y_), z(z_), s(0) {}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, h, r;
cin >> n >> h >> r;
auto r2 = 4LL * r * r;
vector<point> p(n);
for (auto& i : p) {
cin >> i.x >> i.y >> i.z;
}
for (int i = 0; i < n; i++) {
if (p[i].z <= r) {
p[i].s += 1;
}
if (p[i].z + r >= h) {
p[i].s += 2;
}
}
auto check = [&](point p, point q) {
long long dis = 1LL * (p.x - q.x) * (p.x - q.x) + 1LL * (p.y - q.y) * (p.y - q.y) + 1LL * (p.z - q.z) * (p.z - q.z);
return (dis <= r2);
};
vector<vector<int>> g(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (check(p[i], p[j])) {
g[i][j] = g[j][i] = 1;
}
}
}
vector<bool> vis(n);
function<bool(int)> dfs = [&](int now) {
if (p[now].s & 2) {
return true;
}
for (int to = 0; to < n; to++) {
if (!vis[to] && g[now][to]) {
vis[to] = true;
auto ok = dfs(to);
if (ok) {
return true;
}
}
}
return false;
};
bool ok = false;
for (int i = 0; i < n; i++) {
if (!vis[i] && p[i].s & 1) {
vis[i] = true;
if (dfs(i)) {
ok = true;
break;
}
}
}
cout << (ok ? "Yes" : "No") << "\n";
}
return 0;
}H – 删数问题
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int CUT_OFF = 4250000;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int k, m;
cin >> k >> m;
vector<vector<int>> pos(10);
set<int> st;
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(1);
while (!pq.empty()) {
int top = pq.top();
pq.pop();
if (!st.count(top)) {
st.insert(top);
int u = top * 2 + 1;
int v = top * 4 + 5;
if (u < CUT_OFF) {
pq.push(top * 2 + 1);
}
if (v < CUT_OFF) {
pq.push(top * 4 + 5);
}
}
}
auto it = st.begin();
string s = "";
for (int i = 0; i < k; i++) {
s += to_string(*it++);
}
for (int i = 0; i < (int)s.length(); i++) {
pos[s[i] - '0'].push_back(i);
}
cout << s << "\n";
int n = s.length() - m;
for (int i = 0, left = 0; i < n; i++) {
int right = (s.length() - (n - i) + 1); // [left, right)
for (int j = 9; ~j; j--) {
int p = upper_bound(pos[j].begin(), pos[j].end(), left) - pos[j].begin();
if (p < pos[j].size() && pos[j][p] < right) {
cout << j;
left = pos[j][p];
break;
}
}
}
return 0;
}I – DZY Loves Modification
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, k, p;
cin >> n >> m >> k >> p;
priority_queue<int> x, y;
vector<int> prex(k + 1), prey(k + 1);
vector<vector<int>> a(n, vector<int>(m));
for (auto& i : a) {
for (auto& j : i) {
cin >> j;
}
}
for (int i = 0; i < n; i++) {
int sum = 0;
for (auto j : a[i]) {
sum += j;
}
x.push(sum);
}
for (int i = 0; i < m; i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
sum += a[j][i];
}
y.push(sum);
}
for (int i = 1; i <= k; i++) {
int topx = x.top(), topy = y.top();
x.pop(), y.pop();
prex[i] = prex[i - 1] + topx;
prey[i] = prey[i - 1] + topy;
x.push(topx - p * m);
y.push(topy - p * n);
}
int res = LLONG_MIN;
for (int i = 0; i <= k; i++) {
res = max(res, prex[i] + prey[k - i] - 1LL * i * (k - i) * p);
}
cout << res << "\n";
return 0;
}J – Snuke the Wizard
这是一个非常好的二分题，可以自己思考一下~
剩下的题目看这篇文章。