2017-Sp63-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
 * 题目来源：Petrozavodsk Winter Training Camp 2018: ITMO U Contest
 * 现场排名：https://contest.yandex.com/contest/7335/standings/
 * Camp排名：https://official.contest.yandex.com/itmo2018china/contest/7350/standings/
== 流水账 ==
开场各自看题，看到有人过了G后，cjb读了G，想到了做法，sub和yzc讨论了E题，上机尝试了一下发现式子算不出来，最后打算先做很多人过的G。cjb和sub确认了做法，就告诉了yzc，yzc上机写G的线段树，但是有点担心tle，cjb表示过不了就改成线性扫，结果过了，'''G1y62'''。此时场上D和J过的人比较多，cjb和yzc研究J，sub研究D，之后sub上机写D，wa了一发后发现访问越界，修改后'''D2y101'''。cjb和yzc研究了很久J，在sub的鼓励下，决定先写一发(假装状态真的很少)，获得了几发wa，三个人一起找bug，修改后变成了mle，本地发现时限是够的，但是空间需要两倍，cjb和yzc卡了好几发MLE和RE，最后sub看穿了题目，上机'''J7y184'''。接下来时间三个人一起讨论C，很快得到了一个做法，yzc上机获得wa，之后不停修改策略，一直wa，直到assert了一下发现有问题，yzc发现自己的代码写错了，最后终于'''C7y250'''(实际上第一个做法就是对的....多了170min的罚时)。之后考虑做E或者L，E的式子很早得到了，但是一直算不出来，努力了一下放弃了。L也是差一个东西不能很快算出来，最后sub灵机一动让yzc打表找规律，结果真的找到了循环节，最后'''L3y291'''。凭借封榜后的2个题，回到了rk 5，次于thu两个队，pku一个队和sjtu一个队。
== 总结 ==
=== chenjb ===
今天的题风是我不太擅长的，但是感觉自己参与度比以前训asc的时候好多了，这一点还是先表扬一下自己，但是弱项还是要补强才行，不能太依赖sub。今天yzc的状态不是很好，我们三个人还是要注意休息，犯了很多低级错误直接导致我们的罚时感人。但是回顾流水账，我感觉我们的一个进步是比起以前做某一套Trinity Contest的时候，现在即使进程艰难，我们还是打出了自己的思路，双开、合攻都基本体现了我们的思路，我想这就是参加这种camp的意义，在实际比赛中谁能稳定表现平时的自己，谁就会占据优势。不过，这个L题卡了很久，还是证明我们套路不够熟悉，另外交互题以后要更加慎重，虽然策略很重要，但是因为难调试，要更加谨慎对待自己代码实现。至于最后为什么封榜后能过到第五个题，我觉得一个经验就是：高难度场封榜后开一道新的题是比较冒险而不实际的，但是因为sub执行了自己的任务，E和L的式子实际上封榜前都做了出来(也就是说有一定思考度了)，所以封榜后我们E和L都尝试了，最后就做出了L，这个是在高难度场或者卡题的时候很容易忽略的东西，自己的节奏其实是非常重要的(另一个vivid的例子就是北京站的时候我们封榜后做的I也是sub此前就有一定思考量的)，训练中就要非常注意这些东西。
=== oipotato ===
sub今天非常carry。我今天非常sb，可能是没睡好，也可能是昨天被sub在总结里奶了一口。难题场感觉还是有点放不开手脚，疲于跟榜，在前期的交流和开题上相比于昨天差了一些，导致前期非常爆炸。但是这次camp目前来看我们封榜后慢慢的稳定能过题，虽然其中有我们前期打得烂中期题封榜后才过的原因，但是也算是一个进步了。
=== subconscious  ===
结果今天的题仍然非常不友好，更重要的是我们罚时爆炸了...其实今天的可做题题偏数学多一点，导致我压力有点大？不过最后还是保持了排名。
== 题解 ==
 * A：
   * 题意：求题目所述条件下的概率。
   * 题解：根据定义写出积分式子，还剩下一重积分时，可取n=2，3，4分类讨论强行积分，也可以simpson。
 * E：
   * 题意：具体见题意。主要难点求(2n-1)!!%1e9+7,2n-1<=1e18。
   * 题解：标算通过pi(x*2^17^+y)二项式展开的两项分类讨论大力计算获得。杜教的做法：f(x,k)=(2x+1)*...*(2x+2k-1)，原题即求f(0,n)。由以x二项式展开有只需要维护前64项，f(x,k)=c_0*x^0^+...+c_63*x^63^。f(x,0)=1,f(x,2k+1)=f(x,2k)*(2x+2k+1),f(x,2k)=f(x,k)*f(x+k,k),可在O(64^2^)内计算得到。
 * H：
   * 题意：给定数组a，b，定一个排列p，使得数组a和b重排，之后对于每一个a[i]，找到1-i 中和a[i]抑或值最小的b[j]，求最小的和，还有满足条件下的字典序最小的排列。长度50，数字范围1e6。
   * 题解：假设最终排列中，a[i]的贡献来自于b[j]，则视为j向i连一条边，若i=j，则从root向i连一条边。显然这是一棵树，于是最小代价可以通过对完全图做最小树形图得到。至于字典序最小的排列，则暴力枚举每一位填什么，然后建新的图之后跑最小树形图，若答案不变，则直接填入。复杂度O(n^5^)。
 * I：
   * 题意：给出一个n=500000的数字字符串S和一个m=500000的排列P，询问有多少个长度为m的子串满足S[i]=S[P[i]]（即经过一次变换后等于自身)。
   * 题解：这一类对齐的字符串匹配判定问题，一种经典的思路是构造哈希函数然后转化为卷积去做。我们对于p[i]，构建一个数组A，对于每个i随机一个值w，A[i]+=w,A[P[i]]-=w，这样如果子串t中t[i]=t[P[i]]，则自然w*t[i]+(-w)*t[p[i]]=0，将A数组和每一个长度为m的子串作内积，满足条件的子串其哈希值一定是0，不等于0的话则肯定不是，那么我们将S取反后和A作卷积，然后再取反，得到的就是对于每个起点的哈希值，我用了NTT。为了稳妥，应该多检验几次，本来打算设magic(检验次数)=10，结果magic=3就过了，最后magic=1也能过。

 [[BR]] [[BR]]* [https://wiki-nightfall.icpc-camp.org/Day2 Solution by Nightfall]
== 补题 ==
 * ~~A~~ by yzc
 * B
 * ~~E~~ by sub
 * F
 * ~~H~~ by yzc
 * ~~I~~ by cjb
 * K

• 题目来源：Petrozavodsk Winter Training Camp 2018: ITMO U Contest
• 现场排名：https://contest.yandex.com/contest/7335/standings/
• Camp排名：https://official.contest.yandex.com/itmo2018china/contest/7350/standings/

流水账

开场各自看题，看到有人过了G后，cjb读了G，想到了做法，sub和yzc讨论了E题，上机尝试了一下发现式子算不出来，最后打算先做很多人过的G。cjb和sub确认了做法，就告诉了yzc，yzc上机写G的线段树，但是有点担心tle，cjb表示过不了就改成线性扫，结果过了，G1y62。此时场上D和J过的人比较多，cjb和yzc研究J，sub研究D，之后sub上机写D，wa了一发后发现访问越界，修改后D2y101。cjb和yzc研究了很久J，在sub的鼓励下，决定先写一发(假装状态真的很少)，获得了几发wa，三个人一起找bug，修改后变成了mle，本地发现时限是够的，但是空间需要两倍，cjb和yzc卡了好几发MLE和RE，最后sub看穿了题目，上机J7y184。接下来时间三个人一起讨论C，很快得到了一个做法，yzc上机获得wa，之后不停修改策略，一直wa，直到assert了一下发现有问题，yzc发现自己的代码写错了，最后终于C7y250(实际上第一个做法就是对的....多了170min的罚时)。之后考虑做E或者L，E的式子很早得到了，但是一直算不出来，努力了一下放弃了。L也是差一个东西不能很快算出来，最后sub灵机一动让yzc打表找规律，结果真的找到了循环节，最后L3y291。凭借封榜后的2个题，回到了rk 5，次于thu两个队，pku一个队和sjtu一个队。

总结

chenjb

今天的题风是我不太擅长的，但是感觉自己参与度比以前训asc的时候好多了，这一点还是先表扬一下自己，但是弱项还是要补强才行，不能太依赖sub。今天yzc的状态不是很好，我们三个人还是要注意休息，犯了很多低级错误直接导致我们的罚时感人。但是回顾流水账，我感觉我们的一个进步是比起以前做某一套Trinity Contest的时候，现在即使进程艰难，我们还是打出了自己的思路，双开、合攻都基本体现了我们的思路，我想这就是参加这种camp的意义，在实际比赛中谁能稳定表现平时的自己，谁就会占据优势。不过，这个L题卡了很久，还是证明我们套路不够熟悉，另外交互题以后要更加慎重，虽然策略很重要，但是因为难调试，要更加谨慎对待自己代码实现。至于最后为什么封榜后能过到第五个题，我觉得一个经验就是：高难度场封榜后开一道新的题是比较冒险而不实际的，但是因为sub执行了自己的任务，E和L的式子实际上封榜前都做了出来(也就是说有一定思考度了)，所以封榜后我们E和L都尝试了，最后就做出了L，这个是在高难度场或者卡题的时候很容易忽略的东西，自己的节奏其实是非常重要的(另一个vivid的例子就是北京站的时候我们封榜后做的I也是sub此前就有一定思考量的)，训练中就要非常注意这些东西。

oipotato

sub今天非常carry。我今天非常sb，可能是没睡好，也可能是昨天被sub在总结里奶了一口。难题场感觉还是有点放不开手脚，疲于跟榜，在前期的交流和开题上相比于昨天差了一些，导致前期非常爆炸。但是这次camp目前来看我们封榜后慢慢的稳定能过题，虽然其中有我们前期打得烂中期题封榜后才过的原因，但是也算是一个进步了。

subconscious

结果今天的题仍然非常不友好，更重要的是我们罚时爆炸了...其实今天的可做题题偏数学多一点，导致我压力有点大？不过最后还是保持了排名。

题解

• A：
  • 题意：求题目所述条件下的概率。
  • 题解：根据定义写出积分式子，还剩下一重积分时，可取n=2，3，4分类讨论强行积分，也可以simpson。
• E：
  • 题意：具体见题意。主要难点求(2n-1)!!%1e9+7,2n-1<=1e18。
  • 题解：标算通过pi(x*2¹⁷+y)二项式展开的两项分类讨论大力计算获得。杜教的做法：f(x,k)=(2x+1)*...*(2x+2k-1)，原题即求f(0,n)。由以x二项式展开有只需要维护前64项，f(x,k)=c_0*x⁰+...+c_63*x⁶³。f(x,0)=1,f(x,2k+1)=f(x,2k)*(2x+2k+1),f(x,2k)=f(x,k)*f(x+k,k),可在O(64²)内计算得到。
• H：
  • 题意：给定数组a，b，定一个排列p，使得数组a和b重排，之后对于每一个a[i]，找到1-i 中和a[i]抑或值最小的b[j]，求最小的和，还有满足条件下的字典序最小的排列。长度50，数字范围1e6。
  • 题解：假设最终排列中，a[i]的贡献来自于b[j]，则视为j向i连一条边，若i=j，则从root向i连一条边。显然这是一棵树，于是最小代价可以通过对完全图做最小树形图得到。至于字典序最小的排列，则暴力枚举每一位填什么，然后建新的图之后跑最小树形图，若答案不变，则直接填入。复杂度O(n⁵)。
• I：
  • 题意：给出一个n=500000的数字字符串S和一个m=500000的排列P，询问有多少个长度为m的子串满足S[i]=S[P[i]]（即经过一次变换后等于自身)。
  • 题解：这一类对齐的字符串匹配判定问题，一种经典的思路是构造哈希函数然后转化为卷积去做。我们对于p[i]，构建一个数组A，对于每个i随机一个值w，A[i]+=w,A[P[i]]-=w，这样如果子串t中t[i]=t[P[i]]，则自然w*t[i]+(-w)*t[p[i]]=0，将A数组和每一个长度为m的子串作内积，满足条件的子串其哈希值一定是0，不等于0的话则肯定不是，那么我们将S取反后和A作卷积，然后再取反，得到的就是对于每个起点的哈希值，我用了NTT。为了稳妥，应该多检验几次，本来打算设magic(检验次数)=10，结果magic=3就过了，最后magic=1也能过。

* Solution by Nightfall

补题

• A by yzc
• B
• E by sub
• F
• H by yzc
• I by cjb
• K

附加文件

• 1.png by chenjb
• 180131.en.pdf by chenjb
• day2tutorial.pdf by chenjb