算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
A题
求字符串ASCII码之和,遍历即可。
B题
我的方法是先猜一个数,然后向两边递推,用long double刚好卡过~
B
C题
对于长度len,我们要知道len所有的因子 fac,可以分解成的三边互质的三角形种类数,和len/fac的分组种类。
后者是2^(len/fac),也就是插板问题...
前者我的方法是预处理:

先不管互质的问题,如果我们就针对一个长度 L求他可以分解成的三角形种类数。我们可以枚举最长边Lmax。
然后以Lmax为最长边的三角形一共有 Lmax - ceil((L-Lmax)/2) + 1个。也就是枚举次长边。
这样的话,对于每个L,最长边可取范围一定是一个区间,我们可以通过L-1的区间来推出L的区间。
我们可以看出,L增加1的话,对于不变的Lmax,Lmax - ceil((L-Lmax)/2) + 1要么不变,要么变化了1。和奇偶性有关。
于是这个我们也可以维护了。。。。

于是非互质的问题求出来了。
接下来,假设f(L)是非互质的情况,那么互质的性况应该是g(L) = f(L) - sum(g(K));其中K是L的因子。
这个东西可以用筛法来搞,复杂度O(nlogn)。

问题解决。
C

DEFGHJ不会

I题
还是枚举因子,递推预处理。。。
I

K题
大陈题。。。 根据剩余类建图广搜。。。
posted on 2012-11-17 23:04 西月弦 阅读(1026) 评论(6)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: 2012亚洲区成都现场赛原创题解
2012-11-18 12:04 | 目测君
C题三边有要求互质吗?  回复  更多评论
  
# re: 2012亚洲区成都现场赛原创题解
2012-11-18 12:09 | 目测君
C的复杂度为什么是nlogn呢?大神...求个因子是sqrt(n),然后再枚举因子也是sqrt(n)啊@目测君
  回复  更多评论
  
# re: 2012亚洲区成都现场赛原创题解
2012-11-18 12:28 | 西月弦
@目测君
for(int i = 1; i < N; i++)
for(int j = i+i; j < N; j+=i)
用筛法的话,根据调和级数的性质是nlogn的  回复  更多评论
  
# re: 2012亚洲区成都现场赛原创题解
2012-11-18 12:29 | 西月弦
@目测君
不要求互质,但是求互质的可以消除重复的情况。
比如 (2,2,2) (3,3,3) 可以看成 2*(1,1,1) 和 3*(1,1,1)  回复  更多评论
  
# re: 2012亚洲区成都现场赛原创题解
2012-11-19 20:41 | 目测君
懂你意思,两个三元组之间要互质..
关于那个f(x)有个递推式,你可以百度下..
@西月弦
  回复  更多评论
  
# re: 2012亚洲区成都现场赛原创题解
2012-11-20 01:23 | panguan
@西月弦
筛法写水了吧 不是j = i * i ?  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理