test20200116

发表于

闲扯

我怎么又被卡常了呀！ $map$ 常数是真的垃圾。。。

$T1$

Solution

我们将所有点按照 $x$ 为第一关键字， $y$ 为第二关键字的顺序排序，然后我们可以发现一个奥妙重重的事：若 $a,b$ 匹配， $p,q$ 匹配，且满足 $aq$ 。

我们枚举第一对匹配的点为 $a,b$ ，显然 $a$ 之前， $b$ 之后没有匹配的点个数之和不超过 $k$ 。

所以 $a\in[0,k+1],b\in[n-k,n]$ ，我们直接 $k^2$ 枚举，然后使用双指针 $O(n)$ 判断当前情况是否合法即可。

关于双指针判断：如果两端加起来合法，那么 $l+1,r-1$ ，否则，如果加起来小于希望的， $l+1$ ，否则 $r-1$ 。

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
#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 = 1e5+5;
int n,m,x,y,ans;
struct Node{
	int x,y;
	bool operator < (const Node &t) const {
		return x==t.x?y<t.y:x<t.x;
	}
	bool operator == (const Node &t) const {
		return x==t.x&&y==t.y;
	}
	Node operator + (const Node &t) const {
		return (Node){x+t.x,y+t.y};
	}
}node[N];
it Solve(Node x){
	int sum=0;
	for(ri l=1,r=n;l<=r;){
		if(node[l]+node[r]==x)
			++l,--r;
		else{
			++sum;
			if(node[l]+node[r]<x) ++l;
			else --r;
		}
	}
	return sum<=m;
}
map<Node,char> vis;
int main(){
	freopen("chess.in","r",stdin);
	freopen("chess.out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i){
		read(x),read(y);
		node[i]=(Node){x,y};
	}
	if(m>=n) return puts("-1"),0;
	sort(node+1,node+1+n);
	for(ri i=1;i<=m+1;++i)
		for(ri j=0;j<=m;++j)
			if(!vis[node[i]+node[n-j]]){
				vis[node[i]+node[n-j]]=1;
				ans+=Solve(node[i]+node[n-j]);
			}
	print(ans);
	return 0;
}

$T2$

Solution

我考试的时候，最开始完全想偏了，最后有点思路，没时间写了。。。

设 $dp_{t,l,r}$ 表示前 $t$ 行连通，且第 $t$ 行剩的是区间 $(l,r]$ 的概率。

我们有一个十分简单的转移：

条件是 $(l,r] \cap (lp,rp]\not= \empty$ ， $p_{l,r}$ 表示 $k$ 天后剩下区间 $(l,r]$ 的概率。

显然， $p_{l,r}=p_l\times p_{m-r}$ ，而 $p_l=\binom{l}{k}\cdot p^l\cdot (1-p)^{k-l}$ 。

现在，我们定义：

我们可以推出：

我们将 $dp_{t,l,r}$ 代入上面的式子里：

我们只需要处理 $p$ 的前缀和， $p_i\cdot sum1_{t-1,i}$ 的前缀和，以及 $p_{m-i}\cdot sum2_{t-1,i}$ 的前缀和即可 $O(nm)$ 求出答案。

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
#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 MAXN = 1e5+5,N = 2e3+5,mod = 1e9+7;
int n,m,k,a,b,p,q,fac[MAXN],ifac[MAXN],P[N],s[N],S[2][N],dp[2][N][N],sum[2][N][N];
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 C(int n,int m){return m>n?0:mul(mul(ifac[m],ifac[n-m]),fac[n]);}
int main(){
	freopen("camp.in","r",stdin);
	freopen("camp.out","w",stdout);
	read(n),read(m),read(a),read(b),read(k);
	p=mul(a,qpow(b,mod-2,mod)),q=add(1,mod-p);
	fac[0]=1;
	for(ri i=1;i<=k;++i)
		fac[i]=mul(fac[i-1],i);
	ifac[k]=qpow(fac[k],mod-2,mod);
	for(ri i=k-1;i>=0;--i)
		ifac[i]=mul(ifac[i+1],i+1);
	for(ri i=0;i<=min(m,k);++i)
		P[i]=mul(mul(qpow(p,i,mod),qpow(q,k-i,mod)),C(k,i));
	s[0]=P[0];
	for(ri i=1;i<=m;++i)
		s[i]=add(s[i-1],P[i]);
	sum[0][0][m]=1,sum[1][0][0]=1;
	for(ri i=1;i<=n;++i){
		for(ri j=1;j<=m;++j){
			dp[0][i][j]=mul(s[j-1],sum[0][i-1][m]);
			inc(dp[0][i][j],mod-S[0][j-1]);
			inc(dp[0][i][j],mod-mul(s[j-1],sum[1][i-1][j]));
			dp[0][i][j]=mul(dp[0][i][j],P[m-j]);
		}
		for(ri j=0;j<m;++j){
			dp[1][i][j]=mul(s[m-j-1],sum[0][i-1][m]);
			inc(dp[1][i][j],mod-mul(s[m-j-1],sum[0][i-1][j]));
			inc(dp[1][i][j],mod-S[1][j+1]);
			dp[1][i][j]=mul(dp[1][i][j],P[j]);
		}
		for(ri j=1;j<=m;++j)
			sum[0][i][j]=add(sum[0][i][j-1],dp[0][i][j]);
		for(ri j=m-1;j>=0;--j)
			sum[1][i][j]=add(sum[1][i][j+1],dp[1][i][j]);
		for(ri j=0;j<m;++j)
			S[0][j]=mul(P[j],sum[0][i][j]);
		for(ri j=1;j<m;++j)
			inc(S[0][j],S[0][j-1]);
		for(ri j=1;j<=m;++j)
			S[1][j]=mul(P[m-j],sum[1][i][j]);
		for(ri j=m-1;j;--j)
			inc(S[1][j],S[1][j+1]);
	}
	print(sum[0][n][m]);
	return 0;
}

$T3$

Solution

我们先做出 $A$ 边的最小生成树，我们计作 $G$ 。

假设当前的 $x$ 为 $-\infty$ 。显然，此时整幅图的最小生成树就是由 $A$ 边构成的最小生成树。

我们考虑从小到大依次加入 $B$ 边。

我们找出 $G$ 中 $u\rightarrow v$ 这条链上还没断掉的边权最大的边。

显然我们可以算出一个临界值 $k$ ，使得 $x=k$ 时，加入该边和 $B$ 边答案一样，而 $x>k$ 时， $B$ 边更优。所以我们在 $x=k$ 时断掉这条边，而加入 $B$ 边。

显然，我们最多会断掉 $n-1$ 条边，之后就全部都是 $B$ 边了。

但是每条边的临界值是不同的，可能边权更大的边临界值更小。

那么是怎么保证正确性的呢？

假设 $G$ 上的一条边同时被值为 $a,b(a<b)$ 的两条 $B$ 边覆盖。

显然，边权为 $a$ 的边会更早替换这条边。所以边权为 $b$ 的边只能选择另外的边替换。

我们按照临界值从大到小依次换边，同时处理出答案即可。

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#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 = 4e5+5;
int n,A,B,q,u,v,d,fa[N],val[N];
ll sum,ans[N];
struct Edge{
	int u,v,dis;
	bool operator < (const Edge &t) const {
		return dis<t.dis;
	}
}a[N],b[N],edge[N];
int ch[N][2],f[N],mx[N],stk[N];
char rev[N];
#define lc ch[x][0]
#define rc ch[x][1]
inl bool Not_root(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
il pushup(int x){
	mx[x]=x;
	if(lc) if(val[mx[lc]]>val[mx[x]]) mx[x]=mx[lc];
	if(rc) if(val[mx[rc]]>val[mx[x]]) mx[x]=mx[rc];
}
il pushrev(int x){swap(lc,rc),rev[x]^=1;}
il pushdown(int x){
	if(rev[x]){
		if(lc) pushrev(lc);
		if(rc) pushrev(rc);
		rev[x]=0;
	}
}
il Rotate(int x){
	int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
	if(Not_root(y)) ch[z][ch[z][1]==y]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) f[w]=y;
	f[x]=z,f[y]=x,pushup(y);
}
il Splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(Not_root(y)) stk[++top]=y=f[y];
	while(top) pushdown(stk[top--]);
	while(Not_root(x)){
		int y=f[x],z=f[y];
		if(Not_root(y)) Rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		Rotate(x);
	}
	pushup(x);
}
il Access(int x){
	for(ri y=0;x;x=f[y=x])
		Splay(x),rc=y,pushup(x);
}
il Make_root(int x){Access(x),Splay(x),pushrev(x);}
it Find_root(int x){
	Access(x),Splay(x);
	while(lc) pushdown(x),x=lc;
	Splay(x);return x;
}
il Split(int x,int y){Make_root(x),Access(y),Splay(y);}
il Link(int x,int y){Make_root(x),f[x]=y;}
il Cut(int x,int y){Split(x,y),f[x]=ch[y][0]=0,pushup(y);}
pair<int,int> ques[N];
pair<double,int> change[N];
it find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	read(n),read(A),read(B),read(q),del(val,-0x3f);
	for(ri i=1;i<=A;++i){
		read(u),read(v),read(d);
		a[i]=(Edge){u,v,d};
	}
	for(ri i=1;i<=B;++i){
		read(u),read(v),read(d);
		b[i]=(Edge){u,v,d};
	}
	sort(a+1,a+1+A);
	for(ri i=1;i<=n;++i) fa[i]=i;
	for(ri i=1,cnt=0;i<=A;++i){
		u=a[i].u,v=a[i].v;
		if(find(u)==find(v)) continue;
		fa[find(u)]=find(v);
		++cnt,sum+=a[i].dis;
		val[cnt+n]=a[i].dis,Link(u,cnt+n),Link(cnt+n,v);
		edge[cnt]=a[i];
		if(cnt==n-1) break;
	}
	sort(b+1,b+1+B);
	for(ri i=1;i<=n;++i) fa[i]=i;
	for(ri i=1,cnt=0;i<=B;++i){
		u=b[i].u,v=b[i].v;
		if(find(u)==find(v)) continue;
		fa[find(u)]=find(v),++cnt;
		Split(u,v);
		int t=val[mx[v]],pos=mx[v];
		if(t==-INF) change[cnt]=make_pair(INF,b[i].dis-t);
		else{
			change[cnt]=make_pair((b[i].dis-t)/2.,b[i].dis-t);
			Cut(pos,edge[pos-n].u),Cut(pos,edge[pos-n].v);
			Link(2*n+cnt,u),Link(2*n+cnt,v);
		}
		if(cnt==n-1) break;
	}
	sort(change+1,change+n);
	for(ri i=1;i<=q;++i)
		read(d),ques[i]=make_pair(d,i);
	sort(ques+1,ques+1+q);
	for(ri i=1,now=1;i<=q;++i){
		while(now<n&&change[now].first<=ques[i].first)
			sum+=change[now].second,++now;
		ans[ques[i].second]=sum+1ll*ques[i].first*(n-2*now+1);
	}
	for(ri i=1;i<=q;++i)
		print(ans[i]),puts("");
	return 0;
}