2017-Sp297-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
=== chenjb ===
靠着模拟题拿到了rk1，yzcnb。A这个构造还不错，夸夸自己。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：先用1..n-1构造长度为n的链，然后根据长度%3的关系连一条从n回来1的边，之后考虑任意一对(i,j)之间都可以从i连向j且%3不变的边，穷举连就好，注意不要重复连边。

 * B：模拟。

 * C：归纳成最长下降子序列不超过2，reverse原串，然后f[i][j]代表长度为i的排列，目前最长上升子序列dp[2]的最小值为j，转移O(n)，最后再判别后加的几个是否合法，总复杂度O(n^3^)。

 * D：f[i][j][k][p],盐，时空，位置，时间进行dp。

 * E：sub  [https://icpc.camp/three-investigators/2013%20ACM-ICPC%20Asia%20Chengdu%20Regional%20Contest#e.-exhausted-robot]

 * F：白边在前和在后分别做一次算出上下界，注意本身无生成树的情况。

 * G：维护大小两个ac自动机，小自动机每次暴力重构，大小超过sqrt时并进大自动机重构，注意每次要判断新加入的串在两个自动机有没有出现过。

 * H：直接算。

 * I：模拟，用set维护榜单。

 * J：考虑m+kp所作的贡献，一共分成三段，直接等差数列求和。

流水账

chenjb

靠着模拟题拿到了rk1，yzcnb。A这个构造还不错，夸夸自己。

oipotato

subconscious

题解

• A：先用1..n-1构造长度为n的链，然后根据长度%3的关系连一条从n回来1的边，之后考虑任意一对(i,j)之间都可以从i连向j且%3不变的边，穷举连就好，注意不要重复连边。
• B：模拟。
• C：归纳成最长下降子序列不超过2，reverse原串，然后f[i][j]代表长度为i的排列，目前最长上升子序列dp[2]的最小值为j，转移O(n)，最后再判别后加的几个是否合法，总复杂度O(n³)。
• D：f[i][j][k][p],盐，时空，位置，时间进行dp。
• E：sub https://icpc.camp/three-investigators/2013%20ACM-ICPC%20Asia%20Chengdu%20Regional%20Contest#e.-exhausted-robot
• F：白边在前和在后分别做一次算出上下界，注意本身无生成树的情况。
• G：维护大小两个ac自动机，小自动机每次暴力重构，大小超过sqrt时并进大自动机重构，注意每次要判断新加入的串在两个自动机有没有出现过。
• H：直接算。
• I：模拟，用set维护榜单。
• J：考虑m+kp所作的贡献，一共分成三段，直接等差数列求和。

附加文件

• 1.png by chenjb