高产更新。老年退役选手Div.2也还是可以玩得很开心的。
题目大意: $q$ 组询问给定 $l,d,r$ ，每组询问输出最小的 $x$ 满足 $d|x$ 且 $x\notin [l,r]$ 。 $q \le 500, 1 \le l,r,d \le 10^9$ 。
如果 $d \lt l$ 那么答案就是 $d$ ，否则就是 $(\lfloor\frac{r}{d}\rfloor+1)d$ 。 $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$ 求其一个最长的形如[:||||||:]的子序列其中|可以有 $0$ 至若干个。 $\lvert s \rvert \le 5 \times 10^5$ 。
贪心选择最靠左的[右面最靠左的:，选择最靠右的]左面最靠右的:，两个:中间的|全要。注意判断无解。 $O(\lvert s \rvert)$ 。
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$ 组询问每次给出 $n$ 个线段，求将线段分成两个非空 集合的方案，使得不属于同一个集合的线段不相交，或输出无解。 $l_i,r_i,T,\sum n \le 10^5$ 。
这……不是只需要把相交的线段都分到一组就好了？不过如果所有线段都相交(不要求两两相交，就是线段的并是同一个线段)就不行了。 $O((\sum n) \log (\sum 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$ 个点带权值的树，求一条最长的路径使得路径上所有点(包括端点)的 $GCD > 1$ 。 $n,a_i \le 2 \times 10^5$ 。
老年退役OIer基本素养: 看到 $a_i \le 2 \times 10^5$ 这题绝对和这个复杂度有关系。(凡是涉及树上 $GCD$ 的问题权值有范围一定要利用权值范围。)
为方便起见记 $m = \max \lbrace a_i \rbrace$ 。
一般这种题的套路就是枚举约数求虚树: 枚举 $GCD = d$ ，把所有是 $d$ 的倍数的节点都拿出来建一个虚树(虚森林)，然后在这上面当做一个不涉及数论的纯树上问题去做。
这道题按照这个套路来，建出虚森林以后就是求直径。对于每一个大小为 $sz$ 的虚森林。
问题 $1$ : 如何预处理”所有权值是 $d$ 的倍数的节点”的集合？
$O(n \ln n)$ 枚举倍数的方法对每个权值处理出包含它所有约数的vector。然后枚举每个点将它扔到其权值的约数的vector里。
即：ver[i]表示所有权值是 $i$ 的倍数的节点的集合，pr[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$ : 首先需要构建虚森林的连通块，怎么连边？
现在要将所有是 $d$ 的倍数的节点中在原树上相邻的点之间连边。暴力枚举两个是 $d$ 的倍数的节点复杂度是平方的。如果直接枚举边的话复杂度是 $O(n)$ 而不是 $O(sz)$ 的，均摊复杂度不太对。可以将所有是 $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$ : 怎么求直径
随你便。对虚森林的每个连通块做两遍 $DFS/BFS$ ，树上 $DP$ ，点集合并……
这样对于每一个大小为 $sz$ 的虚森林复杂度都是 $O(sz)$ 的，那么 $O(\sum sz)$ 是多少呢？
一个数 $a_i$ 最多有 $O(\sqrt{a_i})$ 个约数。最坏情况下每个数都是那个约数最多的数，即每个都会被加入 $O(\sqrt m)$ 个虚森林，复杂度 $O(n \sqrt m)$ 。
貌似有点慢。但是注意到如果所有数都是 $2d$ 的倍数，那么所有数也都是 $d$ 的倍数，而且 $2d$ 的虚森林一定是 $d$ 的子集，一定不优。那么在枚举 $GCD$ 的时候，如果枚举过 $d$ ，那么就不需要枚举 $2d,3d,4d,…$ 了。实际上，只需要枚举所有的质数 $d$ 使得 $GCD = d$ 就可以了。
复杂度 $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) 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 \times y_i$ 或查询现在所有的长方形能否经过旋转(即可以选择 $x_i \times y_i$ 或者 $y_i \times x_i$)后都 放入一个 $h_i \times w_i$ 的盒子里。 $n \le 5 \times 10^5, x_i, y_i, h_i, w_i \le 10^9$ 。
换位思考，对于每个长方形 $x_i \times y_i$ ，判断其能被放入哪些盒子里。那么将每个长方形和盒子当做二维平面上的点。
长方形 $x_i \times y_i$ 能放入盒子 $h_i \times w_i$ $\Leftrightarrow$ $\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)$ 。
表示成一个线性规划约束条件平面图形就是两个关于 $y = x$ 的矩形的并。
即一个 $L$ 字形，显然一个 $L$ 字形由一个 $(x,y),其中 x \le y$ 唯一确定。
再插入一个点，就相当于求两个 $L$ 字形的交，还是一个 $L$ 字形。所以我们只需要每次插入一个点，维护这个 $L$ 字形。
具体操作起来发现维护的方法就是: 对于每个 $(x_i,y_i)$ 交换使得保证 $x_i \le y_i$ ，然后记录所有 $x$ 的最大值和 $y$ 的最大值，然后把 $h$ 和 $w$ 同 $x$ 和 $y$ 比较，最小值比最小值，最大值比最大值。(这是因为上图中的平面图形关于 $y = x$ 对称)。
复杂度 $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$ 个点，有 $m$ 次行走: 从 $s_i$ 点走到 $f_i$ ，中间可以休息 $r_i$ 次(当然只能在某个点上休息)，每走 $1$ 单位距离消耗体力 $c_i$ 。求最小化 所有行走中不休息连续走 的一段路的最大体力消耗 的 $V$ 。 $n \le 400, m \le 2.5 \times 10^5, a_i \le 10^9$ 。
题目挺绕的，就是说每次给你一个区间的数，把它划分为不超过 $r_i+1$ 段，最小化最大长度。
一般”最大值最小”都是二分答案，比如说考虑: $f_V[l][r]$ 表示从 $l$ 到 $r$ 不允许走超过 $V$ 的一段路，最少可以分为多少段。但这道题有一个 $c_i$ ，使得每一次行走都不一样，不能直接二分答案。
那就反过来， $f[k][l][r]$ 表示从 $l$ 到 $r$ 走不超过 $k$ 段路，最大路程 的最小值。显然就有了一个 $O(n^4+m)$ 的做法。
空间复杂度 $O(n^3)$ 恰恰好超出 $256MB$ 一点点。可以滚动数组，把 $k$ 这一维滚动掉(那么在回答询问的时候就要把所有的行走按照 $DP$ 顺序排序以后一个指针扫描，我一般比较习惯按照 $(k,r-l,l)$ 这个顺序排序，详见代码)。
时间复杂度 $O(n^4)$ ，不过这样一个式子好像很典型，随便一个优化就行。
高三退役狗已经不怎么会选择/证明 $DP$ 优化了。
单调性优化或者四边形不等式优化都行(感觉这俩本质几乎相同)。复杂度 $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$ 个数，将它们划分 成尽可能多的线段，要求不存在一种方法选择若干(非 $0$ )个线段使得这些线段所包含的数字的异或和为 $0$ 。
乱搞选手基本素养: 虽然完全不知道这道题要干什么，但是一看就是个乱搞找规律好题。
第一反应: 没思路。为啥会有 $-1$ ？只要不是所有数异或和为 $0$ 的话总能分成至少 $1$ 组，所以 $-1$ 只有这一种情况。
第二反应: $DP$ 一下试试？
第三反应: 首先一看到异或和为 $0$ 就想到线性基和极大线性无关组。
第四反应: $DP$ 维护极大线性无关组？
第五反应: 观察一下答案和极大线性无关组有啥关系？
第六反应: 手玩一下发现答案和数字的顺序没有关系。
做完了。
我也不知道为啥，反正看上去答案就是极大线性无关组( $-1$ 特判，不然样例都过不去)。
交上去就过了。
看了一下题解，也很容易证明:
求一下异或前缀和，选择 $x$ 个线段就等价于选择 $x$ 个右端点。因此问题就相当于选择尽可能多个右端点异或和不为 $0$ 。这不就是极大线性无关组的定义么？
以后遇到异或问题还要注意多想想前缀和。
顺带复习一行线性基。 $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 () 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 ;}
扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章:
