Codeforces Round #260 (Div.1)
VictorWonder
posted @ 2014年10月16日 19:57
in Codeforces
with tags
解题报告
, 1689 阅读
这是我第一场全部坑完的CF(Div.1)（虽然某些题目是按照标程打的），但还是挺有纪念意义的，所以写了这篇题解，当作是第一篇正式博文吧。
Problem 2A
CF的2A永远都是特别水的，这道题目很明显，每个物品都有x和y这两个关键字，按照关键字x排序后再O(n)判断有没有a[i].x<a[j].x&&a[i].y>a[j].y就行了。
Problem 2B
我在做的时候是打表找规律的，经过打表发现，如果n是4的倍数，那么答案就是4，否则答案就是0
现在证明一下：
首先，1^n mod 5=1
其次，2^n mod 5和3^n mod 5的结果都是四次一循环的
n对4取模 1 2 3 0
2^n mod 5 3 4 2 1
3^n mod 5 2 4 3 1
和对5取模 0 3 0 2
而4^n mod 5的结果则是两次一循环的，分别为4和1，然后我们就可以发现，当n是4的倍数的时候，结果是4，否则结果为0
Problem 1A
首先，统计出数值为i的数一共有多少个，再用dp求解
sum[i]表示选择数值为i的数，一共能获得的积分
g[i]表示不选择i能够获得的最大积分，f[i]表示选择i能够获得的最大积分
那么，如果数i-1不存在，那么g[i]=max(g[i-1],f[i-1]),f[i]=g[i]+sum[i]
否则g[i]=max(f[i-1],g[i-1]),f[i]=g[i-1]+sum[i]
然后输出g[100000]和f[100000]中的最大值就行了
Problem 1B
这到题是我碰到的第一道不是求SG函数的博弈问题
首先，我们将所有的单词都扔到一棵字典树里面，然后进行深搜
win[v]表示在v这个结点之后的多种状态中，先手有无必胜的走法
lose[v]表示在v这个结点之后的多种状态中，先手有无必败的走法
那么，如果v是叶结点，那么lose[v]=true,win[v]=false
接着往根走，逐渐更新每一个结点的lose值和win值
win[0]=true表示有先手必胜的策略
lose[0]=true表示有先手必败的策略
如果不存在先手必败的策略那么必然存在先手必胜的策略
如果k=1，那么结局与win[0]相同
如果先手没有必胜策略那么就一定有先手必败策略，则第一个人每一局都输故后手必胜
如果先手有必胜策略也有必败策略，那么先手无论如何都能赢
如果先手有必胜策略但无必败策略，那么两局一循环，奇数局则先手必胜否则先手必败
Problem 1C
题目的意思很简单，给定一个森林，那么森林中的每棵树都会有一条最长链，接着会有合并操作，合并之后，要求新生成的这棵树的最长链尽可能小
很明显，我们需要用并查集来做，先求出树的数目和每棵树的最长链
假设我们要把树x和树y合并，且d[i]表示以i为根的树的最长链
那么新树的最长链就是d[x],d[y]和(d[x]+1)/2+(d[y]+1)/2中的最大值
因为根据贪心原则，要使得新生成的树的最长链最短，那么我们肯定要把已有的两棵树的最长链的中间部分给连在一起
既然这样，那么用并查集维护一下就可以了
Problem 1D
这道题目还是花了我比较多的时间的，因为我无聊地用三种方法做掉了这道题目
这道题目的实质就是给定一个序列，要求实现两个操作
1.将[l,r]这个区间中的r删除，并将其插入到l这个位置
2.查询区间[l,r]中等于x的数的个数
我用的第一二种方法其实是一样的，就是块状链表
不过我用的第一种方法是题解给出的方法，暴力修改，修改超过1000次后将整个序列重构并再次分块
第二种方法则是普通的块状链表，每一个块都可以分裂与合并，删点和加点的时候就将其所在的块在插入和删除的位置分裂成两个块，然后再操作
每一次修改之后，都要再遍历一遍，如果发现有相邻两块的大小加起来比开始时块的大小size要小的话，就将其合并，速度也是挺快的
第三种方法就是seter大神AC带插入区间K小值的办法，将所有的查询分块，用一个数组记录下修改的次数，每次查询的时候再到修改列表中看一下，特判一下
在修改一定次数之后再重构整个列表，但是本人实在是太弱了，seter大神做带插入区间K小值的时候用这种做法，秒杀O(nlog2n)，结果现在我做这道题目的时候最后还是卡时过去的
抽样调查之后发现，1200次修改操作后重建序列的速度还是比较快的（或许能够更快，但我懒得去检验了）
这道题目大神xiaodao和vfk给出了nlog2n的做法，我也就只能orz了。
Problem 1E
这道题目具体的公式我还是不讲了，可以看一下题解(http://codeforces.com/blog/entry/13336)，反正化简之后就将各个数都转化成了一个一次函数，然后问题就变成这样了：
每次给定一个数x和一个区间[l,r]，查询区间内所有函数将x代入后的最小值
出题人给出的是log2n查询的在线做法，实际上还是有logn查询的离线做法（没有具体的题解，别人的程序实在是看不懂）。。
简单来说就是建一棵线段树，每个结点维护一个凸包，查询就等于是线段树的区间查询，查到一个结点之后将其凸包二分，求出一个最优解
由于还不是很理解（我的程序就是照着出题人的pascal程序打的，咳咳……），所以也说不出个所以然来，只能以后搞懂了再补了……
代码：
Updata：ideone好像出了点问题，代码都消失了……汗……现在重发了一遍。
评论 (0)
