code festival 2016 final题解

考完学考做点小水题练练脑子

Source

code festival 2016 final

E Cookies

请先思考后再展开

因为吃饼干的次数k级别是log的,不妨枚举,设每个间隔烤饼干的时间为$a_i$,那么题意就是$\prod a_i \ge n$的前提下最小化$kA+\sum a_i$

经典模型,设$x=\lfloor n^{-(k+1)} \rfloor,y=x+1,枚举i判断x^iy^{k+1-i} \ge n即可$,$O(log^3)$,code

F Road of the King

题意:统计长度为m值域为n的序列c,要求造出$1 \to c_1 \to c_2…c_m$这样一条链,然后把共点的缩起来,得到的图是个强连通图,$n,m \le 300$

请先思考后再展开

因为1是一切的根,发现会「出+入」多次,且每个块(每次)独立,当然可能是通过到前面的块来实现入的

记$dp(len,done,now)=序列长度,前面块的大小和,当前块的大小$,注意这里的大小都是去重的

1
2
3
4
5
6
7
8
int n=qread(),m=qread();dp[0][1][0]=1;
fo(i,0,m-1) fo(done,0,n) fo(siz,0,n-done)
{
ll now=dp[i][done][siz];if(!now) continue;
add(dp[i+1][done+siz][0],now*done%MOD);
add(dp[i+1][done][siz],now*siz%MOD);
add(dp[i+1][done][siz+1],now*(n-done-siz)%MOD);
}write(dp[m][n][0]);

G Zigzag MST

请先思考后再展开

从小到大考虑边权,对于题目给出的三元组$(x \to y,c)$,考虑简化其衍生边

$(x+a \to y+a,c+2a)$,当考虑到任何权值为$c+2a$的边时一定满足$(x..x+a,y…y+a-1)$在同一个联通块,故等效于$(x \to y+a,c+2a)$;同理,$(y+a \to x+a+1,c+2a+1)$时一定满足$(x..x+a,y..y+a)$在同一个联通块,等效于$(x \to x+a+1,c+2a+1)$

尝试再对新图思考一次这个过程,得到$(x+a \to x+a+1,c+2a+1)$、$(x \to y,c)$、$(y+a,y+a+1,c+2a+2)$

环形dp或别的啥东西得到每条边的最小值,跑kruskal即可

code

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