Educational Codeforces Round 58 做题题解

高产更新。老年退役选手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)$ 。

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

题目大意: 给定一个字符串 $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?


Codeforces 1101C Division and Union

题目大意: $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;
}


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​$ 的约数集合。

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

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

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

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的博客