Codeforces Round #339 (Div. 2)

• contest link

　　CF#339 (Div. 2) ，真的是只做了Div.2的题。难度难以评价，质量呵呵，Div. 1部分可能会有比较好的题目，但除了那道万恶的几何其他都没看题。鉴于Div. 1一题没做，可以考虑virtual一发试试。低分号(Des_Payfor)参赛，最大收获是终于体验了一把Room毒瘤的快感，把整个Room的A题稳稳控住，hack掉了13发，甚至凭借hack加分莫名其妙混了+74的rating，感觉整个人都萌萌哒→_→。
　　扯淡完毕，如果A题一直跪的话请继续看，其他情况可以右上角了~

• 614A-Link/Cut Tree

  题意：
  　　与树链剖分并没有任何卵关系，就是求[l,r]中的k的整数幂。　
  解法：
  　　就算是最小的 k = 2 的时候也只是2^64 >> 1e18了，所以理论上来讲最多枚举60+次了，问题出在喜闻乐见的整数溢出。
  　　设a是我们的枚举的中间结果，也就是k的整数次幂。有以下几种情况：
  　　I. 用while(a <= r)来判断枚举过程是否终止的。 这是最蠢的错法，试想k = 1e9，k^2还可以在范围内，k^3呢？ 所以试试这组数据1 1000000000000000000 1000000000 或者这组 1 1000000000000000000 128 ； 什么？ 你说你过了这两组数据？ 那大概你用的是 unsigned long long吧，恰好躲过去而已，再试试这组数据1 1000000000000000000 256。错的原因是溢出导致a <= r一直成立，于是乎TLE了。
  　　II. 用while(a <= r && a > 0)判断枚举过程是否终止的。 这些同学们考虑到了long long 溢出变成负数，但是要知道并不是溢出一定会变成负数呀，试试这个1 1000000000000000000 370。溢出为正数且在[l,r]范围内，唉...
  　　III. 用for (i = 1;i < somenum;i++)控制枚举次数的。注意到了TLE的问题，但是逃不了WA。同上，溢出为正数且在[l,r]范围内。
  　　---------------分割线-------------------
  　　说了这么多错误的做法，再说几种正确的过题姿势吧：
  　　I. while(a <= r/K)或类似，控制上界。
  　　II. 使用double运算，可以忽略上界的影响。
  　　III.　python大法好。(Room里有一哥们用的python，怎么看都是错的，结果我在本地敲了个差不多的代码才发现，python的int溢出时会自动变成浮点数存储，怎么看这道题都是为python设计的...)
  　　ps: 虽然比赛题目质量不怎么样，但是这题确实搞的挺欢乐的...被hack了若干次的同学们也无需放在心上，这场确实结果与实力无关。
  code

• 614B-Gena's Code

  题意：
  　　题意说的好玄乎，结果就是求若干个数的乘积...而且最多只有一个数不是0 | 10*。 　　
  解法：
  　　没什么好说的，pretest很强，几乎只有TLE没有测出来了。
  　　要注意的是——有0输出0，没有特殊数的话记得输出前缀是'1'，其他情况就是输出特殊数之后，再输出符合上述正则表达式的的数的所有'0'。　　　 　　
  code

Copyright © 2015-2016 zhyack. All Rights Reserved.