3.12模拟测试

-------------------------------------------------------------
JSOI2013 Day2
挺水的...低于230就算挂零什么的...
 
-------------------------------------------------------------
T1:
枚举某个点x
强行让这个点不能选,其他的点能选就选
如果这样会使得有些必须选的点选不到的话,说明x这个点必须选
复杂度O(n*(n+m))(不是标算/标算是O(n^3/log)的,我也不知道怎么搞...)
看起来挺慢的,但实际上跑得过,而且跑的挺快的...
-------------------------------------------------------------
T2:
这题数据超水,认为k<=16状压DP有60分...
 
题意相当于是一开始有k条边,然后每次可以加入一条边(可以有重边),使得原图上关键点的导出子图有欧拉回路且最小
关键点就是和关键边相连的点
因此有两个条件:
1.有欧拉回路
2.一开始大小大于一的连通块都必须和1连通
考虑状压DP,f(s,p)表示有哪些连通块已经和1连通了,以及所有点的度数的奇偶性
SPFA转移
因为大小至少为2的连通块最多有n/2个
每次转移有O(n^2)条边可以选择
所以复杂度是O(n^2 * 2^(1.5 * n))
看起来挺慢的,但实际上跑得过,而且跑的挺快的...
-------------------------------------------------------------
T3:
当年的神题,现在的水题,几乎全场A掉
回文树随便搞一搞每个回文串出现的次数
哈希也能做到这个(先manacher,对每个中心,向内扩展,遇到出现过的就停止,更新一下出现次数,然后因为只有O(n)个本质不同的回文串,所以时间复杂度是O(n)的)
-------------------------------------------------------------