3.12模拟测试
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-------------------------------------------------------------
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)的）
-------------------------------------------------------------
评论 (0)
