TJOI2015 day2 题解报告

BZOJ上的题号分别为3999,4000,4001;COGS上的题号为1978,1979,1980

[TJOI2015] 旅游 给定一棵树,询问操作为求两点u->v路径上两点a,b,$V_b-V_a$的最大值,要求a距离u较近,b距离v较近。直接用树链剖分来做,维护每个区间的最大值、最小值、左边点减右边点的最大值,右边点减左边点的最大值。似乎用LCT代码量可以少一些,不过感觉自己LCT可能虚掉就去敲树链剖分了。

[TJOI2015] 棋盘 题面有些坑其实是自己傻逼读错题。可以发现如果两个棋子会产生冲突那么距离不会超过一行,s为二进制位表示一行每个点是否被放棋子,$f_i,s$表示第$i$行状态为$s$的方案数,预处理转移方案,用矩阵乘法优化。

[TJOI2015] 概率论 萌帝说可以找规律,但是我还是没有看出来。以下萌帝的做法:用$g_i$表示$i$个点的二叉树有多少种同构方式,用$f_i$表示$i$个点的二叉树所有不同构的树的叶子数量和。接着发现$g$其实是卡特兰数。继续打表,发现$f_i=i*g_{i-1}$。卡特兰数的通项式为$g_i=\frac{\tbinom{2n}{n}}{n+1}$,所以可以得到答案为$\frac{n^2(n+1)}{2n(2n-1)}$。在网上找到了证明,但是没有看懂QAQ 。

做题记录3

4.20

COGS1941. 超牛冠军赛 想了个显然错误的贪心,显然WA了…最小生成树,然后就$O(n^2)$没了。学了prim,似乎COGS的逆天评测机kruskal也不会跪。

COGS1942. 审查 AC自动机,顺便记录每个字符匹配到自动机上那个点,以便删除后可以直接找到对应点。我忽略了一个致命的问题,因为这个会往回退,所以复杂度好像不是$O(n)$。科学的做法应该是记录last[u][c],作为当节点u到试图匹配字符c错误时到哪里可以匹配上,不科学的做法是cheat掉….

BZOJ3218: a + b Problem 神题…网络流。首先连边$(S,i,w_i)$,$(i,T,b_i)$,假设已经获得选择白色和黑色全部收益,再减去最小割就是实际收益。对于点$i$,连边$(i’,i,p_i)$,所有满足题目条件的$j$连边$(j,i’,inf)$。这时最小割要么使得所有$j$都为黑色,要么使得$i$为黑色且扣除$p_i$或者$i$为白色。但是因为边数量是$O(n^2)$的,会T掉,就有特别神的方法:把边像主席树上的边一样连起来。PoPoQQQ的题解,看了他的图我才看懂,我就不画了。

BZOJ3687: 简单题 bitset好神奇。背包dp,记录每个和的数量,再异或起来。发现是异或所以只关注每个和的奇偶性即可。对于模2意义下的加法,相当与异或,可以用bitset加速转移。

BZOJ3688: 折线统计 dp即可。可以发现转移条件可以用树状数组优化,就没有了。


4.21

BZOJ3689: 异或之 对于每个数字寻找在这个数字前面的数字的第k小值。可以利用可持久化trie来寻找。


4.22

BZOJ3694: 最短路 符合题目条件的最短路一定可以只经过一条非树边,枚举每条边,会影响的点一定是该边在树上的路径除去lca。可以用树链剖分,我用的是枚举每个点相邻的边,暴力更新这个点的父亲,栈优化。还有种神做法我没有看懂QAQ。


4.23

BZOJ3695: 滑行 有个叫最速原理的东西, 我似乎没有上过高二,大概就是这样。接着二分第一个入射角即可。注意二分的时候角度的误差不能太大,否则时间的误差会更大。


4.25 省选日

就这样低速行进了三天,浮躁了两天去省选了。省选我似乎跪傻了,真的一天啥都不会写。写一天暴力。结果机器逗比奇怪的使得某些正解谜之T,但是神犇们依然虐场,跪梦迪和夹心。

接下来因为奇怪的原因没有去学校,继续浮躁QAQ。


谢谢夹心共享的HAOI2015题解包


4.29

COGS1962. [HAOI2015]树上染色 大力出奇迹,直接dp复杂度其实是$O(n^2)$,ydc大爷的题解。(我才不会告诉你考场上我写的是30分暴力)


5.1

1964. [HAOI2015]数组游戏 好神奇,讲不详细,直接看题解吧,题解包在上面。证明跳跃次数一样($N/i$一样)时,sg值一样。接着就乱搞了。最后不知道怎么搞的卡时过了,就没再管那比较玄学的复杂度了。

做题记录2

2015-4-13至2015-4-18

颓废了一个星期,我也不知道为什么。

BZOJ1978: [BeiJing2010]取数游戏 game 记$f_i$表示第$i$个数字选择的时候最多选多少个。可以枚举$a_i$的大于$L$的约数$d$,然后记上一个含有$d$的约数为$last[d]$那么显然$f_i=max(f_i,f_{last[d]}+1)$。因为如果从一个$j < last[d]$且$d | a_j$转移,那么一定也可以选择$a_{last[d]}$使得答案更大。每个数字最多有$2\sqrt{n}$个约数,复杂度为$O(n\sqrt{n})$

BZOJ3563: DZY Loves Chinese 首先扔度娘的文言文翻译,接着我看了好久也没有意识到哪里逗比了,后来找到了这个……由于每行数量可以读出,就可以利用$k$知道$lastans$,最后一个没法推就并查集暴力。

BZOJ3569: DZY Loves Chinese II 求出dfs树,去掉一些边不连通,那么去掉的边中一定有一条树边且覆盖这条边的非树边全部被去掉。可以记录每条树边有多少条非树边覆盖,然后再枚举其他边要去掉的边看是否覆盖。判断一条边是否覆盖另一条边,可以断判断覆盖边的端点是否是被覆盖边的儿子和祖先,可以利用dfs是记录的$pre$和$suf$两个时间戳判断。还看到另一种判断方法是高斯消元,感觉比较神,记下了可能以后有用。


BZOJ3561: DZY Loves Math VI 推出来一个奇怪的公式:$\sum_{T=1}^{n}\sum_{d\mid T}d^{d^{mod-2}}T^{2d}\mu(\frac{T}{d}) \sum_{i}^{n/T}\sum_{j}^{m/T}i^dj^d$,然后枚举$d$,预处理出$i^d$,然后枚举$d$的倍数$T$。似乎复杂度是$O(nlog^{2}n)$计算$T^{2d}$的log去不掉。卡时过了没有再管。


BZOJ2668: [cqoi2012]交换棋子 建立三层节点…刚才编辑的时候remarkable蹦了,什么都没了…那就YY吧


BZOJ3683: Falsita 可以先dp预处理出答案。接着发现对于单点修改操作,可以用树链剖分修改父亲:对于主链上的点,每次修改答案变动$(size[u]-size[son[u]])d$,主链就可以预处理出变动值,每次询问求d的和。树状数组即可。而主链间交接的点直接暴力修改。对于子树修改,对父节点的影响相当与单点$dsize[u]$。对儿子的修改,相当于平均值加上$2*d$,可以在dfs序上用树状数组维护。

莫比乌斯反演-笔记

关于莫比乌斯反演,主要摘自策爷的笔记知乎–如何证明莫比乌斯反演

Dirichlet卷积定义:对于数论函数$f$和$g$,他们的卷积为$f*g$为

$$(f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})$$


定义以下函数:

衡为1的常函数$1(n)=1$

恒等函数$id(n)=n$

单位函数$\epsilon(n)=[n=1]$


定义莫比乌斯函数:

当$n=1$时,$\mu(1)=1$。

否则将$n$分解成$p_1^{a_1}p_2^{a_2}…p_k^{a_k}$这样的形式,$p_i$为质数,且$a_i$均为$1$时,则$\mu(n)=(-1)^k$。

其余情况$\mu(n)=0$


可以得到:

$$1*\mu=\sum_{d\mid n}\mu(d)=\epsilon(n)$$

由二项式定理可证,这个用途在于当存在类似$ \epsilon(gcd(i,j))$这样的函数的时候,可转换成$\sum_{d\mid n}\mu(d)$的形式,用于进一步变换。

而且证明莫比乌斯反演时,这是一个关键步骤。


莫比乌斯反演:

$$F(n)=\sum_{d\mid n}f(d) \Rightarrow f(n)=\sum_{d\mid n}\mu(d)F(n/d)$$

其实也可以写成Dirichlet卷积的形势:$F=1*f$,这样更好证明。

$$F=1f \Rightarrow \muF=\mu1f \Rightarrow \mu*F=f$$


然后其实莫比乌斯反演还有另外一种形式:

$$F(n)=\sum_{n\mid d}f(d) \Rightarrow f(n)=\sum_{n\mid d}\mu(\frac{d}{n})F(d)$$

证明:

$$\sum_{n\mid d}\mu(\frac{d}{n})F(d) = \sum_{n\mid d}\mu(\frac{d}{n})\sum_{d\mid m}f(m) =\sum_{n\mid m}f(m)\sum_{d\mid \frac{m}{n}}\mu(d)$$

显然当且仅当$m=n$时$\sum_{d\mid \frac{m}{n}}\mu(d)=1$其余为$0$,所以

$$\sum_{n\mid d}\mu(\frac{d}{n})F(d)=f(n)$$


例题:3529: [Sdoi2014]数表

大意:$Q$个询问,每个询问给出$n,m,a$。有一张$nm$的网格,每个格子$(i,j)$的数字为$gcd(i,j)$的约数和。问格子上的数字小于$a$的数字的和,可离线。$ Q \le 210^4 ,1 \le n,m \le 10^5, a\le10^9$

题解(参考PoPoQQQ的题解):

约定$n \le m$,否则交换即可,不影响解。

用$g(k)$表示网格中数字为$k$的数量,记$n’=\lfloor\frac{n}{k}\rfloor$。

$$\begin{split} g(k) =\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k] =\sum_{i=1}^{n’}\sum_{j=1}^{m’}[gcd(i,j)=1] =\sum_{i=1}^{n’}\sum_{j=1}^{m’}\sum_{d\mid gcd(i,j)}\mu(d)=\sum_{d=1}^{n’}\mu(d)\lfloor\frac{n’}{d}\rfloor\lfloor\frac{m’}{d}\rfloor \end{split} $$

用$f(k)$表示$k$的约数和,枚举每个数的倍数可在$O(nlogn)$时间预处理。

那么显然没有a的限制时

$$ \begin{split} ans=\sum_{k=1}^{n}f(k)g(k)= \sum_{k=1}^{n}f(k)\sum_{d=1}^{n’}\mu(d)\lfloor\frac{n’}{d}\rfloor\lfloor\frac{m’}{d}\rfloor=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k\mid T}f(k)\mu(\frac{T}{k}) \ \end{split} $$

对于最后一步变换是把$T$替换成$dk$。因为$\lfloor\frac{n}{T}\rfloor$最多有$2\sqrt{n}$种结果,记$h(T)=\sum_{k\mid T}f(k)\mu(\frac{T}{k})$,那么预处理出$h$的前缀和就可以在$O(\sqrt{n})$的时间完成一次询问。

因为存在a的限制,所以可以先给询问按照a排序,然后离线处理。对于每个询问,我们把$k \le a$的插入$h$中,因为需要插入,所以$h$用树状数组来维护。

代码:

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int L_N = 1e5 + 10;
int mu[L_N], pr[L_N], pn, not_p[L_N];
struct F
{
int val, id;
bool operator<(const F &f) const
{
return val < f.val;
}
} f[L_N];
struct Query
{
int n, m, a, id;
bool operator<(const Query &q) const
{
return a < q.a;
}
} qs[L_N];
struct TreeArr
{
int a[L_N];
int lowbit(int i) { return i & -i; }
void add(int p, int val)
{
for (; p < L_N; p += lowbit(p))
{
a[p] += val;
}
}
int query(int p)
{
int ret = 0;
for (; p; p -= lowbit(p))
{
ret += a[p];
}
return ret;
}
int query(int l, int r)
{
return query(r) - query(l - 1);
}
} ta;
void pre()
{
mu[1] = 1;
for (int i = 2; i < L_N; i++)
{
if (!not_p[i])
mu[i] = -1, pr[++pn] = i;
for (int j = 1; j <= pn && ipr[j] < L_N; j++)
{
not_p[pr[j] i] = true;
if (i % pr[j] == 0)
{
mu[pr[j] i] = 0;
break;
}
mu[pr[j] i] = -mu[i];
}
}

for (int i = 1; i < L_N; i++)
{
f[i].id = i;
for (int j = i; j < L_N; j += i)
{
f[j].val += i;
}
}
sort(f + 1, f + L_N);
}

void insert(F f)
{
for (int j = f.id; j < L_N; j += f.id)
{
ta.add(j, f.valmu[j / f.id]);
}
}

int sol(int n, int m)
{
if (n > m)
swap(n, m);
int ed = 0, ret = 0;
for (int t = 1; t <= n; t = ed + 1)
{
ed = min(n / (n / t), m / (m / t));
ret += (n / t)(m / t) * ta.query(t, ed);
}
return ret;
}

int ANS[L_N];
int main()
{
//freopen(“in.txt”,”r”,stdin);

pre();

int T;
scanf(“% d”, &T);
for (int i = 1; i <= T; i++)
{
scanf(“% d % d % d”, &qs[i].n, &qs[i].m, &qs[i].a);
qs[i].id = i;
}
sort(qs + 1, qs + 1 + T);

int fn = 1;
for (int i = 1; i <= T; i++)
{
Query &q = qs[i];
while (fn < L_N && f[fn].val <= q.a)
{
insert(f[fn]);
fn++;
}
ANS[q.id] = sol(q.n, q.m);
}

for (int i = 1; i <= T; i++)
{
ANS[i] &= (1 << 31) - 1;
printf(“% d\n“, ANS[i]);
}

return 0;
}