Codeforces Round #625 (Div. 1, based on Technocup 2020 Final Round) 题解
Visits: 360
Codeforces Round #625 (Div. 1, based on Technocup 2020 Final Round)
Journey Planning
两个数可以同时选当且仅当下标差等于值的差，也就是值减下标要相等。
那么把值减下标相同的值加起来即可，由于值减下标可能为负，为了方便，使用 map 即可。
const int N = 2e5 + 7;
int n;
ll a[N], ans;
int main() {
rd(n), rda(a, n);
map<ll, ll> f;
for (int i = 1; i <= n; i++) f[a[i]-i] += a[i];
for (auto o : f) ans = max(ans, o.se);
print(ans);
return 0;
}
当一次决策不是最优的时候，必须 rebuild。
当一次决策是最优的，但是同时还有其他最优的决策，可以 rebuild。
当一次决策是最优的，同时没有其他最优的决策，不能 rebuild。
因此建反图跑一遍最短路，由于边权为 $1$，bfs 即可。
const int N = 2e5 + 7;
int n, m, k, v[N], a[N], d[N];
vi e[N], g[N];
queue<int> q;
int main() {
rd(n), rd(m);
for (int i = 1, x, y; i <= m; i++)
rd(x), rd(y), e[x].pb(y), g[y].pb(x);
rd(k), rda(a, k);
q.push(a[k]), v[a[k]] = 1;
while (q.size()) {
int x = q.front();
q.pop();
for (auto y : g[x])
if (!v[y]) q.push(y), d[y] = d[x] + 1, v[y] = 1;
}
int c1 = 0, c2 = 0;
for (int i = 1; i < k; i++) {
int x = a[i], y = a[i+1];
bool b1 = 0, b2 = 0;
for (auto z : e[x])
if (d[z] < d[y]) b1 = 1;
else if (y != z && d[z] == d[y]) b2 = 1;
if (b1) ++c1;
else if (b2) ++c2;
}
print(c1, ' '), print(c1 + c2);
return 0;
}
World of Darkraft: Battle for Azathoth
以攻击值为横坐标，防御值为纵坐标，问题变成：
- 平面上有一些点，每个点都有一个权值，每个横纵坐标都有一个代价。
- 你要选择一个横坐标和一个纵坐标，使严格在它们和坐标轴构成的矩形内的点的权值和减去这两个坐标的代价最大。
考虑扫描线，在当前横坐标选择每个纵坐标的贡献，每次取最大贡献减去当前横坐标的代价。
加入一个点相当于一个区间加的操作，询问相当于全局 $\max$ 的操作，因此线段树维护即可。
由于值域只有 $10^6$，因此甚至不用离散化。
const int N = 2e5 + 7, M = 1e6 + 1;
const ll inf = 1e18;
int n, m, k;
ll a[M], b[M];
vector<pi> p[M];
struct T {
int l, r;
ll x, z;
} t[M*5];
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) return t[p].x = -b[l], void();
build(ls, l, md), build(rs, md + 1, r);
t[p].x = max(t[ls].x, t[rs].x);
}
void spd(int p) {
if (t[p].z) {
t[ls].x += t[p].z;
t[ls].z += t[p].z;
t[rs].x += t[p].z;
t[rs].z += t[p].z;
t[p].z = 0;
}
}
void add(int p, int l, int r, ll k) {
if (t[p].l >= l && t[p].r <= r) return t[p].x += k, t[p].z += k, void();
spd(p);
if (l <= md) add(ls, l, r, k);
if (r > md) add(rs, l, r, k);
t[p].x = max(t[ls].x, t[rs].x);
}
int main() {
rd(n), rd(m), rd(k);
for (int i = 1; i < M; i++) a[i] = b[i] = inf;
for (int i = 1, x, y; i <= n; i++)
rd(x), rd(y), a[x] = min(a[x], 1ll * y);
for (int i = 1, x, y; i <= m; i++)
rd(x), rd(y), b[x] = min(b[x], 1ll * y);
for (int i = 1, x, y, z; i <= k; i++)
rd(x), rd(y), rd(z), p[x].pb(mp(y, z));
build(1, 1, M - 1);
ll ans = -inf;
for (int i = 1; i < M; i++) {
ans = max(ans, t[1].x - a[i]);
for (pi o : p[i]) if (o.fi != M - 1) add(1, o.fi + 1, M, o.se);
}
print(ans);
return 0;
}
Reachable Strings
011 和 110 可以相互转化，相当于每次可以将每个 0 向左右移动两个单位，因此每个 0 的位置下标的奇偶性不会变。
但是当出现 00 时，左边的 0 无法移到右边，右边的 0 无法移到左边，也就是无法跨越奇偶性不同的 0。
换句话说，两个字符串可以相互转化，当且仅当每个 0 所在的位置下标的奇偶性一一对应。
比如一个字符串中有 $6$ 个 0，位置分别在 $1,2,3,4,6,7$，则它一定可以转化为 0 的位置分别在 $1,10,101,102,1000,10101$ 的字符串。
那么，每次询问相当于求出一个区间内每个 0 在以这个区间开头为奇下标时的奇偶性。
我们对这个奇偶性进行 hash，就能快速比较两个区间内的信息是否一致了。
通常我在 CF 写 Hash 会写一个双 base 单 mod 的确定 Hash，然而被 Hack 了，改成随机 Hash 就过了。
#define Hash pair<modint, modint>
Hash B;
inline Hash operator + (Hash a, Hash b) { return mp(a.fi + b.fi, a.se + b.se); }
inline Hash operator - (Hash a, Hash b) { return mp(a.fi - b.fi, a.se - b.se); }
inline Hash operator * (Hash a, Hash b) { return mp(a.fi * b.fi, a.se * b.se); }
inline Hash operator + (Hash a, int b) { return mp(a.fi + b, a.se + b); }
const int N = 2e5 + 7;
int n, q, c[N];
char s[N];
Hash h[N][2], p[N];
inline Hash H(int l, int r, int o) {
return h[r][o] - h[l-1][o] * p[c[r]-c[l-1]];
}
int main() {
P = rdm((int)1e8, (int)1e9), B = mp(rdm(131, 1331), rdm(1331, 13331));
rd(n), rds(s, n), rd(q);
p[0] = mp((modint)1, (modint)1);
for (int i = 1; i <= n; i++) {
if (s[i] != '0') h[i][0] = h[i-1][0], h[i][1] = h[i-1][1], c[i] = c[i-1];
else h[i][0] = h[i-1][0] * B + ('0' + (i & 1)), h[i][1] = h[i-1][1] * B + ('0' + ((i & 1) ^ 1)), c[i] = c[i-1] + 1;
p[i] = p[i-1] * B;
}
while (q--) {
int l1, l2, len;
rd(l1), rd(l2), rd(len);
int r1 = l1 + len - 1, r2 = l2 + len - 1;
prints(H(l1, r1, l1 & 1) == H(l2, r2, l2 & 1) ? "Yes" : "No");
}
return 0;
}
Treeland and Viruses
树上数据结构问题，多组询问，所有询问涉及的总点数与树的大小同阶。
这玩意儿就是在明示虚树嘛……
虚树建出来后，问题相当于树上多源最短路，dijkstra 即可。
const int N = 2e5 + 7;
int n, q, dfn[N], tot, f[N][21], d[N], s[N], t;
vi e[N], g[N];
void dfs(int x) {
dfn[x] = ++tot;
for (int y : e[x])
if (y != f[x][0]) {
d[y] = d[x] + 1, f[y][0] = x;
for (int i = 1; f[y][i-1]; i++)
f[y][i] = f[f[y][i-1]][i-1];
dfs(y);
}
}
inline int lca(int x, int y) {
if (d[x] > d[y]) swap(x, y);
for (int i = 20; ~i; i--)
if (d[f[y][i]] >= d[x]) y = f[y][i];
if (x == y) return x;
for (int i = 20; ~i; i--)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
inline void virtual_tree(vi &p) {
sort(p.begin(), p.end(), [](int x, int y) { return dfn[x] < dfn[y]; });
p.erase(unique(p.begin(), p.end()), p.end());
vi q = p;
for (int x : p) {
int lca = ::lca(x, s[t]);
if (lca != s[t]) {
while (t && d[s[t-1]] >= d[lca])
g[s[t]].pb(s[t-1]), g[s[t-1]].pb(s[t]), --t;
if (s[t] != lca)
g[s[t]].pb(lca), g[lca].pb(s[t]), s[t] = lca, q.pb(lca);
}
s[++t] = x;
}
if (t) while (--t) g[s[t]].pb(s[t+1]), g[s[t+1]].pb(s[t]);
p = q;
}
int w[N];
bool v[N];
struct P {
int d, i, x, r;
inline P() {}
inline P(int d, int i, int x) : d(d), i(i), x(x) {
r = d ? (d - 1) / w[x] : -1;
}
inline bool operator < (const P o) const {
return r == o.r ? i < o.i : r < o.r;
}
inline P operator - () const {
P o = *this;
o.r *= -1, o.i *= -1;
return o;
}
} u[N];
inline void dijkstra(vi a, vi b, vi p) {
pq<pair<P, int>> q;
for (int x : p) u[x].r = u[x].i = n, v[x] = 0;
for (ui i = 0; i < a.size(); i++)
u[a[i]] = P(0, i, a[i]), q.push(mp(-u[a[i]], a[i]));
while (q.size()) {
int x = q.top().se;
q.pop();
if (v[x]) continue;
v[x] = 1;
for (int y : g[x]) {
P o = P(u[x].d + abs(d[x] - d[y]), u[x].i, u[x].x);
if (o < u[y]) u[y] = o, q.push(mp(-u[y], y));
}
}
for (int x : b) print(u[x].i + 1, ' ');
prints("");
}
int main() {
rd(n);
for (int i = 1, x, y; i < n; i++)
rd(x), rd(y), e[x].pb(y), e[y].pb(x);
d[1] = 1, dfs(1);
rd(q);
while (q--) {
int A, B;
rd(A), rd(B);
vi a, b, p;
for (int i = 1, x, y; i <= A; i++)
rd(x), rd(y), a.pb(x), p.pb(x), w[x] = y;
for (int i = 1, x; i <= B; i++)
rd(x), b.pb(x), p.pb(x);
virtual_tree(p);
dijkstra(a, b, p);
for (int x : p) g[x].clear();
}
return 0;
}
Blocks and Sensors
题面太长了……
听说是暴力模拟贪心？那扔了（
