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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforces 177 Div1  

2013-04-04 19:07:46|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
vfleaking神在贴吧说我会被这套题屠然后XXX
于是今天下午乘着放假看了看题目。。。中间洗澡吃饭回家花了好久的时间
接下来吐槽:
当我做完D的时候重新打开了网页,仔细看了看标题,舒了一口气——我确实做的是DIV1。。。
真的,我还以为我不小心点进了Div2。。。再怎么搞也不会全部都是一眼题啊?然而事实就是除了E以外几乎都是如此
码字也很顺利,除了C忘开longlong了都是1A的。
故此这是我见过的最水的一套Div1了。
下面是题解时间:
1.A题。。。贪心构造,看样例就知道怎么做了

2.B题,每个点往其余点连一条边,从前k个点出发,都能够走到点1,其余不能。求方案数。。。显然后面n-k个点的不能往前面的连,其余任意,故此(n-k)^(n-k)。而前面的k个点,除开点1连出去的边,剩下的是棵树。。prufer编码即可。

3.C题,0到n的排列,要求最后第0个数异或0,第1个数异或1,...,第n个数异或n最大。这题相当一眼,虽然我不知道为什么是对的,只能说样例给的太良心的。。。想办法从大到小拼出2的整数幂-1,能够凑出来就凑出来。。当然我不知道这为什么是对的。

4.D题,统计点对(a,b,c,d)的个数,其中ab之间的最短路与cd之间的最短路没有交集。
很明显我们两条最短路之间肯定有条最短路,枚举这条最短路的起点,于是就是选择这个点连出去的一条边,统计不通过这条边而通过这个点的路径*这条边对应的子树中的路径个数(即点数*(点数-1)/2)。超级简单的说。

5.E题,只包含了4,7的数是lucky,给定两个数位相同的lucky数,设其之间的所有lucky数为a1,a2,a3,...an,求a1*a2+a2*a3+,...,an-1*an。
开始想了两个错误算法,感觉我真心傻×到爆了。。。其实就是简单的数位递推(不能说是dp哟)
如果只考虑后i-1位的答案与第i位的答案的关系
那么即
(4(7)000...+a)*(4(7)000...+b)=>4(7)000..*4(7)000..+a*b+a*4(7)0000...+b*4(7)0000...
注意到a*b即后i-1位的答案,后两个为前缀和之类的,第一项可以直接计算的。
注意由于只有两个数,在考虑后i位时,就只有两种可能,第一位只有4,或者有一部分4,后一部分是7,于是就可以很方便的转移了
  评论这张
 
阅读(229)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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