2017-Sp117-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
今天重训去年训得十分差的ASC45（不仅题做得少，也没补，甚至读都没读完，三人可能啥都不记得)。开场各自看题，yzc开A，cjb开D，sub开F，很快三个人就开出来了(这也是去年训的时候过的三个题)，yzc和sub确认之后就上机做A，因为checker写错了耽误了一点时间，'''A1y42'''。cjb上机写D，'''D1y63'''，cjb D的做法似乎和以前sub和yzc做的时候不同。sub给yzc讲了一次做法后'''F1y74'''。sub此前会做了几何题K，开出了B，yzc和cjb研究C和E。sub上机先后'''B1y127'''，'''K2y195'''。期间yzc上机写了C的暴力，cjb上机抄BM效果不理想。后来cjb开出了H，sub写了预处理后，cjb上机'''H1y251'''。之后封榜后yzc决定莽一发和sub讨论过后复杂度更科学的暴力，结果发现能打出来表，最后1min极限操作获得wa，赛后发现有个LL写了int，改了之后重新打表获得通过。
== 总结 ==
=== chenjb ===
C再多5min就过了，最后压哨打表因为LL写成int而失败了，连续两天都因为LL压哨过题失败，要提起注意。另外以后有能冲一冲的算法要更加果断一些，C的打表程序跑得比想象中快得多，快封榜的时候就想出来了，一直没去写是一个巨大的失误，就算打不完，打多几项说不定会有新的思考？
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：第一行(1,4)，第二行(2,3)为初始1状态，一二行互换为初始0状态，2的幂次可行，2^i^的构造为：2^i-1^的01状态取反并在后面。

 * B：整理式子可得原题即求最短的区间S使得其和给定的互不相交区间的集合T的交的长度和大于定值K。Two Pointer扫一遍即可。

 * C：f[i][j][k][p][mask]代表前i个数，上一个数是j，当前A[i-1]为k，然后满足a[i]<a[j]的最大a[i]为p，已有数字状态为mask的方案数，用map来存储状态，暴力dp打表，5min就能打完，记得要用long long。

 * D：建一棵叶子节点>q的满二叉树，显然到达任意一个叶子节点的概率都是均等的，那么选择p个连给home，q-p个连给bar，剩下的直接连回根，这样就能在不改变剩余叶子节点均等概率的情况下消去多余的点了。

 * E：f[i][j]代表第i位是j的最小代价。构造限制j-1与j的第i&-i位互反，更小的位随意。总复杂度O(N^2^logN)。

 * F：与1以外的边随意编号，随后将当前2~n按照编号和排序，用最大的n-1个从小到大给1到i的边编号即可。可以发现2~n互相差至少为1，而1号点大于所有其他点。

 * G：把字符串的每个前缀和后缀塞进map里存下标，然后对于每个字符串，找到能与自己前(后)缀匹配的公共部分最大的串连边，之后跑floodfill，每500输出一下就好了，正确率能到达98%以上。为了时限可以考虑限制前后缀长度不小于magic(第一发过的代码设了25)，但是后来发现把所有前后缀塞进去也不过1.4s。至于证明，因为是长度50000的串里随机挑20000个起点且长度为50的串作为参考数据，那么基本上所有位置都能包括。

 * H：首先预处理出任意两点是否能看见，接下来给出dp，f[l][r]表示l到r之间能放的最多点数，转移的时候，首先用f[l][r-1]和f[l+1][r]更新，然后考虑从l到r找到第一个m，使得m能看见r，可以证明，当存在这一个m时，[l,m-1]和[m+1,r]是完全独立的，所以再用f[l][m-1]+f[m+1][r]去更新答案，如果找不到这样一个m，说明r看不见[l,r-1]任何一个点，则直接用f[l][r-1]+1去更新。

 * I：稳定婚姻算法，每次学生侧未匹配的选择未被拒绝过的最优课程选择，如超过限制，老师再把最差的学生踢掉即可。

 * J：左右两边可以折进来时直接折进来，不然就找到一段左右都比这段长的，并且折痕不同的折起来。

 * K：二分答案，凸多边形每条边向垂直方向收缩mid，求半平面交，旋转卡壳求最远点对是否大于2*mid即可。

 * [https://wiki.icpc.camp/wood-cube/ASC%2045 woodcube]

 * [https://wiki.icpc.camp/new-meta/Andrew%20Stankevich%20Contest%2045 New Meta]

流水账

今天重训去年训得十分差的ASC45（不仅题做得少，也没补，甚至读都没读完，三人可能啥都不记得)。开场各自看题，yzc开A，cjb开D，sub开F，很快三个人就开出来了(这也是去年训的时候过的三个题)，yzc和sub确认之后就上机做A，因为checker写错了耽误了一点时间，A1y42。cjb上机写D，D1y63，cjb D的做法似乎和以前sub和yzc做的时候不同。sub给yzc讲了一次做法后F1y74。sub此前会做了几何题K，开出了B，yzc和cjb研究C和E。sub上机先后B1y127，K2y195。期间yzc上机写了C的暴力，cjb上机抄BM效果不理想。后来cjb开出了H，sub写了预处理后，cjb上机H1y251。之后封榜后yzc决定莽一发和sub讨论过后复杂度更科学的暴力，结果发现能打出来表，最后1min极限操作获得wa，赛后发现有个LL写了int，改了之后重新打表获得通过。

总结

chenjb

C再多5min就过了，最后压哨打表因为LL写成int而失败了，连续两天都因为LL压哨过题失败，要提起注意。另外以后有能冲一冲的算法要更加果断一些，C的打表程序跑得比想象中快得多，快封榜的时候就想出来了，一直没去写是一个巨大的失误，就算打不完，打多几项说不定会有新的思考？

oipotato

subconscious

题解

• A：第一行(1,4)，第二行(2,3)为初始1状态，一二行互换为初始0状态，2的幂次可行，2ⁱ的构造为：2^i-1的01状态取反并在后面。
• B：整理式子可得原题即求最短的区间S使得其和给定的互不相交区间的集合T的交的长度和大于定值K。Two Pointer扫一遍即可。
• C：f[i][j][k][p][mask]代表前i个数，上一个数是j，当前A[i-1]为k，然后满足a[i]
• D：建一棵叶子节点>q的满二叉树，显然到达任意一个叶子节点的概率都是均等的，那么选择p个连给home，q-p个连给bar，剩下的直接连回根，这样就能在不改变剩余叶子节点均等概率的情况下消去多余的点了。
• E：f[i][j]代表第i位是j的最小代价。构造限制j-1与j的第i&-i位互反，更小的位随意。总复杂度O(N²logN)。
• F：与1以外的边随意编号，随后将当前2~n按照编号和排序，用最大的n-1个从小到大给1到i的边编号即可。可以发现2~n互相差至少为1，而1号点大于所有其他点。
• G：把字符串的每个前缀和后缀塞进map里存下标，然后对于每个字符串，找到能与自己前(后)缀匹配的公共部分最大的串连边，之后跑floodfill，每500输出一下就好了，正确率能到达98%以上。为了时限可以考虑限制前后缀长度不小于magic(第一发过的代码设了25)，但是后来发现把所有前后缀塞进去也不过1.4s。至于证明，因为是长度50000的串里随机挑20000个起点且长度为50的串作为参考数据，那么基本上所有位置都能包括。
• H：首先预处理出任意两点是否能看见，接下来给出dp，f[l][r]表示l到r之间能放的最多点数，转移的时候，首先用f[l][r-1]和f[l+1][r]更新，然后考虑从l到r找到第一个m，使得m能看见r，可以证明，当存在这一个m时，[l,m-1]和[m+1,r]是完全独立的，所以再用f[l][m-1]+f[m+1][r]去更新答案，如果找不到这样一个m，说明r看不见[l,r-1]任何一个点，则直接用f[l][r-1]+1去更新。
• I：稳定婚姻算法，每次学生侧未匹配的选择未被拒绝过的最优课程选择，如超过限制，老师再把最差的学生踢掉即可。
• J：左右两边可以折进来时直接折进来，不然就找到一段左右都比这段长的，并且折痕不同的折起来。
• K：二分答案，凸多边形每条边向垂直方向收缩mid，求半平面交，旋转卡壳求最远点对是否大于2*mid即可。
• woodcube
• New Meta

附加文件

• analysis-20160421.pdf by chenjb
• 1.png by chenjb