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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

TCO13 Round 2A & SRM 574  

2013-04-11 16:14:39|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最近状态下降很严重。。。头一直很疼,不知为什么,导致我都没法想题了。。很痛苦啊
唉,希望到省选的时候身体状况能够好转。。
目前的状态就是各处求虐,结果果断各处被虐。。
======================================
下面正题。
SRM 574的题目基本上都不会做。。。。。。。唉,都忘了是些什么题了,1050分的题目懒得写了,毕竟人太弱没办法,而且估计现在这状态也写不出题来。
500pt的题是道状压dp,结论很容易想到,但是我看错了几次题目。。囧死了。
======================================
下面继续正题
Round 2A我参加了比赛的。。结局就是rank 196,既没有晋级也没有T-shirt,郁闷。

第一题,两个相同长度的串,你可以选择一些位,然后分别取出两个串中的这些位,保持原来的顺序,然后将两个串拼起来来,求一种方案使得最终的串的字典序最小。。
显然有个结论,不考虑第二个串B,可以贪心出A的最优策略,并使之最长,方案一定是这个最有策略的前缀。。dp,于是没有然后了。

第二题,n*n的网格,里面的每个数都小于等于10,已经确定了k个数(k<=10),要求填剩下的数的方案数,使得每行每列的和的末位数都相等。
很容易证明n>10时答案就是10^(10+(n-1)*(n-1)-k)。原因嘛,就是列出方程后方程一定是有解的(为何此时我就没有想到正解呢。。。。)
至于n<=10的时候,那么就是有一些未知数,要求其和在mod10之下相等。。裸的高斯消元然后求出自由元的个数。。不过有点要注意,对于方程8*x=0(mod 10),其实是有两个解的,由于8没有逆元,但是自由元只有一个。。这就要求高斯消元必须对一个质数取模。。很简单,中国剩余定理就行了

第三题,求X的Y次方的个数,其中X<=A,Y<=B (A<=10^9,B<10^9)。
挺好的题目,分块容斥,很碉堡了的思路。
具体而言,对于一个数X,其不是任意数的任意次幂(>2),那么可以将其小于A的所有幂全部取出来算,这其实是将小于A内的数分成了很多部分。每部分得出的结果一定是不同的,所以只需分开计算。
若X^2>A,那么答案贡献就是B。
剩下的是X^2<A,这样的数顶多sqrt(A)个,所以可以一个一个考虑。
设num为最大的数使得X^num<A,我们要求出{x|x=1*i}U{x|x=2*i}U...U{x|x=num*i} forall i<=B 的数的个数。
注意到,我们容斥能够算的是这样一个问题,求{1-B}中是某些数的倍数的数的个数,却没有限定这个倍数的范围!
怎么办呢?其实很简单的,num不会超过30,对于每个数,其可能组合出的数是有个区间的,对于每个区间,只考虑能够存在于这个区间中的因子。具体的就是按照(k-1)*B+1,...,k*B,这样划分,对于每个k,只有数>=k-1的因子才会被考虑,注意,对于其中任意数,其倍数都会<=k。于是就可以暴力容斥了。
  评论这张
 
阅读(229)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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