注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

codeforces 246 div2 —— 论水考狗的课余生活  

2014-05-16 20:02:43|  分类: codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
由于搞水考搞得智商降低严重
所以昨天打算来玩一下div2
然后yjg还创了个丧心病狂的小号……ydcloveschinese
要知道乱黑人是要考挂的节奏啊

由于考div2太无聊了……纯粹是在搞水考之余调剂生活
所以也就没有叫上vfk了……自然也没叫上cmg,gwj他们
最后好友里只有我、yjg和一个浙江红名爷考了……
上去看C
题意是这样的……要你进行一些交换操作把一个排列排好序
假设每次交换(i,j),要求i<j且j-i+1是质数
交换次数不能超过5n

交换次数最少很容易想到置换群……然后限制条件很容易想到贪心
我筛出所有质数,预处理一下最近的,打了个表发现最多交换4次就能交换任意的(i,j)
正要开始码,yjg告诉我说他A了D了
吓哭了
codeforces 246 div2 —— 论水考狗的课余生活 - ydc - ydc的博客
  是的你没看错……他贴了个后缀数组的模板,然后1A了
当时是rank3
这个时候我还没敲C

然后开始敲C,感觉置换群那里纠结了一下
然后发现交换影响了其他人的位置,改变了置换群,似乎不是很好换回来
吓傻了

然后发现把第i个数和i所在的位置换一下就行了??
删了重写,好不容易A了……结果已经半个小时过去了
当时差不多是几百名的样子T_T

然后看D
不就是水题么……
其实KMP的算法是很显然的……但是我一般字符串题都喜欢上后缀数据结构艹
由于我对贴模板还是很排斥的……所以准备手敲
所以就是在后缀数组和后缀自动机间纠结了……后缀自动机我肯定是没有后缀数组熟练地……
但如果我后缀自动机能一次写对的话……应该能比后缀数组花的时间短一些?
于是我开始敲后缀自动机……我记得CTSC试机的时候我还是敲出来了的!虽然把陈牧歌和郭文景叫来调了N久的错……
然后发现各种parent的关系纠结了……感觉要调不出来
乱蒙一顿
样例发现过不了
我调后缀自动机都是拿草稿纸画一堆大大的图把串的后缀自动机都建出来
显然没时间?
对着建后缀自动机的函数看了一下,感觉有些地方和记忆不合
改了一下,算是过了样例
抱着必死的心交了一发……竟然过了pretest?
感觉是在玩心跳
对比了一下时间……大概是20分钟搞完……其实如果是oi赛场的话我还是很满足了
可是在CF赛场就弱爆了
发现被各种贴模板的虐翻……当时已经有搞掉了ABCD的若干
然后去看E,第一反应是每次弄最大的贪心……很容易找到了反例
然后就去看AB了

结果英语太差,看不懂
在过了很久很久很久以后……过了AB
E我以为是什么构造什么的……感觉细节很多
结果没有什么好的思路
担心明天上不了课……所以就弃疗提前睡觉了

早自习的时候意识到E题直接用枚举+判定的经典作法就秒了
感觉智商实在没救了
yjg告诉我说他D题挂了??
你知道么……多行不义必自毙啊,叫你用那种奇葩的号

中午得知了真相
自然溢出的hash被卡了,23333
我觉得一直都是用自然溢出昨天忽然改pair<LL,LL>的我简直是爽翻了
还改了一下E题……感觉判定不是很会判定
先写了一个,找个A了的人翻数据,发现有个数据没过
就多加了一些判断……过了那个数据后试着交了一下……结果竟然A了

那就是题解了吧……
A:模拟
B:模拟
C:每次把i和第i大的数换一下,换的话贪心找最接近他的最大质数,打表可以发现最多4次
D:KMP or 后缀数据结构直接爆
E:字典序最小……所以就是枚举当前位,判定是否有解……别问我怎么判定,我乱写的
  评论这张
 
阅读(558)| 评论(4)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017