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
转载请注明出处,谢谢!