2024.7 做题 & 补题
sxyz 做题记录?
7.8.
图论讲课.
还需要学下 Johnson 和 Boruvka.
-
P6381
-
不会总结题面。
-
对边权分解质因数。由于
a^kb^k=(ab)^k ,所以把已经有k 次方的都消掉,即e \to a_1^{b_1} \times a_2^{b_2} \times \cdots \to a_1^{b_1\bmod k}\times a_2^{b_2 \bmod k}\times \cdots 。容易发现这样不影响答案。 -
容易发现,对于
i,j ,满足条件当且仅当相乘次方数量为k 。 -
对于修改后的
e ,令\theta = a_1^{k-b_1\bmod k}\times a_2^{k-b_2 \bmod k}\times \cdots 。 -
则对于
(u,v) 满足条件,当且仅当e_u=\theta_v 。 -
存到一个 map 里,进行 DAG 上 DP 即可。
-
void Topo() { F(i, 1, n) if (ind[i] == 0) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = hd[u]; i; i = e[i].nxt) { int v = e[i].to; mp[v][e[i].w] = max(mp[v][e[i].w], mp[u][e[i]._w] + e[i].l); ans = max(ans, mp[v][e[i].w]); -- ind[v]; if (ind[v] == 0) q.push(v); } } }
int main() { cin >> n >> m >> k;
F(i, 1, m) { int u, v; ll w, l; cin >> u >> v >> w >> l; ll _ = w, _w = 1ll, __ = 1ll; for (ll i = 2; i * i <= _; ++ i) { int tot = 0; while (_ % i == 0ll) {++ tot, _ /= i;} F(j, 1, (tot % k)) _w *= i; if (tot % k != 0) F(j, 1, k - (tot % k)) __ *= i; } if (k - 1) _w *= _; F(i, 1, k - 1) __ *= _; addedge(u, v, _w, __, l); ++ ind[v]; } Topo(); cout << ans;}
-
-
CF1473E
- 题面很简洁了。
- 令
1\sim n 节点为未进行-\max 和+\min 操作的。 -
-
-
- 显然如果减少,
-\max 一定最优,增加\min 同样一定最优。 - 因此对于
(u,v) : -
-
-
-
-
-
- 跑一下 Dijkstra 即可。
-
CF1442C
- 题面很简洁了。
-
P8867
7.9
咕
7.10.
模拟赛。唐完了
-
P4349
-
有一个
N 位的数字,将其分割,以保证每个区间里的数字可以被M 整除。 -
模拟赛加了分割位数
\in [L,R] 的限制。 -
注意到,
1 \sim i 区间内的数可以划分以被M 整除 当且仅当1 \sim i 组成的数能被M 整除。 -
证明:假设
1 \sim i 不能被整除,且可以被划分为[1,\omega_1],[\omega_1+1,\omega_2],\cdots,[\omega_k+1,i] 。 -
当
k=1 时:- 如果
\omega+1 \sim i 不能被整除,显然不能分。 - 如果
\omega+1 \sim i 能被整除,令\omega+1\sim i 组成的数为s_2 ,1\sim\omega 组成s_1 ,1\sim i 组成s ,则s=s_1\times 10^{i-\omega}+s_2 。 - 由于
s_2 \bmod M =0 ,s\bmod M\ne0 ,如果s_1\bmod M=0 ,则s\bmod M=(s_1\times 10^{i-\omega})\bmod M+s_2\bmod M=((s_1 \bmod M)\times10^{i-w}\bmod M)\bmod M+s_2\bmod M=0+0=0 。 - 与题意不符。
- 否则,
s_1 \bmod M \ne 0 ,显然不能分,与题意不符。
- 如果
-
当
k>1 时,同理,可以转化为k-1,\cdots,1 的情况。 -
做 DP 算方案数量即可。
-
可以双指针扫或者用 Seg 维护。
-
int main() { IOS cin >> n >> m/* >> l >> r*/; l = 1, r = n; cin >> st ; st = ' ' + st; F(i, 1, n) a[i] = st[i] - '0'; F(i, 1, n) _[i] = (_[i - 1] * 10ll + a[i]) % m; ll sum = 0ll; int L = 1 - r, R = 1 - l; for (int i = 1; i <= n; ++ i) { if (_[i] % m == 0) { if (i >= l && i <= r) f[i] = 1ll; f[i] += sum ; f[i] %= mod ; } if (R >= 0) sum += f[R + 1]; sum %= mod; if (L > 0) sum += mod - f[L]; sum %= mod; ++ L, ++ R; } cout << f[n]; }
-
-
P9820
- 唐题,但忘打
freopen。
- 唐题,但忘打
-
咕
7.11.
启发式搜索和估价函数。
- 咕
7.12.
7.13.
唐.薯薯题没想到,喜提
-
AGC025B
-
还。是。写。下。吧。
-
有
n 个格子排成一排,每个格子可以涂成红、蓝、绿或不涂色,得分分别为A,B,A+B,0 。求使总得分为K 的方案数,答案对998244353 取模 -
赛时加强到任意质数模数,需要用 Lucas 定理/fn
-
设红色有
x 个,绿色有y 个,没有紫色,则有Ax+By=k 。 -
由于
n \le 3 \times 10^5 ,所以不用 exgcd。 -
然后开始想歪了。
-
令紫色为
i 个,则答案为 -
s = \sum\limits_{i=0}^{\min(x,y)}\binom{n}{x-i}\cdot \binom{n-x+i}{y-i}\cdot \binom{n-x-y+2i}{i} -
然后赛场上对着这个化简了 3 小时,没化简出来/fad
-
最坏时间复杂度
O(n \min(n,k)) 。 -
正解:把它看成
n 列2 行的方格,第一行为红,第二行为蓝,如果红和蓝在一个格子就是紫色。 -
公式简单的
-
关于 Lucas:
-
\binom{n}{k} \bmod p = \binom{n \bmod p}{k \bmod p} \cdot \binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{k}{p}\rfloor} \bmod p -
struct Shiroko { ll x, y; };
vector <Shiroko> v;
//ll mod;
namespace Maths {
ll f[1200000]; inline void Init() { f[0] = 1ll; F(i, 1, 1199999) f[i] = f[i - 1] * (1ll * i) % mod; } inline ll qp(ll x, ll y) { if (y == 0ll) return 1ll; ll Chtholly = qp(x, y / 2ll); if (y & 1ll) return Chtholly * Chtholly % mod * x % mod; else return Chtholly * Chtholly % mod; } inline ll div(ll x) { return qp(x, mod - 2ll) % mod; } inline ll C(ll n, ll m) { if (m > n) return 0ll; return f[n] * div(f[m]) % mod * div(f[n - m]) % mod; } inline ll Lucas (ll n, ll m) { if (m > n) return 0ll; if (m == 0ll) return 1ll; return C(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod; }} ll ans = 0ll; int main() { // OPEN cin >> n >> A >> B >> K >> mod;
Maths::Init(); if (A == 0 && B == 0) { if (K == 0) { cout << Maths::qp(4ll, n); return 0; } else { cout << 0; return 0; } } if (B == 0) { if (K % A != 0) { cout << 0; return 0; } ll _ = K / A; if (K / A > n) {cout << 0; return 0;} cout << Maths::Lucas(n, _) * Maths::qp(2, _) % mod * Maths::qp(2, n - _) % mod; return 0; } if (A == 0) { if (K % B != 0) { cout << 0; return 0; } ll _ = K / B; if (K / B > n) {cout << 0; return 0;} cout << Maths::Lucas(n, _) * Maths::qp(2, _) % mod * Maths::qp(2, n - _) % mod; return 0; } for (ll i = 0ll; i <= n; ++ i) { ll _ = K - A * i; if (_ % B == 0) { ll y = _ / B; if (y <= n && y >= 0) v.push_back({i, y}); } } for (Shiroko i : v) { ans += Maths::Lucas(n, i.y) * Maths::Lucas(n, i.x); ans %= mod; } cout << ans;}
-
7.16
-
T1 唐题,期望得分
100 ,实际得分20 /fn -
T2 比 T3 难.jpeg
-
T3 神秘随机题,期望得分
[50,100] ,实际得分100 -
大意:有一个长度为
n 的序列a ,他需要从中选出一个元素个数为k(k\ge\left\lceil\dfrac{n}{2}\right\rceil) 的子序列w ,使得\gcd\limits_{i=1}^k w_i 最大。 -
正解是
O(\max d(a_i)^2) 的,但是我O(\max d(a_i)\cdot n) 加去重居然能艹过/fad -
拜谢喵喵
O(\max d(a_i)\cdot \max \omega(a_i)) 神仙高维后缀和做法/bx -
随机取一个
p 。 -
找出
p 的因数,对所有a_i 判断这是不是公因数,如果有\ge\left\lceil\dfrac{n}{2}\right\rceil 个,则更新答案 。 -
因为
p 有 至少\dfrac{1}{2} 的概率是w 中的,随机15 次,每次询问就有不到\dfrac{1}{2^{15}} 的概率出错,比 U Rock 掉 U Moon 概率还低。 -
代码跟屎一样
-
mt19937 rng(time(0));
ll a[100010]; ll f[100010];
int r[18];
void w(int x) { for (ll i = 1ll; i i <= a[x]; ++ i) if (a[x] % i == 0ll) { if (i i == a[x]) f[++ m] = i; else {f[++ m] = i; f[++ m] = a[x] / i;} } }
bool cmp(ll x, ll y) {return x > y;}
int main() { OPEN int T; IOS
cin >> T; while (T --) { cin >> n; F(i, 1, n) cin >> a[i]; F(i, 1, 14) r[i] = rng() % n + 1; F(i, 1, 14) w(r[i]); sort (f + 1, f + m + 1, cmp); m = unique(f + 1, f + m + 1) - f - 1; F(i, 1, m) { int tot = 0; F(j, 1, n) { if (a[j] % f[i] == 0) ++ tot; } if (tot * 2 >= n) { cout << f[i] << '\n'; break ; } } } return 0;}
-
7.17.
基础数据结构.
都是典题。
-
CF865D
-
已知接下来
N 天的股票价格,每天你可以买进一股股票,卖出一股股票,或者什么也不做。N 天之后你拥有的股票应为0 ,求这N 天内能够赚最多的钱数。 -
反悔贪心典。
-
注意到,不做等价于买进然后原价卖出。
-
所以碰到一个数,可以直接买进,因为即使之后亏损也会在最后原价卖出。
-
如果碰到一个数大于最小,就直接卖出最小价值的。
-
注意到此时如果再买进当前的,等价于不做,但是还有一种选择是不卖出最小,买进当前的。
-
可以用堆维护。
-
F(i, 1, n) { ll x; cin >> x; if (q.empty()) { q.push(x); continue ; } ll w = q.top(); if (w < x) { ans += (x - w); q.pop(); q.push(x); q.push(x); } else { q.push(x); } }
-
-
CF883J
-
有
m 个建筑,每个建筑拆除需要p_i 代价,装修需要b_i 代价。有n 个月,每个月预算a_i 。每个月可以拆除若干建筑,但对于第i 天,建筑j 需要b_j \le a_i 才能拆除。 -
拆除可以用到之前存的预算,求最多拆除多少个建筑。
-
发现把钱留到尽可能后面一定不劣。
-
但是还有
b_j \le a_i 的限制。 -
先把
b_j \le a_i 且\forall \omega \in [i + 1, n], a_{\omega} < b_j 的尽量在a_i 拆掉。 -
之后就是反悔贪心板子了。
-
int main() { IOS cin >> n >> m; F(i, 1, n) cin >> s[i]; F(i, 1, m) cin >> f[i].b; F(i, 1, m) cin >> f[i].p; sort(f + 1, f + m + 1, cmp); D(i, n, 1) { if (s[i] > mx[i + 1]) tag[i] = 1; mx[i] = max(mx[i + 1], s[i]); } for (int i = 1, j = 1; i <= n; ++ i) { sum += s[i]; if (! tag[i]) continue; while (j <= m) { if (f[j].b > s[i]) {++ j; continue ;} if (f[j].b <= mx[i + 1]) break ; if (f[j].p > sum && q.empty()) {++ j; continue ;} if (f[j].p > sum && q.top() < f[j]) {++ j; continue ;} if (f[j].p > sum) { sum -= f[j].p; sum += q.top().p; q.pop(); q.push(f[j]); } else { sum -= f[j].p; q.push(f[j]); ++ tot; } ++ j; } } cout << tot; }
-
-
ABC359E
Seg & Fenwick (7.18)
-
CF558E
- 题目大意: 给定一个长度不超过
10^5 的字符串(小写英文字母),和不超过50000 个操作。
每个操作
\texttt{L\ R\ K} 表示给区间[L,R] 的字符串排序,K=1 为升序,K=0 为降序。-
小写英文字母,值域不超过
26 ! -
对于
\tt a 到\tt z ,开一个线段树维护数量。 -
然后直接用技术排序的思想区间覆盖就行了。
-
bool st; string str; struct Node { int tag; int w[27]; Node operator +(const Node& p) const { Node q; q.tag = 0; q.w[0] = 0; F(i, 1, 26) q.w[i] = p.w[i] + w[i]; return q; }
}f[410000];
bool ed;
void Build(int l, int r, int p) { if (l == r) { int v = str[l] - 97 + 1;
F(i, 1, 26) if (i != v) f[p].w[i] = 0; else f[p].w[i] = 1; return ; } int m = (l + r) / 2; Build (l, m, ls(p)); Build (m + 1, r, rs(p)); f[p] = f[ls(p)] + f[rs(p)];}
void pushdown(int l, int r, int p) { if (f[p].tag == 0) return ;
int m = (l + r) / 2; int v = f[p].tag; F(i, 1, 26) { if (i != v) f[ls(p)].w[i] = 0; else f[ls(p)].w[i] = (m - l + 1); if (i != v) f[rs(p)].w[i] = 0; else f[rs(p)].w[i] = (r - m); } f[ls(p)].tag = f[rs(p)].tag = f[p].tag; f[p].tag = 0;}
void cover(int l, int r, int s, int t, int p, int v) { if (l <= s && t <= r) { F(i, 1, 26) if (i != v) f[p].w[i] = 0; else f[p].w[i] = (t - s + 1); f[p].tag = v; return; }
int m = (s + t) / 2; pushdown(s, t, p); if (l <= m) cover(l, r, s, m, ls(p), v); if (m < r) cover (l, r, m + 1, t, rs(p), v); f[p] = f[ls(p)] + f[rs(p)];}
char query(int l, int r, int x, int p) { if (l == r) { F(i, 1, 26) if (f[p].w[i] >= 1) return char(i + 96); return '?'; }
pushdown(l, r, p); int m = (l + r) / 2; if (x <= m) return query(l, m, x, ls(p)); else return query(m + 1, r, x, rs(p));}
Node querycnt(int l, int r, int s, int t, int p) { if (l <= s && t <= r) { return f[p]; }
pushdown(s, t, p); int m =(s + t) / 2; Node w; if (l <= m && m < r) w = querycnt(l, r, s, m, ls(p)) + querycnt(l, r, m + 1, t, rs(p)); else if (l <= m) w = querycnt(l, r, s, m, ls(p)); else if (m < r) w = querycnt(l, r, m + 1, t, rs(p)); return w;}
void upsort(int l, int r) { Node _ = querycnt(l, r, 1, n, 1);
for (int i = 1, j = l; i <= 26; ++ i) { if (_.w[i] == 0) continue ; cover(j, j + _.w[i] - 1, 1, n, 1, i); j += _.w[i]; }}
void downsort(int l, int r) { Node = querycnt(l, r, 1, n, 1); for (int i = 26, j = l; i >= 1; -- i) { if (.w[i] == 0) continue ;
cover(j, j + _.w[i] - 1, 1, n, 1, i); j += _.w[i]; }}
- 题目大意: 给定一个长度不超过
-
P2572
-
。
-
区间最长连续,最大子段和这种 trick 很常见了。
-
维护最长连续
0 个数,最长连续1 个数 -
和左端右端最长连续。
-
然后打
3 种\text{tag} 。 -
区间取反
-
区间变
0 -
区间变
1 -
取反下传的时候,如果有标记了,就把标记取反。
-
如区间变
0 变成区间变1 。 -
struct Node { ll cnt0, cnt1; ll mx0, mx1; ll mxl0, mxl1; ll mxr0, mxr1; Node operator +(const Node& p) const { Node q; q.cnt0 = cnt0 + p.cnt0; q.cnt1 = cnt1 + p.cnt1; if (cnt1 == 0) q.mxl0 = mxl0 + p.mxl0; else q.mxl0 = mxl0; if (cnt0 == 0) q.mxl1 = mxl1 + p.mxl1; else q.mxl1 = mxl1; if (p.cnt1 == 0) q.mxr0 = p.mxr0 + mxr0; else q.mxr0 = p.mxr0; if (p.cnt0 == 0) q.mxr1 = p.mxr1 + mxr1; else q.mxr1 = p.mxr1; q.mx0 = max(mx0, max(p.mx0, mxr0 + p.mxl0)); q.mx1 = max(mx1, max(p.mx1, mxr1 + p.mxl1)); return q; }
}S[420000]; int a[110000]; int tag[410000]; bool ed;
void Build (int l, int r, int p) { if (l == r) { if (a[l] == 0) { S[p].cnt0 = S[p].mxl0 = S[p].mxr0 = S[p].mx0 = 1; S[p].cnt1 = S[p].mxl1 = S[p].mxr1 = S[p].mx1 = 0; } else { S[p].cnt0 = S[p].mxl0 = S[p].mxr0 = S[p].mx0 = 0; S[p].cnt1 = S[p].mxl1 = S[p].mxr1 = S[p].mx1 = 1; } return ; }
int m = (l + r) / 2; Build (l, m, ls(p)); Build (m + 1, r, rs(p)); S[p] = S[ls(p)] + S[rs(p)];}
void pushdown(int l, int r, int p) { if (tag[p] == 0) { int m = (l + r) / 2; S[ls(p)].cnt0 = S[ls(p)].mxl0 = S[ls(p)].mxr0 = S[ls(p)].mx0 = m - l + 1; S[ls(p)].cnt1 = S[ls(p)].mxl1 = S[ls(p)].mxr1 = S[ls(p)].mx1 = 0; tag[ls(p)] = 0; S[rs(p)].cnt0 = S[rs(p)].mxl0 = S[rs(p)].mxr0 = S[rs(p)].mx0 = r - m; S[rs(p)].cnt1 = S[rs(p)].mxl1 = S[rs(p)].mxr1 = S[rs(p)].mx1 = 0; tag[rs(p)] = 0; } else if (tag[p] == 1) { int m = (l + r) / 2; S[ls(p)].cnt0 = S[ls(p)].mxl0 = S[ls(p)].mxr0 = S[ls(p)].mx0 = 0; S[ls(p)].cnt1 = S[ls(p)].mxl1 = S[ls(p)].mxr1 = S[ls(p)].mx1 = m - l + 1; tag[ls(p)] = 1; S[rs(p)].cnt0 = S[rs(p)].mxl0 = S[rs(p)].mxr0 = S[rs(p)].mx0 = 0; S[rs(p)].cnt1 = S[rs(p)].mxl1 = S[rs(p)].mxr1 = S[rs(p)].mx1 = r - m; tag[rs(p)] = 1; } else if (tag[p] == 2) { int m = (l + r) / 2; swap(S[ls(p)].cnt0, S[ls(p)].cnt1); swap(S[ls(p)].mx0, S[ls(p)].mx1); swap(S[ls(p)].mxl0, S[ls(p)].mxl1); swap(S[ls(p)].mxr0, S[ls(p)].mxr1); if (tag[ls(p)] == -1) tag[ls(p)] = 2; else tag[ls(p)] ^= 1;
swap(S[rs(p)].cnt0, S[rs(p)].cnt1); swap(S[rs(p)].mx0, S[rs(p)].mx1); swap(S[rs(p)].mxl0, S[rs(p)].mxl1); swap(S[rs(p)].mxr0, S[rs(p)].mxr1); if (tag[rs(p)] == -1) tag[rs(p)] = 2; else tag[rs(p)] ^= 1; } tag[p] = -1;}
void upd0(int l, int r, int s, int t, int p) { if (l <= s && t <= r) { S[p].cnt0 = S[p].mxl0 = S[p].mxr0 = S[p].mx0 = t - s + 1; S[p].cnt1 = S[p].mxl1 = S[p].mxr1 = S[p].mx1 = 0; tag[p] = 0; return ; } if (tag[p] != -1) pushdown(s, t, p);
int m = (s + t) / 2; if (l <= m)upd0(l, r, s, m, ls(p)); if (m < r) upd0(l, r, m + 1, t, rs(p)); S[p] = S[ls(p)] + S[rs(p)];}
void upd1(int l, int r, int s, int t, int p) { if (l <= s && t <= r) { S[p].cnt0 = S[p].mxl0 = S[p].mxr0 = S[p].mx0 = 0; S[p].cnt1 = S[p].mxl1 = S[p].mxr1 = S[p].mx1 = t - s + 1; tag[p] = 1; return ; } pushdown(s, t, p);
int m = (s + t) / 2; if (l <= m)upd1(l, r, s, m, ls(p)); if (m < r) upd1(l, r, m + 1, t, rs(p)); S[p] = S[ls(p)] + S[rs(p)];}
void upd2(int l, int r, int s, int t, int p) { if (l <= s && t <= r) { swap(S[p].cnt0, S[p].cnt1); swap(S[p].mx0, S[p].mx1); swap(S[p].mxl0, S[p].mxl1); swap(S[p].mxr0, S[p].mxr1); if (tag[p] == -1) tag[p] = 2; else tag[p] ^= 1; return ; } pushdown(s, t, p); int m = (s + t) / 2; if (l <= m) upd2(l, r, s, m, ls(p)); if (m < r) upd2(l, r, m + 1, t, rs(p)); S[p] = S[ls(p)] + S[rs(p)]; }
Node newnode() { Node t; t.cnt0 = t.cnt1 = t.mx0 = t.mx1 = t.mxl0 = t.mxl1 = t.mxr0 = t.mxr1 = 0; return t; }
Node query(int l, int r, int s, int t, int p) { if (l <= s && t <= r) { return S[p]; } Node w = newnode(); pushdown(s, t, p); int m = (s + t) / 2; if (l <= m && m < r) w = query(l, r, s, m, ls(p)) + query(l, r, m + 1, t, rs(p)); else if (l <= m) w = query(l, r, s, m, ls(p)); else if (m < r) w = query(l, r, m + 1, t, rs(p)); return w; }
-
7.19
- P9196
- 建立两个 Trie,存储
S_i 的前缀和后缀。 - 对每一个
S_i ,找到她从前往后的\text{dfn} 值和从后往前的\text{dfn} 值,记为x_i, y_i 。 - 容易发现,前缀相同,在 Trie 里的
\text{dfn} 值是连续的。 - 预处理每一个前缀所对应的
\text{dfn} 区间和后缀的\text{dfn} 区间,记为[L,R] ,[X,Y] 。 - 则答案变为满足
L \le x_i \le R,X\le y_i\le Y 的点数量。 - 板子题。
- 按
x_i 排序。 - 遍历
x_i ,将y_i 的值加入到数组中。 - 如果扫到了
L ,记录\le L 且在[X,Y] 区间内的点数量\text{sum}_1 。 - 如果扫到了
R ,记录\le R 且在[X,Y] 区间内的点数量\text{sum}_2 。 - 单点修改,区间查询,用 Seg 维护。注意顺序是先记录
\text{sum}_1 ,再将纵坐标y_i 的数量+1 ,最后统计\text{sum}_2 。 - 6.3KB 应当代码
- 建立两个 Trie,存储
7.25
- 一道递推题:
- 给定
n ,构造1 \sim n 排列p ,要求\forall 1\le i\le n,p_i\ne i ,求方案数。 - 令
d_x 表示n=x 时方案。则有d_x=(x-1)(d_{x-1}+d_{x-2}) 。 - 证明:令
p_x=\theta(1\le\theta<x) 。 - 由于有两种可能:
-
- 两个固定了,其余 $x-2$ 未固定,为 $d_{x-2}$。 -
- 同理,$d_{x-1}$。
- 给定