CF768
Codeforces Round #406 (Div. 1)
A.Berzerk
考虑先手必胜态，一定是先手移动到某一个位置以后，这个位置是后手的必败态
考虑先手必败态，一定是无论先手如何移动，先手所能一道的任何位置都是后手的必胜态
基于此，我们可以直接记忆化搜索
可能题目比较煞笔我的搜索姿势不好,由于loop的关系，我需要正着和倒着各搜一遍才行
B.Legacy
很显然这是最短路
但是有到区间的边
考虑用线段树辅助建图
一颗线段是表示由区间出发的点，即2类型的边，默认所有点对应的叶节点指向所有点，显然，线段树中父节点应该可以花费0通往儿子节点，然后2类型的边，从线段树连向对应的点即可
需要另外一颗线段树，来建出3类型的边，与2相似，显然，线段树中儿子节点应该可以花费0通往父节点，所有的点指向其对应的叶子结点，3类型的边有对应的边指向第二课线段树中的点即可
这是一张稠密图，所以直接跑dij即可
C.Till I Collapse
显然，贪心策略是正确的，考虑优化
数组f[i][j]表示范围[i,j)之内，如果不存在和a[j]相等的数，那么f[i][j]=1，反之f[i][j]=0
对于每一个f[i]我们可以构建一个线段树来快速的求解，考虑的内存，我们用主席树
那么对于每一个k，我们只需要二分即可
复杂度∑ans(k)<=nlogn，那么，直接二分的话，会使复杂度带3个log，会TLE
考虑直接在主席树上二分，可以化掉一个log
D.Rap God
开起来是一道树分治，不过很繁琐啊
弃疗咯...............
E.ALT
只会简单的建图啊
用二分图来建图
把每一个公民看作是第一部分的一个点，第二部分的每一个点对应树上的一条路径
当且仅当，公民x，从xi-->xj经过了节点j，那么从第一部分的点x向第二部分的点y连边
这样以后，我们所需要解决的问题就成了二分图点的最小覆盖
二分图点的最小覆盖是说要把每一条边，至少一个顶点包含在所求集合内，对于这道题目，这样，来建图显然是正确的
然后一个性质就是说二分图的|最小点集|=|最大匹配|
那么直接跑二分图匹配时间复杂度显然是过不去的
然后就gg了........
最新文章
- 深入研究Visual studio 2017 RC新特性
- 如何使用Python在Kaggle竞赛中成为Top15
- fsn文件解析(C#)
- SDWebImage 加载网络图片失败，重新运行，就能加载成功。
- JavaScript动态改变表格单元格内容的方法
- ASCII 非打印字符
- 用Sublime Text搭建简易IDE编写Verilog代码
- iOS 7定制UIPageControl遇到的问题
- mysql数据库---同时插入两个表以上的数据
- GC 基础
- sqlserver分区表实践：对时间分区表自动进行管理
- C++ STL算法系列5---equal() , mismatch()
- Oracle 热备份batch脚本 Windows
- linux-统计行数
- 通过Jquery中Ajax获取json文件数据
- [iOS基础控件 - 2] 按钮的基本使用
- C#语言的新特性及相关信息
- C:\WINDOWS\system32\config\systemprofile\Desktop引用了一个不可用的位置
- Identity-修改Error错误提示为中文
- codeforces#256DIV2 D题Multiplication Table