ACGO挑战赛#24 非官方题解
2025-11-02 22:01:38
发布于：山东
17阅读
0回复
0点赞
A
体感难度：红
直接模拟倒水的过程即可，时间复杂度为 。
B
体感难度：橙
队列的第一个元素一定是唯一一个满足 的元素，然后维护数组 表示第 个人的后面一个人的编号，显然有 。
然后从队首元素 开始，每一次找到其后面一个元素 ，然后令 即可，总时间复杂度为 可以通过。
C
体感难度：橙
因为任意时刻车上人数都会 ，所以考虑找出一个时刻，使得该时刻人数最少，让这个时刻在车上的人数为 ，维护该时刻和初始时刻（即第一次上下车之前）的相对关系即当前时刻比初始时刻多 / 少了多少个人（这里少用多了负数个人来表示），这是简单的，直接求 序列的前缀和，找到其前缀最小值 即可。
最后的答案即为 ，时间复杂度为 可以通过。
D
体感难度：黄
十分的套路，考虑同时维护两个人的位置，设 表示当前两个人分别移动到了 和 两个位置，最少需要从初始状态出发移动多少步，容易发现这个可以直接 BFS 求最短路处理，总状态数为 ，时间复杂度也为 ，可以通过。
namespace Loyalty
{
char s[62][62];
int a[N], ne[N], dis[62][62][62][62];
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
struct Point { int x1, y1, x2, y2; } ;
inline void main([[maybe_unused]] int _case, [[maybe_unused]] int atc)
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cin >> s[i][j];
queue<Point> q;
int x1 = -1, y1 = -1, x2 = -1, y2 = -1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (s[i][j] == 'P')
{
if (!~x1)
x1 = i, y1 = j;
else
x2 = i, y2 = j;
}
q.push({x1, y1, x2, y2});
memset(dis, 0x3f, sizeof dis);
dis[x1][y1][x2][y2] = 0;
while (q.size())
{
auto [x1, y1, x2, y2] = q.front();
q.pop();
for (int d = 0; d < 4; ++d)
{
int ix1 = x1 + dx[d], iy1 = y1 + dy[d];
int ix2 = x2 + dx[d], iy2 = y2 + dy[d];
int nx1 = x1, ny1 = y1, nx2 = x2, ny2 = y2;
if (ix1 >= 1 && ix1 <= n && iy1 >= 1 && iy1 <= n && s[ix1][iy1] != '#')
nx1 = ix1, ny1 = iy1;
if (ix2 >= 1 && ix2 <= n && iy2 >= 1 && iy2 <= n && s[ix2][iy2] != '#')
nx2 = ix2, ny2 = iy2;
if (dis[nx1][ny1][nx2][ny2] > dis[x1][y1][x2][y2] + 1)
dis[nx1][ny1][nx2][ny2] = dis[x1][y1][x2][y2] + 1, q.push({nx1, ny1, nx2, ny2});
}
}
int res = 1e9;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
res = min(res, dis[i][j][i][j]);
cout << ((res > 5e8) ? -1 : res) << '\n';
}
}
E
简要题意：
初始有一个长度为 的序列 ，初始有 。
现在有 个数对 ，需要按照读入的顺序依次执行这 个数对，执行方式为在下面两个操作中选择一种：
- 若序列 满足 ，则可以执行操作 。
- 若序列 满足 ，则可以执行操作 。
问有多少种合法的执行方式。
Sol
体感难度：绿~蓝
感觉是这场比赛里唯一有意思的题（）但是被卡了很久
看到“从两个操作中选一个操作执行”的字眼，容易想到 2-Sat 模型，因为要求计数方案数，所以容易想到判无解后把所有的操作划分为若干个连通块，然后在每个连通块内计数，在连通块之间直接乘法原理得到答案。
直接做比较困难，考虑先挖掘一下操作的性质。容易注意到 操作会被 操作所影响，当且仅当 且 。
然后考虑一个位置 ，设集合 为所有会影响到 的位置 组成的集合，那么对这些位置的 和 位置进行分类讨论：
- 即不存在会影响到位置 的 ，此时该位置不论是覆盖一个前缀还是覆盖一个后缀，都不会导致当前的答案不合法，因此该情况下答案可以乘以 。
- ，此时可以 维护出一个覆盖区间 ，其中 分别表示所有可以影响到 位置的元素中 的最小值和最大值。分类讨论 区间和 的关系：
- 若有 ，那么此时不论 选择的是覆盖前缀还是覆盖后缀，都会和之前的某次操作产生冲突，此时无合法操作方案，答案为 。
- 若有 ，则此时 全部覆盖前缀可以不对答案产生影响。
- 若有 ，则此时 全部覆盖后缀可以不对答案产生影响。
直接按照上述的方法计数会产生后效性，即可能在某一次操作中满足 ，前缀和后缀都可以选，但是在之后的某次操作中因为后面的这个操作和前面的操作产生了冲突，导致两次操作选择的是前缀还是后缀都固定了。因此容易想到解决方案：
- 提前对每个位置 处理出其会被影响到的区间 。
- 只考虑所有 即自己不会被任何区间影响的区间，然后枚举 ，若 所对应的操作会被 所对应的操作影响，则 操作就不能自由选择操作的是前缀还是后缀。
- 若不存在 会被 影响，则 可以自由选择操作前缀还是后缀，答案可以乘以 。
最后判断无解的情况：
- 在前文考虑对于位置 ，判断是否有位置 会被位置 影响的时候，考虑记录是否存在两个操作使得 分别不能选择前缀 / 后缀，若存在这样的两个操作，那么显然无解，输出 即可。
- 对于位置 ，若有 ，那么此时不论 选择的是覆盖前缀还是覆盖后缀，都会和之前的某次操作产生冲突，此时无合法操作方案，答案为 。
直接模拟上述过程，时间复杂度为 可以通过，容易发现上述过程可以用线段树等 ds 优化到 。个人感觉不太能做到严格线性，如果有做法的话可以在评论区留言（）
namespace Luminescent
{
inline int power(int a, int b, int c)
{
int ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % c;
a = a * a % c, b >>= 1;
}
return ans;
}
inline int inversion(int x) { return power(x, mod - 2, mod); }
}
namespace Loyalty
{
int p[N], v[N], L[N], R[N], typ[N];
inline void main([[maybe_unused]] int _case, [[maybe_unused]] int atc)
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i)
cin >> p[i] >> v[i];
for (int i = 1; i <= m; ++i)
{
L[i] = inf, R[i] = -inf;
for (int j = 1; j < i; ++j)
if (v[j] > v[i])
L[i] = min(L[i], p[j]), R[i] = max(R[i], p[j]);
}
for (int i = 1; i <= m; ++i)
if (L[i] <= p[i] && p[i] <= R[i])
{
cout << 0 << '\n';
return;
}
for (int i = 1; i <= m; ++i)
{
if (R[i] < 0)
typ[i] = 0;
else if (L[i] > p[i])
typ[i] = 1;
else if (R[i] < p[i])
typ[i] = 2;
else
typ[i] = 3;
}
for (int i = 1; i <= m; ++i)
if (R[i] >= 0)
for (int j = 1; j < i; ++j)
if (v[j] > v[i] && typ[i] == typ[j])
{
cout << 0 << '\n';
return;
}
int cnt = 0;
for (int i = 1; i <= m; ++i)
if (R[i] < 0)
{
int ok1 = 0, ok2 = 0;
for (int j = i + 1; j <= m; ++j)
if (v[j] < v[i] && typ[j])
{
if (typ[j] == 2 && p[j] > p[i])
ok1 = 1;
else if (typ[j] == 1 && p[j] < p[i])
ok2 = 1;
}
if (ok1 && ok2)
{
cout << 0 << '\n';
return;
}
if (!ok1 && !ok2)
++cnt;
}
cout << Luminescent::power(2, cnt, mod) << '\n';
}
}
F
这不纯唐题（）考虑维护两个线段树，维护的信息分别为：
- 字符串 中第 个位置的值
- 区间 中 的值
判断一段区间 合法可以查询在第二棵线段树中查询区间 的值，若其值为 则该区间组成的字符串合法，否则不合法。
而对于区间 的修改操作，在维护字符串值的线段树中可以直接打懒标记维护，而在维护区间内相邻元素相同的位置的数量的线段树中，注意到只有边界上下标为 的位置的值会变化，所以对这四个位置做单点修改即可。
总时间复杂度为 ，可以通过。
struct Node
{
int l, r, flip_tag;
char val;
inline void init(int p)
{
l = r = p;
flip_tag = 0, val = s[p];
}
inline void push()
{
flip_tag ^= 1;
val ^= 1;
}
} tree[N << 2];
inline Node operator+(const Node &l, const Node &r)
{
return {l.l, r.r, 0, 0};
}
inline void pushdown(int rt)
{
if (tree[rt].flip_tag)
{
tree[rt << 1].push();
tree[rt << 1 | 1].push();
tree[rt].flip_tag = 0;
}
}
inline void build(int l, int r, int rt)
{
if (l == r)
return tree[rt].init(l);
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
inline void loyalty(int rt, int ll, int rr)
{
int &l = tree[rt].l, &r = tree[rt].r;
if (ll <= l && r <= rr)
return tree[rt].push();
int mid = l + r >> 1;
pushdown(rt);
if (ll <= mid)
loyalty(rt << 1, ll, rr);
if (mid < rr)
loyalty(rt << 1 | 1, ll, rr);
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
inline char luminescent(int rt, int pos)
{
int &l = tree[rt].l, &r = tree[rt].r;
if (l == r)
return tree[rt].val;
int mid = l + r >> 1;
pushdown(rt);
return luminescent((pos <= mid) ? (rt << 1) : (rt << 1 | 1), pos);
}
struct SgtNode
{
int l, r, val;
inline void init(int p)
{
l = r = p, val = (int)(s[p] == s[p + 1]);
}
};
inline SgtNode operator+(const SgtNode &l, const SgtNode &r)
{
return {l.l, r.r, l.val + r.val};
}
struct Segment_Tree
{
SgtNode tree[N << 2];
inline void build(int l, int r, int rt)
{
if (l == r)
return tree[rt].init(l);
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
inline void loyalty(int rt, int pos, int val)
{
int &l = tree[rt].l, &r = tree[rt].r;
if (l == r)
{
tree[rt].val = val;
return;
}
int mid = l + r >> 1;
if (pos <= mid)
loyalty(rt << 1, pos, val);
else
loyalty(rt << 1 | 1, pos, val);
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
inline int luminescent(int rt, int ll, int rr)
{
if (ll > rr)
return 0;
int &l = tree[rt].l, &r = tree[rt].r;
if (ll <= l && r <= rr)
return tree[rt].val;
int mid = l + r >> 1, s = 0;
if (ll <= mid)
s = luminescent(rt << 1, ll, rr);
if (mid < rr)
s += luminescent(rt << 1 | 1, ll, rr);
return s;
}
} Sgt;
namespace Loyalty
{
inline void main([[maybe_unused]] int _case, [[maybe_unused]] int atc)
{
int n, q;
cin >> n >> q;
scanf("%s", s + 1);
if (n == 1)
{
while (q--)
{
int o;
scanf("%lld", &o);
if (o == 1)
{
int l, r;
scanf("%lld%lld", &l, &r);
}
else
{
int l, r;
scanf("%lld%lld", &l, &r);
puts("Yes");
}
}
return;
}
Sgt.build(1, n - 1, 1);
build(1, n, 1);
while (q--)
{
int o;
cin >> o;
if (o == 1)
{
int l, r;
scanf("%lld%lld", &l, &r);
loyalty(1, l, r);
if (l - 1 >= 1 && l <= n)
{
char v1 = luminescent(1, l), v2 = luminescent(1, l - 1);
if (v1 == v2)
Sgt.loyalty(1, l - 1, 1);
else
Sgt.loyalty(1, l - 1, 0);
}
if (l >= 1 && l + 1 <= n)
{
char v1 = luminescent(1, l), v2 = luminescent(1, l + 1);
if (v1 == v2)
Sgt.loyalty(1, l, 1);
else
Sgt.loyalty(1, l, 0);
}
if (r - 1 >= 1 && r <= n)
{
char v1 = luminescent(1, r), v2 = luminescent(1, r - 1);
if (v1 == v2)
Sgt.loyalty(1, r - 1, 1);
else
Sgt.loyalty(1, r - 1, 0);
}
if (r >= 1 && r + 1 <= n)
{
char v1 = luminescent(1, r), v2 = luminescent(1, r + 1);
if (v1 == v2)
Sgt.loyalty(1, r, 1);
else
Sgt.loyalty(1, r, 0);
}
}
else
{
int l, r;
scanf("%lld%lld", &l, &r);
cout << (Sgt.luminescent(1, l, r - 1) ? "No" : "Yes") << '\n';
}
}
}
}
有帮助，赞一个