ACGO排位赛2题解
2023-12-05 15:27:23
发布于：天津
172阅读
0回复
0点赞
T1
最开始是爱丽丝尽量远离绿，绿去追爱丽丝，如果爱丽丝和绿初始位置距离小于等于 （不是 是因为爱丽丝先手，等绿出手会远离一格），那么等绿刷出来技能可以直接干掉爱丽丝，否则爱丽丝会干掉绿。
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 1, inf = 2147483647;
int a, b, c, d;
int main() {
scanf("%d%d%d%d", &a, &b, &c, &d);
if (abs(c - a) + abs(d - b) <= 5) printf("Midori\n");
else printf("Arisu\n");
return 0;
}
T2
一个区间如果纳入新的数，那么这个数有可能会成为这个区间最大值或最小值，那么肯定是不优的，所以只需要枚举每相邻的两个的差就可以了。
时间复杂度
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 1e5 + 55, inf = 2147483647;
int n;
int a[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int ans = 2e9;
for (int i = 2; i <= n; i++) ans = min(ans, abs(a[i] - a[i - 1]));
printf("%d\n", ans);
return 0;
}
T3
分块，每个点如果块有标记则颜色为块的标记，没有则是原数组颜色，更新完整块直接给块打标记，非完整先下放标记，再暴力更新。
时间复杂度 。
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 2e5 + 55, M = 800, inf = 2147483647;
int n, q, len, tot;
int a[N], b[M], bl[N], l[M], r[M];
void init() {
len = sqrt(n);
tot = (n - 1) / len + 1;
for (int i = 1; i <= tot; i++) {
l[i] = r[i - 1] + 1;
r[i] = i * len;
}
r[tot] = n;
for (int i = 1; i <= tot; i++)
for (int j = l[i]; j <= r[i]; j++)
bl[j] = i;
}
void update(int ll, int rr, int c) {
int p = bl[ll], q = bl[rr];
if (p == q) {
if (b[p]) for (int i = l[p]; i <= r[q]; i++) a[i] = b[p];
for (int i = ll; i <= rr; i++) a[i] = c;
b[p] = 0;
}
else {
if (b[p]) for (int i = l[p]; i < ll; i++) a[i] = b[p];
for (int i = ll; i <= r[p]; i++) a[i] = c;
b[p] = 0;
for (int i = p + 1; i <= q - 1; i++) b[i] = c;
for (int i = l[q]; i <= rr; i++) a[i] = c;
if (b[q]) for (int i = rr + 1; i <= r[q]; i++) a[i] = b[q];
b[q] = 0;
}
}
int main() {
scanf("%d%d", &n, &q);
init();
while (q--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
update(x, y, z);
}
for (int i = 1; i <= n; i++) printf("%d ", b[bl[i]] ? b[bl[i]] : a[i]);
return 0;
}
T4
定义状态 为走到 所需最小的步数，每一位可以从上一位走过来，即
也可以从之前的位置跳跃而来，设 为蓄力的时间
初始在 点
时间复杂度
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 2e5 + 55, inf = 2147483647;
int n;
int a[N];
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) a[i] = N;
for (int i = 2; i <= n; i++) {
a[i] = a[i - 1] + 1;
for (int j = 2; i - j * j >= 1; j++) {
a[i] = min(a[i], a[i - j * j] + j + 1);
}
}
printf("%d\n", a[n]);
return 0;
}
T5
感觉 T5 有问题啊，感觉我做法没啥问题，大家都 20 分，是都忽略啥了吗。
设 为在第 秒走到点 的方案数，你可以从上一秒相邻安全的点转移。其中起点在第 秒为 ，答案是第 秒的终点。
时间复杂度
非AC代码：
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#define int long long
using namespace std;
const int N = 205, MOD = 998244353;
int n, m, t;
int a, b, c, d;
char str[N][N];
int f[N][N][N];
int nt[5][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
signed main() {
scanf("%lld%lld%lld", &n, &m, &t);
for (int i = 1; i <= n; i++) scanf("%s", str[i] + 1);
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
f[a][b][0] = 1;
for (int k = 1; k <= t; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if ((i != c || j != d) && str[i][j] == '*') continue;
for (int p = 0; p < 4; p++) {
int xx = i + nt[p][0];
int yy = j + nt[p][1];
f[i][j][k] = (f[i][j][k] + f[xx][yy][k - 1]) % MOD;
}
}
}
}
printf("%lld\n", f[c][d][t]);
return 0;
}
T6
设 为以 为根的子树魔法值之和， 为以 为根的子树颜色为 结点总数， 为如果 的父亲结点颜色为 ，子树中所有颜色为 的结点与他相连能产生的除去这个父亲节点外能产生的魔法值。
对于每个结点：
直接累加所有子树的每种颜色，最后在自己的颜色 。
也是直接累加，但对于自己的颜色，要额外加上那个子树的 ，因为上面的点连接下面的点都会穿过他。
先直接累加，对于与自己相连产生的贡献，就是那个子树与自己颜色相同的 ，原因：累加 请看他的定义， 是因为还要算上当前结点产生的贡献。
然后考虑跨过当前结点产生的贡献，在每个子树内，其他子树所有颜色相同的节点都可以和自己的所有结点连接，设当前节点为 ，当前子树根结点为 贡献就是 ，对于每种颜色都要统计。还要额外颜色与当前结点相同时跨过当前结点产生的贡献。
时间复杂度
#include <iostream>
#include <cmath>
#include <cstdio>
#define int long long
using namespace std;
const int N = 1e5 + 55, C = 105, inf = 2147483647;
int n, tot;
int f[N], d[N][C], s[N][C], h[N], a[N];
struct edge {
int v, nxt;
} e[N << 2];
void add(int x, int y) {
e[++tot] = {y, h[x]};
h[x] = tot;
}
void dfs(int u, int fa) {
int cnt = 0;
for (int i = h[u]; i; i = e[i].nxt) {
if (e[i].v == fa) continue;
dfs(e[i].v, u);
f[u] += f[e[i].v];
f[u] += d[e[i].v][a[u]] + s[e[i].v][a[u]];
d[u][a[u]] += s[e[i].v][a[u]];
for (int j = 1; j <= 100; j++) {
d[u][j] += d[e[i].v][j];
s[u][j] += s[e[i].v][j];
}
}
int ct = 0;
for (int i = h[u]; i; i = e[i].nxt) {
if (e[i].v == fa) continue;
ct += (s[u][a[u]] - s[e[i].v][a[u]]) * s[e[i].v][a[u]];
for (int j = 1; j <= 100; j++) {
f[u] += (d[e[i].v][j]) * (s[u][j] - s[e[i].v][j]);
}
}
ct /= 2;
f[u] += ct;
s[u][a[u]]++;
d[u][a[u]]++;
}
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i < n; i++) {
int x, y;
scanf("%lld%lld", &x, &y);
add(x, y);
add(y, x);
}
dfs(1, 0);
printf("%lld\n", f[1]);
return 0;
}
有帮助，赞一个