Educational Codeforces Round 58 做题题解

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


Codeforces 1101A Minimum Integer

题目大意: qq 组询问给定 l,d,rl,d,r ,每组询问输出最小的 xx 满足 dxd|xx[l,r]x\notin [l,r]q500,1l,r,d109q \le 500, 1 \le l,r,d \le 10^9


如果 d<ld \lt l 那么答案就是 dd ,否则就是 (rd+1)d(\lfloor\frac{r}{d}\rfloor+1)dO(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;}

Codeforces 1101B Accordion

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


贪心选择最靠左的[右面最靠左的:,选择最靠右的]左面最靠右的:,两个:中间的|全要。注意判断无解。 O(s)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?


Codeforces 1101C Division and Union

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


这…不是只需要把相交的线段都分到一组就好了?不过如果所有线段都相交(不要求两两相交,就是线段的并是同一个线段)就不行了。 O((n)log(n))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;
}

Codeforces 1101D GCD Counting

题目大意: 给定 nn​ 个点带权值的树,求一条最长的路径使得路径上所有点(包括端点)的 GCD>1GCD > 1​n,ai2×105n,a_i \le 2 \times 10^5​


老年退役OIer基本素养: 看到 ai2×105a_i \le 2 \times 10^5 这题绝对和这个复杂度有关系。(凡是涉及树上 GCDGCD 的问题权值有范围一定要利用权值范围。)

为方便起见记 m=max{ai}m = \max \lbrace a_i \rbrace

一般这种题的套路就是枚举约数求虚树: 枚举 GCD=dGCD = d ,把所有是 dd 的倍数的节点都拿出来建一个虚树(虚森林),然后在这上面当做一个不涉及数论的纯树上问题去做。

这道题按照这个套路来,建出虚森林以后就是求直径。对于每一个大小为 szsz​ 的虚森林。

  • 问题 11 : 如何预处理"所有权值是 dd 的倍数的节点"的集合?

    O(nlnn)O(n \ln n) 枚举倍数的方法对每个权值处理出包含它所有约数的vector。然后枚举每个点将它扔到其权值的约数的vector里。

    即:ver[i]表示所有权值是 ii​ 的倍数的节点的集合,pr[i]表示 ii​ 的约数集合。

    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);
  • 问题 22 : 首先需要构建虚森林的连通块,怎么连边?

    现在要将所有是 dd 的倍数的节点中在原树上相邻的点之间连边。暴力枚举两个是 dd 的倍数的节点复杂度是平方的。如果直接枚举边的话复杂度是 O(n)O(n) 而不是 O(sz)O(sz) 的,均摊复杂度不太对。可以将所有是 dd 的倍数的节点标记为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);
  • 问题 33 : 怎么求直径

    随你便。对虚森林的每个连通块做两遍 DFS/BFSDFS/BFS ,树上 DPDP ,点集合并…

这样对于每一个大小为 szsz 的虚森林复杂度都是 O(sz)O(sz) 的,那么 O(sz)O(\sum sz)​ 是多少呢?

一个数 aia_i 最多有 O(ai)O(\sqrt{a_i}) 个约数。最坏情况下每个数都是那个约数最多的数,即每个都会被加入 O(m)O(\sqrt m) 个虚森林,复杂度 O(nm)O(n \sqrt m)

貌似有点慢。但是注意到如果所有数都是 2d2d 的倍数,那么所有数也都是 dd 的倍数,而且 2d2d 的虚森林一定是 dd 的子集,一定不优。那么在枚举 GCDGCD 的时候,如果枚举过 dd ,那么就不需要枚举 2d,3d,4d,...2d,3d,4d,... 了。实际上,只需要枚举所有的质数 dd 使得 GCD=dGCD = d​ 就可以了。

复杂度 O(nlogm)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;
}

Codeforces 1101E Polycarp’s New Job

题目大意: 每次插入一个长方形 xi×yix_i \times y_i 或查询现在所有的长方形能否经过旋转(即可以选择 xi×yix_i \times y_i 或者 yi×xiy_i \times x_i)后放入一个 hi×wih_i \times w_i 的盒子里。 n5×105,xi,yi,hi,wi109n \le 5 \times 10^5, x_i, y_i, h_i, w_i \le 10^9


换位思考,对于每个长方形 xi×yix_i \times y_i​ ,判断其能被放入哪些盒子里。那么将每个长方形和盒子当做二维平面上的点。

长方形 xi×yix_i \times y_i 能放入盒子 hi×wih_i \times w_i \Leftrightarrow ((xihi)  and  (yiwi))  or  ((xiwi)  and  (yihi))\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=xy = x 的矩形的并。

即一个 LL 字形,显然一个 LL 字形由一个 (x,y),xy(x,y),其中 x \le y 唯一确定。

再插入一个点,就相当于求两个 LL 字形的交,还是一个 LL 字形。所以我们只需要每次插入一个点,维护这个 LL 字形。

具体操作起来发现维护的方法就是: 对于每个 (xi,yi)(x_i,y_i) 交换使得保证 xiyix_i \le y_i ,然后记录所有 xx 的最大值和 yy 的最大值,然后把 hhwwxxyy 比较,最小值比最小值,最大值比最大值。(这是因为上图中的平面图形关于 y=xy = x 对称)。

复杂度 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;}

这水得不能再水了


Codeforces 1101F Trucks and Cities

题目大意: 给定一维数轴上 nn 个点,有 mm 次行走: 从 sis_i 点走到 fif_i ,中间可以休息 rir_i 次(当然只能在某个点上休息),每走 11 单位距离消耗体力 cic_i 。求最小化所有行走中不休息连续走的一段路的最大体力消耗VVn400,m2.5×105,ai109n \le 400, m \le 2.5 \times 10^5, a_i \le 10^9


题目挺绕的,就是说每次给你一个区间的数,把它划分为不超过 ri+1r_i+1 段,最小化最大长度。

一般"最大值最小"都是二分答案,比如说考虑: fV[l][r]f_V[l][r] 表示从 llrr 不允许走超过 VV 的一段路,最少可以分为多少段。但这道题有一个 cic_i​ ,使得每一次行走都不一样,不能直接二分答案。

那就反过来, f[k][l][r]f[k][l][r] 表示从 llrr 走不超过 kk 段路,最大路程的最小值。显然就有了一个 O(n4+m)O(n^4+m) 的做法。

f[k][l][r]=minl<ir{max(disl,i,f[k1][i][r])}V=max1im{cif[ri+1][si][fi]}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(n3)O(n^3) 恰恰好超出 256MB256MB 一点点。可以滚动数组,把 kk 这一维滚动掉(那么在回答询问的时候就要把所有的行走按照 DPDP 顺序排序以后一个指针扫描,我一般比较习惯按照 (k,rl,l)(k,r-l,l) 这个顺序排序,详见代码)。

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

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

单调性优化或者四边形不等式优化都行(感觉这俩本质几乎相同)。复杂度 O(n3+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,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

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


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

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

第二反应: DPDP 一下试试?

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

第四反应: DPDP 维护极大线性无关组?

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

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

做完了。

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

交上去就过了。


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

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

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

顺带复习一行线性基。 O(nlogA)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;}

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


文章作者: Magolor
文章链接: https://magolor.cn/2019/01/31/2019-01-31-blog-01/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Magolor
扫描二维码在手机上查看或转发二维码以分享Magolor的博客