lyzlyz?lyzlyz!

这是一套比较简单的题目！

然而我依然只会打暴力。。。

做比赛的时候机房里一直是小黄歌的单曲循环=。=

T1

若一个序列插入Q个数并排序后是一个公差为P的序列，那么称该序列为PQ序列。

求序列A的最长连续子PQ序列。

此题：暴力可AC，乱搞踩标程。

YWN：枚举最小值，左右分治，85pts

DRC：枚举端点，计数排序，70pts

LYZ：splay暴力维护，加了个break优化，50pts

以上算法均可被卡成n²甚至n²logn。

下面给出标解。

首先要特判P=0的情况。

对于P>1的情况，可以利用模P的值分组，那么问题就转化为P=1的情况。

枚举R，令delta[L]=max(a[L~R])-min(a[L~R])-(R-L)，若delta[L]≤Q，那么[L,R]是PQ序列。

利用单调栈维护max和min，然后用线段树维护delta[L]，最后在线段树上询问即可。

对于重复元素的影响，可以处理出其前一个相同元素的位置pre[i]，然后在区间[max(pre[L~R]+1),R]询问即可。

T2

有n个半径为r的石柱，第i个石柱的圆心坐标为(i*d,0)，有一根起点为(0,0)，终点为((i+1)*d,0)的绳子，要求绳子必须绕过所有柱子且必须绷紧，求第k长的绳子的长度。

需要一堆balabala的讨论，在此不再赘述。

T3

有一棵n个点、每条边长度均为1的树，每次从给定的m个点中选出k个，求能经过这k个点的最短路径的长度的期望。

如果已经知道了k个点，可以先求出斯坦纳树（使特定集合联通的最小子图）的边数t以及斯坦纳树的直径d，那么答案就是2*t-d。

那么只要求出边数的期望Et和直径的期望Ed就可以解决问题了！

考虑每一条边对Et的贡献，就是该边在斯坦纳树中出现的概率。

假设切断这条边后两棵子树分别有x、y个给定点，那么该边对答案的贡献为2*(1-f(m,x,k)-f(m,y,k))。

其中f(x,y,z)表示在x个点中选出z个全在y个特殊点集合内部的概率，则：

[tex]f(x,y,z)=\frac{C^z_y}{C^z_x}[/tex]

考虑直径(x,y)对Ed的贡献，首先假设(x,y)总满足x<y且(x,y)在所有直径中字典序最小以消除多条直径对答案的影响。

那么(x,y)成为斯坦纳树直径的条件为不存在z使得：

1、dist(x,z)>dist(x,y)||(dist(x,z)==dist(x,y)&&z<y)

2、dist(y,z)>dist(x,y)||(dist(y,z)==dist(x,y)&&z<x)

假设有cnt个给定点满足以上两个条件，那么对答案的贡献就是：

[tex]-f(m-2,cnt,k-2)*\frac{C^{k-2}_{m-2}}{C^m_k}[/tex]

最终复杂度O(n²+m³)

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=300010;
const int inf=1000000007;
int n,P,Q,x,i,top,Top,now;
int a[M],b[M],A[M],B[M],C[M],pre[M],stack[M],Stack[M],st[M],St[M];
int tree[M*4],tag[M*4];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void pushdown(int p){
	int l=p<<1,r=p<<1^1;
	tree[l]+=tag[p];
	tag[l]+=tag[p];
	tree[r]+=tag[p];
	tag[r]+=tag[p];
	tag[p]=0;
}
void pushup(int p){
	tree[p]=min(tree[p<<1],tree[p<<1^1]);
}
void update(int x,int y,int l,int r,int p,int w){
	if (x==l&&y==r){
		tree[p]+=w;
		tag[p]+=w;
		return;
	}
	pushdown(p);
	int mid=l+r>>1;
	if (y<=mid)update(x,y,l,mid,p<<1,w);
		else if (x>mid)update(x,y,mid+1,r,p<<1^1,w);
			else update(x,mid,l,mid,p<<1,w),update(mid+1,y,mid+1,r,p<<1^1,w);
	pushup(p);
}
int Query(int x,int l,int r,int p){
	if (l==r)return tree[p];
	int mid=l+r>>1;
	if (x<=mid)return Query(x,l,mid,p<<1);
		else return Query(x,mid+1,r,p<<1^1);
}
int query(int x,int y,int l,int r,int p){
	if (x==l&&y==r){
		while (l<r){
			pushdown(p);
			int mid=l+r>>1;
			if (tree[p<<1]<=Q)p=p<<1,r=mid;
				else p=p<<1^1,l=mid+1;
		}
		return l;
	}
	pushdown(p);
	int mid=l+r>>1;
	if (y<=mid)return query(x,y,l,mid,p<<1);
		else if (x>mid)return query(x,y,mid+1,r,p<<1^1);
			else{
				int tmp=query(x,mid,l,mid,p<<1);
				if (Query(tmp,1,n,1)<=Q)return tmp;
					else return query(mid+1,y,mid+1,r,p<<1^1);
			}
}
int main(){
	n=read(),P=read(),Q=read();
	if (P==0){
		for (i=1;i<=n;i++)a[i]=read();
		int now=1,L=1,R=1;
		for (i=2;i<=n;i++)
			if (a[i]==a[i-1]){
				if (i-now+1>R-L+1)L=now,R=i;
			}else now=i;
		printf("%d\n",R-L+1);
		printf("%d %d\n",L,R);
		return 0;
	}
	for (i=1;i<=n;i++){
		x=read();
		x+=1000000000;
		A[i]=B[i]=x;
		a[i]=x/P;
		b[i]=x%P;
	}
	sort(B+1,B+n+1);
	int cnt=unique(B+1,B+n+1)-B-1;
	for (i=1;i<=n;i++)A[i]=lower_bound(B+1,B+cnt+1,A[i])-B-1;
	for (i=1;i<=n;i++){
		pre[i]=C[A[i]];
		C[A[i]]=i;
	}
	b[0]=-1;
	int L=0,R=-1;
	for (i=1;i<=n;i++)
		if (b[i]!=b[i-1]){
			top=Top=1;
			stack[top]=Stack[Top]=st[top]=St[Top]=i;
			now=i;
			int tmp=query(max(pre[i]+1,now),i,1,n,1);
			if (i-tmp+1>R-L+1)L=tmp,R=i;
		}else{
			if (i>1)update(now,i-1,1,n,1,-1);
			st[top+1]=i;
			int orz=i;
			while (top&&a[stack[top]]>a[i])update(st[top],st[top+1]-1,1,n,1,a[stack[top]]-a[i]),orz=st[top],top--;
			stack[++top]=i;st[top]=orz;
			St[Top+1]=i;
			orz=i;
			while (Top&&a[Stack[Top]]<a[i])update(St[Top],St[Top+1]-1,1,n,1,a[i]-a[Stack[Top]]),orz=St[Top],Top--;
			Stack[++Top]=i;St[Top]=orz;
			now=max(now,pre[i]+1);
			int tmp=query(now,i,1,n,1);
			if (i-tmp+1>R-L+1)L=tmp,R=i;
		}
	printf("%d\n",R-L+1);
	printf("%d %d\n",L,R);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=5010;
int n,m,K,i,j,k,x,y,edgenum;
double ans;
int a[M],head[M],vet[M],next[M],flag[M],mark[M],dis[2010][2010];
void addedge(int x,int y){
	vet[++edgenum]=y;
	next[edgenum]=head[x];
	head[x]=edgenum;
}
void dfs(int u,int dist){
	flag[u]=1;
	dis[i][u]=dist;
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (flag[v])continue;
		dfs(v,dist+1);
	}
}
int Dfs(int E,int u){
	flag[u]=1;
	int ans=mark[u];
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (flag[v]||e==E)continue;
		ans+=Dfs(E,v);
	}
	return ans;
}
double cal(int x,int y,int z){
	if (z>y) return 0;
	double ans=1;
	for (int i=1;i<=z;i++) ans=ans*(y-i+1)/(x-i+1);
	return ans;
}
int main(){
	scanf("%d%d%d",&n,&m,&K);
	for (i=1;i<=m;i++)scanf("%d",&a[i]),mark[a[i]]=1;
	for (i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	for (i=1;i<=n;i++){
		memset(flag,0,sizeof flag);
		dfs(i,0);
	}
	for (i=1;i<=n;i++){
		for (int e=head[i];e;e=next[e]){
			memset(flag,0,sizeof flag);
			int x=Dfs(e,i);
			int y=Dfs(e,vet[e]);
			ans+=1-cal(m,x,K)-cal(m,y,K);
		}
	}
	for (i=1;i<=m;i++)
		for (j=i+1;j<=m;j++){
			int cnt=m-2,len=dis[a[i]][a[j]];;
			for (k=1;k<=m;k++)
				if (k!=i&&k!=j&&(dis[a[i]][a[k]]>len||a[k]<a[j]&&dis[a[i]][a[k]]==len||dis[a[k]][a[j]]>len||a[k]<a[i]&&dis[a[k]][a[j]]==len))cnt--;
			ans-=cal(m-2,cnt,K-2)*K*(K-1)/m/(m-1)*len;
		}
	printf("%.11lf\n",ans);
}