JOI Final 2019 题解
Visits: 699
勇者ビ太郎 (Bitaro the Brave)
前缀和计数一下,时间复杂度 $\mathcal O(nm)$。
const int N = 3e3 + 7;
int n, m, c[2][N][N];
char s[N][N];
ll ans;
int main() {
rd(n, m);
for (int i = 1; i <= n; i++) rds(s[i], m);
for (int i = 1; i <= n; i++)
for (int j = m; j; j--)
c[0][i][j] = c[0][i][j+1] + (s[i][j] == 'O');
for (int j = 1; j <= m; j++)
for (int i = n; i; i--)
c[1][i][j] = c[1][i+1][j] + (s[i][j] == 'I');
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans += (s[i][j] == 'J') * c[0][i][j] * c[1][i][j];
print(ans);
return 0;
}
展覧会 (Exhibition)
sort
+ 贪心,时间复杂度 $\mathcal O(n \log n)$。
const int N = 1e5 + 7;
int n, m, c[N], ans;
pi a[N];
int main() {
rd(n, m);
for (int i = 1; i <= n; i++) rd(a[i].se, a[i].fi);
sort(a + 1, a + n + 1);
rda(c, m);
sort(c + 1, c + m + 1);
for (int i = m, j = n; i && j; i--) {
while (j && a[j].se > c[i]) --j;
if (j) ++ans, --j;
}
print(ans);
return 0;
}
たのしいたのしいたのしい家庭菜園 (Growing Vegetables is Fun 3)
考虑确定了最终的字符串后如何计算最少交换次数。
首先同一个字符的相对顺序不变,于是可以一一对应起来。
考虑计算逆序对的个数,由于每次交换可以使逆序对个数减 $2$,因此答案就是逆序对个数除以 $2$。
把这个玩意儿套到一个 $\mathcal O(n^3)$ 的 DP 上去即可。
const int N = 407, inf = 1e9;
int n, p[3][N], f[3][N][N][N], a[N], b[N], c[N];
char s[N];
inline void upd(int &x, int y) {
x = min(x, y);
}
int main() {
rd(n), rds(s, n);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) p[j][i] = p[j][i-1];
switch (s[i]) {
case 'R' : a[++a[0]] = i, ++p[0][i]; break;
case 'G' : b[++b[0]] = i, ++p[1][i]; break;
case 'Y' : c[++c[0]] = i, ++p[2][i]; break;
}
}
for (int i = 0; i < 3; i++)
for (int x = 0; x <= a[0]; x++)
for (int y = 0; y <= b[0]; y++)
for (int z = 0; z <= c[0]; z++)
f[i][x][y][z] = inf;
if (a[0]) f[0][a[0]-1][b[0]][c[0]] = abs(n - a[a[0]]);
if (b[0]) f[1][a[0]][b[0]-1][c[0]] = abs(n - b[b[0]]);
if (c[0]) f[2][a[0]][b[0]][c[0]-1] = abs(n - c[c[0]]);
for (int i = n - 1; i; i--)
for (int x = 0; x <= a[0] && x <= i; x++)
for (int y = 0; y <= b[0] && x + y <= i; y++) {
int z = i - x - y;
if (z > c[0]) continue;
if (x) upd(f[0][x-1][y][z], min(f[1][x][y][z], f[2][x][y][z]) + abs(p[1][a[x]] - y) + abs(p[2][a[x]] - z));
if (y) upd(f[1][x][y-1][z], min(f[0][x][y][z], f[2][x][y][z]) + abs(p[0][b[y]] - x) + abs(p[2][b[y]] - z));
if (z) upd(f[2][x][y][z-1], min(f[0][x][y][z], f[1][x][y][z]) + abs(p[0][c[z]] - x) + abs(p[1][c[z]] - y));
}
int ans = min(min(f[0][0][0][0], f[1][0][0][0]), f[2][0][0][0]);
print(ans == inf ? -1 : (ans >> 1));
return 0;
}
コイン集め (Coin Collecting)
依然是贪心,先把每个方块移到离它最近的范围内的位置,然后调整一下即可,时间复杂度 $\mathcal O(n)$。
const int N = 1e5 + 7;
int n, c[N][3];
ll ans;
int main() {
rd(n);
for (int i = 1, x, y; i <= (n << 1); i++) {
rd(x, y);
if (x < 1) ans += 1 - x, x = 1;
if (x > n) ans += x - n, x = n;
if (y < 1) ans += 1 - y, y = 1;
if (y > 2) ans += y - 2, y = 2;
++c[x][y];
}
for (int i = 1, c1 = 0, c2 = 0; i <= n; i++) {
c1 += c[i][1] - 1, c2 += c[i][2] - 1;
while (c1 < 0 && c2 > 0) ++c1, --c2, ++ans;
while (c1 > 0 && c2 < 0) --c1, ++c2, ++ans;
if (i < n) ans += abs(c1) + abs(c2);
}
print(ans);
return 0;
}
珍しい都市 (Unique Cities)
关于 $x$ 合法的城市一定在以 $x$ 为根的最长链上,这条最长链的另一端一定是直径的某一端。
因此我们对于直径的两端各算一次答案,取 $\max$ 即为最终的答案。
考虑对于直径的一端如何计算答案,将这个点设为根,然后长链剖分。
全局上用一个栈记录从根到每个点的路径上合法的点,用一个桶维护答案。
处理到一个点时,优先递归重儿子,因此要先把栈中和他距离不大于深度最大的轻儿子的点退栈。接着再递归所有轻儿子,把栈中和他距离不大于重儿子的点退栈。
这样可以保证每个点的贡献被删掉后不可能还需要加回来。
总时间复杂度 $\mathcal O(n)$。
const int N = 2e5 + 7;
int n, m, a[N], ans[N];
vi e[N];
int rt, d[N];
void dfs1(int x, int fa) {
d[x] = d[fa] + 1;
if (d[x] > d[rt]) rt = x;
for (int y : e[x])
if (y != fa) dfs1(y, x);
}
int f[N], son[N][2];
#define s0 son[x][0]
#define s1 son[x][1]
void dfs2(int x, int fa) {
d[x] = d[fa] + 1;
s0 = s1 = 0;
for (int y : e[x])
if (y != fa) {
dfs2(y, x);
if (f[y] > f[s1]) s1 = y;
if (f[s1] > f[s0]) swap(s0, s1);
}
f[x] = f[s0] + 1;
}
int st[N], tp;
int c[N], cnt;
inline void ins(int x) {
cnt += !c[x]++;
}
inline void del(int x) {
cnt -= !--c[x];
}
void dfs3(int x, int fa) {
if (fa) ins(a[fa]), st[++tp] = fa;
if (s0) {
while (tp && d[st[tp]] >= d[x] - f[s1]) del(a[st[tp--]]);
dfs3(s0, x);
}
while (tp && d[st[tp]] >= d[x] - f[s0]) del(a[st[tp--]]);
for (int y : e[x])
if (y != fa && y != s0)
dfs3(y, x);
ans[x] = max(ans[x], cnt);
if (st[tp] == fa) del(a[st[tp--]]);
}
inline void work(int x) {
rt = x;
dfs1(x, 0);
dfs2(rt, 0);
for (int i = 1; i <= m; i++) c[i] = 0;
cnt = tp = 0;
dfs3(rt, 0);
}
int main() {
rd(n, m);
for (int i = 1, x, y; i < n; i++)
rd(x, y), e[x].pb(y), e[y].pb(x);
rda(a, n);
work(1), work(rt);
for (int i = 1; i <= n; i++) print(ans[i]);
return 0;
}