正赛的几道 Easy,不是很简单,如果评为 Easy-Medium 也不过分。
热身赛 ACD 都是听群友思路补的。
5 6 快 7 快
ID Diff Description Solution Code A 已知 S = n ! m S=\dfrac{n!}{m} S = m n ! 及 1 ≤ m < n ≤ 10 6 1 \le m < n \le 10^6 1 ≤ m < n ≤ 1 0 6 ,求 n , m n,m n , m 。 选模数 P P P ,枚举 n n n ,计算 m = n ! S m o d P m=\dfrac{n!}{S} \bmod P m = S n ! mod P 。如果 m ∈ [ 1 , n − 1 ] m\in[1,n-1] m ∈ [ 1 , n − 1 ] ,就说明找到了答案;否则说明此时 m m m 不是整数,不是答案。O ( log S + n log P ) \mathcal{O}(\log S + n \log P) O ( log S + n log P ) 。 AC B Easy 平面上整点 A A A 和 B B B ,找到整点 C C C ,使三角形 A B C A B C A BC 是直角三角形。 分类:如果 A B AB A B 是斜着的,取 C ( x A , y B ) C(x_{A},y_{B}) C ( x A , y B ) ;如果是垂直的,取 C ( x A , y A ± 1 ) C(x_{A},y_{A}\pm 1) C ( x A , y A ± 1 ) 或 C ( x A ± 1 , y A ) C(x_{A} \pm 1,y_{A}) C ( x A ± 1 , y A ) 之一。 AC C 长度为 N N N 的序列 a a a ,初始全为 0 0 0 。设 f ( k ) = ∑ i = 1 k lowbit ( i ) f(k)=\sum_{i=1}^k\operatorname{lowbit}(i) f ( k ) = ∑ i = 1 k lowbit ( i ) 。在线 M M M 次操作:(1) 输出 a Y a_Y a Y ;(2) 对所有 k k k ,置 a X + f ( k ) ← + W a_{X + f(k)} \xleftarrow{+} W a X + f ( k ) + W 。 f f f 有分形结构,分块。取块长 B = 2 w B=2^w B = 2 w ,设 k = q B + r k=qB+r k = qB + r ,r ≥ 1 r \ge 1 r ≥ 1 时有 lowbit ( q B + r ) = lowbit ( r ) \operatorname{lowbit}(qB+r)=\operatorname{lowbit}(r) lowbit ( qB + r ) = lowbit ( r ) ,f ( q B + r ) = f ( q B ) + f ( r ) f(qB+r)=f(qB)+f(r) f ( qB + r ) = f ( qB ) + f ( r ) 。考虑更新 X X X 对查询 Y Y Y 的影响,Y = X + f ( k ) = X + f ( q B ) + f ( r ) Y=X+f(k)=X+f(qB)+f(r) Y = X + f ( k ) = X + f ( qB ) + f ( r ) ,移项得 X + f ( q B ) = Y − f ( r ) \boxed{X+f(qB)=Y-f(r)} X + f ( qB ) = Y − f ( r ) 。更新时,对所有 q ⩾ 0 q \geqslant 0 q ⩾ 0 ,Lazy [ X + f ( q B ) ] ← + W \operatorname{Lazy}[X+f(qB)] \xleftarrow{+} W Lazy [ X + f ( qB )] + W ;查询 Y Y Y 时,对所有 0 ⩽ r < B 0 \leqslant r < B 0 ⩽ r < B ,Ans ← + Lazy [ Y − f ( r ) ] \text{Ans} \xleftarrow{+} \operatorname{Lazy}[Y-f(r)] Ans + Lazy [ Y − f ( r )] 。O ( M N ) \mathcal{O}(M\sqrt{ N}) O ( M N ) 。AC D Medium 简单多边形,平行直线系。求多边形内部被所有直线截得的线段总长度。 另见 P8008。变换坐标系,使直线平行于 x x x 轴,且间距为 1。考虑多边形上相邻两点 P , Q P,Q P , Q ,截取线段上纵坐标为整数的部分,并求这些整数纵坐标对应的横坐标之和。 AC A Easy 多重集 S S S ,每个元素出现无穷次。求 f ( k ) = gcd S ′ ⊂ S , ∣ S ′ ∣ = k ∑ x ∈ S ′ x f(k) = \gcd\limits_{S' \subset S, \vert S' \vert = k} \sum\limits_{x \in S'} x f ( k ) = S ′ ⊂ S , ∣ S ′ ∣ = k g cd x ∈ S ′ ∑ x 的最大值及达到该最大值的最小 k k k 。 设 D = gcd ( a i − a j ) D=\gcd(a_{i}-a_{j}) D = g cd( a i − a j ) ,f ( k ) = gcd ( k A 1 , D ) f(k) = \gcd(k A_{1}, D) f ( k ) = g cd( k A 1 , D ) 。 若 D = 0 D=0 D = 0 ,则 f ( k ) = k A 1 f(k) = k A_{1} f ( k ) = k A 1 ,最大值无穷大。 否则,设 G = gcd ( A 1 , D ) G = \gcd(A_{1}, D) G = g cd( A 1 , D ) ,那么 f ( k ) = G gcd ( k , D G ) f(k) = G \gcd(k, \frac{D}{G}) f ( k ) = G g cd( k , G D ) ,f ( k ) f(k) f ( k ) 最大为 f ( D G ) = D f(\frac{D}{G}) = D f ( G D ) = D 。 AC B Hard 二维矩形内有点,点碰到边后会反弹。左右边向外匀速扩张,上下边向内匀速压缩。求点在压缩结束时的位置。 依据 y y y 坐标计算结束时间。当左右边速度都为 0 时,直接计算答案。否则,暴力模拟左右碰撞。设第 n n n 次碰撞时的宽度 d n d_n d n ,时刻 t n t_n t n ,那么 Δ t n ∝ d n \Delta t_n\propto d_n Δ t n ∝ d n (追及),Δ d n ∝ Δ t n \Delta d_n\propto \Delta t_n Δ d n ∝ Δ t n ,因此 Δ d n ∝ d n \Delta d_n\propto d_n Δ d n ∝ d n ,得到 d n = O ( e n ) d_{n}= \mathcal{O}(\mathrm{e}^{n}) d n = O ( e n ) ,在碰撞 O ( log ) \mathcal{O}(\log) O ( log ) 次后将达到目标。 AC 只包含 1 和 2 的序列,若干次选择两个相邻的数替换为一个按位或。求本质不同序列数量。保证相同数字段长度单调不降。 G Easy 网格,格子有石子,数量可能为负。可以无代价将石子向右方或下方移动石子,或花 1 代价移除或添加石子。求将所有位置都变为 0 的最小代价。 贪心。如果只有一行:从左向右扫,如果有个地方是负数,就贪心找左边距离它最近的正数,二者相消,如果找不到则必须添加,如果处理完毕后有剩余则必须移除。如果有多行,第一行按上述思路单独处理,把余下的正数转移给下一行,再单独处理第二行。复杂度线性。 AC N N N 个集合共 2 M 2M 2 M 个不同元素。每轮操作将全部元素随机两两配对;对于每一对,随机选择一个元素移动到其配对元素所在的集合。求所有元素属于同一集合的期望轮数。I Medium 黑白六边形网格图,每次选择一格并翻转与其相邻的六格,自身不变。 充要条件:同一斜行黑格的奇偶性不变。 AC AC K Medium 构造包含 n n n 个物品的 01 背包例,满足对于所有背包的容量 2 ≤ c ≤ C 2 \le c \le C 2 ≤ c ≤ C ,按 ( v i / w i , w i ) (v_i/w_i, w_i) ( v i / w i , w i ) 降序贪心选取,不能得到最大总价值。需依次最小化 n n n 、max w \max w max w 、max v \max v max v 。 (1) 按性价比排序后,若前几个物品恰好装满背包,那么贪心最优,不合题意。 (2) w 1 = 1 w_{1} = 1 w 1 = 1 ,即不能 w 1 ≥ 2 w_{1}\ge2 w 1 ≥ 2 。否则取 c = w 1 c=w_{1} c = w 1 ,贪心第一个就选它并装满,由 (1),贪心最优。 (3) 归纳得到,至少 C C C 个物品,且 w k = k w_k=k w k = k 。归纳方法:对 c = 2 c=2 c = 2 ,不能出现另一个 w = 1 w=1 w = 1 。此外,有 w = 2 w=2 w = 2 ,否则贪心与背包相同,都只选了一个 w = 1 w=1 w = 1 。对 c = 3 c=3 c = 3 ,贪心将直接选中 w 1 w_{1} w 1 和刚才的 w = 2 w=2 w = 2 ,但希望这种贪心选择不如直接背包选择 w = 3 w=3 w = 3 。以此类推。 (4) 对 c c c ,贪心选择 w 1 = 1 w_{1}=1 w 1 = 1 和 w = c − 1 w=c-1 w = c − 1 不如直接背包选 w = c w=c w = c 。于是 v 1 + v k − 1 < v k v_{1} + v_{k-1} < v_{k} v 1 + v k − 1 < v k ,化简得 v k ≥ ( k − 1 ) ( v 1 + 1 ) v_{k} \ge (k-1)(v_{1}+1) v k ≥ ( k − 1 ) ( v 1 + 1 ) 。 (5) 为使 w 1 = 1 w_{1} = 1 w 1 = 1 ,有 v 1 > v k k v_{1} > \dfrac{v_{k}}{k} v 1 > k v k ,即 k v 1 > v k = ( k − 1 ) ( v 1 + 1 ) k v_{1} > v_{k} = (k-1)(v_{1}+1) k v 1 > v k = ( k − 1 ) ( v 1 + 1 ) ,有 v 1 ⩾ C v_{1} \geqslant C v 1 ⩾ C ,于是取 v 1 = C v_{1}=C v 1 = C 。 (6) 至此,w k = k w_k=k w k = k ,v 1 = C v_{1}=C v 1 = C ,v k = ( k − 1 ) ( v 1 + 1 ) v_{k} = (k-1)(v_{1}+1) v k = ( k − 1 ) ( v 1 + 1 ) 是唯一的构造方法。 AC L Easy 网格,起点为第 1 1 1 列,终点为第 M M M 列,每次移动可向右、向上或向下。对 2 K 2^{K} 2 K 种障碍排布方式,分别求起点到终点的最小步数。 在可以走的格子内做 BFS 求最短路。因为知道 BFS 的顺序(从左到右,再从上到下或从下到上),可直接用循环完成。O ( 2 K M N ) \mathcal{O}(2^{K} M N) O ( 2 K MN ) 。 AC 正三角形网格图,每个斜行的边的方向相同,求连通的正三角形子图数量。 AC
先将所有 w w w 变成两个 v v v ,做 Manacher。代码里只保留了相同的连续字符的数量,方便写一些。
现在有两个问题:
ov 串的最长回文串不一定对应 ovw 串的最长回文串,这可以枚举每个回文中心求最长半径解决。 ov 串的回文串在 ovw 串里不一定合法,所以如果边界是 vw 串,需要枚举所有可能的位置(如 vwv 的合法位置有 0134) 复杂度是 O ( n ) \mathcal{O}(n) O ( n ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 vector<int > Manacher (const vector<int >& t) { const int n = t.size (); vector<int > rad (n) ; for (int i = 0 , j = 0 ; i < n; i++) { if (2 * j - i >= 0 && j + rad[j] > i) { rad[i] = min (rad[2 * j - i], j + rad[j] - i); } while (i - rad[i] >= 0 && i + rad[i] < n && t[i - rad[i]] == t[i + rad[i]]) { rad[i]++; } if (i + rad[i] > j + rad[j]) { j = i; } } return rad; } void solve () { int n; cin >> n; string s; cin >> s; vector<int > nums; vector<int > lens; vector<int > opts; vector<vector<int >> strs; for (int i = 0 ; i < n; i++) { char c = s[i] == 'o' ? 'o' : 'v' ; int len = (s[i] == 'w' ) + 1 ; if (!opts.empty () && c == opts.back ()) { nums.back () += len; lens.back () += 1 ; strs.back ().push_back (len); } else { nums.push_back (len); opts.push_back (c); lens.push_back (1 ); strs.push_back ({len}); } } auto rad = Manacher (nums); vector<vector<int >> bucpre (lens.size ()), bucsuf (lens.size ()); for (int i = 0 ; i < rad.size (); i++) { if (opts[i] == 'o' ) continue ; int siz = accumulate (strs[i].begin (), strs[i].end (), 0 ); bucpre[i].resize (siz + 1 ); bucsuf[i].resize (siz + 1 ); int pre = 0 ; int len = 0 ; for (int j = 0 ; j < strs[i].size (); j++) { pre += strs[i][j]; len += 1 ; bucpre[i][pre] = len; } int suf = 0 ; len = 0 ; for (int j = int (strs[i].size ()) - 1 ; j >= 0 ; j--) { suf += strs[i][j]; len += 1 ; bucsuf[i][suf] = len; } } vector<int > prelens (lens.size() + 1 ) ; for (int i = 0 ; i < lens.size (); i++) { prelens[i + 1 ] = prelens[i] + lens[i]; } int reslen = 0 , resl = -1 ; auto chres = [&](int len, int l) { if (len > reslen) { reslen = len; resl = l; } }; for (int i = 0 ; i < rad.size (); i++) { int l = i - rad[i]; int r = i + rad[i]; int len = prelens[r] - prelens[l + 1 ]; chres (len, prelens[l + 1 ]); if (l >= 0 && r < lens.size ()) { if (opts[l] == 'o' ) { chres (len + 2 * min (lens[l], lens[r]), prelens[l + 1 ] - min (lens[l], lens[r])); } else if (bucsuf[l].size () < bucpre[r].size ()) { for (int u = 0 ; u < bucsuf[l].size (); u++) { if (bucsuf[l][u] && bucpre[r][u]) { chres (len + bucsuf[l][u] + bucpre[r][u], prelens[l + 1 ] - bucsuf[l][u]); } } } else { for (int u = 0 ; u < bucpre[r].size (); u++) { if (bucsuf[l][u] && bucpre[r][u]) { chres (len + bucsuf[l][u] + bucpre[r][u], prelens[l + 1 ] - bucsuf[l][u]); } } } } } cout << s.substr (resl, reslen) << '\n' ; }
考虑固定水平线 u u u ,考察左斜线 v v v 和右斜线 w w w 的限制,三角形合法当且仅当
{ s 2 u = s 1 v = s 3 w ( 1 ) v ⩾ n − u ( 2 ) w ⩾ n − u ( 3 ) w + v ⩾ n ( 4 ) w + v ≠ 2 n − u ( 5 ) \begin{cases} s_{2u} = s_{1v} = s_{3w} & (1) \\ v \geqslant n - u & (2) \\ w \geqslant n - u & (3) \\ w + v \geqslant n & (4) \\ w + v \neq 2 n - u & (5) \\ \end{cases} ⎩ ⎨ ⎧ s 2 u = s 1 v = s 3 w v ⩾ n − u w ⩾ n − u w + v ⩾ n w + v = 2 n − u ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 )
(5) 这个限制很奇怪,先暂时不考虑。
先枚举 (1)。然后我们升序枚举 u u u ,用两个数据结构 V , W V,W V , W 分别存储满足 (2)(3) 的 v , w v,w v , w ,并记录满足 (4) 的 ( v , w ) (v,w) ( v , w ) 数量 sum。u u u 改变时,答案的增量包括
已有的 sum,加入答案; 对于 v = n − u v=n-u v = n − u ,在 W W W 中查询满足 w + v ⩾ n w + v \geqslant n w + v ⩾ n (4) 的 w w w 数量,加入 sum; 对于 w = n − u w=n-u w = n − u ,在 V V V 中查询满足 w + v ⩾ n w + v \geqslant n w + v ⩾ n (4) 的 v v v 数量,加入 sum; 如果 v = n − u v=n-u v = n − u 和 w = n − u w=n-u w = n − u 满足 (4),sum 加 1。 在查询之后,把 v , w v,w v , w 加入数据结构。
然后考虑 (5),这是一个经典的指标和为定值的形式,用 FFT 或 bitset 做卷积就能计算。
复杂度是 O ( n log n ) \mathcal{O}(n\log n) O ( n log n ) 或 O ( n 2 w ) \mathcal{O}(\frac{n^{2}}{w}) O ( w n 2 ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 #include <bits/stdc++.h> using namespace std;using ll = long long ;using ull = unsigned long long ;using ulll = unsigned __int128;constexpr int inf = 0x3f3f3f3f ;template <typename T>struct Fenwick { int N; vector<T> A; Fenwick (int N = 0 ) : N (N), A (N) {} void add (int x, const T& v) { for (x++; x <= N; x += x & -x) { A[x - 1 ] += v; } } T operator () (int x) const { T res{}; for (; x > 0 ; x -= x & -x) { res += A[x - 1 ]; } return res; } T operator () (int L, int R) const { return operator ()(R) - operator ()(L); } }; constexpr int MAXN = 200002 ;void solve () { int n; cin >> n; array<bitset<MAXN>, 3> s; for (int i = 0 ; i < 3 ; i++) { for (int j = 1 ; j <= n; j++) { char c; cin >> c; s[i][j] = c - '0' ; } } ll res = 0 ; for (int opt = 0 ; opt <= 1 ; opt++) { Fenwick<int > W (n + 1 ) , V (n + 1 ) ; ll sum = 0 ; for (int u = 0 ; u <= n; u++) { int v = n - u; int w = n - u; auto add = [&](int x) { if (s[1 ][u]) res += x; sum += x; }; if (s[1 ][u]) res += sum; if (s[0 ][v]) add (W (n - v, n + 1 )); if (s[2 ][w]) add (V (n - w, n + 1 )); if (s[0 ][v] && s[2 ][w]) add (v + w >= n); if (s[0 ][v]) V.add (v, 1 ); if (s[2 ][w]) W.add (w, 1 ); } bitset<MAXN> s1_rev; for (int i = 1 ; i <= n; i++) { if (s[1 ][i]) s1_rev[n - i] = 1 ; } for (int uv = n; uv < 2 * n; uv++) { int w = 2 * n - uv; if (s[2 ][w]) { res -= (s[0 ] & (s1_rev << uv - n)).count (); } } for (int i = 0 ; i < 3 ; i++) { for (int j = 1 ; j <= n; j++) { s[i][j].flip (); } } } cout << res << endl; } int main () { cin.tie (nullptr )->sync_with_stdio (false ); int t; cin >> t; while (t--) { solve (); } return 0 ; }