2017-C15-team6

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

= 比赛过程 =
    ||16m   ||i  ||1y||
    ||49m   ||k  ||2y||
    ||3h37m || c ||3y||
    ||4h59m ||d  || n||
 = 赵竟霖 = 
   正如表里面显示的,这次我们队的表现还是很菜菜.签完两道水题后大家就不知道该做什么了...看看榜,大家怎么都会做c呀,于是决定三个人一起先把c拿下.没有具体思路,只好先把最裸的暴力先敲出来,发现跑不过极限数据,于是无奈想办法优化.想了半小时有了大概的思路,就在暴力的基础上做了些修改.后来还是出现了O(n)个1e12以内的数判断是1,p,p^2^或者p*q中哪种形式.首先是想到用ml判素数,但不管我们用什么办法加以改进,在不超时的情况下都无法稳定出解.然后最终决定转向暴力,后来又想到这些数大部分都会是1,复杂度不容易达到最坏的上界,就写了暴力.后来是一个long long写成了int导致两种暴力跑出来不同的解,多亏队友及时发现错误才改正过来.过了c之后主要是集中精力做d,起初我们理解的题意是对的,但后来觉得这不符合赛制规则,大家都读了一遍题,就都同意了错误的提议,直到比赛结束都没有发现...似乎我们b也读错了题意,然后就放弃了.

   我本人嘛,就写了c,然后把大家带上了d错误的题意.这锅我背.

   首先,肯定是认真读题.其次,看见别人别人都过了一道题但自己却毫无头绪,记得大开脑洞,抛出一些大胆的想法和队友多多讨论,三个人合力把这种需要集智的题做出来.还有,记得补题.

 = 唐小虎 =

   - 关于Lazy Running一题的一些想法：
      - 要求大于k的距离最小值，所以我们最好把所有的距离都列出来变成一张表，然后找一个最小的大于k的就行了
      - 但是这显然是做不到的
      - 现在对这张表mod 2w
      - 因为显然如果dist在这张表里面，dist+2w也一定在这张表里面，那么这张表还是很有规律的
      - 所以就给出了这张表的另一个表示形式就是f[2][j]表示从起点出发再回到起点，dist\equiv j\ (mod\ 2w)的情况下的距离最小值
      - 这和第一点中提到的原表是等价的
      - 然后我们就相当于获得了所有距离的表，然后就可以了。
      - 如果没有想错的话，其实这个2w应该可以取各种各样的值
      - 比如d12+d23+d34+d41，再比如4w或者其他什么乱七八糟的模数，也一定有类似的性质
      - 所以这种解法的本质是什么？
      - 一种bool列表生成器？

比赛过程

16m	i	1y
49m	k	2y
3h37m	c	3y
4h59m	d	n

赵竟霖

正如表里面显示的,这次我们队的表现还是很菜菜.签完两道水题后大家就不知道该做什么了...看看榜,大家怎么都会做c呀,于是决定三个人一起先把c拿下.没有具体思路,只好先把最裸的暴力先敲出来,发现跑不过极限数据,于是无奈想办法优化.想了半小时有了大概的思路,就在暴力的基础上做了些修改.后来还是出现了O(n)个1e12以内的数判断是1,p,p²或者p*q中哪种形式.首先是想到用ml判素数,但不管我们用什么办法加以改进,在不超时的情况下都无法稳定出解.然后最终决定转向暴力,后来又想到这些数大部分都会是1,复杂度不容易达到最坏的上界,就写了暴力.后来是一个long long写成了int导致两种暴力跑出来不同的解,多亏队友及时发现错误才改正过来.过了c之后主要是集中精力做d,起初我们理解的题意是对的,但后来觉得这不符合赛制规则,大家都读了一遍题,就都同意了错误的提议,直到比赛结束都没有发现...似乎我们b也读错了题意,然后就放弃了.

我本人嘛,就写了c,然后把大家带上了d错误的题意.这锅我背.

首先,肯定是认真读题.其次,看见别人别人都过了一道题但自己却毫无头绪,记得大开脑洞,抛出一些大胆的想法和队友多多讨论,三个人合力把这种需要集智的题做出来.还有,记得补题.

唐小虎

- 关于Lazy Running一题的一些想法：

- 要求大于k的距离最小值，所以我们最好把所有的距离都列出来变成一张表，然后找一个最小的大于k的就行了

- 但是这显然是做不到的

- 现在对这张表mod 2w

- 因为显然如果dist在这张表里面，dist+2w也一定在这张表里面，那么这张表还是很有规律的

- 所以就给出了这张表的另一个表示形式就是f[2][j]表示从起点出发再回到起点，dist\equiv j\ (mod\ 2w)的情况下的距离最小值

- 这和第一点中提到的原表是等价的

- 然后我们就相当于获得了所有距离的表，然后就可以了。

- 如果没有想错的话，其实这个2w应该可以取各种各样的值

- 比如d12+d23+d34+d41，再比如4w或者其他什么乱七八糟的模数，也一定有类似的性质

- 所以这种解法的本质是什么？

- 一种bool列表生成器？