链接：https://atcoder.jp/contests/abc416
A – Vacation Validation
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
string s;
int n, l, r;
cin >> n >> l >> r >> s;
--l, --r;
for (int i = max(0, l); i <= min(r, n - 1); ++i)
{
if (s[i] == 'x')
{
cout << "No" << endl;
return;
}
}
cout << "Yes" << endl;
}B – 1D Akari
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
string s;
cin >> s;
int n = s.size();
string ans;
for (int i = 0; i < n; ++i)
{
if (s[i] == '#')
ans.push_back('#');
else
ans.push_back('o');
}
for (int i = 0; i < n; ++i)
{
if (ans[i] == 'o')
{
bool flag = 0;
for (int j = i + 1; j < n; ++j)
{
if (ans[j] == 'o')
{
if (flag)
break;
else if (!flag)
ans[j] = '.';
}
else if (s[j] == '#')
flag = 1;
}
}
}
cout << ans << endl;
}C – Concat (X-th)
算法：
全排列。
思路：
无。
关键代码：
void solve()
{
int n, k, x;
cin >> n >> k >> x;
vector<string> s(n + 10);
for (int i = 1; i <= n; ++i)
cin >> s[i];
vector<string> v;
vector<int> g(k + 10);
function<void(int)> dfs = [&](int u) -> void
{
if (u == k)
{
string ss = "";
for (int i = 0; i < k; ++i)
{
ss += s[g[i]];
}
v.push_back(ss);
return;
}
for (int i = 1; i <= n; ++i)
{
g[u] = i;
dfs(u + 1);
}
};
dfs(0);
sort(all(v));
cout << v[x - 1] << endl;
}D – Match, Mod, Minimize 2
算法：
贪心。
思路：
贪心策略：
- 在 \(a\) 数组中如果存在大于等于 \(m – b[i]\) 的元素，就选择与之配对。
- 如果没有就选择一个最小的元素。
关键代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(n + 10);
vector<int> b(n + 10);
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
cin >> b[i];
sort(a.begin(), a.begin() + n);
multiset<int> s(a.begin(), a.begin() + n);
ll ans = 0;
for (int i = 0; i < n; ++i)
{
int need = m - b[i];
auto it = s.lower_bound(need);
if (it == s.end())
{
ans += (b[i] + *s.begin()) % m;
s.erase(s.begin());
}
else
{
ans += (b[i] + *it) % m;
s.erase(it);
}
}
cout << ans << endl;
}E – Development
算法：
动态最短路，\(Floyd\)。
思路：
观察到 \(n\) 为 \(500\) 且为稠密图，并且需要动态添加边，考虑使用 \(Floyd\) 并使用邻接矩阵存储边。
初始时先只处理公路的边，对于每条公路边直接使用 \(Floyd\) 跑出所有点之间的距离，使用 \(dist\) 数组存储；而有机场的城市先使用标记数组 \(st\) 标记上有机场即可。
对于机场不难发现每两点之间最多只会做一次飞机，因为机场间可以互相到达。
操作1：由于添加了一条新边 \((u, v, w)\)，所以需要更新所有经过 \(u, v\) 的点，既对于所有的 \((x, y)\) 多了一条可选择的边 \(x -> u -> v -> y\) 或 \(x -> v -> u -> y\)，只需枚举所有 \((x, y)\) 即可，更新边 \((u, v, w)\) 的影响即可。
操作2：使用 \(st\) 标记上有机场即可。
操作3：先前已经将所有有机场的边全标记上了并且已推导出每次最多做一次飞机，求出每个点 \(i\) 到达最近机场的时间，记作 \(da\)，此时对于每条最短路 \((i, j)\) 只有两种情况：
- 不坐飞机，最短路为 \(dist[i][j]\)。
- 坐飞机，最短路为 \(da[i] + t + da[j]\)。
两种情况取最小值即可。
关键代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<ll>> dist(n + 10, vector<ll>(n + 10, 1e18));
for (int i = 1; i <= n; ++i)
dist[i][i] = 0;
for (int i = 0; i < m; ++i)
{
ll u, v, w;
cin >> u >> v >> w;
dist[u][v] = dist[v][u] = min(dist[u][v], w);
}
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
vector<int> st(n + 10, 0);
ll k, t;
cin >> k >> t;
for (int i = 0; i < k; ++i)
{
int x;
cin >> x;
st[x] = 1;
}
int q;
cin >> q;
while (q--)
{
int op;
cin >> op;
if (op == 1)
{
ll u, v, w;
cin >> u >> v >> w;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
ll cnt = min(dist[i][u] + w + dist[v][j], dist[i][v] + w + dist[u][j]);
dist[i][j] = min(dist[i][j], cnt);
}
}
}
else if (op == 2)
{
int x;
cin >> x;
st[x] = 1;
}
else
{
vector<ll> da(n + 10, 1e18);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (st[j])
{
da[i] = min(da[i], dist[i][j]);
}
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
ll cnt = min(dist[i][j], da[i] + t + da[j]);
if (cnt >= 1e18 / 2)
cnt = 0;
ans += cnt;
}
}
cout << ans << endl;
}
}
}F – Paint Tree 2
还没补。
