Codeforces Round #279 (Div.2)
VictorWonder
posted @ 2014年11月24日 20:52
in Codeforces
with tags
解题报告
, 1546 阅读
我果然还是两题的命,比赛的时候先用极快的速度秒掉了第一题,然后乱七八糟地搞过了第二题,再胡乱地完成第三题,然后就卡在后面三题一直毫无进展,而且,最后的时候,B题还FST了,TAT。
出乎我的意料,小号的rating还是涨了很多,也算是聊以自慰了。
这场CF好像是全俄罗斯学校信息学奥赛的网络同步赛,开始时间为莫斯科时间12点(这个时间点也是醉了),由于莫斯科时间现在是UTC+3的缘故,时差变成了5个小时。
因为正好是饭点,所以我让人帮忙带了饭,拿到饭的时候,还有三分钟开始了,本来是打算空腹做题(感觉这样子脑子会好使一点?)没想到竟然推迟了10分钟开始(我猜是Saratov那边有人还没有吃完饭233),于是三下五除二把饭吃完了,真是感人肺腑。
下面上题解:
Problem 2A
暴力就不说了,完全就是拼手速。
Problem 2B
比赛的时候莫名其妙地打了一个离散化,后来经证实,我的二分打萎了,因此FST了。实际上由于数据范围只有10^6(我下意识地以为是10^9),所以不离散化是完全没有问题的。
每个人都有一个前继pre[i]和后继suc[i],那么很明显,pre[i]往后第二个人是suc[i],所以我们从pre[i]往suc[i]连一条边,那么只要我们确定第一个点和第二个点,那么就可以确定整个序列。
第一个点的前继就是0,那么它的后继就是第二个点。
第一个点很明显在整个序列中只出现一次。整个序列中出现一次的数有两个,分别是第一个点和最后一个点,但是最后一个点是没有后继的,所以我们就能够找到第一个点并把序列补充完整了(唯一的一个问题是,对于n是2的情况需要特判,否则会出问题)。
Updata:突然发现一个无语的事实,第二个点的前继就是第一个点,所以……TAT……
Problem 2C
这道题目和今年Noip day2 T3差不多,都需要用hash(如果有谁愿意打高精度除法我也不会拦着)。首先从头往后判断前i位组成的数能否被a整除,如果可以,那么f[i]=true。
接着从后往前判断,后i位组成的数字能否被b整除,如果可以的话,那么g[n-i]=true,其中,n是整个数的长度,我们假设储存是从下标为0的数组开始的。
处理完毕之后,我们实际上就是要找到一个点x,满足f[x]==true&&g[x+1]==true&&s[x+1]!='0',因为不允许前导零的存在,所以还要加上第三个判断,复杂度是O(1)的。
Problem 2D
Problem 2E
坑爹的细节题,比赛的时候,我的思路是这样子的,对于第i个数,如果其长度大于第i-1个数,那么我们其能填0的地方填0,不能填0的地方(首位)填1。
如果两个数的长度相同,对于第i个数所有?的地方复制第i-1个数,如果第i个数存在某一位大于第i-1个数的相同位,那么我们用贪心的方法将第i个数填充完整就可以了,否则我们找到一个?所在的地方,把它的值改为第i-1个数同一位+1,如果找不到符合要求的?,那么就输出NO。
但是我的这一切都是基于第i个数的每一位要么是?,要么>=第i-1个数的相同位,但是忘记了第i-1个数某位可以大于第i个数。
假如第i-1个数为32713,第i个数为3?123,那么因为第i个数的第四位大于第i-1个数,根据贪心算法, 我的程序会将第i个数的第二位填充为2,这样子,第i个数就比第i-1个数要小了,显然答案是错误的。
所以,如果存在第i个数的某一位比第i-1个数的相同位小的话,就需要分类讨论,具体的就不赘述了,还是看我的代码吧。
Problem 2F
题目大意是给出一棵有6000个结点的树,让你找到树上的一条链,使得这条链的LIS长度最长。很明显,O(n^2logn)的做法是能够卡过去的(实际上到目前为止,我还没有发现更好的算法,感觉点分治什么的应该能搞,但是实在是懒得想了)。
对于每个结点,我们假设其为一条链的开始节点,然后深搜整棵树,再用线段树判断求LIS。开始的时候我打了主席树,后来改了线段树,但是常数都还是太大了,一到6000个结点的数据就被卡,然后又懒得打zkw线段树……最后只能被迫无奈,根据别人的程序选择了lower_bound大法。
语句 lower_bound(dp,dp+n+1,v[x])-dp 能够返回数组dp中比v[x]大的第一个数所在的位置k,那么对于结点x来说,到它为止的LIS的长度就是k+1,然后将dp[k]更新为v[x],要注意的是,dp数组最初要置为INF,搜完之后要将dp数组逐层还原。
查询是O(logn)的,修改却是O(1)的,CF好像是会开-O2的,反正就是各种快,完全碾压了线段树TAT……
Code: