2017-Sp237-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，sub试图做个E，然后失败了，然后他跑路去打计蒜客了，cjb和yzc开始双打。cjb试图艹E，但是本地测试不太行，经过一番努力终于'''E2y74'''。cjb和yzc讨论F，觉得F瞎jb染就行了，'''F1y99'''。之后cjb骗yzc去写G，结果tle了，只好打表'''G3y122'''。cjb想到了B的重要性质，给了大概做法给yzc，结果还是有点细节的，yzc写的很努力，'''B1y166'''。cjb很努力地做J，想到关键性质之后图画错了，又浪费了很久时间，最后'''J2y223'''。sub终于良心发现回来了，和yzc做了个D，'''D2y235'''。
== 总结 ==
=== chenjb ===
艹，sub没良心。不过我和yzc怎么已经能双打ASC了啊，这场里面几个题其实都还不错啊？
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：sub

 * B：按位枚举，f[i]表示前i位是border的方案数，枚举满足border的子串的最小位数，分类讨论进行转移。

 * C：

 * D：单字母字符串无解，否则第一个自动机是整个串形成一个环，起点是接受态，第二个自动机是任意取某种字母，从起点出发走次数加1步，则自动机只能接受这种字母恰好出现这么多次的字符串，而第一个自动机一定是原串的重复，所以任意字母出现次数不会和原来相等。

 * E：筛出素数后从小到大枚举，随机打乱行和列，然后给每行、列恰n/2+1个元素*=p，重复直到找到合法解。

 * F：随便染色，每次优先取染色边数最多的点，如果有多个可以考虑取边数最多的。

 * G：维护两个人手上数字的状态，直接dp，打表。

 * H：

 * I：

 * J：先分成右下和左下各做一次，对于一个点(i,j)，令L表示最左端，U表示最右端，则在(L,U)到(i,j)中至多走一步，因此直接考虑f[i][j]=f[L][U]+1，注意要去掉那些位于边缘且左上部分没有任何块的点，最后ans取两次的max(f[i][j])。

流水账

出门各自看题，sub试图做个E，然后失败了，然后他跑路去打计蒜客了，cjb和yzc开始双打。cjb试图艹E，但是本地测试不太行，经过一番努力终于E2y74。cjb和yzc讨论F，觉得F瞎jb染就行了，F1y99。之后cjb骗yzc去写G，结果tle了，只好打表G3y122。cjb想到了B的重要性质，给了大概做法给yzc，结果还是有点细节的，yzc写的很努力，B1y166。cjb很努力地做J，想到关键性质之后图画错了，又浪费了很久时间，最后J2y223。sub终于良心发现回来了，和yzc做了个D，D2y235。

总结

chenjb

艹，sub没良心。不过我和yzc怎么已经能双打ASC了啊，这场里面几个题其实都还不错啊？

oipotato

subconscious

题解

  • A：sub
  • B：按位枚举，f[i]表示前i位是border的方案数，枚举满足border的子串的最小位数，分类讨论进行转移。
  • C：
  • D：单字母字符串无解，否则第一个自动机是整个串形成一个环，起点是接受态，第二个自动机是任意取某种字母，从起点出发走次数加1步，则自动机只能接受这种字母恰好出现这么多次的字符串，而第一个自动机一定是原串的重复，所以任意字母出现次数不会和原来相等。
  • E：筛出素数后从小到大枚举，随机打乱行和列，然后给每行、列恰n/2+1个元素*=p，重复直到找到合法解。
  • F：随便染色，每次优先取染色边数最多的点，如果有多个可以考虑取边数最多的。
  • G：维护两个人手上数字的状态，直接dp，打表。
  • H：
  • I：
  • J：先分成右下和左下各做一次，对于一个点(i,j)，令L表示最左端，U表示最右端，则在(L,U)到(i,j)中至多走一步，因此直接考虑f[i][j]=f[L][U]+1，注意要去掉那些位于边缘且左上部分没有任何块的点，最后ans取两次的max(f[i][j])。
附加文件