• 2018.5.5-6 GDCPC2018广东省赛 6/10 Rank12 Au


    开场各自读题。

    Hong看了A推了一会没推出来就继续读题了

    然后发现大家开始过A..就继续推了一会..还是没推出来..决定上机打个表..然后就找到规律了..就过了..

    He想出了B..上机写了就过了..

    Hong推出了F..上了就过了..

    He想了个J的假算法..上机开始写..发现是假的..就下来了..开始想C

    Hong想出了H..上了就过了..

    He准备好C就上了..然后没过样例..

    Hong上机打了一下毕达哥拉斯三元组的板子..打了个表..瞬间找到了规律..就过了E..

    (甚至感觉..E的数据范围可以巨大..)

    然后He过了C的样例..改了就交了..然后WA了..

    然后三人对着C的代码Debug了1h..最后对拍发现..He把变量名zz和z打反了.......改了就过了..

    Huang之前想出了I..但没什么时间了..但还是上机写了..

    Hong和He一起推了一下D..建了个假图..把Huang赶下来了两次..最后都没写完..然后就GG了..

    然后我们就6题滚了啊..

    题解


    A


    打表发现 an = 2 * an-1 + 2 ^ (n - 2), a1 = 1, ans = n * an。上了个矩阵快速幂过的。

    赛后发现可以拆成sigma (i ^ 2 - i + i)C.. 的形式..可以直接求出公式

    签到题

    B


     暴力从每个点找环+树状数组+预处理因子

    C


     可持久化字典树

    D


    网络流。把所有点拆点入点出点之间连点价值的边,原图中的边出点向入点连无穷大边。由于原图是二分图,可以先对原图唯一的黑白染色。之后B1和B2的点若和染色结果不同,则源向点连点价值的边,否则向汇连等于点价值的边。跑最大流即可。

    坑点是B1和B2有交集..交集的点必须删掉。

    E


    原题等价于寻找n使得 (n - 1) ^ 2 + n ^ 2为完全平方数,即寻找x与y相差1的勾股数。

    用毕达哥拉斯三元组打表发现,以3.4.5为基不断乘B矩阵(全是正数的矩阵)可以得到所有满足如上条件的勾股数。这样的勾股数有20组左右。

    求出来所有这样的勾股数暴力找即可。

    数据范围可以扩大很多。

    F


    博弈。发现2是先手必败态,4是先手必胜态。手玩6、7、8、9之后发现,开始时每次切2出来,到4或5为止,获胜状态最多。

    若n为奇数,概率为(n + 1) / 2 / n

    若n为4k,概率为(n / 2 + 2) / n

    若n为4k+2,概率为(n / 2 - 1) / n

    G


    H


    DP。DP[i]表示到当前位置为止,和为i需要的最多元素个数,0<=i<=9。开始时,能加成9就尽量加成9,之后尽量加成8.....当DP[本次要加成的数]不为0,则记录次数并将DP清0。

    复杂度O(10*10*n)

    I


    J


    吐槽


    还可以啊

    就是本来打算全1A的来着..被Hels搞了啊..

    过快点可能就7题了啊..

    惨啊..

    前面中山队真是无敌啊..

    总结


    Hong


    前期出题还是有点慢啊..30min才想到打表啊..下次数学题先打表啊..

    E应该早点上啊..下次是不是应该我的题想到直接上机啊..?反正基本5min过啊..这样罚时会少不少啊..

    前期节奏还是有点慢啊..感觉应该果断3开啊

    小目标下次2.5h过5题?

    He


     手不太稳,仍需多连续数据结构(长代码)的题,大型数据结构还不太会。

    Huang


  • 相关阅读:
  • 原文地址:https://www.cnblogs.com/aseer/p/9003535.html
  • 最新文章
  • 热门文章
一二三 - 开发者的网上家园