链接：https://codeforces.com/contest/2126
A. Only One Digit
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
string s;
cin >> s;
sort(all(s));
cout << s[0] << endl;
}B. No Casino in the Mountains
算法：
贪心。
思路：
无。
关键代码：
void solve()
{
int n, k;
cin >> n >> k;
vi a(n + 10);
cin >> a;
ll ans = 0;
ll cnt = 0;
ll wait = 0;
for (int i = 0; i < n; ++i)
{
if (!a[i] && !wait)
++cnt;
else if (!a[i] && wait)
wait--;
else
cnt = 0, wait = 0;
if (cnt >= k && !wait)
{
++ans;
cnt -= k;
wait++;
}
}
cout << ans << endl;
}C. I Will Definitely Make It
算法：
贪心。
思路：
无。
关键代码：
void solve()
{
int n, k;
cin >> n >> k;
vi a(n + 10);
cin >> a;
vector<pii> v;
for (int i = 0; i < n; ++i)
v.push_back({a[i], i});
sort(all(v));
int pos = -1;
for (int i = 0; i < n; ++i)
{
if (v[i].second == k - 1)
{
pos = i;
break;
}
}
ll h2o = 0;
ll now = v[pos].first;
for (int i = pos; i < n - 1; ++i)
{
ll cnt = v[i + 1].first - v[i].first;
h2o += cnt;
if (h2o > now)
{
cout << "NO" << endl;
return;
}
now += cnt;
}
cout << "YES" << endl;
}D. This Is the Last Time
算法：
贪心。
思路：
对区间左端点进行排序，遍历数组每次取\(k = max(k, real_i)\)即可。
关键代码：
void solve()
{
ll n, k;
cin >> n >> k;
vector<array<ll, 3>> v(n + 10);
for (int i = 0; i < n; ++i)
{
ll l, r, real;
cin >> l >> r >> real;
v[i] = {l, r, real};
}
sort(v.begin(), v.begin() + n);
for (int i = 0; i < n; ++i)
{
if (k < v[i][0])
break;
else
k = max(k, v[i][2]);
}
cout << k << endl;
}E. G-C-D, Unlucky!
算法：
数学，数论。
思路：
由于 \(p\)为数组的前缀\(gcd\)，\(s\)为数组的后缀\(gcd\)，可得以下条件：
- \(p[0] == s[n – 1]\)
- \(p\) 数组中每对\(p[i] \text{ % } p[i + 1]\)都等于\(0\)
- \( s \) 数组中每对\(s[i] \text{ % } s[i – 1]\)都等于\(0\)
- 每个\(i\)都满足\(p[n – 1] == gcd(p[i], s[i + 1])\)
关键代码：
void solve()
{
int n;
cin >> n;
vector<ll> p(n + 10), s(n + 10);
cin >> p >> s;
if (s[0] != p[n - 1])
{
cout << "NO" << endl;
return;
}
for (int i = 1; i < n; ++i)
{
if (p[i - 1] % p[i] != 0)
{
cout << "NO" << endl;
return;
}
}
for (int i = n - 2; i >= 0; --i)
{
if (s[i + 1] % s[i] != 0)
{
cout << "NO" << endl;
return;
}
}
for (int i = 0; i < n - 1; ++i)
{
if (p[n - 1] != __gcd(p[i], s[i + 1]))
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}F. 1-1-1, Free Tree!
算法：
dfs，图论。
思路：
定义：
- \(ans\) 为初始时整个图的代价。
- 节点 \(1\) 为根节点。
- \(m[u][color]\) 为以节点 \(u\) 为父节点的所有子边中子节点颜色为 \(color\) 的边权总和。
- \(fa[u]\) 为节点 \(u\) 的父节点。
- \(va[u]\) 为节点 \(u\) 到达父节点的边的权值。
从节点 \(1\)开始 \(dfs\)，将所有节点 \(u\) 的 \(fa[u]\), \(va[u]\), \(m[u][color]\) 都统计出来。
由于每次查询只需修改一个点的颜色，每次查询时只需讨论当前节点与父节点与子节点的颜色即可，分情况对\(ans\), \(m[u][color]\)进行增减即可。
关键代码：
void solve()
{
int n, q;
cin >> n >> q;
vector<int> a(n + 10);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<pii> g[n + 10];
for (int i = 0; i < n - 1; ++i)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<map<ll, ll>> m(n + 10);
ll ans = 0;
vector<int> fa(n + 10, -1), va(n + 10);
function<void(int)> dfs = [&](int u) -> void
{
for (auto [v, w] : g[u])
{
if (v == fa[u])
continue;
fa[v] = u;
va[v] = w;
m[u][a[v]] += w;
dfs(v);
if (a[u] != a[v])
ans += w;
}
};
dfs(1);
while (q--)
{
int u, x;
cin >> u >> x;
if (fa[u] != -1)
{
if (a[u] == a[fa[u]])
ans += va[u];
if (x == a[fa[u]])
ans -= va[u];
m[fa[u]][a[u]] -= va[u];
m[fa[u]][x] += va[u];
}
if (m[u].count(a[u]))
ans += m[u][a[u]];
if (m[u].count(x))
ans -= m[u][x];
a[u] = x;
cout << ans << endl;
}
}G1. Big Wins! (easy version)
还没补。
G2. Big Wins! (hard version)
还没补。
