数字统计
统计[L, R]的所有整数中，数字2出现的次数。
题解
经典题，这题数据范围较小，直接暴力。
#include <bits/stdc++.h>
using namespace std;
int main() {
int count = 0, l, r;
cin >> l >> r;
for (int i = l; i <= r; i++) {
int x = i;
while(x > 0) {
count += (x%10 == 2);
x /= 10;
}
}
cout << count << endl;
}
接水问题
n个学生，m个水龙头按顺序接水，计算总时间。
方法1
模拟，时间复杂度$O(nm)$。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n, m, a[N], b[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int mn = 1e9, k;
for (int j = 1; j <= m; j++) {
if (mn > b[j]) {
mn = b[j];
k = j;
}
}
if (mn == 0) {
b[k] = a[i];
} else {
ans += mn;
for (int j = 1; j <= m; j++) {
b[j] -= mn;
}
b[k] = a[i];
}
}
int mx = 0;
for (int j = 1; j <= m; j++) {
mx = max(mx, b[j]);
}
ans += mx;
cout << ans << endl;
}
方法2
也可以用优先队列，每次pop最小的出队时间，push当前同学下次出队的时间，时间复杂度到$O(n\log{m})$。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n, m, a[N], b[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
priority_queue<int, vector<int>, greater<int> > q;
int cur = 0;
for (int i = 1; i <= n; i++) {
if (q.size() == m) {
cur = q.top();
q.pop();
}
q.push(cur + a[i]);
}
while(!q.empty()) {
cur = q.top();
q.pop();
}
cout << cur << endl;
}
导弹拦截
给两个圆心坐标和$n$个点，求最小的半径平方和覆盖所有的点。
题解
对每个点分别计算出到两个圆心的距离的平方，记为$a_i$，$b_i$。
最优解一定存在一个点在圆上，考虑枚举在第一个圆上的点$i$，比$a_i$小的可以被覆盖到，
比$a_i$大的需要用第二个圆覆盖，所以需要计算剩下的点中$b$的最大值。
对$(a_i, b_i)$按照$a_i$排序，那么剩下的点就是$i+1$到$n$之间的点，
这段区间$b$的最大值可用类似前缀和的方法计算出来。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, b[N];
pair<int, int> a[N];
int main() {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d%d", &x, &y);
a[i].first = (x-x1) * (x-x1) + (y-y1)*(y-y1);
a[i].second = (x-x2) * (x-x2) + (y-y2)*(y-y2);
}
sort(a + 1, a + n + 1);
for (int i = n; i >= 1; i--) {
b[i] = max(b[i+1], a[i].second);
}
int ans = 1e9;
for (int i = 1; i <= n + 1; i++) {
ans = min(ans, a[i-1].first + b[i]);
}
cout << ans << endl;
}
三国游戏
给一个对称的$n*n$的矩阵P，n为偶数。A同学和B同学交替从$1$到$n$选数字。在所有数字选完之后，A和B分别从自己选择的$n/2$个数字中选出两个$(i,j)$，使得$P_{i,j}$最大，数字大的一方获胜。B的策略为不让A选择到当前可选的最大的组合，问A先手能否获胜，能选到的最大的$P$为多少。
题解
在B的策略下，A和B都选不到每个数的最大匹配，所以A只能选出每个数的第二大的匹配，那么所有数的第二大匹配的最大值就是A能选出来的最大值。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int a[N][N], n;
int main() {
cin >> n;
for (int i = 1 ; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
scanf("%d", &a[i][j]);
a[j][i] = a[i][j];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
sort(a[i]+1, a[i]+n+1);
ans = max(ans, a[i][n-1]);
}
cout << 1 << endl << ans << endl;
}