CompetitionAD20211229

发表于 分类于
AD20211229 校模拟赛

比赛链接：这里。

相较于往次的比赛，质量有了较大的提升。

但其实难度只能说一般。

A.

这个题先分析一手。

发现是个内向基环树森林。

然后我们发现这个能够抓到的充要条件是 $a$ 可到达 $b$，并且 $a$ 和 $b$ 所在的基环树上的环是一个二元环。

特判一手 $a$ 一步就可以到达 $b$ 的情况。

因为没有注意到森林的情况，痛失 5pts。

时间复杂度 $O(Tn)$。

代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=2e3;

ll T,n,a,b,amt,flg,flag,top;

ll ver[N+5],st[N+5];

bool vis[N+5];

inline void dfs(ll p) {
	if(vis[p]) {
		if(ver[ver[p]]==p) flg=1;
		return;
	}
	vis[p]=1;
	st[++top]=p;
	dfs(ver[p]);
}

inline void dfs_(ll p) {
	if(p==b) flag=1;
	if(vis[p]) return;
	vis[p]=1;
	dfs_(ver[p]);
}

inline ll read() {
	ll ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
	return ret*f;
}

int main() {

	T=read();

	while(T--) {
		memset(vis,0,sizeof(vis));
		top=0;memset(st,0,sizeof(st));
		flg=0;flag=0;memset(ver,0,sizeof(ver));
		n=read();a=read();b=read();
		for(ll i=1;i<=n;i++) {
			ver[i]=read();
		}
		dfs(a);
		memset(vis,0,sizeof(vis));
		dfs_(a);
		if(ver[a]==b||a==b) printf("Yes\n");
		else
		if(!flag) printf("No\n");
		else {
			if(flg) printf("Yes\n");
			else printf("No\n");
		}
	}

	return 0;
}

B.

其实可以严谨证明。

最小代价就是区间最小值。

因为中途任何一次清零操作所需要付出的代价都会是 $a_{\min}\times A>a_{\min}$ 的。然后就没了。

时间复杂度 $O(n\log 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
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<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e6;

ll n,q,ans,l,r;

ll a[N+5];

struct sgt{
	ll l,r,dat;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define dat(x) tree[x].dat
}tree[N*4+5];

inline void build(ll p,ll l,ll r) {
	l(p)=l;r(p)=r;
	if(l==r) {dat(p)=a[l];return;}
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	dat(p)=min(dat(p<<1),dat(p<<1|1));
}

inline ll getmin(ll p,ll l,ll r) {
	if(l(p)>=l&&r(p)<=r) {return dat(p);}
	ll mid=(l(p)+r(p))>>1;
	if(l>mid) return getmin(p<<1|1,l,r);
	if(r<=mid) return getmin(p<<1,l,r);
	return min(getmin(p<<1|1,l,r),getmin(p<<1,l,r));
}

inline ll read() {
	ll ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
	return ret*f;
}

inline void write(ll x) {
	static char buf[22];static ll len=-1;
	if(x>=0) {
		do{buf[++len]=x%10+48;x/=10;}while(x);
	}
	else {
		putchar('-');
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {
	write(x);putchar('\n');
}

int main() {

	n=read();q=read();

	for(ll i=1;i<=n;i++) {
		a[i]=read();
	}

	build(1,1,n);

	while(q--) {
		l=read();r=read();
		ans=getmin(1,l,r);
		writeln(ans);
	}

	return 0;
}

C.

这个题实际上仔细分析一下性质。

深度浅的点一定能够尽量多地抢走自己路径上的东西。

深度相同的点可以放在一起后处理。

所以说先按照深度排序，先处理深度浅的点，再处理深的点。

深度相同的点放在一起处理，先统计答案再修改路径。

实际上就是求路径的前缀和，然后附带一个路径乘上一个固定常数（这个动物不会参加游戏的概率）的操作。

显然树链剖分可以实现。

但是这个题它卡树剖。非常的烦人。

于是尝试把线段树结构体中的区间改为传参，取模全部先进行判断再取模。再加上一个 $O(fast)$ 的优化，勉强贴着 900ms 的线过掉了。

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

气人的是 fcy 的暴力 $O(n^2)$ 跑得巨快直接碾到 AC。

可能是我人傻自带大常数。。。

代码：

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=2e5;

ll n,m,rt,mo,u,v,tot,cnt,inv;

ll siz[N+5],hs[N+5],dt[N+5],fa[N+5],top[N+5];

ll a[N+5],wt[N+5],id[N+5],b[N+5];

ll ver[N*2+5],nxt[N*2+5],head[N+5];

struct sgt{
	ll sum,mul;
	#define sum(x) tree[x].sum
	#define mul(x) tree[x].mul
}tree[N*4+5];

struct node{
	ll id,dt,ans,p;
	bool operator < (const node& rhs) const{
		return dt<rhs.dt;
	}
}c[N+5];

inline ll pow(ll b,ll p) {
	ll res=1;
	while(p) {
		if(p&1) res=(res*b)%mo;
		b=(b*b)%mo;p>>=1;
	}
	return res;
}

inline void build(ll p,ll l,ll r) {
	mul(p)=1;
	if(l==r) {sum(p)=wt[l];return;}
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	sum(p)=sum(p<<1)+sum(p<<1|1);
	if(sum(p)>=mo) sum(p)%=mo;
}

inline void spread(ll p) {
	sum(p<<1)=sum(p<<1)*mul(p);
	if(sum(p<<1)>=mo) sum(p<<1)%=mo;
	sum(p<<1|1)=sum(p<<1|1)*mul(p);
	if(sum(p<<1|1)>=mo) sum(p<<1|1)%=mo;
	mul(p<<1)=(mul(p<<1)*mul(p))%mo;
	if(mul(p<<1)>=mo) mul(p<<1)%=mo;
	mul(p<<1|1)=(mul(p<<1|1)*mul(p))%mo;
	if(mul(p<<1|1)>=mo) mul(p<<1|1)%=mo;
	mul(p)=1;
}

inline void _mul(ll p,ll L,ll R,ll l,ll r,ll d) {
	if(l<=L&&r>=R) {
		sum(p)=sum(p)*d;
		if(sum(p)>=mo) sum(p)%=mo;
		mul(p)=mul(p)*d;
		if(mul(p)>=mo) mul(p)%=mo;
		return;
	}
	ll mid=(L+R)>>1;spread(p);
	if(l<=mid) _mul(p<<1,L,mid,l,r,d);
	if(r>mid) _mul(p<<1|1,mid+1,R,l,r,d);
	sum(p)=sum(p<<1)+sum(p<<1|1);
	if(sum(p)>=mo) sum(p)%=mo;
}

inline ll query(ll p,ll L,ll R,ll l,ll r) {
	if(l<=L&&r>=R) {return sum(p);}
	ll mid=(L+R)>>1,res=0;spread(p);
	if(l<=mid) {res=res+query(p<<1,L,mid,l,r);if(res>=mo) res%=mo;};
	if(r>mid) {res=res+query(p<<1|1,mid+1,R,l,r);if(res>=mo) res%=mo;};
	return res;
}

inline void dfs(ll p,ll fath) {
	dt[p]=dt[fath]+1;siz[p]=1;fa[p]=fath;
	for(ll i=head[p];i;i=nxt[i]) {
		if(ver[i]==fath) continue;
		dfs(ver[i],p);siz[p]+=siz[ver[i]];
		if(siz[ver[i]]>siz[hs[p]]) hs[p]=ver[i];
	}
}

inline void _dfs(ll p,ll fath,ll topf) {
	id[p]=++cnt;wt[cnt]=a[p];top[p]=topf;
	if(!hs[p]) return;
	_dfs(hs[p],p,topf);
	for(ll i=head[p];i;i=nxt[i]) {
		if(ver[i]==fath||ver[i]==hs[p]) continue;
		_dfs(ver[i],p,ver[i]);
	}
}

inline void mulpath(ll x,ll y,ll k) {
	while(top[x]!=top[y]) {
		if(dt[top[x]]<dt[top[y]]) swap(x,y);
		_mul(1,1,n,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(id[x]>id[y]) swap(x,y);
	_mul(1,1,n,id[x],id[y],k);
}

inline ll qpath(ll x,ll y) {
	ll ans=0;
	while(top[x]!=top[y]) {
		if(dt[top[x]]<dt[top[y]]) swap(x,y);
		ans=ans+query(1,1,n,id[top[x]],id[x]);
		if(ans>=mo) ans%=mo;
		x=fa[top[x]];
	}
	if(id[x]>id[y]) swap(x,y);
	ans=ans+query(1,1,n,id[x],id[y]);
	if(ans>=mo) ans%=mo;
	return ans;
}

inline void addedge(ll u,ll v) {
	ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
	ll ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
	return ret*f;
}

inline void write(ll x) {
	static char buf[22];static ll len=-1;
	if(x>=0) {
		do{buf[++len]=x%10+48;x/=10;}while(x);
	}
	else {
		putchar('-');
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {
	write(x);putchar('\n');
}

inline bool cmp(node x,node y) {
	return x.id<y.id;
}

int main() {
	
	n=read();rt=1;mo=998244353;inv=pow(100,mo-2);

	for(ll i=1;i<=n;i++) a[i]=1;
	
	for(ll i=1;i<=n;i++) {b[i]=read();}
	
	for(ll i=1;i<n;i++) {u=read();v=read();addedge(u,v);addedge(v,u);}
	
	dfs(rt,0);_dfs(rt,0,rt);build(1,1,n);
	
	for(ll i=1;i<=n;i++) {
		c[i].id=i;c[i].dt=dt[i];c[i].p=(100-b[i]+mo)*inv%mo;
	}

	sort(c+1,c+n+1);

	ll L=1,R=0;

	for(ll i=1;i<=n;i++) {
		if(c[i].dt==c[i+1].dt) continue;
		R=i;
		for(ll j=L;j<=R;j++) {
			c[j].ans=qpath(1,c[j].id);
		}
		for(ll j=L;j<=R;j++) {
			mulpath(1,c[j].id,c[j].p);
		}
		L=i+1;
	}

	sort(c+1,c+n+1,cmp);

	for(ll i=1;i<=n;i++) {
		writeln(c[i].ans);
	}
	
	return 0;
}

D.

这个题一个暴力的想法是 $O(n^2)$ 的，实际上就是做一个暴力的背包。

事实上，循环的顺序会极大影响程序的效率。

同机房一堆人使用循环展开加 $O(fast)$ 直接碾掉了这个题，然而我还在想怎么用 NTT。。。

这个题的 NTT 看似不太可做，实则需要一些奇技淫巧。

假如说是 $0$ 和 $1$ 的卷积，显然相乘就是正确的。

那么就可以这样干：如果说一个数大于等于一个常数 $k$，我们就把这个系数当作 $1$，否则当作 $0$。然后得到了两个生成函数，直接 NTT 即可。

那么剩下的肯定还有一点边边角角的数值，我们可以暴力处理。

比较偷懒的话可以直接取一个 $k=100$ 或 $k=1000$ 什么的，这样算下来大概就可以过了。

但是我不会写。

代码（$O(n^2)$）：

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
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll int
using namespace std;

const ll N=2e5;

ll n,res;

ll a[N+5],b[N+5],g[N+5],f[N+5],ans[N+5];

inline ll read() {
	ll ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
	return ret*f;
}

inline void write(ll x) {
	static char buf[22];static ll len=-1;
	if(x>=0) {
		do{buf[++len]=x%10+48;x/=10;}while(x);
	}
	else {
		putchar('-');
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

int main() {
	
	n=read();

	ll tmp1=0,tmp2=0;

	for(ll i=1;i<=n;i++) {
		a[i]=read();f[a[i]]++;
		tmp1=max(tmp1,a[i]);
	}

	for(ll i=1;i<=n;i++) {
		b[i]=read();g[b[i]]++;
		tmp2=max(tmp2,b[i]);
	}

	for(ll i=1;i<=tmp1;i++) {
		for(ll j=1;j<=tmp2;j++) {
			ans[i+j]+=min(f[i],g[j]);
		}
	}

	for(ll i=1;i<=tmp1+tmp2;i++) {
		res=max(res,ans[i]);
	}

	write(res);
	
	return 0;
}