test20191021

发表于

题面

题面

$T1$

Solution

看一看样例，发现是每次能向下跳两步就跳两步，没法就一步或者往回跳，模拟一下即可。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 3e5+5;
int n,u,v,head[MAXN],num_edge,ans[MAXN],cnt;
char tr[MAXN];
struct Edge{
	int next,to;
	Edge(){}
	Edge(int next,int to):next(next),to(to){}
}edge[MAXN<<1];
il add_edge(int u,int v){
	edge[++num_edge]=Edge(head[u],v),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u),head[v]=num_edge;
}
il DFS(int u,int fa){
	tr[u]=1,ans[++cnt]=u;
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		ri pos=edge[i].to;
		for(ri j=head[pos];j;j=edge[j].next){
			if(tr[edge[j].to]) continue;
			DFS(edge[j].to,pos);
		}
		ans[++cnt]=pos,tr[pos]=1;
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n);
	for(ri i=1;i<n;++i) read(u),read(v),add_edge(u,v);
	DFS(1,0);
	puts("Yes");
	for(ri i=1;i<=n;++i) print(ans[i]),putchar(' ');
	return 0;
}

$T2$

Solution

先简化一下题意：给一个序列，再给出几个形如 $(l,r)$ 的条件，表示 $[l,r]$ 中至少要删去一个数。求一个方案，使得删去的数的总和最小。

我们考虑这样一件事：当 $r_i=r_j$ 时，我们显然只需要删除在 $\max(l_i,l_j)\sim r$ 中的一个数即可（贪心）。

所以我们可以对所有 $r$ 相同的限制，我们取一个左端点的最大值来作为最终的左端点。

我们设 $dp_i$ 表示删除第 $i$ 个，且 $[1,i-1]$ 中不存在禁忌词的最小花费。显然，最后的答案为 $dp_{n+1}$ 。

考虑转移。

假设在 $1\sim i-1$ 中最大的 $l$ 为 $L$ ，那么我们显然只能从 $L\sim i-1$ 中的 $dp$ 转移过来。（因为要保证之前的所有条件都满足）。

因为要代价最小，所以我们相当于求 $\min_{j=L}^{i-1}dp_j$ 。

因为 $L$ 是单调不降的，所以我们可以用单调队列优化 $dp$ 。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define ull unsigned ll
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 2e5+5;
int n,m,val[MAXN],len[MAXN],f[MAXN],le[MAXN],q[MAXN],l,r;
//f[i]: delete i , the min cost to let 1 ~ i - 1 don't have dangerous words
char s[MAXN],t[11][MAXN];
ull H[MAXN],p[MAXN],H1[11][MAXN];
inl ull calc(int l,int r){return H[r]-H[l-1]*p[r-l+1];}
il init(){
	p[0]=1;
	for(ri i=1;i<=n;++i) H[i]=H[i-1]*131+s[i]-'a'+1,p[i]=p[i-1]*131;
	for(ri j=1;j<=m;++j)
		for(ri i=1;i<=len[j];++i)
			H1[j][i]=H1[j][i-1]*131+t[j][i]-'a'+1;
	for(ri j=1;j<=m;++j)
		for(ri i=len[j];i<=n;++i)
			if(calc(i-len[j]+1,i)==H1[j][len[j]])
				le[i]=max(le[i],i-len[j]+1);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	scanf("%s",s+1);
	for(ri i=1;i<=n;++i) read(val[i]);
	for(ri i=1;i<=m;++i) scanf("%s",t[i]+1),len[i]=strlen(t[i]+1);
	init();
	q[++r]=0;
	for(ri i=1,mx=0;i<=n+1;++i){
		while(l+1<=r&&q[l+1]<mx) ++l;
		f[i]=f[q[l+1]]+val[i];
		while(l+1<=r&&f[q[r]]>=f[i]) --r;
		q[++r]=i;
		mx=max(mx,le[i]);
	}
	print(f[n+1]);
	return 0;
}

$T3$

Solution

可以发现两个端点是互不影响的，所以我们可以算出每一端的答案，再乘起来。

明显的，我们可以知道每一条链上只能选一个点，且有且仅有一个能放在该链上。

我们可以先处理出每一个点所有的子树中选 $i$ 的答案。

这样做的复杂度为 $O(\sum_{i=1}^{n} d_i^2)=O(n\cdot L)$ 。

在查询时，我们需要删去一个子树的贡献，我们是可以推出删去之后的贡献的（详细见代码）。

然后我们即可以直接计算了。

对于计算答案的时候，我们采取如下策略：

其中 $i$ 枚举的是有几个选则了链上的点， $s$ 表示一种合法的选取方式， $S$ 表示所有的选取方式的集合，即 $dp_{u,i}$ 。

$i!$ 是由于之前没有确定顺序，需要求个排列， $C_k^i$ 是由于我们需要确定这 $k$ 个中哪几个用的是链上的点。

$i!\cdot C_k^i$ 还有一种理解方式是：这 $k$ 个位置中，第一个点有 $k$ 种放法，第二个点有 $k-1$ 种放法，以此类推，一共有 $\frac{k!}{(k-i)!}$ 种方式，这其实是一个下降幂，计算时即为前面的东西。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 1e5+5,mod = 998244353;
int n,m,L,u,v,k,head[MAXN],num_edge,dp[MAXN][505];
struct Edge{
	int next,to;
	Edge(){}
	Edge(int next,int to):next(next),to(to){}
}edge[MAXN<<1];
il add_edge(int u,int v){
	edge[++num_edge]=Edge(head[u],v),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u),head[v]=num_edge;
}
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
int f[MAXN][18],dep[MAXN],sz[MAXN],deg[MAXN];
il DFS(int u,int fa){
	sz[u]=1,f[u][0]=fa,dep[u]=dep[fa]+1;
	for(ri i=1;i<=17;++i) f[u][i]=f[f[u][i-1]][i-1];
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		DFS(edge[i].to,u);
		sz[u]+=sz[edge[i].to];
	}
}
it LCA(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(ri i=17;i>=0;--i) if(dep[f[u][i]]>=dep[v]) u=f[u][i];
	if(u==v) return u;
	for(ri i=17;i>=0;--i)
		if(f[u][i]!=f[v][i])
			u=f[u][i],v=f[v][i];
	return f[u][0];
}
it jump(int u,int lca){//找到u到lca这条路径上除了lca外深度最小的点
	for(ri i=17;i>=0;--i)
		if(dep[f[u][i]]>dep[lca])
			u=f[u][i];
	return u;
}
il calc(int u){//dp[u][i]表示在u的子树中选择其中i颗上的点的方案数。
	dp[u][0]=1;
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==f[u][0]) continue;
		for(ri j=deg[u];j;--j)
			dp[u][j]=add(dp[u][j],mul(dp[u][j-1],sz[edge[i].to]));
	}
	for(ri i=deg[u];i;--i)
		dp[u][i]=add(dp[u][i],mul(dp[u][i-1],n-sz[u]));
}
int fac[MAXN],ifac[MAXN],inv[MAXN];
il init(){
	for(ri i=1;i<=n;++i) calc(i);
	fac[0]=ifac[0]=inv[1]=1;
	for(ri i=1;i<=L;++i) fac[i]=mul(fac[i-1],i);
	ifac[L]=qpow(fac[L],mod-2,mod);
	for(ri i=L-1;i;--i) ifac[i]=mul(ifac[i+1],i+1);
	for(ri i=2;i<=n;++i) inv[i]=mul(mod-mod/i,inv[mod%i]);
}
it C(int n,int m){return mul(fac[n],mul(ifac[n-m],ifac[m]));}
int ans[MAXN],tmp[MAXN];
it solve(int u,int k,int t){
	for(ri i=1;i<=deg[u];++i) ans[i]=0;//ans表示在背包中去掉大小为t的部分后的答案
	for(ri i=1;i<=deg[u];++i) tmp[i]=dp[u][i]; //tmp表示原来的答案
	//由于背包问题具有交换性（加入背包顺序可以改变），所以我们可以看做t是最后被加入背包的
	//因为我们有tmp[i]=ans[i]+ans[i-1]*sz，且在加入最后一个之前dp[deg[u]]=0，所以我们可以倒着推出ans[i]
	//即ans[i-1]=(tmp[i]-ans[i])/sz
	for(ri i=deg[u];i;--i){
		ans[i-1]=mul(tmp[i],inv[t]);
		tmp[i]=0,tmp[i-1]=add(tmp[i-1],mod-ans[i-1]);
	}
	ri res=0;
	for(ri i=0;i<=min(deg[u],k);++i) res=add(res,mul(mul(fac[i],ans[i]),C(k,i)));
	//见上面的详细分析
	printf("u=%d res=%d\n",u,res);
	for(ri i=0;i<=min(deg[u],k);++i) printf("%d ",ans[i]);puts("");
	return res;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),read(L);
	for(ri i=1;i<n;++i) read(u),read(v),add_edge(u,v),++deg[u],++deg[v];
	DFS(1,0);
	init();
	for(ri i=1;i<=m;++i){
		read(u),read(v),read(k);
		if(dep[u]<dep[v]) swap(u,v);
		ri lca=LCA(u,v);
		if(lca!=v) print(mul(solve(u,k,n-sz[u]),solve(v,k,n-sz[v]))),puts("");
		else{
			ri t=jump(u,lca);
			print(mul(solve(u,k,n-sz[u]),solve(v,k,sz[t]))),puts("");
		}
	}
	return 0;
}