PKUSC2019前后

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

PKUSC2019
从文化课中放松一会，准备很匆忙，再次体验了下OI的快乐

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
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]);
}

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
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}$

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

Day1

t1，题意修正=强烈暗示，大胆猜测就是跨组（按隔板分组）逆序对，写个暴力过了，时间倒流+启发式合并+主席树就好了，$O(nlog^2n)$

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

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

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

t3还不会（upd：当时不知为何没写，现在已经忘记自己拿了多少了，应该是60吧）

Day2

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

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

回来改题了，因为只过了7个月且还稍微记得一些标签，算是比较顺利

截止20191203没看到更详细的题解，不过可能也没啥人想看就是了

D1T1

题意：给出排列p排成一行，相邻两个元素间有空位，最开始没有隔板，按给出的n-1的排列q的顺序依次插入隔板，每次插入后询问将这个排列p排序的最小代价。两个位置上元素能免费交换当且仅当中间空位无隔板且两人都不曾跨过隔板，$n \le 3e5$

显然将上面的启发式合并改线段树合并就是一个log了，不知道哪个好写的情况下我选择主席树，记得当时不到40min过

证一下，因为每对逆序对被消掉都会有一次贡献，所以下界是逆序对，通过每段排序后冒泡可以达到这个下界

D1T2

题意：2n个人n个球桌打m+1轮比赛，给出第一轮每桌是哪两人，编号小的有1/3概率获胜，对$\forall i,j求第m+1轮i在第j桌的概率$

每轮第k桌由上轮k-1的胜者和k+1的败者组成，第1桌是上轮1、2败者，第n桌是上轮n-1、n胜者，$n \le 9,m \le 20$

肯定要考虑怎么压状态，考虑枚举每个人E做，即设0表示<E的，1表示>E的，2表示自己，状态数不多（00、01、11，不超过$3^{n-1}2nm$），然后转移是只需要考虑01那些桌是谁赢了，记忆化搜索

D1T3

题意：给出序列a，q次询问是否存在一个k使得序列异或k后，第x个数排名为y，$n\le 5e4,q\le 1e6,a<2^{60}$

排名为y即<x的数恰y-1个，考虑到k的这位是1意味着交换trie上两个子树，枚举x去回答询问，那么就是把trie上x的路径另一个孩子取出，得到60个数，暴力做背包是$O(n*\frac{n}{w}*60)$

发现只要能把60去掉就能过了，考虑dfs去做，存向上这条链上另一个孩子的背包，如果只有一个孩子就把bitset直接传下去，于是做bitset的次数=trie上有两个孩子的节点数=每次合并两个集合的次数=O(n)个，$O(n^2/w)$

D2T1

题意：$n \le 2e5$个点的树，$m \le 1e9$种颜色去染色计数，要求$col_x \ne col_{fa}$，另有$K \le 4e5$条限制$col_x \ne y$

颜色离散化后为$tot \le K+1$种，允许颜色0和颜色0相邻，然后一种染色方案的贡献就是

$\prod_{0联通块} (m-tot)*(m-tot-1)^{siz-1}=(m-tot)^{联通块数}*(m-tot-1)^{点数-联通块数}=(A=m-tot)^{点数}*( B=\frac{m-tot-1}{m-tot})^{边数}$

$dp_{x,t}=[t \notin ban_x]\prod (S_y-dp_{y,t}),g_x=A\prod (g_y*B+S_y-g_y),S_x=\sum dp_{x,t},O(nK)$

发现合并是一个稍有不同的点积，只要能合并且维护和，ban掉非法部分啊g的转移啊都很好做

很自然的想法是考虑线段树合并（启发式合并似乎不见得好写很多），动态开点下叶子个数是$O(子树内ban的和)$

打标记就是$ax+b$的和，非常经典，$O(KlogK)$，但跑很慢，开O2也要1.7s

感觉只口胡多半是假的所以写了代码，60行因为我对打标记的线段树合并不熟练强行写了1.5h才过拍，对拍对象，然而这位老哥空间开小了大家自行开大即可

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
const int N=4e5+10;

int tot;
namespace SGT
{
    #define mid (l+r)/2
    struct Nod{int lc,rc,sum;pr tg;}p[N*40];int id;
    void upd(int &x,pr a,int ln){
        if(!x) x=++id;
        p[x].tg={1ll*p[x].tg.FR*a.FR%MOD,(1ll*p[x].tg.SE*a.FR+a.SE)%MOD};
        p[x].sum=(1ll*p[x].sum*a.FR+1ll*a.SE*ln)%MOD;
    }
    void pushup(int x){p[x].sum=(p[p[x].lc].sum+p[p[x].rc].sum)%MOD;}
    void pushdown(int x,int l,int r){upd(p[x].lc,p[x].tg,mid-l+1),upd(p[x].rc,p[x].tg,r-mid);p[x].tg={1,0};}
    void change(int &x,int fl,int fr,pr c,int l=1,int r=tot)
    {
        if(!x) x=++id;if(l==fl and r==fr){upd(x,c,r-l+1);return;}pushdown(x,l,r);
        if(fr<=mid) change(p[x].lc,fl,fr,c,l,mid); else if(fl>mid) change(p[x].rc,fl,fr,c,mid+1,r);
        else change(p[x].lc,fl,mid,c,l,mid),change(p[x].rc,mid+1,fr,c,mid+1,r);
        p[x].sum=(p[p[x].lc].sum+p[p[x].rc].sum)%MOD;pushup(x);
    }
    bool is(int x){return !p[x].lc and !p[x].rc;}
    void merg(int &x,int y,int l=1,int r=tot)
    {
        if(is(x)){p[y].sum=1ll*p[y].sum*p[x].tg.SE%MOD;p[y].tg={1ll*p[y].tg.FR*p[x].tg.SE%MOD,1ll*p[y].tg.SE*p[x].tg.SE%MOD};x=y;return;}
        if(is(y)){p[x].sum=1ll*p[x].sum*p[y].tg.SE%MOD;p[x].tg={1ll*p[x].tg.FR*p[y].tg.SE%MOD,1ll*p[x].tg.SE*p[y].tg.SE%MOD};return;}
        pushdown(x,l,r),pushdown(y,l,r);
        merg(p[x].lc,p[y].lc,l,mid);merg(p[x].rc,p[y].rc,mid+1,r);pushup(x);
    }
};

ll A,B;
vc<int> to[N];
vc<int> ban[N],all;int getid(int num){return lower_bound(all(all),num)-all.begin()+1;}
ll g[N],S[N];int rt[N];
void solve(int x,int fa)
{
    SGT::change(rt[x],1,tot,{0,1});g[x]=A;
    for(auto y:to[x]) if(y!=fa)
    {
        solve(y,x);
        g[x]=g[x]*(g[y]*B%MOD+S[y]-g[y])%MOD;
        SGT::change(rt[y],1,tot,{-1,S[y]});
        SGT::merg(rt[x],rt[y]);
    }
    for(auto t:ban[x]) SGT::change(rt[x],t,t,{0,0});
    S[x]=(g[x]+SGT::p[rt[x]].sum)%MOD;
}
void main()
{
    int n=qread(),m=qread(),k=qread();
    fo(i,2,n){int x=qread(),y=qread();to[x].PB(y),to[y].PB(x);}
    fo(i,1,k){int x=qread(),y=qread();ban[x].PB(y),all.PB(y);}
    sort(all(all));all.resize(unique(all(all))-all.begin());tot=sz(all);A=m-tot,B=(m-tot-1)*invm(m-tot)%MOD;
    fo(x,1,n){sort(all(ban[x]));ban[x].resize(unique(all(ban[x]))-ban[x].begin());fo(t,0,sz(ban[x])-1)ban[x][t]=getid(ban[x][t]);}
    solve(1,0);write((S[1]+MOD)%MOD);
}

D2T2

题意：给出一棵n个点的无权树，构造m维空间内n个点，使得$\forall i,j在树上距离=空间里两点曼哈顿距离$，最小化m的前提下输出任意方案即可，$n \le 100$

菊花m=n-1，应该可证明；二叉树怎么搞我已经不太记得了，总之当时真的玩了很久很久，现在有阴影不想玩了

直接考虑正解，随便取一个根为$(0,0..0)$，先把父亲关系的点对处理了，考虑差分的话就是$(a_{x,1},a_{x,1}…a_{x,m})$形如$(0,0..1…0)或(0,0..-1,…0)$；然后处理祖先关系的点对，充要条件就是某一维都非0则同号；剩下非祖先关系的点对，充要条件就是某一维都非0则异号

因此度为1的节点，其差分坐标都是相异的，而且是最大的相异集合（最长反链=最小链覆盖），于是我们得出一个不等式：$度1节点数 \le 2m$，尝试能否达到这个下界

首先看到这个已经让我想到之前不知何时见过的套路集锦-树形结构-7，得到的下界非常相似

没见过也无所谓挺好想的，就是你关注每维，所形成的若干条链必须能用一条路径包含起来（以x-lca-y为例，则x-lca代表这一维1，lca-y代表这一维-1），那我们每维做一条链，前提是这些链把整棵树每条边都覆盖了，允许有交。然后一个点的差分坐标就是覆盖在上面那个链对应维的1或-1，如果多条链覆盖在上面的话任选一个。那么这个问题就是上面那个，用最少的链将整棵树覆盖了，其下界怎么构造出上面有写，$O(n^2)$

D2T3

题意：给出一棵$n \le 2e5$个点的树，问有多少种加边方案（应该是要求无重边无自环），满足结果的线图（每条边在新图中建点，新点有边当且仅当原图两边有公共点）是弦图

这个仙仙图的充要条件是没有$k \ge 4$元环的仙人掌，现在回想一下好像我当时是知道这是必要条件的，要是大胆猜一猜的话就做完了

那么等价于每次选两条没打过标记的树边打上标记，这样的选边二元组的集合的方案数

显然有$f(x)=向上的边未用，g(x)=向上的边已用，A=\prod (f(y)+g(y)+f(y)*x)，这个分治NTT求$

$f(x)=\sum \frac{(2i)!}{2^i} [x^{2i}]A,g(x)=\sum \frac{(2i)!}{2^i}*(2i+1)[x^{2i+1}]A$

感觉猜出结论后就是板是怎么回事

相关文章推荐

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