高产更新。老年退役选手Div.2也还是可以玩得很开心的。

Codeforces 1101A Minimum Integer

题目大意: $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)$ 。

#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;}

Codeforces 1101B Accordion

题目大意: 给定一个字符串 $s​$ 求其一个最长的形如[:||||||:]的子序列其中|可以有 $0​$ 至若干个。 $\lvert s \rvert \le 5 \times 10^5​$ 。

贪心选择最靠左的[右面最靠左的:，选择最靠右的]左面最靠右的:，两个:中间的|全要。注意判断无解。 $O(\lvert s \rvert)​$ 。

#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？

Codeforces 1101C Division and Union

题目大意: $T$ 组询问每次给出 $n$ 个线段，求将线段分成两个非空集合的方案，使得不属于同一个集合的线段不相交，或输出无解。 $l_i,r_i,T,\sum n \le 10^5$ 。

这…不是只需要把相交的线段都分到一组就好了？不过如果所有线段都相交(不要求两两相交，就是线段的并是同一个线段)就不行了。 $O((\sum n) \log (\sum n))$ ，复杂度的瓶颈在于排序。

#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;
}

Codeforces 1101D GCD Counting

题目大意: 给定 $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​$ 的约数集合。

  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，然后再枚举这些点的父亲判断是否直接相邻。

  即：

  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)$ 。

#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;
}

Codeforces 1101E Polycarp’s New Job

题目大意: 每次插入一个长方形 $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)$ 。

#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;}

这水得不能再水了

Codeforces 1101F Trucks and Cities

题目大意: 给定一维数轴上 $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)$ 的做法。

$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$

空间复杂度 $O(n^3)$ 恰恰好超出 $256MB$ 一点点。可以滚动数组，把 $k$ 这一维滚动掉(那么在回答询问的时候就要把所有的行走按照 $DP$ 顺序排序以后一个指针扫描，我一般比较习惯按照 $(k,r-l,l)$ 这个顺序排序，详见代码)。

时间复杂度 $O(n^4)​$ ，不过这样一个式子好像很典型，随便一个优化就行。

高三退役狗已经不怎么会选择/证明 $DP$ 优化了。

单调性优化或者四边形不等式优化都行(感觉这俩本质几乎相同)。复杂度 $O(n^3+m)​$ 。

#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,1ll*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,1ll*_*q[p].c), p++);
        }
    }   printf("%I64d\n",V); return 0;
}

Codeforces 1101G (Zero XOR Subset)-less

题目大意: 给定 $n$ 个数，将它们划分成尽可能多的线段，要求不存在一种方法选择若干(非 $0$ )个线段使得这些线段所包含的数字的异或和为 $0$ 。

乱搞选手基本素养: 虽然完全不知道这道题要干什么，但是一看就是个乱搞找规律好题。

第一反应: 没思路。为啥会有 $-1​$ ？只要不是所有数异或和为 $0​$ 的话总能分成至少 $1​$ 组，所以 $-1​$ 只有这一种情况。

第二反应: $DP$ 一下试试？

第三反应: 首先一看到异或和为 $0$ 就想到线性基和极大线性无关组。

第四反应: $DP$ 维护极大线性无关组？

第五反应: 观察一下答案和极大线性无关组有啥关系？

第六反应: 手玩一下发现答案和数字的顺序没有关系。

做完了。

我也不知道为啥，反正看上去答案就是极大线性无关组( $-1$ 特判，不然样例都过不去)。

交上去就过了。

看了一下题解，也很容易证明:

求一下异或前缀和，选择 $x$ 个线段就等价于选择 $x$ 个右端点。因此问题就相当于选择尽可能多个右端点异或和不为 $0$ 。这不就是极大线性无关组的定义么？

以后遇到异或问题还要注意多想想前缀和。

顺带复习一行线性基。 $O(n \log A)$ 。

#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;}

扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章: