游记及总结在逼乎。
全部补完~！
A. 托米的字符串
题目描述
托米有一个字符串，他经常拿出来玩。这天在英语课上，他学习了元音字母$a,e,i,o,u$以及半元音$y$。“这些字母是非常重要的！”，托米这样想着，“那么我如果随机取一个子串，里面元音占比期望会有多大呢？”
于是，请你求出对于托米的字符串，随机取一个子串，元音$(a,e,i,o,u,y)$字母占子串长度比的期望是多少。
题目分析
只要统计出$f(l,r)$表示$[l,r]$区间内元音字母的个数，那么$\frac{f(l,r)}{r-l+1}$就是这段区间对答案长度比的贡献，统计出所有区间的贡献，除以$\frac{n(n+1)}2$就是答案。
贡献可以用前缀和简单的统计。
代码
1 |
|
B. 萨博的方程式
题目描述
萨博有个方程式：
其中$\oplus$指代位运算中的异或符号。
萨博同时还对每个未知数限制了范围为$0\le x_i\le m_i$，希望你计算出解的个数，最终答案对$10^9+7$取模后输出。
题目分析
又一道想不到的题。
考场上觉得可能是高斯消元或者线性基搞一波，然后发现不可行，于是就放掉了。
考完评价结果是一道数位Dp，这种数位Dp是一种和以往不同的特殊数位Dp，之后在yk的点拨下A掉了。
我们将$m_i$都转化为二进制表示，从高位到低位逐位考虑。
假设当前二进制位是$bit$，提取出所有$bit$位为$1$的$m_i$，考虑它们$x_i$的取值。
假如所有当前的$x_i$的$bit$位都取$1$，考虑$bit$位是否满足$k$的限制，倘若满足，那么转化为考虑$bit-1$位的情形，否则方案数为$0$。
现在来考虑不全取$1$的情况。
假设对于某个$x_i$，它在$bit$位不选择$1$，于是$x_i$的高位限制就被取消了，那么无论其他解的$0~bit-1$位怎么取值，总有一种$x_i$的取值能使题面的等式成立，这样我们可以通过另外一次Dp来计算出这一位的贡献。
设$f(i,j)$为$bit$位为$1$的前$i$个$x$，$x$的高位确定了$j$个$1$的方案数。
其中$lim[i]_{(0,bit-1)}$表示$lim[i]$的二进制表示中取第$0$位到$bit-1$的值。
状态转移方程的解释如下：
- 如果$x_i$第$bit$位取值为$0$，那么高位限制解除，$x_i$有$2^{bit}$种选择。
- 如果$x_i$第$bit$位取值为$1$，那么高位限制没有解除，$x_i$只有$lim[i]_{(0,bit-1)}$种选择。
需要注意的是，对于那些$lim[i]$的$bit$位不为$1$的$x_i$而言，他们对本次答案的贡献就是$lim[i]$，累乘即可。在统计答案的时候，由于不全取$1$，而我们尚未确定究竟是哪一个$1$不取，在Dp的时候多算了一次$2^{bit}$的贡献，除去即可，详见代码。
这道题和一般的数位Dp的区别在于，一般的数位Dp只考虑某一个数在某一位是否有高位限制，而本题将一些数打包一起考虑。
代码
1 |
|
C. 萨博的方程式
题目描述
纳新一百和乱得尬得在玩取石子的游戏。他们一共有$N$堆石子，第$i$堆有$a_i$颗石子（若$a_i=0$则表示这是一堆空石子堆）。
纳新一百和乱得尬得轮流进行游戏，纳新一百先手。轮到某个人时，他需要选择一堆非空的石子堆，并拿走任意数量的石子。如果不存在一堆非空的石子堆，则轮到的人输掉游戏。纳新一百想要知道，他的第一轮操作有多少种不同的取法能够保证他最后取得游戏的胜利。假设两个人都是用最优策略在玩游戏，两种操作方式视为不同当且仅当两种方式选取的石子堆的序号不同或取走的石子数量不同。
为了增加趣味性，纳新一百和乱得尬得决定对前$i$堆石子都玩一次游戏，两次游戏相互独立，也就是说，每开始一个新的游戏，石子堆都会被复原。
现在，纳新一百想要知道每一次游戏中，他能够取得胜利的第一轮操作方案数。
题目分析
签到题。
众所周知第$i$堆石子的SG函数$SG(a_i)=a_i$。
所以问题转化为对于前$i$堆石子的异或和$x$，有多少堆石子满足$a_i\gt x\oplus a_i$，因为只要满足这个条件，就能拿走一些石子使其石子数变为$x\oplus a_i$，从而使异或和变为$0$使得后手必输。
可以证明，若异或和$x$的最高有效位为$bit$，那么所有$bit$位为$1$的$a_i$都满足条件，而为$0$的不满足条件。
代码
来自cyy的代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
long long a[100005];
int cnt[64];
int main() {
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
long long xorsum = 0;
for (int i=1;i<=n;i++) {
xorsum ^= a[i];
for (int j=63;j>=0;j--) if ((a[i] >> j) & 1) cnt[j] ++;
if (xorsum == 0) printf("0\n");
else {
int hb = 0;
for (int j=63;j>=0;j--) if ((xorsum >> j) & 1) {
hb = j;
break;
}
printf("%d\n",cnt[hb]);
}
}
return 0;
}
D. 卡拉巴什的字符串
题目描述
卡拉巴什是字符串大师，这天他闲着无聊，又造了个字符串问题。
给定一个长度为$N$字符串$S$，定义后缀$i$为从第$i$个位置开始的后缀，即$s_{i}s_{i+1}\cdots s_{n}$，定义$lcp(i,j)$为后缀$i$和后缀$j$的最长公共前缀。
卡拉巴什想要知道，每次他给出一组$i,j$，你能否快速告诉他$lcp(i,j)$。
卡拉巴什的好朋友葫芦是字符串宗师，他认为这个题太无聊，于是他想了另一个问题，假设有一个集合$lcp(i,j) | 1\leq i < j\leq N$，他想知道这个集合的$MEX$值是多少。一个集合的$MEX$值为最小的没有出现在集合中的非负整数。
这个问题对卡拉巴什来说太容易了，于是葫芦想知道，对于字符串的每一个前缀，对应的集合的$MEX$值是多少。
题目分析
考试时没认真想，考完了想想还是不难的。。。
考虑用后缀自动机求两个后缀的LCP，即它们在后缀树上$lca$结点的$Max$值，所以两两后缀的$LCP$的集合就是后缀自动机上非叶子结点的$Max$值的集合。
- 方法一：考虑一个个字母加入时动态构建后缀自动机，每当一个节点有儿子结点，那这个结点就能成为两个不同后缀的$lca$，就在布尔数组里将它的$Max$标记为$1$。每加入一个字母都暴力维护$MEX$的值，均摊时间复杂度$O(n)$
- 方法二：考虑两个后缀的LCP值加入为$x$，同时删掉第一个字母，LCP就变$x-1$，所以$1$到$x$都存在，所以答案就是的最大值+1
注意特判单字母的字符串是没有为$0$的$LCP$的。在方法一中，体现为后缀树的根结点在只有一个儿子的时候不能成为$lca$，因为根结点不代表一个后缀。
代码
方法二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
using namespace std;
const int maxn=1000005,maxc=26;
struct Suffix_Automaton {
int cnt,root,last,f;
int child[maxn<<1][maxc],next[maxn<<1],Max[maxn<<1];
Suffix_Automaton() {init();}
void init() {cnt=f=0;root=last=newnode(0);}
int newnode(int val) {
cnt++;
next[cnt]=0;
Max[cnt]=val;
fill(child[cnt],child[cnt]+maxc,0);
return cnt;
}
void insert(int data) {
int p=last,u=newnode(Max[last]+1);
last=u;
for(; p&&!child[p][data]; p=next[p])child[p][data]=u;
if(!p)next[u]=root;
else {
int old=child[p][data];
if(Max[old]==Max[p]+1)next[u]=old;
else {
int New=newnode(Max[p]+1);
copy(child[old],child[old]+maxc,child[New]);
next[New]=next[old];
next[u]=next[old]=New;
for(; child[p][data]==old; p=next[p])child[p][data]=New;
}
f=max(f,Max[next[u]]);
}
}
} sam;
string s;
int main() {
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--) {
cin>>s;
sam.init();
char last=s[0];
bool flag=0;
for(auto x:s) {
sam.insert(x-'a');
if(x!=last)flag=1;
printf("%d ",flag?sam.f+1:0);
}
putchar('\n');
}
return 0;
}
E. 阔力梯的树
题目描述
阔力梯有一棵树，这棵树有$N$个节点，每个节点按顺序编号为$1−N$，其中，$1$号节点是根结点。
定义树上一个节点的“结实程度”为，将这个节点的子树中的所有的节点编号拿出来之后，按照从小到大的顺序排列，然后将相邻元素做差之后求平方和。即假设子树的节点编号排序后的序列为$a_1,a_2,a_3,\ldots,a_k$，这个节点的“结实程度”就是：现在，阔力梯想要加固这棵树，但是他的资源有限，不能加固所有的节点，所以他想知道每个节点的“结实程度”是多少。
题目分析
维护一个set，那么$1$的答案很好求，换根的时候也很好处理贡献差，所以写一个换根DP就好了。
结果我写着写着写成了dsu on tree。
启发式合并一下，继承重儿子的set，暴力合并轻儿子的set，就可以了。
反正复杂度也是对的，所以就没管了，没想到标解也是dsu on tree。
代码
1 |
|
F. 采蘑菇的克拉莉丝
题目描述
克拉莉丝在玩一个采蘑菇的游戏。游戏地图是一张$N$个节点，$N-1$条边的连通无向图。一开始起点在$1$号点。
游戏过程中会发生两种事件：
- $1\ v\ x\ (1\le x\le10^5)\,$表示在编号为$v$的节点新出现了$x$个蘑菇
- $2\ v$表示克拉莉丝的起点变成了节点$v$
在每个事件之后，克拉莉丝想要知道，他收集完所有的蘑菇所需的代价。
蘑菇的收集规则是这样的，对于每个蘑菇，克拉莉丝要收集它，所需要的代价是这个蘑菇所在节点和起点之间的路径上最靠近起点的边的边权。在起点上的蘑菇不需要代价就能收集。
题目分析
我们有一种暴力的方法是，直接用树状数组维护子树和，然后对于每个询问，枚举“新根”的每一条边统计答案。
但显然，这种做法在菊花图会被卡成$nq$。
我们可以利用类似树链剖分维护动态规划的思想，在询问时只处理重儿子的贡献，那么我们还差轻儿子的贡献。我们可以在修改时爬重链，把轻链的答案全部累加到重链链头的父亲处，这样我们就可以$O(1)$获得轻儿子贡献了，而爬树的复杂度是$O(\log n)$的。回答询问时将三部分相加即可。
时间复杂度是$O(q\log n)$
这道题考试时yk用了一种两次离线的做法A掉了，还没研究，贴份代码。
代码
1 |
|
yk的两次离线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
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=1000007;
const ll inf=1<<29;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int head[maxn],nex[maxn<<1],to[maxn<<1],e1,w[maxn<<1];
int L[maxn],cl,R[maxn];
void addedge(int u,int v,int x){
++e1;nex[e1]=head[u];head[u]=e1;to[e1]=v;w[e1]=x;
}
void dfs(int u,int fa){
L[u]=++cl;
for(int i=head[u];i;i=nex[i]){
int v=to[i];
if(v==fa) continue;
dfs(v,u);
}
R[u]=cl;
}
vector<int> g[maxn];
int n;ll ans[maxn];
struct node{
int l,r,x;
node(int l,int r,int x):l(l),r(r),x(x){}
};
vector<node> G[maxn];
inline void DFS(int u,int fa,int x){
for(int i=0;i<g[u].size();i++){
int pos=g[u][i];
if(L[u]>1) G[pos].push_back(node(1,L[u]-1,x));
if(R[u]<n) G[pos].push_back(node(R[u]+1,n,x));
}
for(int i=head[u];i;i=nex[i]){
int v=to[i];
if(v==fa) continue;
DFS(v,u,w[i]);
for(int k=0;k<g[u].size();k++){
int pos=g[u][k];
G[pos].push_back(node(L[v],R[v],w[i]));
}
}
}
ll sum[maxn<<2];
void update(int o,int l,int r,int x,int y){
if(l==r){
sum[o]+=y;return;
}
int m=(l+r)>>1;
if(x<=m) update(o<<1,l,m,x,y);
else update(o<<1|1,m+1,r,x,y);
sum[o]=sum[o<<1]+sum[o<<1|1];
}
ll query(int o,int l,int r,int ql,int qr){
if(l==ql&&r==qr) return sum[o];
int m=(l+r)>>1;
if(ql<=m&&qr>m) return query(o<<1,l,m,ql,m)+query(o<<1|1,m+1,r,m+1,qr);
else if(ql<=m) return query(o<<1,l,m,ql,qr);
else return query(o<<1|1,m+1,r,ql,qr);
}
int main(){
n=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),x=read();
addedge(u,v,x);addedge(v,u,x);
}
dfs(1,0);
int q=read(),Now=1;
DFS(1,0,0);
for(int i=1;i<=q;i++){
int opt=read();
if(opt==1){
int x=read(),y=read();
G[i].push_back(node(0,L[x],y));
}
else Now=read();
g[Now].push_back(i);
}
DFS(1,0,0);
for(int i=1;i<=q;i++){
ll tot=0;
for(int k=0;k<G[i].size();k++){
if(G[i][k].l==0){
update(1,1,n,G[i][k].r,G[i][k].x);
}
else{
tot+=G[i][k].x*query(1,1,n,G[i][k].l,G[i][k].r);
}
}
printf("%lld\n",tot);
}
return 0;
}
G. 糖糖王国的道路修建
题目描述
质量和辉辉是一对姐妹，她们统治着糖糖王国。糖糖王国有$n+m$个城镇，可以看作是平面上的$n+m$个整点，其中$n$个属于质量，另外$m$个属于辉辉。
现在质量和辉辉要在各自的城镇之间修建道路，道路必须是笔直的线段。学过简单图论的小盆友都知道，只需要$n+m−2$条线段就可以让质量和辉辉的城镇各自两两相连。
现在就希望你能给出方案，要求在满足连通性的同时，任意两条线段都不能在城镇点以外的地方相交。如果不存在这样的方案也请判断。
题目分析
太神了不会做，应该不会回来补了。
贴个官方题解在这儿吧。
H. 叁佰爱抠的序列
题目描述
叁佰爱抠的智商有三百，他特别喜欢构造各种各样的序列。
这天他突然想出了这样一个序列：
一个长度为n的序列A，元素的值域是$[1,m]$。
对于任意$x,y\in[1,m],x\neq y$，序列中存在一个位置$p(1\le p\lt n)$，满足$A[p]=x,A[p+1]=y$或者$A[p+1]=x,A[p]=y$。
叁佰爱抠很开心地走了。作为他忠实粉丝的你只听清楚了$n$的大小，那么你好奇了起来，$m$最大值可以取到多少，并且打算自己动手构造一个这样的序列。
题目分析
考试时试了一波OEIS，然而并没有什么卵用。
本题近似等价于求$n$个点完全图的欧拉回路。
通过二分求出$n$的值，需要注意的是，因为要保证有欧拉回路，所以如果二分出来的$n$是偶数，那么应该增加$\frac n2-1$条重边才能保证奇点只有$2$个以保证欧拉回路。
题目给出的边数减去二分出来的边数可以直接用来构造重边。
剩下的跑欧拉回路即可。
代码
yk的代码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
using namespace std;
typedef long long ll;
const int maxn=2000007;
const int inf=(1LL<<29);
int head[maxn],to[maxn<<1],next1[maxn<<1],vis[maxn<<1];
int aa[maxn],e1,ee;
void addedge(int u,int v){
++e1;next1[e1]=head[u];head[u]=e1;to[e1]=v;
}
void euler_path(int u){
for(int &i=head[u];i;i=next1[i]){
if(vis[i]) continue;
vis[i]=vis[((i-1)^1)+1]=1;
euler_path(to[i]);
}
aa[++ee]=u;
}
ll solve(int x){
ll ans=0;
ans=1LL*x*(x-1)/2;
if(x%2==0) ans+=x/2-1;
return ans;
}
int main(){
cin.tie(0);ios_base::sync_with_stdio(false);
ll n;cin>>n;
ll l=1,r=2e9,ans;
while(l<=r){
int mid=(l+r)>>1;
if(solve(mid)<=n-1){
l=mid+1;ans=mid;
}
else r=mid-1;
}
ll a=n-1-solve(ans);
if(n>2000000) printf("%lld",ans);
else{
printf("%lld\n",ans);
for(int i=1;i<=ans;i++)
for(int k=i+1;k<=ans;k++){
addedge(i,k);
addedge(k,i);
}
if(ans%2==0){
for(int i=1;i<=ans/2-1;i++){
addedge(i*2-1,i*2);
addedge(i*2,i*2-1);
}
euler_path(ans);
}
else euler_path(1);
int first=1;
for(int i=1;i<=ee;i++){
if(first) first=0;
else printf(" ");
printf("%d",aa[i]);
}
for(int i=1;i<=a;i++) printf(" %d",aa[ee]);
}
return 0;
}
I. 堡堡的宝藏
题目描述
堡堡有一张大小为$n\times m$的地图，每个位置都有一个宝箱，宝箱要通过一定数量的投币才能打开。
堡堡想要打开所有的宝箱，但是他不想浪费太多钱。幸运的是，位置相邻的宝箱内部是相连的。
具体地说，存在$k$个约束条件，每个约束条件为：(保证$(x_1,y_1)$与$(x_2,y_2)$相邻，$coin[x][y]$代表对宝箱$(x,y)$投币数量)请你求出堡堡最少需要投多少个币才能打开所有的宝箱。
题目分析
标解的算法是KM算法，因为KM算法可以用来解决一类不等式问题。
然而考场上用单纯形算法水过去了。
和这道题基本上一样，时间复杂度$O(\text{不清楚})$。
代码
1 |
|
J. 邦邦的2-SAT模板
题目描述
邦邦是图论白痴，他有一天捡到了一份模板，可以解决2-SAT问题并输出方案。
所谓2-SAT问题，指：有$n$个布尔变量$a_i$，有$m$个形如$x\ or\ y=true$的方程，$x$和$y$为$a_i$或者$!a_i$，求是否存在一组$a_i$的取值满足所有方程。
戳戳是真正的图论大师，他看了看邦邦的板子，发现这段代码会超时。邦邦不相信，戳戳要赶去约会了，于是希望你构造一个数据让邦邦这段代码超时。
具体地，你需要根据给定的n按如下格式构造：
第一行输出一个整数$m(0\le m\le n)$，代表有$m$个方程。
接下来$m$行，给出两个数$x$和$y(−n\le x,y\le n,x,y\neq0)$，若数字为负数，代表$!a_i$，否则代表$a_i$。
要求保证代码中solve的返回值是true(存在至少一组解)，且$CNT$的值满足邦邦的2-SAT模板见附录。
附录
1 |
|
题目分析
考场上没想出来，其实构造方法不是很难。
如图所示：
于是输出$-i$和$i+1$，最后输出$-n$和$-n$即可。
来自出题人：
没错，本题就是为了告诉在座各位你们的板子可能是个暴力…..
代码
1 |
|
K. 破忒头的匿名信
题目描述
破忒头想要写一封匿名信来做坏事，由于他不想被认出自己的笔迹，因此他想要雇佣萨博来帮他写这封信。萨博按照这样的标准来收费：他的词典里有$N$个单词，第$i$个单词的单价是$p_i$。如果你提供一个长度为$M$的序列$a_1,a_2,\ldots,a_M(1\le a_i\le N)$，那么你需要支付$\sum_{i=1}^Mp_{a_i}$的金钱，而萨博会依次往信里写上。破忒头希望支付最少的金钱，让萨博写的内容恰好为他想要的信件内容$T$。请你告诉破忒头，最少需要付多少钱，能让萨博写出他想要的匿名信，或者告诉他这是不可能做到的。
题目分析
考场上sb了，以为AC自动机来做是$n^2$的，但其实AC自动机上不同长度的单词至多有$\sqrt n$种，同时trie树与后缀树的树高都不会超过$\sqrt n$，这两种描述是等价的，下面进行证明。
限定串的总长度为$n$，定义trie树上一个结点的有效高度为从根到这个结点时经过的单词结尾结点的个数，定义trie树的有效高度为所有结点有效高度的最大值。
假设加入串长度递增，若想使得trie树的有效高度变高，那么我只能从上一次插入的串的结束结点处继续增加结点，也就是说上一个串是当前串的前缀，故增加的结点数$f(i)=f(i-1)+x$，$x$是大于等于$1$的自然数，显然其他情况下的串都不会使得trie树的有效高度变高。
那么$1+2+3+\cdots+\sqrt n=O(n)$，也就是说trie树的有效高度至多为$\sqrt n$。
如果我们在用AC自动机DP的时候暴力跳$fail$指针，由于后缀树的树高是没有保证的，所以复杂度最坏$O(n^2)$，但利用到上面证明的性质，如果我们能够快速定位这些有效结点（是单词结尾的结点），我们便可以$O(\sqrt n)$跳完后缀树。
这就是AC自动机上的$next$指针，在menci的学习笔记里也有介绍，一个结点的$next$指针指向它的$fail$链上距离它最近的一个单词结尾结点。
有了$next$指针，每次跳跃都可以进行一次有效的DP转移，故时间复杂度为$O(n\sqrt n)$。$next$指针的求法也很简单，详见代码。
代码
1 |
|
