高产更新。老年退役选手Div.2也还是可以玩得很开心的。
题目大意: q q q 组询问给定 l , d , r l,d,r l , d , r ,每组询问输出最小的 x x x 满足 d ∣ x d|x d ∣ x 且 x ∉ [ l , r ] x\notin [l,r] x ∈ / [ l , r ] 。 q ≤ 500 , 1 ≤ l , r , d ≤ 1 0 9 q \le 500, 1 \le l,r,d \le 10^9 q ≤ 5 0 0 , 1 ≤ l , r , d ≤ 1 0 9 。
如果 d < l d \lt l d < l 那么答案就是 d d d ,否则就是 ( ⌊ r d ⌋ + 1 ) d (\lfloor\frac{r}{d}\rfloor+1)d ( ⌊ d r ⌋ + 1 ) d 。 O ( 1 ) O(1) O ( 1 ) 。
1 2 3 4 5 6 #include <bits/stdc++.h> using namespace std ;#define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}int q, l, r, d; int main () {for (q = rf(); q--; l = rf(), r = rf(), d = rf(), printf ("%d\n" ,d>=l?r/d*d+d:d)); return 0 ;}
题目大意: 给定一个字符串 s s s 求其一个最长的形如[:||||||:]
的子序列其中|
可以有 0 0 0 至若干个。 ∣ s ∣ ≤ 5 × 1 0 5 \lvert s \rvert \le 5 \times 10^5 ∣ s ∣ ≤ 5 × 1 0 5 。
贪心选择最靠左的[
右面最靠左的:
,选择最靠右的]
左面最靠右的:
,两个:
中间的|
全要。注意判断无解。 O ( ∣ s ∣ ) O(\lvert s \rvert) O ( ∣ s ∣ ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 #include <bits/stdc++.h> using namespace std ;#define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}char S[500005 ]; int l, r, n, x;int main () { scanf ("%s" ,S); n = strlen (S); for (r = n-1 ; ~r && S[r]^']' ; r--); for (; ~r && S[r]^':' ; r--); for (l = 0 ; l < n && S[l]^'[' ; l++); for (; l < n && S[l]^':' ; l++); printf ("%d\n" ,l<r?count(S+l,S+r,'|' )+4 :-1 ); return 0 ; }
为啥会有588个Tests?
题目大意: T T T 组询问每次给出 n n n 个线段,求将线段分成两个非空 集合的方案,使得不属于同一个集合的线段不相交,或输出无解。 l i , r i , T , ∑ n ≤ 1 0 5 l_i,r_i,T,\sum n \le 10^5 l i , r i , T , ∑ n ≤ 1 0 5 。
这…不是只需要把相交的线段都分到一组就好了?不过如果所有线段都相交(不要求两两相交,就是线段的并是同一个线段)就不行了。 O ( ( ∑ n ) log ( ∑ n ) ) O((\sum n) \log (\sum n)) O ( ( ∑ n ) log ( ∑ n ) ) ,复杂度的瓶颈在于排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <bits/stdc++.h> using namespace std ;#define MAXN 100000 #define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}struct Seg {int l,r,i;}s[MAXN+5 ]; inline bool operator < (const Seg &a, const Seg &b){return a.l<b.l;} int T, n, r, c; bool ans[MAXN+5 ], f;int main () { for (T = rf(); T--; ) { n = rf(); for (rint i = 1 ; i <= n; s[i].i = i, s[i].l = rf(), s[i].r = rf(), i++); sort(s+1 ,s+n+1 ); f = 1 , r = 0 , c = -1 ; for (rint i = 1 ; i <= n; i++) if (s[i].l <= r) r = max(r,s[i].r), ans[s[i].i] = f; else r = s[i].r, f ^= 1 , ans[s[i].i] = f, ++c; if (f) for (rint i = 1 ; i <= n; printf ("%d%c" ,ans[i]+1 ,"\n " [i<n]), i++); else puts ("-1" ); } return 0 ; }
题目大意: 给定 n n n 个点带权值的树,求一条最长的路径使得路径上所有点(包括端点)的 G C D > 1 GCD > 1 G C D > 1 。 n , a i ≤ 2 × 1 0 5 n,a_i \le 2 \times 10^5 n , a i ≤ 2 × 1 0 5 。
老年退役 OIer基本素养: 看到 a i ≤ 2 × 1 0 5 a_i \le 2 \times 10^5 a i ≤ 2 × 1 0 5 这题绝对和这个复杂度有关系。(凡是涉及树上 G C D GCD G C D 的问题权值有范围一定要利用权值范围。)
为方便起见记 m = max { a i } m = \max \lbrace a_i \rbrace m = max { a i } 。
一般这种题的套路就是枚举约数求虚树: 枚举 G C D = d GCD = d G C D = d ,把所有是 d d d 的倍数的节点都拿出来建一个虚树(虚森林),然后在这上面当做一个不涉及数论的纯树上问题去做。
这道题按照这个套路来,建出虚森林以后就是求直径。对于每一个大小为 s z sz s z 的虚森林。
问题 1 1 1 : 如何预处理"所有权值是 d d d 的倍数的节点"的集合?
O ( n ln n ) O(n \ln n) O ( n ln n ) 枚举倍数的方法对每个权值处理出包含它所有约数的vector
。然后枚举每个点将它扔到其权值的约数的vector
里。
即:ver[i]
表示所有权值是 i i i 的倍数的节点的集合,pr[i]
表示 i i i 的约数集合。
1 2 for (rint i = 1 , j; i <= m; i++) for (j = i; j <= m; pr[j].push_back(i), j += i);for (rint i = 1 ; i <= n; i++) for (auto j:pr[a[i]]) ver[j].push_back(i);
问题 2 2 2 : 首先需要构建虚森林的连通块,怎么连边?
现在要将所有是 d d d 的倍数的节点中在原树上相邻的点之间连边。暴力枚举两个是 d d d 的倍数的节点复杂度是平方的。如果直接枚举边的话复杂度是 O ( n ) O(n) O ( n ) 而不是 O ( s z ) O(sz) O ( s z ) 的,均摊复杂度不太对。可以将所有是 d d d 的倍数的节点标记为true
,然后再枚举这些点的父亲判断是否直接相邻。
即:
1 2 for (auto v:ver[d]) book[v] = true , e[v].clear();for (auto v:ver[d]) if (book[fa[v]]) e[v].push_back(fa[v]), e[fa[v]].push_back(v);
问题 3 3 3 : 怎么求直径
随你便。对虚森林的每个连通块做两遍 D F S / B F S DFS/BFS D F S / B F S ,树上 D P DP D P ,点集合并…
这样对于每一个大小为 s z sz s z 的虚森林复杂度都是 O ( s z ) O(sz) O ( s z ) 的,那么 O ( ∑ s z ) O(\sum sz) O ( ∑ s z ) 是多少呢?
一个数 a i a_i a i 最多有 O ( a i ) O(\sqrt{a_i}) O ( a i ) 个约数。最坏情况下每个数都是那个约数最多的数,即每个都会被加入 O ( m ) O(\sqrt m) O ( m ) 个虚森林,复杂度 O ( n m ) O(n \sqrt m) O ( n m ) 。
貌似有点慢。但是注意到如果所有数都是 2 d 2d 2 d 的倍数,那么所有数也都是 d d d 的倍数,而且 2 d 2d 2 d 的虚森林一定是 d d d 的子集,一定不优。那么在枚举 G C D GCD G C D 的时候,如果枚举过 d d d ,那么就不需要枚举 2 d , 3 d , 4 d , . . . 2d,3d,4d,... 2 d , 3 d , 4 d , . . . 了。实际上,只需要枚举所有的质数 d d d 使得 G C D = d GCD = d G C D = d 就可以了。
复杂度 O ( n log m ) O(n \log m) O ( n log m ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> using namespace std ;#define MAXN 200000 #define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}vector <int > e[MAXN+5 ], pr[MAXN+5 ], ver[MAXN+5 ]; bool book[MAXN+5 ]; int a[MAXN+5 ], fa[MAXN+5 ], n, m, D, V, ans;void Far (int p, int fa, int t) {book[p] = false ; D<t?D=t,V=p:0 ; for (auto v:e[p]) if (v^fa) Far(v,p,t+1 );}void DFS (int p) {for (auto v:e[p]) if (v^fa[p]) fa[v] = p, DFS(v);}int main () { n = rf(); generate(a+1 ,a+n+1 ,rf); m = *max_element(a+1 ,a+n+1 ); for (rint i = 2 , j; i <= m; i++) if (!book[i]) for (j = i; j <= m; book[j] = true , pr[j].push_back(i), j += i); for (rint i = 2 , u, v; i <= n; u = rf(), v = rf(), e[u].push_back(v), e[v].push_back(u), i++); for (rint i = 1 ; i <= n; i++) for (auto j:pr[a[i]]) ver[j].push_back(i); DFS(1 ); memset (book,0 ,m); for (rint i = 2 ; i <= m; i++) if (ver[i].size()) { for (auto v:ver[i]) book[v] = true , e[v].clear(); for (auto v:ver[i]) if (book[fa[v]]) e[v].push_back(fa[v]), e[fa[v]].push_back(v); for (auto v:ver[i]) if (book[v]) D = 1 , V = v, Far(v,v,1 ), Far(V,V,1 ), ans = max(ans,D); } printf ("%d\n" ,ans); return 0 ; }
题目大意: 每次插入一个长方形 x i × y i x_i \times y_i x i × y i 或查询现在所有的长方形能否经过旋转(即可以选择 x i × y i x_i \times y_i x i × y i 或者 y i × x i y_i \times x_i y i × x i )后都 放入一个 h i × w i h_i \times w_i h i × w i 的盒子里。 n ≤ 5 × 1 0 5 , x i , y i , h i , w i ≤ 1 0 9 n \le 5 \times 10^5, x_i, y_i, h_i, w_i \le 10^9 n ≤ 5 × 1 0 5 , x i , y i , h i , w i ≤ 1 0 9 。
换位思考,对于每个长方形 x i × y i x_i \times y_i x i × y i ,判断其能被放入哪些盒子里。那么将每个长方形和盒子当做二维平面上的点。
长方形 x i × y i x_i \times y_i x i × y i 能放入盒子 h i × w i h_i \times w_i h i × w i ⇔ \Leftrightarrow ⇔ ( ( x i ≤ h i ) a n d ( y i ≤ w i ) ) o r ( ( x i ≤ w i ) a n d ( y i ≤ h i ) ) \left((x_i \le h_i) \;and\; (y_i \le w_i)\right) \;or\; \left((x_i \le w_i) \;and\; (y_i \le h_i)\right) ( ( x i ≤ h i ) a n d ( y i ≤ w i ) ) o r ( ( x i ≤ w i ) a n d ( y i ≤ h i ) ) 。
表示成一个线性规划约束条件 平面图形就是两个关于 y = x y = x y = x 的矩形的并。
即一个 L L L 字形,显然一个 L L L 字形由一个 ( x , y ) , 其 中 x ≤ y (x,y),其中 x \le y ( x , y ) , 其 中 x ≤ y 唯一确定。
再插入一个点,就相当于求两个 L L L 字形的交,还是一个 L L L 字形。所以我们只需要每次插入一个点,维护这个 L L L 字形。
具体操作起来发现维护的方法就是: 对于每个 ( x i , y i ) (x_i,y_i) ( x i , y i ) 交换使得保证 x i ≤ y i x_i \le y_i x i ≤ y i ,然后记录所有 x x x 的最大值和 y y y 的最大值,然后把 h h h 和 w w w 同 x x x 和 y y y 比较,最小值比最小值,最大值比最大值。(这是因为上图中的平面图形关于 y = x y = x y = x 对称)。
复杂度 O ( n ) O(n) O ( n ) 。
1 2 3 4 5 6 #include <bits/stdc++.h> using namespace std ;#define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}int n, h, w, x, y; char o[2 ]; int main () {for (n = rf(); n--; scanf ("%s" ,o),h=rf(),w=rf(),o[0 ]^'+' ?puts ((x<=h&&y<=w)||(x<=w&&y<=h)?"YES" :"NO" ):(h>w?h^=w^=h^=w:0 ,x=max(x,h),y=max(y,w))); return 0 ;}
这水得不能再水了
题目大意: 给定一维数轴上 n n n 个点,有 m m m 次行走: 从 s i s_i s i 点走到 f i f_i f i ,中间可以休息 r i r_i r i 次(当然只能在某个点上休息),每走 1 1 1 单位距离消耗体力 c i c_i c i 。求最小化 所有行走中不休息连续走 的一段路的最大体力消耗 的 V V V 。 n ≤ 400 , m ≤ 2.5 × 1 0 5 , a i ≤ 1 0 9 n \le 400, m \le 2.5 \times 10^5, a_i \le 10^9 n ≤ 4 0 0 , m ≤ 2 . 5 × 1 0 5 , a i ≤ 1 0 9 。
题目挺绕的,就是说每次给你一个区间的数,把它划分为不超过 r i + 1 r_i+1 r i + 1 段,最小化最大长度。
一般"最大值最小"都是二分答案,比如说考虑: f V [ l ] [ r ] f_V[l][r] f V [ l ] [ r ] 表示从 l l l 到 r r r 不允许走超过 V V V 的一段路,最少可以分为多少段。但这道题有一个 c i c_i c i ,使得每一次行走都不一样,不能直接二分答案。
那就反过来, f [ k ] [ l ] [ r ] f[k][l][r] f [ k ] [ l ] [ r ] 表示从 l l l 到 r r r 走不超过 k k k 段路,最大路程 的最小值。显然就有了一个 O ( n 4 + m ) O(n^4+m) O ( n 4 + m ) 的做法。
f [ k ] [ l ] [ r ] = min l < i ≤ r { max ( d i s l , i , f [ k − 1 ] [ i ] [ r ] ) } V = max 1 ≤ i ≤ m { c i ⋅ f [ r i + 1 ] [ s i ] [ f i ] } f[k][l][r] = \min_{l \lt i \le r} \lbrace \max(dis_{l,i},f[k-1][i][r]) \rbrace\\
V = \max_{1 \le i \le m} \lbrace c_i \cdot f[r_i+1][s_i][f_i] \rbrace
f [ k ] [ l ] [ r ] = l < i ≤ r min { max ( d i s l , i , f [ k − 1 ] [ i ] [ r ] ) } V = 1 ≤ i ≤ m max { c i ⋅ f [ r i + 1 ] [ s i ] [ f i ] }
空间复杂度 O ( n 3 ) O(n^3) O ( n 3 ) 恰恰好超出 256 M B 256MB 2 5 6 M B 一点点。可以滚动数组,把 k k k 这一维滚动掉(那么在回答询问的时候就要把所有的行走按照 D P DP D P 顺序排序以后一个指针扫描,我一般比较习惯按照 ( k , r − l , l ) (k,r-l,l) ( k , r − l , l ) 这个顺序排序,详见代码)。
时间复杂度 O ( n 4 ) O(n^4) O ( n 4 ) ,不过这样一个式子好像很典型,随便一个优化就行。
高三退役狗已经不怎么会选择/证明 D P DP D P 优化了。
单调性优化或者四边形不等式优化都行(感觉这俩本质几乎相同)。复杂度 O ( n 3 + m ) O(n^3+m) O ( n 3 + m ) 。
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 #include <bits/stdc++.h> using namespace std ;#define SZ 656100 #define ll long long #define f(k,i,j) f[(k)&1][i][j] #define s(k,i,j) s[(k)&1][i][j] #define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}int n, m, p = 1 , a[405 ], f[2 ][405 ][405 ], s[2 ][405 ][405 ]; ll V; struct Q {int s,f,c,r;}q[250005 ];inline bool operator < (const Q &a, const Q &b){return a.r^b.r?a.r<b.r:a.f-a.s==b.f-b.s?a.s<b.s:a.f-a.s<b.f-b.s;}int main () { n = rf(); m = rf(); generate(a+1 ,a+n+1 ,rf); for (rint l = 1 , r; l <= n; l++) for (r = l; r <= n; f(1 ,l,r) = a[r]-a[l], s(1 ,l,r) = r, r++); for (rint i = 1 ; i <= m; q[i].s = rf(), q[i].f = rf(), q[i].c = rf(), q[i].r = min(rf()+1 ,q[i].f-q[i].s), i++); sort(q+1 ,q+m+1 ); for (; p <= m && q[p].r == 1 ; V = max(V,1l l*f(1 ,q[p].s,q[p].f)*q[p].c), p++); for (rint k = 2 , d, l, r, i; k <= n; k++) { memset (f[k&1 ],0x3f ,SZ); for (i = 1 ; i <= n; f(k,i,i) = 0 , s(k,i,i) = i, i++); for (d = 2 ; d <= n; d++) for (l = 1 , r = d; r <= n; l++, r++) { int &_ = f(k,l,r), t; for (i = s(k,l,r-1 ); i <= s(k,l+1 ,r); t = max(a[i]-a[l],f(k-1 ,i,r)), _>t?_=t,s(k,l,r)=i:0 , i++); for (; p <= m && q[p].r == k && q[p].s == l && q[p].f == r; V = max(V,1l l*_*q[p].c), p++); } } printf ("%I64d\n" ,V); return 0 ; }
题目大意: 给定 n n n 个数,将它们划分 成尽可能多的线段,要求不存在一种方法选择若干(非 0 0 0 )个线段使得这些线段所包含的数字的异或和为 0 0 0 。
乱搞选手基本素养: 虽然完全不知道这道题要干什么,但是一看就是个乱搞找规律好题。
第一反应: 没思路。为啥会有 − 1 -1 − 1 ?只要不是所有数异或和为 0 0 0 的话总能分成至少 1 1 1 组,所以 − 1 -1 − 1 只有这一种情况。
第二反应: D P DP D P 一下试试?
第三反应: 首先一看到异或和为 0 0 0 就想到线性基和极大线性无关组。
第四反应: D P DP D P 维护极大线性无关组?
第五反应: 观察一下答案和极大线性无关组有啥关系?
第六反应: 手玩一下发现答案和数字的顺序没有关系。
做完了。
我也不知道为啥,反正看上去答案就是极大线性无关组( − 1 -1 − 1 特判,不然样例都过不去)。
交上去就过了。
看了一下题解,也很容易证明:
求一下异或前缀和,选择 x x x 个线段就等价于选择 x x x 个右端点。因此问题就相当于选择尽可能多个右端点异或和不为 0 0 0 。这不就是极大线性无关组的定义么?
以后遇到异或问题还要注意多想想前缀和。
顺带复习一行线性基。 O ( n log A ) O(n \log A) O ( n log A ) 。
1 2 3 4 5 6 #include <bits/stdc++.h> using namespace std ;#define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}int B[32 ], S[200005 ], n; inline void Ins (int x) {for (rint i = 31 ; ~i && x; i--) if (x>>i&1 ){if (!B[i]){B[i] = x; return ;} x ^= B[i];}}int main () {n = rf(); generate(S+1 ,S+n+1 ,rf); for (rint i = 1 ; i <= n; S[i] ^= S[i-1 ], Ins(S[i]), i++); printf ("%d\n" ,S[n]?32 -count(B,B+32 ,0 ):-1 ); return 0 ;}
扫描二维码即可在手机上查看这篇文章,或者转发二维码来分享这篇文章: