CSP-J/S 2019 游记 & CSP-S 2019 自己的题解

如题。

游记

作为一只参加第一届 CSP-J/S 且在此之前从未参加过 NOIP 提高组的蒟蒻,我感觉自己还是太菜了……

Day -???:

要开始停课了呢。
大概是第一次为了 OI 而停课吧,从前只是远远望着罢了,从未想过自己这么快就要接触到传说中的「停课」了。

集训的日子让我似放松而非放松,似紧张而非紧张;如此一天天过着,每晚回去做做文化课的作业,依然和同班同学们住在一起,大抵也就这样吧。

曾经的同学逐渐也知道了这事,然而总有对「OI」与「停课」抱有刻板印象的人认为「真爽啊」。凡此种种,我都不想多解释了;毕竟「OI」的意义,也不是人人都认识得到,也不是人人的认识都一样吧。

机房没法上洛谷,我都掉蓝了……

Day -4 ~ -3:

周一。
不愿面对的期中考。

最后到这一步了,我还能怎么逃避?
硬着头皮上吧。

果然力不从心了,成绩早已不如从前。
然而另一个一起停课的同学却考到了年级前十?
我果然太菜了啊。

罢了。
我明明是在为 CSP-J/S 备战吧。

Day -2 ~ -1:

这几天文化课那边也比较放松了,基本没啥作业,就当自己是他人的放松中的另类吧。

依然在训练。
被 JZ 的题虐爆了。

Day 0:

今天没有任务了。
文化课那边去研学了。

刷了下天天爱跑步、列队和保卫王国。
就开始颓废了。

这时 P6174 问我要不要面基,我说我在二中考场,他说他和 snakes、codesonic 都在六中考场玩,问我要不要坐地铁。
这是真的没办法啊……

晚上,也总算是出发了吧。
这到底是集训到最后的释怀,还是大敌当前的恐惧?
我无从得知。

到酒店了,本来打算是双人房加个床三人住(我,LHF,ZYM,虽然中间那个人似乎不大愿意)的,服务员说不能加床。
然后问我要不要一个人睡大床房,教练还说只要交一个人的钱。
果断摇头。
(不要问为什么)

Day 1:

自以为「久等了」的却其实是初次面对的 CSP-S,终于让我见了一面么?

考试开始。
看到 T1 题目名大概就知道啥东西了,看了眼题目就秒了。
T2 不知道为什么自然而然地想到了转化成 1/1{1}/{-1} 然后再做,虽然做法没问题,不过好像不是很主流?
T3 没想出来,打了个自以为的 35pts35\text{pts} 的程序滚粗了。

Day1 100+100+35=235100+100+35=235,成功拿到大众分。

下午是 J,本来觉得能好好发挥一把,没想到也崩掉了,似乎乐观估计只有 250250
(此处 Orz LHF 大佬,280280 吊打我,以及一个初一的家伙似乎四题都想到了正解?顺带一提,这两个人的名字缩写都是 LHF)
大概是心态问题吧,反正我的目的是 S。

晚上教练说要请前年我校参加 GDKOI 的同学去吃寿司,于是我就跟去蹭了下。
曾经吃素的我稍微尝试了下鳗鱼吞拿鱼和牛舌之类的,感觉原来没有想象的那么难吃?
拍了张合照(见本人 QQ 空间)。

回到酒店已经快十点了。
睡得还不错吧。

Day 2:

早上可能心态会好点吧。

T1 稍微扫了一眼就没看了,先去看了后面的题(话说土狼家今天的饭是什么鬼)。
T2 看到分段 + 平方下意识想到斜率优化(虽然正解貌似不是),推了一下发现不会做,于是直接写了个 O(n2)O(n^2) 的 DP。
T3……居然没想到统计贡献?暴力滚粗。
回来看 T1,大概降智了居然没想到最多只会有一个这样的食材???
大概是一开题就打算转换模型的后遗症???
针对 m=2,3m=2,3 的数据写了个无聊的暴力。

Day2 64+64+55=18364+64+55=183,成功打满自己想要的暴力分。

吃了午饭就返程了呢……
感觉 418418 不挂分的话应该一等有戏了?
不枉我停课这么多天啊(逃

事实证明 D1T3 有 2525 分假掉了,D2T2 因为空间按着 4×1074\times 10^7 开的于是爆零……
(LHF 大佬和我做法一样,但比我少开一个数组,然后就有那 6464 分了……)

回到学校先回了下宿舍稍微睡了一会。
然后就去教室了。

他们研学的还没回来,还能再浪两天,哈哈。

既然都到了这一步了,大抵也是稍微释怀了吧。
我对于 OI,目的到底是什么呢?
OI 给我的东西那么多,我却把游记写得跟 AFO 似的,是想干什么呢?
再战吧,大抵我也没有发挥出巅峰实力。

Day 5:

暂时回归文化课了啊。
我的 OI 路还很长啊。

班主任问我考得怎么样……
我说我 J 炸 S 海星……
他愣了一下……

题解

格雷码

要么用某著名结论,要么分治。
这题代码就不贴了(其实是不想找)。

括号树

我的做法怎么这么奇异?目前似乎没找到和我一样的……
也是 DP,但是和大多数人的思路不大一样。

首先考虑把 看做 11 看做 1-1,再来考虑一个串合法的充要条件:

  1. 和为 00,即 个数相等。
  2. 任意位置的前缀和非负。

考虑一个序列上的弱化版问题,则易想到设状态 fi,jf_{i,j} 表示ii 结尾,和为 jj,任意位置的前缀和非负的子串个数
若设 aia_i 表示字符串第 ii 位的字符,则有转移

注意到若缩掉第一维,转移相当于将整个状态平移 111-1,并修改部分状态。
由于修改的状态很少,所以可以直接暴力修改。

转回树上,发现只需要支持一个回溯操作。
容易发现只需要记下被修改为 00 的状态原来如何即可。

复杂度是 O(n)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
28
29
30
31
32
33
34
35
#include <cstdio>
using namespace std;
const int N = 5e5;
int n,a[N + 5];
int to[N * 2 + 5],pre[N * 2 + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int _f[N * 3 + 5],*f = _f + N,rot,temp[N + 5];
long long cur,ans;
void dfs(int p)
{
rot += a[p];
a[p] == 1 && (temp[p] = f[-rot],f[-rot] = 0,++f[1 - rot]);
ans ^= p * (cur += f[-rot]);
for(register int i = first[p];i;i = pre[i])
dfs(to[i]);
cur -= f[-rot];
a[p] == 1 && (--f[1 - rot],f[-rot] = temp[p]);
rot -= a[p];
}
int main()
{
scanf("%d",&n);
char ch;
for(register int i = 1;i <= n;++i)
scanf(" %c",&ch),a[i] = ch == '(' ? 1 : -1;
int u;
for(register int i = 2;i <= n;++i)
scanf("%d",&u),add(u,i);
dfs(1);
printf("%lld\n",ans);
}

树上的数

咕咕咕。

Emiya 家今天的饭

注意到出现次数过半的主要食材至多有一种,容斥即可。
枚举这种主要食材为 ss,并设 fi,jf_{i,j} 表示做完了前 ii 种烹饪方式,ss 的出现次数与其它食材的总出现次数的差为 jj 的方案数。

复杂度 O(n2m)O(n^2m)

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
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 100;
const int M = 2000;
const int mod = 998244353;
int n,m;
int a[N + 5][M + 5],sum[N + 5];
int f_[N + 5][N * 2 + 5],*f[N + 5];
int ans = 1;
int main()
{
for(register int i = 0;i < N + 5;++i)
f[i] = f_[i] + N;
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
{
for(register int j = 1;j <= m;++j)
scanf("%d",a[i] + j),sum[i] = (sum[i] + a[i][j]) % mod;
ans = (long long)ans * (sum[i] + 1) % mod;
}
ans = (ans - 1 + mod) % mod;
for(register int i = 1;i <= m;++i)
{
memset(f_,0,sizeof f_),f[0][0] = 1;
for(register int j = 1;j <= n;++j)
for(register int k = -j;k <= j;++k)
f[j][k] = ((f[j - 1][k] + (long long)f[j - 1][k - 1] * a[j][i] % mod) + (long long)f[j - 1][k + 1] * (sum[j] - a[j][i] + mod) % mod) % mod;
for(register int j = 1;j <= n;++j)
ans = (ans - f[n][j] + mod) % mod;
}
printf("%d\n",ans);
}

划分

注意到显然分的越多越好。
故设 fif_i 表示所有 [1,i][1,i] 的最优方案中,ii 所在块的可能最大左端点减一。
再令 si=j=1iajs_i=\sum\limits_{j=1}^i a_j

故显然 fif_i 有单调性(因为 fi1f_{i-1} 一定也满足 fif_i 的条件)。
用单调队列维护即可。
压位高精 / 手写 __int128 统计答案(出题人手写了个 __int116)。

代码:

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
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 4e7;
const int M = 1e5;
int n,type;
int x,y,z,b[N + 5],m;
int p[M + 5],l[M + 5],r[M + 5];
int f[N + 5],q[N + 5],head,tail;
long long sum[N + 5];
struct Bigint
{
static const int w = 1e4;
static const int len = 8;
int a[len];
inline Bigint()
{
memset(a,0,sizeof a);
}
inline Bigint(long long x)
{
memset(a,0,sizeof a);
for(register int i = 0;i < len && x;++i)
a[i] = x % w,x /= w;
}
inline Bigint &operator+=(const Bigint &o)
{
for(register int i = 0,k = 0;i < len;++i)
a[i] += o.a[i] + k,k = a[i] / w,a[i] %= w;
return *this;
}
inline Bigint operator*(const Bigint &o) const
{
Bigint ret;
for(register int i = 0;i < len;++i)
for(register int j = 0,k = 0;j < len;++j)
ret.a[i + j] += a[i] * o.a[j] + k,k = ret.a[i + j] / w,ret.a[i + j] %= w;
return ret;
}
inline void output() const
{
int i = len - 1;
for(;~i && !a[i];--i);
printf("%d",a[i]);
for(--i;~i;--i)
printf("%04d",a[i]);
}
} ans;
int main()
{
scanf("%d%d",&n,&type);
if(!type)
for(register int i = 1;i <= n;++i)
scanf("%lld",sum + i),sum[i] += sum[i - 1];
else
{
scanf("%d%d%d%d%d%d",&x,&y,&z,b + 1,b + 2,&m);
for(register int i = 3;i <= n;++i)
b[i] = x * b[i - 1] + y * b[i - 2] + z & (1 << 30) - 1;
for(register int i = 1;i <= m;++i)
scanf("%d%d%d",p + i,l + i,r + i);
for(register int j = 1;j <= m;++j)
for(register int i = p[j - 1] + 1;i <= p[j];++i)
sum[i] = sum[i - 1] + b[i] % (r[j] - l[j] + 1) + l[j];
}
for(register int i = 1;i <= n;++i)
{
for(;head < tail && 2 * sum[q[head + 1]] - sum[f[q[head + 1]]] <= sum[i];++head);
f[i] = q[head];
for(;head < tail && 2 * sum[q[tail]] - sum[f[q[tail]]] >= 2 * sum[i] - sum[f[i]];--tail);
q[++tail] = i;
}
for(register int i = n;i;i = f[i])
ans += Bigint(sum[i] - sum[f[i]]) * Bigint(sum[i] - sum[f[i]]);
ans.output();
}

树的重心

首先显然可以考虑每个点作为重心的贡献(然鹅我考场没想到)。
则一个点 pp 的贡献应为pp 为根时在以 pp 的某个儿子为根的子树中删去一棵子树并使得 pp 仍为整棵树的重心的方案数
故我们只需要考虑这样的子树个数。

注意到若 pp 为重心,则以 pp 为根时 pp 的重儿子的子树大小不超过 n2\frac n2
sizex\text{size}_x 表示以 pp 为根时以 xx 为根的子树大小。
再设删去的子树的根为 sspp 的重儿子为 wson\text{wson}pp 的次重儿子为 wson\text{wson}'

ss 不在以 pp 的重儿子为根的子树内,则 pp 的重儿子不会改变。
故应满足 sizewsonnsizes2\text{size}_{\text{wson}} \le \frac{n - \text{size}_s}2
解得 sizesn2sizewson\text{size}_s \le n - 2\text{size}_{\text{wson}}

ss 在以 pp 的重儿子为根的子树内,则 pp 的重儿子可能不变,可能会变成原来的次重儿子。
故应满足 sizewsonsizesnsizes2,sizewsonnsizes2\text{size}_{\text{wson}} - \text{size}_s \le \frac{n - \text{size}_s}2,\text{size}_{\text{wson}'} \le \frac{n - \text{size}_s}2
解得 2sizewsonnsizesn2sizewson2\text{size}_{\text{wson}} - n \le \text{size}_s \le n - 2\text{size}_{\text{wson}'}

于是枚举根结点做就做完了(逃

肯定是需要各种奇怪的换根操作的,也就是说要维护以每个点为根时所有子树大小的出现次数。
随便钦定一个根然后就是要分别维护每个点向下的和向上的。
向下的线段树合并。
向上的?可以用总共的减掉向下的。
总共的话,考虑沿一条边从 uuvv,则会减少 sizev\text{size}_v 的贡献,增加 nsizevn - \text{size}_v 的贡献。

然后就做完了。

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 299995;
int T;
int n;
int to[N * 2 + 5],pre[N * 2 + 5],first[N + 5],edge_tot;
inline void add(int u,int v)
{
int &tot = edge_tot;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int c[N + 5];
inline void update(int x,int k)
{
for(;x <= n;x += lowbit(x))
c[x] += k;
}
inline int query(int x)
{
if(x < 0)
return 0;
int ret = 0;
for(;x;x -= lowbit(x))
ret += c[x];
return ret;
}
struct node
{
int sum;
int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5],seg_tot;
void update(int x,int k,int &p,int tl,int tr)
{
int &tot = seg_tot;
!p && (p = ++tot,seg[p].sum = seg[p].ls = seg[p].rs = 0),seg[p].sum += k;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? update(x,k,seg[p].ls,tl,mid) : update(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
if(l > r)
return 0;
if(!p || (l <= tl && tr <= r))
return seg[p].sum;
int mid = tl + tr >> 1;
int ret = 0;
l <= mid && (ret += query(l,r,seg[p].ls,tl,mid));
r > mid && (ret += query(l,r,seg[p].rs,mid + 1,tr));
return ret;
}
int merge(int x,int y)
{
if(!x || !y)
return x | y;
seg[x].sum += seg[y].sum;
seg[x].ls = merge(seg[x].ls,seg[y].ls),seg[x].rs = merge(seg[x].rs,seg[y].rs);
return x;
}
int fa[N + 5],sz[N + 5],son[N + 5],son1[N + 5];
long long ans;
void dfs1(int p)
{
sz[p] = 1;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = p,dfs1(to[i]),sz[p] += sz[to[i]];
if(!son[p] || sz[to[i]] > sz[son[p]])
son[p] = to[i];
}
for(register int i = first[p];i;i = pre[i])
if((to[i] ^ fa[p]) && (to[i] ^ son[p]))
if(!son1[p] || sz[to[i]] > sz[son1[p]])
son1[p] = to[i];
update(sz[p],1);
}
void dfs2(int p)
{
update(sz[p],-1);
int cur = 0;
if(n - sz[p] >= sz[son[p]])
{
cur += query(n - 2 * (n - sz[p]));
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
update(n - sz[to[i]],1),dfs2(to[i]),update(n - sz[to[i]],-1),rt[p] = merge(rt[p],rt[to[i]]);
cur -= query(n - 2 * (n - sz[p])) - query(1,n - 2 * (n - sz[p]),rt[p],1,n),
cur += (query(n - 2 * sz[son[p]]) - query(2 * (n - sz[p]) - n - 1)) - query(2 * (n - sz[p]) - n,n - 2 * sz[son[p]],rt[p],1,n);
}
else
{
cur += query(n - 2 * sz[son[p]]);
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
update(n - sz[to[i]],1),dfs2(to[i]),update(n - sz[to[i]],-1);
if(to[i] == son[p])
cur -= query(1,n - 2 * sz[son[p]],rt[to[i]],1,n),
cur += query(2 * sz[son[p]] - n,n - 2 * max(sz[son1[p]],n - sz[p]),rt[to[i]],1,n);
rt[p] = merge(rt[p],rt[to[i]]);
}
}
ans += (long long)p * cur;
update(sz[p],1,rt[p],1,n);
update(sz[p],1);
}
int main()
{
scanf("%d",&T);
for(;T;--T)
{
scanf("%d",&n),edge_tot = seg_tot = ans = 0,memset(first,0,sizeof first),memset(c,0,sizeof c),memset(son,0,sizeof son),memset(son1,0,sizeof son1),memset(rt,0,sizeof rt);
int u,v;
for(register int i = 1;i < n;++i)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs1(1),dfs2(1);
printf("%lld\n",ans);
}
}