Codeforces Round #635 (Div. 1) 题解
Visits: 275
Linova and Kingdom
设深度为 $d$,子树大小为 $s$,点 $i$ 对答案的贡献为 $d_i – s_i + 1$,从大到小贪心就好了。
const int N = 2e5 + 7;
int n, k, d[N], s[N];
vi e[N];
ll ans;
pq<pi> q;
void dfs(int x, int f) {
s[x] = 1;
for (int y : e[x])
if (y != f) {
d[y] = d[x] + 1;
dfs(y, x);
s[x] += s[y];
q.push(mp(d[y] - s[y] + 1, y));
}
}
int main() {
rd(n, k);
for (int i = 1, x, y; i < n; i++)
rd(x, y), e[x].pb(y), e[y].pb(x);
dfs(1, 0);
while (k--) {
ans += q.top().fi;
q.pop();
}
print(ans);
return 0;
}
Xenia and Colorful Gems
乱搞,让三个数尽可能接近就行了。
const int N = 1e5 + 7;
int x, y, z;
ll a[N], b[N], c[N], ans;
inline void upd(ll x, ll y, ll z) {
ans = min(ans, (x - y) * (x - y) + (y - z) * (y - z) + (z - x) * (z - x));
}
inline void work(ll *a, int x, ll *b, int y, ll *c, int z) {
for (int i = 1, j, k; i <= x; i++) {
j = lower_bound(b + 1, b + y + 1, a[i]) - b;
if (j <= y) {
k = lower_bound(c + 1, c + z + 1, (a[i] + b[j]) >> 1) - c;
if (k <= z) upd(a[i], b[j], c[k]);
if (k > 1) upd(a[i], b[j], c[k-1]);
}
if (j > 1) {
k = lower_bound(c + 1, c + z + 1, (a[i] + b[j-1]) >> 1) - c;
if (k <= z) upd(a[i], b[j-1], c[k]);
if (k > 1) upd(a[i], b[j-1], c[k-1]);
}
}
}
inline void solve() {
rd(x, y, z), rda(a, x), rda(b, y), rda(c, z);
sort(a + 1, a + x + 1);
sort(b + 1, b + y + 1);
sort(c + 1, c + z + 1);
ans = 4e18;
work(a, x, b, y, c, z);
work(b, y, c, z, a, x);
work(c, z, a, x, b, y);
print(ans);
}
int main() {
int T;
rd(T);
while (T--) solve();
return 0;
}
Kaavi and Magic Spell
正着比较难考虑,反着就容易了。
设 $f_{i,j}$ 表示考虑 $s^r$ 的前 $i$ 个字符,覆盖了要求目标字符串的前 $j$ 个字符和后 $i-j$ 个字符的方案数。
时间复杂度 $\mathcal O(n^2)$。
const int N = 3e3 + 7;
int n, m;
char s[N], t[N];
modint f[N][N], ans;
int main() {
rds(s, n), rds(t, m);
reverse(s + 1, s + n + 1);
for (int i = 1; i <= n; i++) {
if (n - i + 1 >= m) f[i-1][0] += 1;
for (int j = 0; j < i; j++) {
if (s[i] == t[j+1] || !t[j+1]) f[i][j+1] += f[i-1][j];
if (s[i] == t[n-i+1+j] || !t[n-i+1+j]) f[i][j] += f[i-1][j];
}
}
for (int j = 0; j <= n; j++) ans += f[n][j];
print(ans);
return 0;
}
Yui and Mahjong Set
题目太神仙了,先咕咕咕着。
Chiori and Doll Picking
题目太神仙了,先咕咕咕着。
Journey
题目太神仙了,先咕咕咕着。