Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

每日做题简要题解

辣真的牛批,啊,辣真的牛批。“WA司马脸,RE司马脸。”你是不是SB啊这种人?“TLE司马脸,MLE司马脸。”,是不是要把题出成两小时个位数人过题你才觉得是一套好题嘛?啊写题的人被你的毒瘤题干了,不做表情,是司马脸吗?

求求你们不要说我是神仙了,我觉得你们才是神仙。你们这些水友嗨粉,你们是水神仙,你们是嗨神仙,你们才是神仙。我是个锤子神仙,我天天被弱智题卡我还神仙。

2021.5.6

CF1516D

首先发现这个东西实际上是让你求划分成多少个区间能让这些区间内的数两两互质。那么接下来继续观察,显然对于每个位置我们可以求出其最大的一个右端点 $f_i$ 表示从 $i$ 到 $f_i$ 之间都是互质的。有了这个 $f_i$ 我们就可以通过倍增拼答案了。

那考虑怎么算这个 $f_i$,怎么求 $f_i$ 就很有说法了,这个东西显然是具有单调性的,所以看到单调性就可以往双指针的方面想。

以前没怎么写过双指针,这次写了下发现很精妙。就你考虑一个数加进去会发生什么,开个桶存一下每个质因子(这边因为 $a_i \leq 10^5$ 质因子很少),如果加进去发现质因子重复了就退出本次的查找过程,否则就继续找。

代码贴一下,感觉这个还是值得记录的

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
26
27
28
29
30
31
32
33
34
35
36
int k = 0;
for (int i = 1;i <= n;++i) {
if (i > 1) {
for (auto x : fac[a[i-1]]) tmp[x]--;
}
while (k <= n) {
//printf("%d %d\n",i,k);
++k;if (k > n) break;
for (auto x : fac[a[k]]) tmp[x]++;
bool flag = 0;
for (auto x : fac[a[k]]) {if (tmp[x] > 1) {flag = 1;break;}}
if (flag) {
for (auto x : fac[a[k]]) tmp[x]--;
break;
}
}
nxt[i][0] = k;--k;
}
//for (int i = 1;i <= n;++i) printf("%d ",nxt[i][0]);
//puts("");
for (int i = 0;i <= t;++i) nxt[n+1][i] = n+1;
for (int i = 1;i <= t;++i) {
for (int j = 1;j <= n;++j) nxt[j][i] = nxt[nxt[j][i-1]][i-1];
}

for (int i = 1;i <= m;++i) {
int l,r;read(l,r);
int ans = 0,now = l;
for (int k = t;k >= 0;--k) {
if (nxt[now][k] <= r) {
now = nxt[now][k];
ans += (1 << k);
}
}
printf("%d\n",ans+1);
}

CF1515E

首先考虑最终答案序列可以表示成一段全部手工,一个自动,然后再一段全部手工。这个是一个蛮重要的思想,以后要注意这种特殊触发的题都可以往这方面去想。

那么先考虑纯手工的部分,比如你现在要把 $1\cdots k$ 全部手工点亮,那么显然你需要让那些本来会被自动点亮的先给他手工点掉。点亮第一个有 $k$ 种选择,那么你第一个点亮的是 $i$,接下来就要把 $i+1 \cdots k$ 点掉,那么 $1 \cdots i-1$ 你就需要倒序点,这个插板法易得是 $\binom{k-1}{i}$,都加起来根据二项式定理就是 $2^{k-1}$

好,那么接下来其实就是一个枚举分割段的经典问题了,结合数据范围也不难想到DP,于是就定义 $f_{i,j}$ 表示 $1\cdots i$ 这段有 $j$ 盏灯是手工点亮的,那么就有初始状态 $f_{i,i} = 2^{i-1}$。接下来我们考虑枚举一个自动点亮的点 $k$,则有 $f_{i,j} = \sum_{k = 1}^{j} f_{i-k-1,j-k} \times 2^{k-1} * \binom{j}{k}$。

这边为什么取了个组合数?因为我们这 $k$ 个位置可以在 $j$ 个位置中选择,代码其实不难写。

CF1515F

这个题无解的情况很简单,我们考虑如果 $x \times (n-1) < \sum a_i$ 那就无解了。但是怎么证明?这里其实是有说法的,而且这里蕴含着本题构造方法。

首先我们肯定要对于一颗生成树来讨论,我们这里直接随机声称一颗:对于一个点 $p$ 来讨论,

  • 如果$a_p \geq x$ 那这里我们可以直接让 $p$ 和它的父亲连起来
  • 如果$a_p < x$,我们可以把 $p$ 去掉,然后在剩下的处理。根据鸽巢原理,肯定是存在一个 $u$ 使 $a_u > x$,那么如果这里 $x \times (n-1) < \sum a_i$ 就无法构造,反之则一定存在一种构造方案。

上面两种讨论暗示了本题的构造方法:对于一个点 $p$,如果$a_p \geq x$ 直接让 $p$ 和它的父亲连起来,反之则先递归到其子树最后再连。

实现很短就贴上来,这题启发对于某些看似显然的定力还是要证明一下会发现很多东西

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
26
27
28
29
30
31
32
33
34
35
36
37
void dfs(int x,int f) {
for (auto e : G[x]) {
int y = e.first,num = e.second;
if (y != f) {
dfs(y,x);
if (a[y] >= lim) {
ans[l++] = num;
a[x] += a[y] - lim;
} else {
ans[r--] = num;
}
}
}
}

signed main() {
read(n,m,lim);
for (int i = 1;i <= n;++i) read(a[i]),f[i] = i,sum += a[i];
if (lim * (n-1) > sum) {
puts("NO");return 0;
}
puts("YES");
for (int i = 1;i <= m;++i) read(u[i],v[i]);
l = 2,r = n;
for (int i = 1;i <= m;++i) {
int x = u[i],y = v[i];
if (find(x) != find(y)) {
G[x].push_back(make_pair(y,i));G[y].push_back(make_pair(x,i));
f[find(x)] = find(y);
}
}
dfs(1,0);
for (int i = 2;i <= n;++i) {
printf("%d\n",ans[i]);
}
return 0;
}

2021.5.7-2021.5.8

CFgym102331B

首先考虑这个题的条件是否可以优化,我们考虑利用 trie 树那一套证明,最小的 $\operatorname{xor}$ 值只可能出现在相邻的两个数上。简要叙述一下,我们现在有三个数 $a,b,c$ 满足 $a < b < c$。那么我们要找与 $a$ 最小的 $\operatorname{xor}$ 值的数,直接考虑若 $c - b \geq x(x = 2^k)$,那么从这一位开始的 $xor$ 值就会变掉。

严格证明(By:jiangly):

那么我们易得一个 dp 方程 $f_i = 1 + \sum_{1 \leq i < j}f_j(a_i \operatorname{xor} a_j \geq x)$

这个东西是 $O(n^2)$,关于 $\operatorname{xor}$ 的东西首先考虑用 0-1 trie 优化。

我们考虑把 $f$ 都叠加在 trie 的某些节点上,然后再求和的时候下功夫。每次求和,我们在 trie 树上跑 $a_i$ $xor$ $a_j$,接下来考虑怎么跑。

设当前在第 $k$ 位,$a_i$ 的第 $k$ 位为 $x_1$,$a_j$ 的第 $k$ 位为 $x_2$,$x$ 第 $k$ 位为 $x_3$。

  • 若 $x_3 = 0$:
    如果此时 $x_1 \operatorname{xor} x_2 = 1$,那么低位来看肯定有 $a_i \operatorname{xor} x_j \geq x$。所以这里 $x_1,x_2$ 就有两种情况,分别讨论掉就可以。直接把整颗子树加进来,接下来就朝着 $x_1 \operatorname{xor} x_2 \operatorname{xor} x_3$ 的方向走,代码长这样:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    if ((lim & (1ll << i))) {
    r = trie[r][(x & (1ll << i)) ^ 1];
    } else {
    if ((x & (1ll << i))) {
    if (trie[r][0]) ans = add(ans,f[trie[r][0]]);
    r = trie[r][1];
    } else {
    if (trie[r][1]) ans = add(ans,f[trie[r][1]]);
    r = trie[r][0];
    }
    }
  • 若 $x_3 = 1$:
    那你这里做什么都不能保证是一定包含的,直接走到 $x_3 \operatorname{xor} 1$ 即可。

trie 写的比较少,这里贴代码,不会的可以问我,被这个题搞了两天

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
const int N = 4e5 + 10;

const ll mod = 998244353;

ll a[N],n,lim,tot,trie[N*70][2],f[N*70],ans;

ll add(ll a,ll b) {return (a % mod + b % mod) % mod;}

void insert(ll x,ll val) {
int r = 0;
for (int i = 60;i >= 0;--i) {
if (x & (1ll << i)) {
if (!trie[r][1]) {
trie[r][1] = ++tot;
f[r] = add(f[r],val);
r = tot;
} else {
f[r] = add(f[r],val);
r = trie[r][1];
}
} else {
if (!trie[r][0]) {
trie[r][0] = ++tot;
f[r] = add(f[r],val);
r = tot;
} else {
f[r] = add(f[r],val);
r = trie[r][0];
}
}
}
f[r] = add(f[r],val);
return ;
}

ll query(ll x) {
int r = 0;
ll ans = 0;
for (int i = 60;i >= 0;--i) {
if ((lim & (1ll << i))) {
r = trie[r][(x & (1ll << i)) ^ 1];
} else {
if ((x & (1ll << i))) {
if (trie[r][0]) ans = add(ans,f[trie[r][0]]);
r = trie[r][1];
} else {
if (trie[r][1]) ans = add(ans,f[trie[r][1]]);
r = trie[r][0];
}
}
if (!r) break;
}
if (r) ans = add(ans,f[r]);
return ans;
}

signed main() {
read(n,lim);
for (int i = 1;i <= n;++i) read(a[i]);
sort(a+1,a+1+n);
for (int i = 1;i <= n;++i) {
ll now = add(1,query(a[i]));
ans = add(ans,now);
insert(a[i],now);
}
printf("%lld\n",ans % mod);
return 0;
}

2020.5.9

P7595 猜树

场上分别研究了下 Sub 4 和 Sub 5。

Sub 4:先用询问 2 求出每个节点的深度,然后暴力枚举它的儿子询问距离。若二元组 (u,v) 距离为 1,且 $dep_v = dep_u+1$, 则 $v$ 在 $u$ 的子树,大力判断一下就行了,时间复杂度是 $O(n)$ 的。

Sub 5:完全二叉树最多只有 logn 层,考虑逐层遍历。先用询问 2 求出每个节点的深度。

之后,对于每个节点,使用询问 1 求出其子树的所有节点。若当前节点为 $u$, 子树中存在某个节点 $v$ 使得 $dep_v = dep_u+1$,则 $v$ 在 $u$ 的子树中,时间复杂度是 $O(n\log n)$ 的。

先用询问 2 求出每个节点的深度。

考虑逐层处理:设定一个闸值 T。若当前层的节点数量 > T,则使用 Sub5 的方法求出父子关系,否则使用 Sub3 的方法求。

输出数量 $O(nT + n^2/T)$,取$T = \sqrt(n)$ 最佳,这种trick 通常叫根号分治。

2020.5.10 - 2020.5.16

2020.5.17

P7594 「EZEC-8」Clear Up

首先先研究一下 $a_i \not ={0}$ 的情况,我们先把操作记为 $(l_1,r_1),(l_2,r_2)$ 显然两个操作的代价分别是 $\frac{l_1 + r_1}{2},\frac{l_2 + r_2}{2}$

可以证明,如果 $(l_1,r_1),(l_2,r_2)$ 有交集,结果肯定不如选 $(\min(l_1,l_2),\max(r_1,r_2))$ 来的优。

简要证明一下:

第一种情况:$(l_2,r_2) \in (l_1,r_1)$ 如图:

这里,选紫色的覆盖方式代价与 $(l_1,r_1),(l_2,r_2)$ 的代价相同,但是可以覆盖到更多的数。

第二种情况:$(l_2,r_2) \notin (l_1,r_1)$

同上。

所以我们不难写出 45 分代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int las,nxt;++n;
for (int i = 1;i <= n;++i) {
if (a[i] && !a[i-1]) {
las = i;
continue;
}
if (!a[i]) {
if (!a[i-1]) continue;
nxt = i - 1;
ll tmp = 0x3f3f3f3f3f3f3f3f;
pre[las] = a[las] - las;suf[nxt] = a[nxt] + nxt;
for (int j = las + 1 ;j <= nxt;++j) pre[j] = max(pre[j-1],a[j] - j);
for (int j = nxt - 1 ;j >= las;--j) suf[j] = max(suf[j+1],a[j] + j);
for (int j = las ;j <= nxt;++j) tmp = min(tmp,max(pre[j] + j,suf[j] - j));
ans += tmp;
}
}

该算法的核心在于找出前缀最大后缀最大,然后选择这个位置。

那么存在 $0$ 的时候,显然整个东西会被分成若干个段,这些段之间选的点可能有交集,所以不能直接算。

但是交集启发我们可以通过判断区间交来合并,我们利用一个栈来完成这个工作,每做完一个非 $0$ 段之后就把区间与栈里的能合并的区间都合并到一起,代码很好写,时间复杂度 $O(n)$。

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
26
27

pii s[N];

int top,n,L,R;
ll ans;

signed main() {
read(n);
for (int i = 1;i <= n;++i) {
int x;read(x);
if (!x) continue;
int l = i - x,r = i + x;
if (l > R) {
s[++top] = make_pair(L,R);
L = l,R = r;
} else {
L = min(L,l),R = max(R,r);
while (L <= s[top].second && top) {
L = min(L,s[top--].first);
}
}
}
s[++top] = make_pair(L,R);
for (int i = 1;i <= top;++i) ans += (ll)(s[i].second - s[i].first + 1) / 2;
printf("%lld\n",ans);
return 0;
}

这种方法里使用的是不同的求非 $0$ 段方法,其实是等价的。

BZOJ3687 简单题

这里