从 AGC001A 开始。
[AGC001A] BBQ Easy
显然排序后所有奇数位相加即为答案。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
const int N = 205;
int n, a[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
n *= 2;
for (int i = 1; i <= n; i++) cin >> a[i];
int ans = 0;
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i += 2) ans += a[i];
cout << ans << "\n";
return 0;
}
[AGC001C] Shorten Diameter
考虑贪心。
每次找出直径，显然我们能删的只有直径端点。一棵树的直径端点必然是叶子，否则就不是最长链了。
考虑有两个端点，删哪个更优。比较显然的是删掉在树中能到距离 $>k$ 的点较多的那个。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N = 2005;
int n, k;
vector<int> G[N];
int mxlen, mu;
int ff[N];
void dfs(int u, int fa, int len)
{
ff[u] = fa;
if (len > mxlen)
{
mxlen = len;
mu = u;
}
for (auto& j : G[u])
{
if (j ^ fa) dfs(j, u, len + 1);
}
}
int cnt = 0;
void get_cnt(int u, int f, int len)
{
if (len > k) cnt++;
for (auto& j : G[u])
{
if (j != f) get_cnt(j, u, len + 1);
}
}
int solve()
{
mxlen = -1, mu = 0;
dfs(1, 0, 0);
int u = mu;
mu = 0, mxlen = -1;
dfs(u, 0, 0);
int res = mxlen;
cnt = 0;
get_cnt(u, 0, 0);
int c1 = cnt;
cnt = 0;
get_cnt(mu, 0, 0);
int c2 = cnt;
if (c2 > c1)
{
if (ff[mu]) G[ff[mu]].erase(find(G[ff[mu]].begin(), G[ff[mu]].end(), mu));
}
else
{
dfs(mu, 0, 0);
mu = u;
if (ff[mu]) G[ff[mu]].erase(find(G[ff[mu]].begin(), G[ff[mu]].end(), mu));
}
return res;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
int ans = 0;
while (solve() > k) ans++;
cout << ans << "\n";
return 0;
}
[AGC001D] Arrays and Palindrome
考虑回文的本质是什么。即第一个和最后一个相等，第二个和倒数第二个相等，……。
先考虑如果给定 $a$ 和 $b$ 怎么判定。我们考虑图论建模，对于每个 $a_i$ 和 $b_i$ 在对应范围内两两头尾相连。容易知道总共连了 $\sum \limits_{i=1}^n \lfloor \dfrac{a_i}{2} \rfloor + \sum \limits_{i=1}^n \lfloor \dfrac{b_i}{2} \rfloor$ 条边。如果最终图连通，则必然符合题意。
图连通的必要条件是边数 $\geq n-1$，又发现无论如何构造 $b$，$b$ 队边的贡献不超过 $\lfloor \dfrac{n}{2} \rfloor$，从而推出 $a$ 中奇数个数不超过 $2$。否则 impossible。
把 $a$ 中两个奇数放两边，如果只有一个奇数就放在 $1$ 的位置。其他在中间随便排，最终让 $b_1 = a_1+1$，$b_i = a_i(2 \leq i < m)$，$b_m=a_m-1$，手玩一下发现很对。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N];
vector<int> ans;
void solve_1()
{
for (int i = 1; i <= n / 2; i++) ans.emplace_back(2);
ans.emplace_back(1);
}
void solve_2()
{
for (int i = 1; i < n / 2; i += 2)
{
ans.emplace_back(2);
}
ans.emplace_back(1);
for (int i = n / 2 + 2; i < n; i += 2) ans.emplace_back(2);
ans.emplace_back(1);
}
bool vis[N];
int na[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> a[i];
}
if (m == 1)
{
if (n & 1) solve_1();
else solve_2();
cout << a[1] << "\n";
cout << ans.size() << "\n";
for (auto& i : ans) cout << i << " ";
return 0;
}
int sum = 0;
for (int i = 1; i <= m; i++)
{
sum += (a[i] >> 1);
}
if (sum + (n / 2) < n - 1)
{
cout << "Impossible\n";
return 0;
}
bool f = 0;
int c = 0;
for (int i = 1; i <= m; i++)
{
if (a[i] & 1)
{
c++;
vis[i] = 1;
if (!f)
{
na[1] = a[i];
f = 1;
}
else na[m] = a[i];
}
}
int idx = (f ? 2 : 1);
for (int i = 1; i <= m; i++)
{
if (!(a[i] & 1))
{
na[idx++] = a[i];
}
}
ans.emplace_back(na[1] + 1);
for (int i = 2; i < m; i++) ans.emplace_back(na[i]);
if (na[m] != 1) ans.emplace_back(na[m] - 1);
for (int i = 1; i <= m; i++) cout << na[i] << " ";
cout << "\n";
cout << ans.size() << "\n";
for (auto& i : ans) cout << i << " ";
cout << "\n";
return 0;
}