如题。
游记
作为一只参加第一届 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}\) 然后再做，虽然做法没问题，不过好像不是很主流？
T3 没想出来，打了个自以为的 \(35\text{pts}\) 的程序滚粗了。
Day1 \(100+100+35=235\)，成功拿到大众分。
下午是 J，本来觉得能好好发挥一把，没想到也崩掉了，似乎乐观估计只有 \(250\)？
（此处 Orz LHF 大佬，\(280\) 吊打我，以及一个初一的家伙似乎四题都想到了正解？顺带一提，这两个人的名字缩写都是 LHF）
大概是心态问题吧，反正我的目的是 S。
晚上教练说要请前年我校参加 GDKOI 的同学去吃寿司，于是我就跟去蹭了下。
曾经吃素的我稍微尝试了下鳗鱼吞拿鱼和牛舌之类的，感觉原来没有想象的那么难吃？
拍了张合照（见本人 QQ 空间）。
回到酒店已经快十点了。
睡得还不错吧。
Day 2:
早上可能心态会好点吧。
T1 稍微扫了一眼就没看了，先去看了后面的题（话说土狼家今天的饭是什么鬼）。
T2 看到分段 + 平方下意识想到斜率优化（虽然正解貌似不是），推了一下发现不会做，于是直接写了个 \(O(n^2)\) 的 DP。
T3……居然没想到统计贡献？暴力滚粗。
回来看 T1，大概降智了居然没想到最多只会有一个这样的食材？？？
大概是一开题就打算转换模型的后遗症？？？
针对 \(m=2,3\) 的数据写了个无聊的暴力。
Day2 \(64+64+55=183\)，成功打满自己想要的暴力分。
吃了午饭就返程了呢……
感觉 \(418\) 不挂分的话应该一等有戏了？
不枉我停课这么多天啊（逃
事实证明 D1T3 有 \(25\) 分假掉了，D2T2 因为空间按着 \(4\times 10^7\) 开的于是爆零……
（LHF 大佬和我做法一样，但比我少开一个数组，然后就有那 \(64\) 分了……）
回到学校先回了下宿舍稍微睡了一会。
然后就去教室了。
他们研学的还没回来，还能再浪两天，哈哈。
既然都到了这一步了，大抵也是稍微释怀了吧。
我对于 OI，目的到底是什么呢？
OI 给我的东西那么多，我却把游记写得跟 AFO 似的，是想干什么呢？
再战吧，大抵我也没有发挥出巅峰实力。
Day 5:
暂时回归文化课了啊。
我的 OI 路还很长啊。
班主任问我考得怎么样……
我说我 J 炸 S 海星……
他愣了一下……
题解
格雷码
要么用某著名结论，要么分治。
这题代码就不贴了（其实是不想找）。
括号树
我的做法怎么这么奇异？目前似乎没找到和我一样的……
也是 DP，但是和大多数人的思路不大一样。
首先考虑把 \(\texttt (\) 看做 \(1\)，\(\texttt )\) 看做 \(-1\)，再来考虑一个串合法的充要条件： 1. 和为 \(0\)，即 \(\texttt (,\texttt )\) 个数相等。 2. 任意位置的前缀和非负。
考虑一个序列上的弱化版问题，则易想到设状态 \(f_{i,j}\) 表示以 \(i\) 结尾，和为 \(j\)，任意位置的前缀和非负的子串个数。
若设 \(a_i\) 表示字符串第 \(i\) 位的字符，则有转移 \[f_{i,j}=\begin{cases}0,&a_i=\texttt ( \land j=0 \\f_{i-1,0}+1,&a_i=\texttt ( \land j=1 \\f_{i-1,j-1},&a_i=\texttt ( \land j \ge 2 \\f_{i-1,j+1},&a_i=\texttt )\end{cases}\]
注意到若缩掉第一维，转移相当于将整个状态平移 \(1\) 或 \(-1\) 位，并修改部分状态。
由于修改的状态很少，所以可以直接暴力修改。
转回树上，发现只需要支持一个回溯操作。
容易发现只需要记下被修改为 \(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
28
29
30
31
32
33
34
35
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 家今天的饭
注意到出现次数过半的主要食材至多有一种，容斥即可。
枚举这种主要食材为 \(s\)，并设 \(f_{i,j}\) 表示做完了前 \(i\) 种烹饪方式，\(s\) 的出现次数与其它食材的总出现次数的差为 \(j\) 的方案数。
则 \[f_{i,j} = f_{i-1,j} + f_{i-1,j-1} a_{i,s} + f_{i-1,j+1}\sum\limits_{\substack{1 \le k \le n\\ k \ne s}}a_{i,k}\]
复杂度 \(O(n^2m)\)。
1 |
|
划分
注意到显然分的越多越好。
故设 \(f_i\) 表示所有 \([1,i]\) 的最优方案中，\(i\) 所在块的可能最大左端点减一。
再令 \(s_i=\sum\limits_{j=1}^i a_j\)。
则 \[f_i = \max\limits_{\substack{0\le j < i\\s_i-s_j\ge s_j-s_{f_j}}} j\] 故显然 \(f_i\) 有单调性（因为 \(f_{i-1}\) 一定也满足 \(f_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
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();
}
树的重心
首先显然可以考虑每个点作为重心的贡献（然鹅我考场没想到）。
则一个点 \(p\) 的贡献应为以 \(p\) 为根时在以 \(p\) 的某个儿子为根的子树中删去一棵子树并使得 \(p\) 仍为整棵树的重心的方案数。
故我们只需要考虑这样的子树个数。
注意到若 \(p\) 为重心，则以 \(p\) 为根时 \(p\) 的重儿子的子树大小不超过 \(\frac n2\)。
设 \(\text{size}_x\) 表示以 \(p\) 为根时以 \(x\) 为根的子树大小。
再设删去的子树的根为 \(s\)，\(p\) 的重儿子为 \(\text{wson}\)，\(p\) 的次重儿子为 \(\text{wson}'\)。
若 \(s\) 不在以 \(p\) 的重儿子为根的子树内，则 \(p\) 的重儿子不会改变。
故应满足 \(\text{size}_{\text{wson}} \le \frac{n - \text{size}_s}2\)。
解得 \(\text{size}_s \le n - 2\text{size}_{\text{wson}}\)。
若 \(s\) 在以 \(p\) 的重儿子为根的子树内，则 \(p\) 的重儿子可能不变，可能会变成原来的次重儿子。
故应满足 \(\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\)。
解得 \(2\text{size}_{\text{wson}} - n \le \text{size}_s \le n - 2\text{size}_{\text{wson}'}\)。
于是枚举根结点做就做完了（逃
肯定是需要各种奇怪的换根操作的，也就是说要维护以每个点为根时所有子树大小的出现次数。
随便钦定一个根然后就是要分别维护每个点向下的和向上的。
向下的线段树合并。
向上的？可以用总共的减掉向下的。
总共的话，考虑沿一条边从 \(u\) 到 \(v\)，则会减少 \(\text{size}_v\) 的贡献，增加 \(n - \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
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);
}
}