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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

老子不玩了(挖坑)->终于填完了  

2013-07-25 09:39:32|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
好不容易将ABBYY Cup final的代码题写好。。。
400行啊400行啊
结果codeforces抽风了抽风了。。。。。。。。。。。。。。。。。。
TLE On Test1。。
去你的TLE。。。。。。。。。。。
坑在此。。
等cf正常了再管吧
=======================================================
既然cf正常了。。。而且已经在这儿挖了个坑
那我就一定得做完!!!
只要有人AC的题,就一定可做,这是我的信念头!!!(专A不可做题的vfleaking神见笑了)
=======================================================
当我做完后。。现在回顾不禁感慨:
我为什么就这么屌呢?

好了。。。
很久没在空间上写题解了。。。不过考虑到妈妈肯定会喊我去洗澡。。所以继续挖坑。。
不过爽啊。。终于有时间去搞剩下欠下的一屁股题了。。。T_T
(哭瞎了。。。为嘛感觉进队了颓的时间还没以前多了呢???)
=======================================================
C题:
一个数,你可以减去这个数的十进制表示的一个数位上的数,得到一个新的数,称为一次操作
求将一个数N(<=10^18)变成0所需的最小步骤
题解:
记f(n)为将n变成0的答案。。
很容易打表或者归纳法证明f(n)是单调的。。由此有贪心策略,每次减去最大的那个数位
注意到我们可以用dp实现这个贪心策略:
f(p,a),表示前面的最大位是p,将a变成0的最小步数。。
每次将a的除开开头那位减成非正数,将开头那位-1实现转移。。
由于a要么是N的最后几位,要么是a*10^b-p(a,p<10)这种形式。所以状态数极其有限。。

D题:
b*b的网格,在一些格线上有水平或者垂直的不相交的长度不一的箭头,质点在平面上水平或垂直以每秒一个单位运动,碰到箭头的话会按照箭头改变运动轨迹。
给出平面上n个箭头(给出箭头的起点和终点,方向由起点连向终点),和m个质点的位置和初始运动方向,对于每个质点询问它运动某个时间后的位置。。
n,m<=10^5
题解:
很傻×的题目的说。。
用扫描线+排序处理出每个箭头指向的箭头或者无穷远。。
同时用扫描线处理出每个点第一个碰到的箭头
用倍增来进行logn级别的跳跃和定位。。
然后——
我写了411行!!!
从未写过代码量如此之大的题啊。。虽然也从某种意义上反映了我代码能力的欠缺和代码题做得非常少。。。
只能无限膜拜tourist——
长达9KB的代码在CF的赛场上直接手写,一个小时就过了。。。。。这已经不是人与人的差距了(虽然早就应该了解到)

E题:
这题是道比较神的题目,虽然思想说起来简单,但实现和细节都比较多。。。
想起来比较繁琐,加上题解如此之简略不负责任。。。
题意:
给定一个没有重边没有自环的有向图,每条边上会有一个序列,长度可能为0。
求出这样的各个长度(长度<=2*n)的路径的个数:
路径上的序列拼起来刚好就是原本的路劲。。。
n<=50。

题解:
最重要的是观察到一个非常碉堡的性质:对于一条路径,一定会有一条边上的序列包含了自己本身。。这个非常非常容易证明。。
然后注意到没有重边!我们找到一个包含了自己本身的边之后,那么两旁的东西可以由这条边的序列确定了。。然后依次往左右衍生即可找到符合条件的序列。。
但是只是这样是不够的~
比如说1,4(序列:4)这样的边,可以接在任意的以1结尾的路径后面。。。我们还要处理出所有的这样的开头和结尾。。
然后,任意两条完整的路径,如果有条空的边连接其开头和结尾也是可以的哟。。
于是dp啊dp
搞了一天终于将算法理清解决的^_^
  评论这张
 
阅读(728)| 评论(7)
推荐 转载

历史上的今天

评论

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

页脚

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