NOI赛前总结

发表于 分类于

这是在NOI前一个星期的一些总结。

08.07

今天发挥的还算可以，最后T3也想到了单调性DP的做法，但是已经来不及了。

T1

输出任意一个长度最小的字符串，满足在这个字符串的子串中能找到所有长度为 $l$ 且字符在集合 $c$ 中的串。

手玩一下发现，输出不超过10MB就是大概 $1.2\times 10^7$ 个字符。如果输出的字符串中每个长度为 $l$ 的子串与 $c^l$ 种字符串一一对应，那么得到长度下界为 $c^l+l-1$。

考虑构造，并尝试在构造过程中证明下界是可以到达的。

将 $c^l$ 种字符串看成一个点，对于一个长度为 $l$ 的字符串，将第一位删掉然后在最后一位加上一个字符，形成了一个新的字符串。将这两个字符串连一条有向边。于是需要跑一遍哈密顿路径。

然后这个是NP完全的。

或许尝试一下将每个点只经过一次转换成边之经过一次，这样就只需要跑欧拉路径？

建一个二分图，左边是所有字符集为 $c$，长度为 $l-1$ 的字符串；右边是所有字符集为 $c$，长度为 $l$ 的字符串。当左边的某个字符串在最后加一个点形成右边的一个字符串则它们连一条边；右边的字符串与删掉一位后形成的左边的字符串连一条边。

这样实际上是把点变成了两条边，于是转成了求欧拉路径。

为了证明达到下界，我们来看是否任意的这样的图都存在欧拉路径。

证明很显然，左边的点有 $2c$ 条边，右边的点有 $2$ 条边。于是必定存在。

那么dfs跑一遍，发现栈空间极大无比，搞到了512MB。

于是手写一个栈，发现时间复杂度是 $O(c^{l+1})$ 的，因为每次都需要枚举一遍 $0\cdots c-1$。

于是再加一个当前弧优化之类的东西就可以了。

时间和空间复杂度都是 $O(c^l)$。

T2

有一个字符串，多次询问区间内的回文子串个数。不同的位置算多个。

$n,m\leq 1.3\times 10^5$。

有一个或许能拿优秀部分分的做法是莫队，每次莫队的端点移动时产生的贡献是固定一个端点，询问另一个端点在一段区间内的回文串个数。这个可以预处理PAM的parents树然后树链剖分or倍增解决。时间复杂度 $O(n\sqrt n\log n)$。

考虑正解，换一种思考方式，用manacher去做。

考虑枚举回文串的中间点，设 $f_i$ 为最长的延伸长度，然后稍微转换一下变成求 $\sum_{i=L}^R\min{f_i,i-L,R-i}$。

这个min里面有三个数，考虑将数量变少。将 $[L,R]$ 从中间断开，设 $mid=\frac{L+R}{2}$，那么min里面的东西就变为两个了。

考虑 $[L,mid]$ 如何算（$[mid+1,R]$ 同理），相当于求 $\sum_{i=L}^{mid}\min{f_i,i-L}$。

当 $f_i\le i-L$ 时，即 $i-f_i\geq L$。这时需要分别统计符合条件的 $i$ 的 $f_i$，$i$，$1$ 之和。

于是上个可持久化线段树即可。

时间复杂度 $O((n+m)\log n)$。

T3

建造记者站

08.08

今天在酒店里做题，用了几个小时做了两题。晚上颓废+NOI原题。

T1

0808T1

$n,q\leq 10^5$。

权值在边上十分不好做。考虑将贡献扔到点上。

将一条边 $(u,v,w)$ 的贡献扔到点上，令 $val_u,val_v$ 加上 $\frac{w}{2}$。那么如果一个人两个点都选了，贡献刚好是 $w$；否则减一下贡献就是 $0$ 了。

那么题目变成，每次修改两个点的权值。然后将这些权值从大到小排序，在奇数位的贡献为正，偶数位的贡献为负，问贡献和。

由于需要强制在线，那么写个Treap维护一下就好了。

这个Treap需要支持维护将某个特定节点取出来，因此需要维护父亲。

程序：

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=100010;
namespace Treap{
	int siz[N],rnd[N],sum[N],val[N],ch[N][2],fa[N],rt;
	inline void pushup(int u)
	{
		if(!u) return;
		if(siz[ch[u][0]]&1) sum[u]=sum[ch[u][0]]-val[u]+sum[ch[u][1]];
		else sum[u]=sum[ch[u][0]]+val[u]-sum[ch[u][1]];
		siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;
		if(ch[u][0]) fa[ch[u][0]]=u;
		if(ch[u][1]) fa[ch[u][1]]=u;
	}
	int merge(int x,int y)
	{
		if(!x||!y)
		{
			fa[x]=fa[y]=x+y;
			return x+y;
		}
		if(rnd[x]<rnd[y])
		{
			ch[x][1]=merge(ch[x][1],y); pushup(x); return x;
		}
		else
		{
			ch[y][0]=merge(x,ch[y][0]); pushup(y); return y;
		}
	}
	void split_val(int u,int v,int &x,int &y)
	{
		if(!u) return (void)(x=y=fa[x]=fa[y]=0);
		if(val[u]>=v)
		{
			x=u; split_val(ch[u][1],v,ch[x][1],y); pushup(x);
		}
		else
		{
			y=u; split_val(ch[u][0],v,x,ch[y][0]); pushup(y);
		}
	}
	void split_siz(int u,int k,int &x,int &y)
	{
		if(!u) return (void)(x=y=fa[x]=fa[y]=0);
		if(k>siz[ch[u][0]])
		{
			x=u; split_siz(ch[u][1],k-siz[ch[u][0]]-1,ch[x][1],y); pushup(x);
		}
		else
		{
			y=u; split_siz(ch[u][0],k,x,ch[y][0]); pushup(y);
		}
	}
	inline int kth(int u)
	{
		int s=siz[ch[u][0]];
		for(;u!=rt;u=fa[u])
			if(ch[fa[u]][1]==u)
				s+=siz[ch[fa[u]][0]]+1;
		return s;
	}
	void dfs(int u)
	{
		if(ch[u][0]) dfs(ch[u][0]);
		printf("%d ",val[u]);
		if(ch[u][1]) dfs(ch[u][1]);
	}
	inline void take(int u)
	{
		int x,y,z;
		split_siz(rt,kth(u),x,y);
		split_siz(y,1,y,z);
		rt=merge(x,z);
	}
	inline void add(int u,int v)
	{
		int x,y;
		take(u);
		val[u]+=v; sum[u]+=v;
		split_val(rt,val[u],x,y);
		rt=merge(merge(x,u),y);
	}
	inline void dec(int u,int v)
	{
		int x,y;
		take(u);
		val[u]-=v; sum[u]-=v;
		split_val(rt,val[u],x,y);
		rt=merge(merge(x,u),y);
	}
}
using namespace Treap;
int n,q,ty,cnt;
struct Edge{
	int x,y,z;
}e[N];

int main()
{
	FO(round);
	srand(20030403);
	n=read(); q=read(); ty=read();
	fo(i,1,n) siz[i]=1,rnd[i]=rand();
	fo(i,1,n) rt=merge(rt,i);
	int opt,x,ans=0;
	fo(i,1,q)
	{
		opt=read();
		if(!opt)
		{
			x=read()^(ty*ans);
			dec(e[x].x,e[x].z);
			dec(e[x].y,e[x].z);
		}
		else
		{
			++cnt;
			e[cnt].x=read()^(ty*ans),e[cnt].y=read()^(ty*ans);
			e[cnt].z=read();
			add(e[cnt].x,e[cnt].z);
			add(e[cnt].y,e[cnt].z);
		}
		printf("%d\n",ans=(sum[rt]>>1));
	}
	return 0;
}

时间复杂度 $O(n\log n)$。

T2

一个叫做Lindström–Gessel–Viennot的引理

感性证明：

将这些点按横坐标排序后，一共有 $n!$ 种配对方案。考虑上方第 $i$ 个点配对下面第 $p_i$ 个点，那么一个合法的配对方案的必要条件是逆序对个数为 $0$。

现在要求的是不相交的方案，考虑反面，看看相交的方案数是多少。

如果有一种相交的情况，考虑在交点的位置将两条路径反过来。这样做相当于在一个排列中交换了两个位置不同的数，由经典结论，此时逆序对的奇偶性改变。

因此，当有相交的情况时，逆序对为奇数的相交方案=逆序对为偶数的相交方案。

又因为有：逆序对为偶数的所有方案=逆序对为偶数的相交方案+逆序对为 $0$ 的不相交方案，因此得证。

于是如果能求出某两个点配对的方案数，然后高斯消元解行列式就可以了。

枚举第一行的某个点为起点，然后用经典容斥去做DP即可。

时间复杂度 $O(n+m+p^2q+pq^2+p^3)$。

T3

双重积分？格林公式？

不会不会，溜了溜了。