PKUSC2019前后

发表于 更新于 分类于 评论数： 阅读次数：

PKUSC2019
准备很匆忙，再次体验了下OI的快乐

n个随机实数的第k小的期望

下面我们只讨论在[0,1]间随机的情况，其他直接放缩就好了

众所周知最大可以直接积分，最小翻转一下，今天看到地震后的幻想乡，发现k任意也可以求

有两种方法：A,B

B比较简单先说B，就是 $\sum_{all} \frac{1}{all} a_{p_k}=\sum_{all} \frac{1}{all} [变量s \leq a_{p_k}]$

将所有点取值情况投影到数轴，对于某种投影，共$(n+1)!$种情况，有 $k \times n!$ 种合法，即 $\frac{k}{n+1}$

注意到每种投影的概率不同，但因为权值相同，所以没有影响

A的做法虽然复杂，但值得一看，毕竟好想的东西总有其存在价值

PKUWC2019D1T2口胡

注意到树的并也是树，既然是树的计数考虑 点-边，以点为例

考虑求出每个点被多少棵虚树包含（$col_x$），这个可以差分，用些小技巧让虚树上每个点的系数=1

那么 $ans_i=\sum_x C_{col_x}^i=\frac{1}{i!}\sum_{j=i}^n \frac{tot_j j!}{(j-i)!}$ 这个翻转一下ntt优化即可

CF1146F Leaf Partition

一开始的想法是f(x,0/1)表示x这个点当前已占用或钦定后面占用，但似乎后面没法确保被合并掉

换个角度，设0/1表示x向上这条变是否会被使用

实现的时候，f为0，g为1
$$
f(x)=f(x)f(y)+g(x)g(y)\\
tt(x)=\prod f(y) \\
g(x)=g(x)g(y)+g(x)f(y)+tt(x)g(y)
$$
g的转移用tt是因为f中，可能节点x已经被占用

时间复杂度为线性

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<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
	typedef long long ll;
	//#define double long double
	const int INF=0x3f3f3f3f;
	const ll LLINF=0x3f3f3f3f3f3f3f3fll;
	ll qread()
	{
		ll ans=0;char c=getchar();int f=1;
		while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num)
	{
		if(num<0) {num=-num;putchar('-');}
		if(num>9) write(num/10);
		putchar('0'+num%10);
	}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);puts("");}
	#define FR first
	#define SE second
	#define MP make_pair
	#define pr pair<int,int>
	#define PB push_back
	#define vc vector
	void chmax(int &x,const ll y) {x=(x>y?x:y);}
	void chmin(int &x,const ll y) {x=(x<y?x:y);}
	const ll MOD=998244353;
	void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
	ll qpower(ll x,int e)
	{
		ll ans=1;
		while(e)
		{
			if(e&1) ans=ans*x%MOD;
			x=x*x%MOD;e>>=1;
		}
		return ans;
	}
	ll inv(ll x){return qpower(x,MOD-2);}
	const int MAX_N=2e5+10;
	vc<int> son[MAX_N];
	ll f[MAX_N],g[MAX_N],tt[MAX_N];//这个点是否被用到
	void dp(int x)
	{
		tt[x]=1;
		if(son[x].size()==0) f[x]=g[x]=1;
		for(int t=0;t<(int)son[x].size();t++)
		{
			int y=son[x][t];dp(y);
			if(t==0) f[x]=tt[x]=f[y],g[x]=g[y];
			else
			{
				ll ff=f[x]*f[y]+g[x]*g[y];ff%=MOD;
				ll gg=g[x]*g[y]%MOD+g[x]*f[y]%MOD+tt[x]*g[y]%MOD;gg%=MOD;
				f[x]=ff,g[x]=gg;tt[x]=tt[x]*f[y]%MOD;
			}
		}
	}
	void main()
	{
		int n=qread();for(int x=2;x<=n;x++){int fa=qread();son[fa].PB(x);}
		dp(1);write(f[1]);
	}
};
signed main()
{
	srand(time(0));
	mine::main();
}

Loj2136 「ZJOI2015」地震后的幻想乡

一开始考虑排名的期望做的，但太菜了似乎没搞出来；还有就是下述状压用到经典的【考虑集合内编号最小节点所在连通块】

众所周知，一个图的最小生成树具有【最大边权最小】的特性，所以最大边的期望=【最小的，只需要比这个更小的边就能让图连通】的期望

然后期望这东西众所周知是可以转化为概率密度函数的积的，即求 $\int_0^1 P(t)，P(t)为只使用t以内的边导致不连通的概率$
$$
f(集合S,t)=\sum_{最小编号所在集合SS} (1-f(SS,t))(1-t)^{cnt=SS与S-SS间的边数} \\
\int_0^1 f(S,t)dt=\sum \int_0^1 (1-f(SS,t))(1-t)^{cnt}dt=\sum \frac{1}{1+cnt}-\int_0^1 f(SS,t)(1-t)^{cnt}dt \\
同理\int_0^1 (1-t)^Tf(S,t)dt=\sum \frac{1}{1+T+cnt}-\int_0^1 f(SS,t)(1-t)^{T+cnt}dt \\
$$
于是就可以dp了，设 $g(S,T) ，符号意思如上，g(S,T)=\sum \frac{1}{1+T+cnt}-g(SS,T+cnt),ans=g(all,0)$

时间复杂度为 $O(3^nn^2)$，受限于处理两集合间边数量

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int qread()
{
	int num=0;char c=getchar();
	while(c<'0' or c>'9') c=getchar();
	while('0'<=c and c<='9') num=num*10+c-'0',c=getchar();
	return num;
}
const int MAX_N=12,MAX_M=110;
int bin[MAX_N],siz[1<<MAX_N],mark[MAX_N];
double g[1<<MAX_N][MAX_M];
int main()
{
	bin[0]=1;for(int i=1;i<MAX_N;i++) bin[i]=bin[i-1]<<1;
	for(int i=1;i<bin[MAX_N-1];i++) siz[i]=siz[i>>1]+(i&1);
	int n=qread(),m=qread();
	for(int i=1;i<=m;i++)
	{
		int x=qread()-1,y=qread()-1;
		mark[x]|=bin[y];mark[y]|=bin[x];
	}
	for(int T=m;T>=0;T--)
		for(int S=1;S<bin[n];S++)
		{
			int mi=(S&-S),wt=S^mi;if(S==mi) continue;
			for(int SS=(wt-1)&wt;SS>=0;SS=(SS-1)&wt)
			{
				int a=mi^SS,b=S^a,cnt=0;
				for(int i=0;i<n;i++) if(a&bin[i]) cnt+=siz[mark[i]&b];
				if(T+cnt<=m) g[S][T]+=1.0/(1+T+cnt)-g[a][T+cnt];
				if(SS==0) break;
			}
		}
	printf("%.6lf",g[bin[n]-1][0]);
}

upd：徐国王教了我一种新做法

首先有个很妙的题意转化，就是$ans=\sum_{选边到恰好连通的情况} \frac{边数}{m+1}=\sum_{非法选边方案} \frac{1}{m+1}$

于是就可以dp了，$非法g(S,i)=\sum_{T \subset S,mi(S) \in T} 连通f(T,j)C_{edge(S-T)}^{i-j},g(S,i)+f(S,i)=C_{edge(S)}^i,ans=\frac{g(U,i)}{(m+1)C_{m}^i}$

注意到一个方案可能是若干个其他方案的子集，需要多次计数，统计答案的系数必须这样搞

PKUSC2018真实排名

细节：ai相同、=0（特判）

若x不变，则 $[x/2,x)不变，ans=C_{all-cnt-1}^k$

若x变，则 $[x,2x)变，ans=C_{all-cnt}^{k-cnt}$

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int qread()
{
	int num=0;char c=getchar();
	while(c<'0' or c>'9') c=getchar();
	while('0'<=c and c<='9') num=num*10+c-'0',c=getchar();
	return num;
}
#define MP make_pair
typedef long long ll;
const int MOD=998244353;
const int MAX_N=1e5+10;
ll fac[MAX_N],inv[MAX_N],facinv[MAX_N];
ll C(int n,int m){if(n<m or m<0)return 0;return fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;}
int a[MAX_N],b[MAX_N];
int main()
{
	fac[0]=1;for(int i=1;i<MAX_N;i++) fac[i]=fac[i-1]*i%MOD;
	inv[1]=1;for(int i=2;i<MAX_N;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
	facinv[0]=1;for(int i=1;i<MAX_N;i++) facinv[i]=facinv[i-1]*inv[i]%MOD;
	int n=qread(),k=qread();
	for(int i=1;i<=n;i++) a[i]=b[i]=qread();
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)
	{
		int ans=0,x=a[i];
		if(x==0) ans=C(n,k);
		else
		{
			int aa=lower_bound(b+1,b+n+1,x)-1-lower_bound(b+1,b+n+1,(int)ceil(x/2.0))+1;
			int bb=lower_bound(b+1,b+n+1,2*x)-1-lower_bound(b+1,b+n+1,x)+1;
			ans=C(n-aa-1,k)+C(n-bb,k-bb);
		}
		printf("%d\n",(ans%MOD+MOD)%MOD);
	}
}

Day1

t1明显就是在直接逆序对的基础上改了改（题意修正=强烈暗示），时间倒流+启发式合并+主席树就好了，$O(nlog^2n)$

t2花了很久debug假做法，然后爽快一分没有

正解的压法挺不错，对于每个数，把它小的设为0，大的设为1，那么状态为 $3^n$

然后只有01的情况需要枚举0/1，复杂度应该是 $O(n^2m4^n)$

t3还不会

Day2

t1应该会47分，但太难写了（3个代码）就没有写，玩了玩t3感觉不好搞就跑路了

然后就玩了一整场t2，先把菊花写了，然后二叉树玩半天终于发现了一种有解策略，因为不知道有没有更优的情况所以就先写了，gg后又玩了半天，从数轴开始逐步考虑，把二叉树的做法搞出来了（把dfs换成bfs），此时剩1.7h；然后此时回去看看t1发现还是不会，有点小难受，然后这个t2我不知道为什么做法不能拓展到正解，想半天觉得应该是插入顺序什么的，瞎jb试了各种方法都不行，不太会理性分析，于是就滚粗了

相关文章推荐

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址：http://zory.ink/posts/99ca.html
转载请注明出处，谢谢！