目录
A - BBQ Easy
先将 \(2N\) 个数排序，从大到小考虑，最大的数一定不会产生贡献，次大的数可以和最大的数捆绑在一起，并产生贡献，以此类推，这样的贪心正确性还是较为显然的。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
const int N = 205;
int n, a[N];
int main() {
int i;
n = Read(), n <<= 1;
for(i = 1; i <= n; i++) {
a[i] = Read();
}
sort(a + 1, a + n + 1);
int ans = 0;
for(i = 1; i <= n; i += 2) {
ans += a[i];
}
Write(ans), putchar('\n');
return 0;
}
B - Mysterious Light
可以看到，从光反射第二次后开始后，以两轮为周期，光可能经过的范围总是为一个平行四边形，且光总是沿着平行四边形某个 \(120^\circ\) 的内角的角平分线射出。
比如样例的图：
设两条边长为 \(x, y\)。则对于一个平行四边形，只算它内部的光线总长，答案为：
边界为 \(f(x, x) = x\)。
显然初始两条光线总长为 \(N\)，则答案为 \(N + f(X, N - X)\)，\(O(N)\) 暴力计算可拿 \(300\) 分。
观察这个式子，首先可以令边界为 \(f(x, 0) = -x\)，可以证明两个边界是等价的，很像辗转相减法，可以优化为辗转相除法，即：
观察到当 \(x < y\) 时，下面的式子等价于上面的式子，可得：
\[f(x, y) = f(x \bmod y, y) + 2 \cdot \lfloor \frac{x}{y} \rfloor \cdot y \]#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
ll Solve(ll x, ll y) {
return y ? Solve(y, x % y) + 2ll * (x / y) * y : -x;
}
int main() {
ll n = Read(), x = Read();
Write(n + Solve(n - x, x));
return 0;
}
C - Shorten Diameter
没看数据范围，结果一看 \(N\) 只有 \(2000\)。
考虑暴力枚举直径的中心，对 \(K\) 的奇偶性进行分类讨论。
- 当 \(K\) 为奇数时，枚举一条边，将与边的两个端点的距离最小值小于等于 \(\frac{K - 1}{2}\) 的点删去。
- 当 \(K\) 为偶数时，枚举一个点，将与点的距离小于等于 \(\frac{K}{2}\) 的点删去。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
const int N = 2005;
int n, cnt = 0, k, o;
vector<int> e[N];
bool vis[N];
void Dfs(int u, int dis) {
vis[u] = true;
if(dis > k / 2) {
cnt++;
}
for(auto v : e[u]) {
if(vis[v] || v == o) {
continue;
}
Dfs(v, dis + 1);
}
}
int main() {
int i;
n = Read(), k = Read();
vector<pair<int, int> > vec;
for(i = 1; i < n; i++) {
int u = Read(), v = Read();
vec.emplace_back(u, v);
e[u].push_back(v), e[v].push_back(u);
}
int ans = INT_MAX;
if(k & 1) {
for(auto p : vec) {
int u = p.first, v = p.second;
memset(vis, 0, sizeof(vis)), cnt = 0;
o = v, Dfs(u, 0), o = u, Dfs(v, 0);
ans = min(ans, cnt);
}
}
else {
for(i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis)), cnt = 0;
Dfs(i, 0);
ans = min(ans, cnt);
}
}
Write(ans);
return 0;
}