[NOIP2018模拟赛10.18]自闭报告

闲扯

这一天,菜鸡RyeCatcher又想起来了被毒瘤题支配的恐惧

今天比较好玩,还是ljy提醒才发现文件夹里有题面…不知道外面的人什么时候才发现

看完了题面,又回到了雅礼啥题也不会写的感觉

T1 发现操作就是交换两个数于是写了个假做法就是不同的数之和;分类讨论后文件夹里突然出现一个大样例!发现我的输出居然少5!?于是又分类讨论码码码.后面又有人说大样例是假的woc…T2 暴力 没码完 T3 没思路…

结果30+0+0凉凉,分类讨论多给了我10分hhh

下午讲题的时候因为1926过于瞩目被钦点了,因为码风一贯过长被出题人问是不是正解写挂了也是尴尬…

啊鼠标电池没电了好烦啊 QAQ

T1 duliu

操作就是交换你手中的数和数列中的一个数

怎么判-1?把异或和放在末尾判断排序后是否完全相等(虽然用哈希表也可以)

然后把数字离散化之后将$a[i],bi$连边,我们发现如果你手中有一个联通块中的数,那么这个联通块中的数你都可以经过交换得到,但是考虑你从一个联通块跳到另一个还需要换一次数.所以答案为联通块个数+各个联通块的大小.

这个联通块的大小怎么定义?对于联通块点集$T$, $size[T] =\sum_{x \in T} times[x]$,$times[x]$指$x$在$a$数组中的出现次数

但是还有一件事要注意,就是特判你当前手中的数—$a$数组的异或之和

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
/*
  code by RyeCatcher
*/
inline char gc(){
    static char buf[SIZE],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;
    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
gp_hash_table <int,int> g;
const int maxn=100005;
const int inf=0x7fffffff;
int f[maxn],tot=0;
int a[maxn],b[maxn],c[maxn],d[maxn],n;
int fa[maxn<<1],size[maxn<<1];
bool vis[maxn<<1];
int get(int x){return (fa[x]==x)?fa[x]:(fa[x]=get(fa[x]));}
inline void merge(int x,int y){
	x=get(x),y=get(y);
	if(x==y){
		//size[x]++;
		return ;
	}
	if(size[x]<size[y]){
		size[y]+=size[x];
		fa[x]=y;
	}
	else{
		size[x]+=size[y];
		fa[y]=x;
	}
	return ;
}
ll ans=0;
int main(){
	//DEBUG
	//freopen("dat.in","r",stdin);
	//freopen("duliu_3.in","r",stdin);
	int x,pre_sum=0;
	read(n);
	for(ri i=1;i<=n;i++){
		read(x);
		pre_sum^=x;
		if(!g[x]){
			g[x]=++tot;
			vis[tot]=0,size[tot]=0,fa[tot]=tot;
			f[tot]=x;
		}
		c[i]=a[i]=g[x];
	}
	if(!g[pre_sum]){
		g[pre_sum]=++tot,f[tot]=g[pre_sum];
		vis[tot]=0,size[tot]=0,fa[tot]=tot;
	}
	//printf("--%d--\n",pre_sum);
	a[n+1]=c[n+1]=g[pre_sum];
	pre_sum=0;
	for(ri i=1;i<=n;i++){
		read(x);
		pre_sum^=x;
		if(!g[x]){
			g[x]=++tot;
			vis[tot]=0,size[tot]=0,fa[tot]=tot;
			f[tot]=x;
		}
		d[i]=b[i]=g[x];
		if(a[i]!=b[i])size[a[i]]++;
	}
	if(!g[pre_sum]){
		g[pre_sum]=++tot,f[tot]=g[pre_sum];
		vis[tot]=0,size[tot]=1,fa[tot]=tot;
	}
	b[n+1]=d[n+1]=g[pre_sum];
	n++;	
	std::sort(c+1,c+1+n);std::sort(d+1,d+1+n);
	for(ri i=1;i<=n;i++){
		if(c[i]!=d[i]){puts("-1");exit(0);}
		if(a[i]!=b[i]){
			merge(a[i],b[i]);
		}
	}
	int cnt=0;
	x=get(a[n]);
	if(size[x]==0){//用if(a[n]==b[n])更好
		ans=0,cnt=1;
	}
	for(ri i=1;i<n;i++){
		x=get(a[i]);
		if(!vis[x]){
			if(size[x]==0)continue;
			cnt++,vis[x]=1;
			ans+=size[x];
		}
	}
	printf("%lld\n",ans+cnt-1);
	return 0;
}

T2 travel

又是道树形DP神仙题

这个平方和期望期望有点毒,不能普通地用$(a+b)^2$算,类比搞矩阵时的非齐次线性递推（似乎叫这个名字）

$(a+b)^2 = a^2 + 2 \times ab +b^2$

又转化成线性的了

先想想怎么算$F$值,倍增/链剖都是资瓷的.然而题解有一种高明的线性做法—-树上差分+栈

我们dfs到一个点$x$将该点入栈,从这点回溯到父亲就出栈,发现$y=st[max(0,top-d[x]-1)]$就是能走到最远的点的父亲

然后$tag[x]+=a[x],tag[y]-=a[x]$ ,最后按照树上差分套路求波子树和就好了

求期望考虑naiive 的树形DP,钦定每一个点为根计算答案

$g[x]$表示$x$子树联通块和平方期望,按上面式子推;$s[x]$表示$x$子树期望和,这是可以线性推的

一开始$g[x]=F[x]^2,s[x]=F[x]$

$g[x] = p \times (g[x]+2 \times s[x] \times s[son[x]]+g[son[x]]) +(1-p) \times g[x]$

$s[x]= p \times (s[x]+s[son[x]])+(1-p) \times s[x]$

对于$x$的每个儿子这么合并就好了

这样是$O(nq)$或$O(n^2)$的,发现这个可以二次扫描加换根搞

如果不知道建议先去学一学https://rye-catcher.github.io/tags/%E4%BA%8C%E6%AC%A1%E6%89%AB%E6%8F%8F%E4%B8%8E%E6%8D%A2%E6%A0%B9/

二次换根是从上往下递推的,我们对于点$x$,求出$o[x][0/1]$,表示向上的联通块和平方期望&和期望,再对于$x$的儿子的遍历顺序搞一个前缀$pre$和后缀$suf$记录兄弟子树的联通块平方和期望与和期望,然后按照平方和公式拆开合并就好了

注意合并前缀后缀,父亲向上和父亲本身成$o[v][0/1]$时,我们只用乘以相连$p$的概率,昨天就是这里搞错了

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
/*
  code by RyeCatcher
*/
/*
  code by RyeCatcher
*/
inline char gc(){
    static char buf[SIZE],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;
    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
const int maxn=200005;
const int inf=0x7fffffff;
const ll P=998244353;
int n,q;
struct Edge{
	int ne,to;
	ll p;
}edge[maxn<<1];
int h[maxn],num_edge=1;
inline void add_edge(int f,int to,ll c){
	edge[++num_edge].ne=h[f];
	edge[num_edge].to=to;
	edge[num_edge].p=c;
	h[f]=num_edge;
}
int d[maxn];
ll a[maxn],tag[maxn],f[maxn],g[maxn],s[maxn];
int st[maxn],top=0,fa[maxn];
void pre_dfs(int now){
	int v,x;
	x=st[max(0,top-d[now])];
	st[++top]=now,tag[now]=(tag[now]+a[now])%P,tag[x]=(tag[x]+P-a[now])%P;
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa[now])continue;
		fa[v]=now;
		pre_dfs(v);
	}
	top--;
	return ;
}
void get_sum(int now){
	int v;
	f[now]=(f[now]+tag[now]+P)%P;
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa[now])continue;
		get_sum(v);
		f[now]=(f[now]+f[v])%P;
	}
	return ;
}
int rt;
ll fa_dis[maxn],ans[maxn],pp;
vector <int> son[maxn];
void dfs_1(int now,int fa){
	int v;
	g[now]=f[now]*f[now]%P,s[now]=f[now];
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa)continue;	
		dfs_1(v,now);
		pp=edge[i].p;
		fa_dis[v]=pp;
		son[now].push_back(v);
		g[now]=(g[now]+pp*((2*s[now]*s[v]%P+g[v])%P)%P)%P;
		s[now]=((s[now]+s[v])*pp%P+((1-pp)%P+P)*s[now]%P)%P;
	}
	return ;
}
ll pre[maxn][2],suf[maxn][2],o[maxn][2];//兄弟前缀  兄弟后缀 上方 
void dfs_2(int now,int fa){
	int x,v;
	unsigned int size=son[now].size();
	o[now][0]=(o[now][0]+2*o[now][1]*f[fa]%P+f[fa]*f[fa]%P)*fa_dis[now]%P;
	o[now][1]=(o[now][1]+f[fa])*fa_dis[now]%P;
	ans[now]=((g[now]+o[now][0])%P+2*s[now]*o[now][1]%P)%P;
	pre[now][0]=o[now][0],pre[now][1]=o[now][1];
	suf[now][0]=suf[now][1]=0;
	for(ui i=0;i<size;i++){
		v=son[now][i],pp=fa_dis[v];
		o[v][0]=(o[v][0]+2*o[v][1]*pre[now][1]%P+pre[now][0])%P;
		o[v][1]=(o[v][1]+pre[now][1])%P;		
		pre[now][0]=(pre[now][0]+pp*(2*pre[now][1]*s[v]%P+g[v])%P)%P;
		pre[now][1]=((pre[now][1]+s[v])*pp%P+((1-pp)%P+P)*pre[now][1]%P)%P;
		v=son[now][size-i-1],pp=fa_dis[v];
		o[v][0]=(o[v][0]+2*o[v][1]*suf[now][1]%P+suf[now][0])%P;
		o[v][1]=(o[v][1]+suf[now][1])%P;
		suf[now][0]=(suf[now][0]+pp*(2*suf[now][1]*s[v]%P+g[v])%P)%P;
		suf[now][1]=((suf[now][1]+s[v])*pp%P+((1-pp)%P+P)*suf[now][1]%P)%P;
	}
	for(ui i=0;i<size;i++){
		dfs_2(son[now][i],now);
	}
	return ;
}
int main(){
	//freopen("travel_1.in","r",stdin);
	//freopen("wa.out","w",stdout);
	//FO(travel);
	int x,y;ll z;
	read(n);
	for(ri i=1;i<=n;i++){
		read(a[i]),read(d[i]);
	}
	for(ri i=1;i<n;i++){
		read(x),read(y),read(z);
		add_edge(x,y,z);
		add_edge(y,x,z);
	}
	fa[1]=0;
	pre_dfs(1);
	get_sum(1);
	dfs_1(1,0);
	dfs_2(1,0);
	read(q);
	while(q--){
		read(x);
		printf("%lld\n",ans[x]);
	}
	return 0;
}

T3 VanUSee

思维智商题,看完solution后只能说自己太傻了

易知总步数为$|s|-|t|$.

我们先来考虑最简单的情况,就是步数为偶数,$t$出现在$s$正中央,那么无论先手怎么取,后手对称地取必定能胜利

再稍稍拓展一下发现我们设一个$t$串出现在$s$串的$[st,st+|t|)$位置,那么从左边取需要取$st$步,右边取需要$|s|-(st+|t|)+1$步.我们设那么我们就令一个目标状态$sta$为右边需要取得步数-左边需要取得步数（你左右反一下也没关系）.我们发现每一步操作就是使所有$sta+1/sta-1$.

考虑步数为偶数时,刚刚已经提过后手必胜状态是$sta==0$.但是还有一种情况是同时存在两种目标状态+2/-2.无论先手怎么走,都可以使得另一个目标状态保持为$0$(比如先手+1,那么变成+3/-1,后手也走+1,就成了+4/0)

步数为奇数的时候,先手可以多走一步,他肯定希望朝着不是目标状态的方向走,但是如果同时存在两种目标状态+1/-1.无论你怎么走都可以使一个状态保持为$0$

于是直接KMP求出所有目标状态扫一遍就好了

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
/*
  code by RyeCatcher
*/
inline char gc(){
    static char buf[SIZE],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;
    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
const int maxn=200005;
const int inf=0x7fffffff;
int fail[maxn];
char s[maxn],t[maxn];
int n,m;
int pos[maxn],tot=0;
bool g[maxn];
inline void kmp(){
	memset(fail,0,sizeof(fail));
	//printf("%d %d\n",n,m);
	for(ri i=2,j=0;i<=m;i++){
		if(j&&t[j+1]!=t[i])j=fail[j];
		j+=(t[j+1]==t[i]);
		fail[i]=j;
		//printf("-qwq %d--\n",fail[i]);
	}
	int k=0;
	for(ri i=1;i<=n;i++){
		while(k&&t[k+1]!=s[i])k=fail[k];
		k+=(t[k+1]==s[i]);
		if(k==m){
			g[i]=1;
			pos[++tot]=i;
			k=fail[k];
		}
	}
	return ;
}
int main(){
	int x,T;
	bool flag1,flag2,flag3;
	read(T);
	while(T--){
		flag1=flag2=flag3=0;
		scanf("%s",s+1);
		scanf("%s",t+1);
		n=strlen(s+1),m=strlen(t+1);
		kmp();
		if((n-m)&1){
			//printf("%d %d\n",n,m);
			for(ri i=1;i<=n;i++){
				if(g[i]){
					//printf("%d ",i);
					x=(n-i)-(i-m);
					if(x==1)flag1=1;
					else if(x==-1)flag2=1;
					else if(x==0)flag3=1;
				}
				g[i]=0;
			}
		}
		else{
			for(ri i=1;i<=n;i++){
				if(g[i]){
					//printf("--%d--\n",i);
					x=(n-i)-(i-m);
					if(x==2)flag1=1;
					else if(x==-2)flag2=1;
					else if(x==0)flag3=1;
				}
				g[i]=0;
			}
		}
		if((flag1&&flag2)||flag3)puts("pty");
		else puts("cqf");
	}
	
	return 0;
}

终于把咕掉的补上了一点@TYQ