2016 ACM-ICPC Shenyang Onsite

2016年11月8日4000

一些队友写的还没太搞清楚,就先贴几题

hdu5948.Thickest Burger

模拟

hdu5949.Relative atomic mass

模拟

hdu5950.Recursive sequence

\(f_1=a,f_2=b,f_i=f_{i-2}*2+f_{i-1}+i^4\),求\(f_n\)

推出式子后矩阵乘法

hdu5952.Counting Cliques

求一个无向图大小为S的团的数量

由于图的度数很小,选一个点,在其所有相邻点中取S-1个

复杂度\(C(20,10)*S^2\)

hdu5954.The Elder

一棵树,长者在1号结点,记者从i号结点传递消息到1号结点,长度L的路程需要\(L^2\)的时间,不过他可以花P的时间停在某个结点让另一个记者接力

求最少需要时间,任意一个结点的记者都有方案把消息传递到1号结点

\(f_i=min\{f_j+(d_j-d_i)^2+P\}\)

斜率优化的式子,放到树上的时候,只要在某个结点记录一下决策序列的两个指针

同时记录右端有哪些元素被弹掉了,递归回来的时候恢复决策序列即可