test20200115

发表于

闲扯

终于有一道考试能想出做法而且不会打炸的题了泪目。

$T1$

Solution

由于要使得距离最大，我们考虑贪心的进行匹配。

假设对边 $(u,v)$ 来说，它的一边有 $j$ 个男生，有 $k$ 个女生，那么我们一定有 $\min(j,m-k)$ 个男生和另外一边的女生配对，有 $\min(k,m-j)$ 个女生和另外一边的男生配对。

那么该边贡献就为 $w\cdot (\min(j,m-k)+\min(k,m-j))$ ，化简一下得到： $w\cdot \min(j+k,2m-j-k)$ 。

一共有 $\binom{m}{j}\cdot \binom{m}{k}$ 种分配方法，每个人的站位共有 $sz^{j+k}\cdot (n-sz)^{2m-j-k}$ 种，其中 $sz$ 为深度较深的点所在子树大小。

将每条边的权值下放到深度较深的点上，那么我们得到答案为：

至此我们得到了一个 $O(n^3)$ 的做法。

考虑优化。我们可以发现当 $j+k$ 确定时，变化的部分只有 $\sum_{j=0}^m\sum_{k=0}^m \binom{m}{j}\cdot \binom{m}{k}$ 。

我们只需要将其预处理出来，然后枚举 $j+k$ 即可做到 $O(n^2)$ 。

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
#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;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 5e3+5,mod = 1e9+7;
int n,m,u,v,d,ans,val[N],sz[N],fac[N],ifac[N],c[N],sum[N],pw[N][N],head[N],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;}
il inc(int &x,int y){x=add(x,y);}
it max(int x,int y){return x>y?x:y;}
it min(int x,int y){return x<y?x:y;}
struct Edge{int next,to,dis;}edge[N<<1];
il add_edge(int u,int v,int dis){
	edge[++num_edge]=(Edge){head[u],v,dis},head[u]=num_edge;
	edge[++num_edge]=(Edge){head[v],u,dis},head[v]=num_edge;
}
il DFS(int u,int fa){
	sz[u]=1;
	for(ri i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa) continue;
		DFS(v,u),sz[u]+=sz[v];
		val[v]=edge[i].dis;
	}
}
it C(int n,int m){return mul(mul(ifac[m],ifac[n-m]),fac[n]);}
int main(){
	freopen("class.in","r",stdin);
	freopen("class.out","w",stdout);
	read(n),read(m),fac[0]=1;
	for(ri i=1;i<=m;++i)
		fac[i]=mul(fac[i-1],i);
	ifac[m]=qpow(fac[m],mod-2,mod);
	for(ri i=m-1;i>=0;--i)
		ifac[i]=mul(ifac[i+1],i+1);
	for(ri i=1;i<=n;++i){
		pw[i][0]=1;
		for(ri j=1;j<=2*m;++j)
			pw[i][j]=mul(pw[i][j-1],i);
	}
	for(ri i=1;i<n;++i){
		read(u),read(v),read(d);
		add_edge(u,v,d);
	}
	DFS(1,0);
	for(ri i=0;i<=m;++i)
		c[i]=C(m,i);
	for(ri i=0;i<=2*m;++i)
		for(ri j=0;j<=min(i,m);++j)
			inc(sum[i],mul(c[j],c[i-j]));
	for(ri i=1;i<=n;++i){
		for(ri j=0;j<=2*m;++j){
			int res=mul(pw[sz[i]][j],pw[n-sz[i]][2*m-j]);
			res=mul(res,min(j,2*m-j)),res=mul(res,sum[j]);
			inc(ans,mul(res,val[i]));
		}
	}
	print(ans);
	return 0;
}

$T2$

Solution

处理环上问题，我们先将环拆成链。

由于相邻的不能相同，我们在每个相邻处经链断开，这样链就变成了几段，每次只需要考虑端点是否相同即可。

我们考虑一个长为 $k$ 的链是否可行，如果可行的话，那么对应的删去 $n-k$ 个就是可行的。

对于每一段，我们枚举长度 $k$ ，只要满足 $s[l\cdots r-k+1]\not=s[l+k-1\cdots r]$ ，我们即可找出至少一组可行解。

这个可以用字符串 $hash$ 解决。

时间复杂度上界为 $O(n)$ ，可能跑不满。

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
#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;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 5e6+5;
int n,sum[N<<1];
char s[N<<1],vis[N];
unsigned ll H[N<<1],p[N<<1];
il Init(){
	int m=n<<1;
	for(ri i=1;i<=m;++i)
		H[i]=H[i-1]*131+(s[i]-'a'+1);
}
unsigned ll Calc(int l,int r){return H[r]-H[l-1]*p[r-l+1];}
il Solve(int l,int r){
	int len=min(r-l+1,n);
	for(ri i=2;i<=len;++i){
		if(vis[n-i]) continue;
		if(Calc(l,r-i+1)==Calc(l+i-1,r)) continue;
		vis[n-i]=1;
	}
}
int main(){
	freopen("loop.in","r",stdin);
	freopen("loop.out","w",stdout);
	p[0]=1;
	for(ri i=1;i<=N+N-10;++i)
		p[i]=p[i-1]*131;
	while(~scanf("%s",s+1)){
		n=strlen(s+1),vis[0]=0;
		for(ri i=1;i<=n;++i)
			s[i+n]=s[i],vis[i]=0;
		Init();
		int pre=1,m=n<<1;
		for(ri i=2;i<=m;++i)
			if(s[i]==s[i-1])
				Solve(pre,i-1),pre=i;
		Solve(pre,m);
		for(ri i=0;i<n;++i)
			print(vis[i]);
		puts("");
	}
	return 0;
}