A set of simple problems II(xtc退役纪念赛)

Codeforces - Unofficial

From huzecongfarmerhza


小时

尚未报名

备选题3 9/32 500 分 From
备选题4 5/11 1,000 分 From
备选题1 10/18 1,500 分 From
NOIP完挂 9/11 2,000 分 From
省选完挂 20/32 2,500 分 From

Codeforces赛制,题解依旧发在网盘。

看楼下一堆省队互测好萌,互相萌。

答疑帖地址:http://tieba.baidu.com/p/2317496042

pdf版的题目会马上放出在答疑帖

 

 

简易题解:

备选题3

裸的数据结构题,不过有比较方便的实现而已,就是对第一维排序,第二维可以用分治,第三维用树状数组维护一个和就可以了。

至于用到二维数据结构的解法这里不多说了。

备选题4

对于k=0的情况可以直接输出n^n-2

对于k=1和k=2的情况可以先用Matrix-Tree定理,然后观察高斯消元后的矩阵就可以发现规律了。

然后对于n=1、2的情况要特判

备选题1

hza有一个比较神奇的解法——先用拉格朗日插值法求出多项式后用分治法对多项式分治

我提供的解法是用差分表(不会的上wikipedia看看)

利用前面n+1项把差分表暴力打出来,然后是一个形如f(x)=sigma(ai*C(x,i))的形式,其中ai是差分表的第一列的值

然后利用组合恒等式化简即可

NOIP完挂:

这个是TC SRM 551 L3的原题,题解见TC

HNOI完挂:

这个题可以把n-1个位视为一个节点,然后对于两个长度为n-1的01串A,B,如果A的后n-2位与B的前n-2位相同,那么就连接边A->B,然后可以构造出一个节点数为2^n,边数为2^n+1的图,不难发现每条边就是一个长度为n的01串,且每条边互不相同,那么就只需要一笔画这个图就可以了,欧拉路的算法就可以搞定这个题。