The 2020 ICPC Asia Macau Regional Contest

发表于 分类于

链接

题目链接

题解

A.Accelerator

对于一个长度为 $k$ 的数组，方案数是确定的，为 $k!(n-k)!$。问题转换成对于每个 $k$，从 $n$ 个数里选择 $k$ 个的乘积之和。

显然为 $[x^k]\prod_{i=1}^n(a_ix+1)$。

分治FFT即可。

15min从开始想到写完，速度还行。。

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
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
const int M=1<<20;
ll W[M];
int R[M];
inline void PolyInit()
{
	ll w;
	for(int i=1;i<M;i<<=1)
	{
		W[i]=1; w=Pow(3,(mod-1)/2/i);
		fo(j,1,i-1) W[i+j]=W[i+j-1]*w%mod;
	}
}

inline void ntt(ll *a,int n,int opt)
{
	fo(i,0,n-1)
	{
		R[i]=(R[i>>1]>>1)|((i&1)*(n>>1));
		if(i<R[i]) swap(a[i],a[R[i]]);
	}
	ll w;
	for(int i=1;i<n;i<<=1)
		for(int j=0;j<n;j+=(i<<1))
			for(int k=0;k<i;k++)
			{
				w=W[i+k]*a[i+j+k]%mod;
				a[i+j+k]=Dec(a[j+k],w);
				a[j+k]=Add(a[j+k],w);
			}
	if(opt==1) return;
	reverse(a+1,a+n);
	w=Pow(n,mod-2);
	fo(i,0,n-1) a[i]=a[i]*w%mod;
}
typedef vector<ll> Poly;
inline void ntt(Poly &A,int n,int t)
{
	ntt(&A[0],n,t);
}
inline Poly operator *(Poly A,Poly B)
{
	int n=A.size(),m=B.size(),k=n+m-1,len=1;
	for(;len<k;len<<=1);
	A.resize(len); ntt(A,len,1);
	B.resize(len); ntt(B,len,1);
	fo(i,0,len-1) A[i]=A[i]*B[i]%mod;
	ntt(A,len,-1);
	A.resize(k);
	return A;
}
const int N=100010;
int n,a[N];
Poly solve(int l,int r)
{
	if(l==r)
	{
		Poly B; B.clear();
		B.pb(1); B.pb(a[l]);
		return B;
	}
	int mid=(l+r)>>1;
	return solve(l,mid)*solve(mid+1,r);
}
ll inv[N],fac[N];
inline void init(int n)
{
	fac[0]=1;
	fo(i,1,n) fac[i]=fac[i-1]*i%mod;
	inv[n]=Pow(fac[n],mod-2);
	fd(i,n,1) inv[i-1]=inv[i]*i%mod;
}
Poly A;
int main()
{
	PolyInit();
	init(100000);
	CASET
	{
		n=read();
		fo(i,1,n) a[i]=read();
		A=solve(1,n);
		ll ans=0;
		fo(i,1,n)
			ans=Add(ans,A[i]*fac[i]%mod*fac[n-i]%mod);
		printf("%lld\n",ans*inv[n]%mod);
	}
	return 0;
}

B.Boring Problem

一个显然的做法是：建出AC自动机以后在上面dp，由于有后效性，需要使用高斯消元，时间复杂度 $O((nm)^3)$，没有办法通过。

考虑使用主元法。设 $dep_u$ 表示节点 $u$ 在Trie中的深度。设 $F(x)=0$ 为节点 $x$ 的一个方程。那么有：

$F(x)=1+\sum_{i=1}^kp_iF(ne_{x,i})$。

对于每个方程，可以发现，有些 $ne_{x,i}$ 的深度是大于 $x$ 的，此时 $ne_{x,i}$ 必为 $x$ 在原 Trie中的儿子。

考虑从上往下bfs，每遇到一个 $x$ 时，$ne_{x,i}$ 的深度小于等于 $x$ 的点的方程已经知道了。记 $ne_{x,i}$ 深度大于 $x$ 的个数为 $k$，我们新增 $k-1$ 个未知数，用这 $k-1$ 个未知数和 $F(x)$ 表示出剩下的那一个，这样就刚好有叶子结点个数+1个未知数和方程，就可以解出来了。

时间复杂度 $O(n^3+nm^2k)$。

C.Club Assignment

建出Trie，在Trie上dfs，看什么时候能取到答案。

设 $siz_i$ 表示节点 $i$ 的子树中有多少个数，$dep_i$ 表示$i$ 子树的高度。如果 $siz_{i}\geq 3$，则说明这里面当中一定有两个数在一个集合里，则说明答案至多为 $2^{dep-1}-1$。

于是，如果两个儿子的其中一个的 $siz\geq 3$，那么答案一定在子树内出现，而不用考虑当前子树。

剩下的就是两个子树的 $siz\le 2$，总个数不超过 $4$ 个，暴力枚举集合即可。

D.Artifacts

简单模拟。

E.Mountain

大毒瘤计算几何+DP。

或许是自己的实现太拉胯了。。。

对于 $[i,i+1]$ 部分，能覆盖这一段的只有在 $[i-w+1,i+w]$ 区间当中的点。

设 $f_{i,j,s}$ 表示考虑到前 $i$ 点，选了 $j$ 个，前 $2w$ 个点（包括自己）选择的情况为 $s$，只统计到 $[i-w,i-w+1]$ 段的最大值。

那么转移就是枚举上一种的情况，枚举第 $i$ 个点的选择情况，然后得到新的状态 $s_1$，统计出在 $s_1$ 状态下，$[i-w,i-w+1]$ 有多少被覆盖到，设为 $g_{i-w,s_1}$，然后转移就比较简单了。

很容易出错的是这个 $g_{i,j}$ 的计算。训练时没有考虑到覆盖部分并不是一个连续的段，而有可能会分成若干段。那么对于每个选择的点，会有一个覆盖区间，将这些区间的左右端点排序后，扫描线维护一下这个括号序列，然后对于一段覆盖的 $[l,r]$，用基础计算几何知识算出覆盖的面积即可。

时间复杂度 $O(n\times(n+w\log w)\times 2^{2w})$。

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
#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=205;
db f[N+20][N][(1<<10)+5];
db g[N+20][1<<11];
int n,w,h,m,a[N+20],tot;
inline bool check(int x){return (x>=2*w+1)&&(x<=n+2*w);}
inline bool check2(int x){return x>=2*w&&x<=n+2*w;}
int mx,mi;
inline db calc(int l,int r)
{
	if(r<=0) return 0;
	db x,y;
	if(l<0) l=0;
	if(l>=r) return 0;
	if(l>=mx) return 0;
	if(l<=mi)
	{
		if(r<=mi)
			return 0.0+r-l;
		else
			if(r>=mx)
				return (0.0+mx-l+mi-l)/2.;
			else
			{
				x=(0.0+mx-r)/(0.0+mx-mi);
				return (0.0+mx-l+mi-l)/2.-x*(mx-r)/2.;
			}
	}
	else
	{
		if(r>=mx)
		{
			x=(0.0+mx-l)/(0.0+mx-mi);
			return x*(mx-l)/2.;
		}
		else
		{
			x=(0.0+mx-r)/(mx-mi);
			y=(0.0+mx-l)/(mx-mi);
			return (x+y)*(r-l)/2.;
		}
	}
}
struct node{
	int x,id;
	friend inline bool operator<(const node &A,const node &B)
	{
		return (A.x!=B.x)?A.x<B.x:A.id<B.id;
	}
};
node st[23];
int top;
inline void init()
{
	int l,r,now=0;
	top=0;
	fo(i,2*w,n+2*w)
	{
		ff(s,0,tot)
		{
			mx=max(a[i],a[i+1]);
			mi=min(a[i],a[i+1]);
			bool flag=0;
			top=0;
			ff(j,0,w<<1)
				if((1<<j)&s)
				{
					if(check(i+w-j))
					{
						st[++top]=(node){a[i+w-j]-h,0};
						st[++top]=(node){a[i+w-j]+h,1};
					}
					else{flag=1; break;}
				}
			if(flag||s==0)
			{
				g[i][s]=0;
				continue;
			}
			sort(st+1,st+top+1);
			int pre=0;
			now=0;
			fo(k,1,top)
			{
				if(st[k].id==0)
				{
					now++;
					if(now==1) pre=st[k].x;
				}
				else now--;
				if(!now)
					g[i][s]+=calc(pre,st[k].x);
			}
		}
	}

}
inline void solve(int n,int m,int w)
{
	int t=(1<<(2*w-1))-1,s1;
	fo(i,0,n+2)
		fo(j,0,m)
			ff(s,0,tot)
				f[i][j][s]=-100000000000.00;
	f[2*w][0][0]=0;
	fo(i,2*w+1,n+2)
	{
		fo(j,0,m)
			ff(s,0,tot)
			{
				s1=((s&t)<<1);
				if(f[i-1][j][s]>=0)
					f[i][j][s1]=max(f[i][j][s1],f[i-1][j][s]+g[i-w][s1]);
				s1++;
				if(j&&f[i-1][j-1][s]>=0&&i<=m+(w<<1))
					f[i][j][s1]=max(f[i][j][s1],f[i-1][j-1][s]+g[i-w][s1]);
			}
	}
	fo(i,1,m) printf("%.12lf\n",f[n+2][i][0]);
}
int main()
{
	n=read(); w=read(); h=read();
	tot=1<<(2*w);
	fo(i,1,n) a[i+2*w]=read();
	m=n+4*w;
	init();
	solve(m,n,w);
	return 0;
}

F.Fixing Networks

构造题。

除去特殊情况后，剩下的每次用 $d+1$ 个点形成的完全图去用掉一个颜色。最后剩下 $m=n-(d+1)(c-1)$ 个点，需要每个点的度数为 $d$，且图连通。

那么对于 $d$ 为偶数的情况，每个点 $i$ 向 $(i+j)\bmod m(j\le \frac{d}{2})$ 连边。

$d$ 为奇数也同理，每个点多连一条边即可。

G.Game on Sequence

设 $f_i$ 表示从 $i$ 开始是否必胜。

那么对于所有的 $j$ 满足题意，只要有一个 $f_j=0$，那么 $f_i=1$，否则 $f_i=0$。

对于一个 $i,j$，满足 $i<j$ 且 $a_i=a_j$，那么 $f_i$ 必定为 $1$：

  1. 若 $f_j=0$，显然 $f_i=1$。

  2. 若 $f_j=1$，那么存在一个 $k$，使得 $j$ 能到 $k$ 且 $f_k=0$，那么这个 $i$ 也能到 $k$，因此 $f_i=1$。

于是设 $las_i$ 表示 $a_j=i$ 的最大的下标 $j$，若 $i\neq las_{a_i}$，那么 $f_i=1$，

否则暴力枚举剩下的情况。

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

H.Fly Me To The Moon

留坑…

I.Nim Cheater

设 $f_{u,i}$ 表示点 $u$ 的路径中，异或和为 $i$ 的最大值。

方程为 $f_{u,i}=f_{fa_u,i\bigoplus a_u}+val_u$。

为了使空间比较小，可以用如下性质：

重链剖分后，每个点到根节点的路径中，遇到到轻链的个数不超过 $\log_2 n$。

于是，设 $f’_{dep,i}$ 表示当前点到树上路径中，遇到轻链个数为 $dep$ 时的DP值。

类似于树上启发式合并，我们先走轻链，走完后全部清空。然后走重链，走重链时 $dep$ 不更新。

这样就能保证空间复杂度为 $O(n+a\log n)$ 了。

J.Jewel Grab

设 $pre_x$ 表示 $x$ 前第一个颜色相同的下标。

那也就是找到最大的 $r$，使得 $\sum_{i=l}^r [pre_i\geq l]\le k$。

由于 $k\le 10$ 的限制，考虑每次暴力找到最大的下标 $r$ 满足大于等于当前的下标 $now$ 且 $[now,r]$ 间的 $pre$ 均小于 $l$。

线段树二分找到这个 $r$。

然后还需动态维护 $pre$ 数组，以及需要对每个颜色维护最大值，以确定需要跳过哪些数。

时间复杂度 $O(nk\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
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
#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=200010;
set<int> s[N];
int n,m,pre[N],val[N],col[N];
#define lc (u<<1)
#define rc (u<<1|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
int mi[N<<2];
ll sum[N<<2];
inline void pushup(int u)
{
	sum[u]=sum[lc]+sum[rc];
	mi[u]=max(mi[lc],mi[rc]);
}
void build(int u,int l,int r)
{
	if(l==r)
	{
		mi[u]=pre[l]; sum[u]=val[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls); build(rs);
	pushup(u);
}
void update(int u,int l,int r,int p)
{
	if(l==r)
	{
		mi[u]=pre[l]; sum[u]=val[l]; return;
	}
	int mid=(l+r)>>1;
	if(p<=mid) update(ls,p);
	else update(rs,p);
	pushup(u);
}
ll ask(int u,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return sum[u];
	int mid=(l+r)>>1;
	ll ans=0;
	if(L<=mid) ans+=ask(ls,L,R);
	if(mid<R)  ans+=ask(rs,L,R);
	return ans;
}
int query(int u,int l,int r,int p,int s)
{
	if(l==r) return l;
	int mid=(l+r)>>1;
	int ans=-1;
	if(mi[lc]>=s&&p<=mid) ans=query(ls,p,s);
	if(ans!=-1) return ans;
	if(mi[rc]>=s) ans=query(rs,p,s);
	return ans;
}
inline void change(int x,int c,int v)
{
	int y;
	val[x]=v;
	auto it=s[col[x]].lower_bound(x);
	auto it2=it;
	it--;
	it2++;
	if(it2!=s[col[x]].end())
	{
		y=(*it2); pre[y]=(*it);
		update(1,1,n,y);
	}
	
	s[col[x]].erase(x);
	col[x]=c;
	s[col[x]].insert(x);
	it2=it=s[col[x]].lower_bound(x);
	it2--;
	pre[x]=(*it2);
	update(1,1,n,x);
	it++;
	if(it!=s[col[x]].end())
	{
		y=(*it); pre[y]=x;
		update(1,1,n,y);
	}
}
int tag[N],bel[N];
int main()
{
	memset(tag,-1,sizeof(tag));
	n=read(); m=read();
	fo(i,1,n) s[i].insert(0);
	fo(i,1,n)
	{
		col[i]=read(),val[i]=read();
		pre[i]=*(--s[col[i]].end());
		s[col[i]].insert(i);
	}
	build(1,1,n);
	for(int opt,l,x,k,y,c,v;m--;)
	{
		opt=read();
		if(opt==1)
		{
			x=read(); c=read(); v=read();
			change(x,c,v);
		}
		else
		{
			l=read(); k=read();
			int now=l,r;
			bool flag=0;
			ll ans=0;
			for(;k>=0&&now<=n;k--)
			{
				r=query(1,1,n,now,l);
				assert(r<=n);
				if(r==-1)
				{
					ans+=ask(1,1,n,now,n);
					break;
				}
				if(now<r) ans+=ask(1,1,n,now,r-1);
				if(k<=0) break;
				c=col[r];
				if(tag[c]!=m)
				{
					tag[c]=m;
					bel[c]=pre[r];
				}
				if(val[r]>val[bel[c]])
				{
					ans-=val[bel[c]];
					ans+=val[r];
					bel[c]=r;
				}
				now=r+1;
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

K.Candy Ads

大毒瘤题。

2-SAT模型，关键是如何建图。

用bitset存下哪两个广告间有可能重复。

用Kosaraju算法跑出SCC，关键是如何快速跳过已选过的点。

再开两个bitset，存下 $2n$ 个点中哪些点已经遍历过了。

超级无敌卡空间，只能开得下 $50000\times 50000$ 的bitset。

过于毒瘤，并不想写代码。。。

L.Random Permutation

简单数学题，答案为 $\frac{(n!)^2}{n^n}$。