2017-Personal4-team2

从 Trac 迁移的文章

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

原文章内容如下：

 * A
  * 区间DP+四边形不等式。
 * B
  * 显然老鼠归属的洞的位置顺序是按照老鼠的位置顺序不减的。f[i][j]表示前i个洞，进前j只老鼠的最小值。f[i][j]=min(f[i-1][k]+(k+1...j)到i号洞的代价)。根据第k+1只老鼠和第j只老鼠在第i个洞的哪一边有三种不同的式子，但是贡献都是只跟自己有关的定值，由于有容量限制，维护一个递增的单调队列即可。
 * C
  * 考虑维护w个栈，每个栈维护这一列的球，用线段树维护区间的栈顶的最小值。从上往下模拟球下落的过程，在每块板处，在线段树中将有元素可以弹栈的栈找出并弹栈计算答案。由于每块板最多产生2个新的同种球，所以至多w+2*n种球，只要每次保证线段树区间最小值都不会弹栈时及时退出，即可保证复杂度。
 * D
  * 没有传送门就是普通的概率DP，有了传送门之后，就是某个DP值直接等于另一个DP值，由于转移产生了环，用高斯消元求解所有DP值即可。
 * E
  * 显然的DP是f[i][j]表示前j个人，分成k组的最优值。注意对于一组f[i][*]，从f[i-1][*]转移时具有决策单调性，分治维护即可。
 * F
  * 数位DP，f[i][j][k]表示前i位，和模7结果为j，数字模7结果为k的答案，用cnt，sum，sqrsum即可维护末尾加一个数字之后的新的sqrsum。枚举新的一位数字时不枚举7即可避开第一个条件。
 * G
  * dp[i][j]表示i层的二叉树，有j条互不相交的路径的方案数。转移时新增一个根结点，考虑新方案不包括根结点/根结点形成新路径/根结点连接左右各一条路径/根结点接在左(右)某条路径的一端/根结点连接左(右)某两条路径，每种情况转移即可。由于每次转移最多将L,R的答案转移给L+R-1，最后要的答案又是dp[k][1]，所以过程中最多只需要用到j<=k的dp[i][j]。
 * H
  * dp[i][0/1][j]表示i子树中选了j件物品，i这个点用不用减价的最小价格。最后枚举整棵树选几件的价格在b以内即可。合并子树时，只枚举到子树大小，任意两个点就只会在lca处产生一次转移，复杂度为N^2^。
 * I
  * dp[i][j][k][0/1]表示选取了i个V，j个K，k个X，是否最后一个字母是V的最小次数。转移枚举下一个字母，代价就是这个字母前面还有多少个另外两个字母没有进入转移，预处理时记录即可。
 * J
  * dp[i][0/1]表示i这棵子树，最后有没有回到父亲的最大答案。对于回到父亲的dp值，所有儿子取k-1个最大的回来的值即可，对于不回到的，再找一个下去之后不回来的即可。
 * K
  * 可以发现，f0(n)=2^(n的不同质因子个数)^，显然这是一个积性函数。fr+1(n)=sigma(fr(d)),d|n,这可以看成fr和g(n)=1的狄利克雷卷积，所以也是一个积性函数。于是fr(n)=fr(p1^k1^)*fr(p2^k2^)...*fr(pi^ki^)，于是只需要求fr(p^x^)，显然只和x有关，与p无关。于是求fr(2^x^)的值，用R*log(N)的dp即可求出。
 * L
  * 对于同一个Sy,对于子序列，预处理每个位置向后每种字母第一次出现位置。对于子串，建SAM。这样就能在O(min{len(Sx),len(Sy)})的时间里回答询问。对于不超过sqrt(n)的Sy，单次询问<=sqrt(n)。对于长度超过sqrt(n)的，将询问去重之后，总扫描长度<=n，这类串至多只有sqrt(n)个。所以总复杂度为nsqrt(n)。

• A
  • 区间DP+四边形不等式。
• B
  • 显然老鼠归属的洞的位置顺序是按照老鼠的位置顺序不减的。f[i][j]表示前i个洞，进前j只老鼠的最小值。f[i][j]=min(f[i-1][k]+(k+1...j)到i号洞的代价)。根据第k+1只老鼠和第j只老鼠在第i个洞的哪一边有三种不同的式子，但是贡献都是只跟自己有关的定值，由于有容量限制，维护一个递增的单调队列即可。
• C
  • 考虑维护w个栈，每个栈维护这一列的球，用线段树维护区间的栈顶的最小值。从上往下模拟球下落的过程，在每块板处，在线段树中将有元素可以弹栈的栈找出并弹栈计算答案。由于每块板最多产生2个新的同种球，所以至多w+2*n种球，只要每次保证线段树区间最小值都不会弹栈时及时退出，即可保证复杂度。
• D
  • 没有传送门就是普通的概率DP，有了传送门之后，就是某个DP值直接等于另一个DP值，由于转移产生了环，用高斯消元求解所有DP值即可。
• E
  • 显然的DP是f[i][j]表示前j个人，分成k组的最优值。注意对于一组f[i][*]，从f[i-1][*]转移时具有决策单调性，分治维护即可。
• F
  • 数位DP，f[i][j][k]表示前i位，和模7结果为j，数字模7结果为k的答案，用cnt，sum，sqrsum即可维护末尾加一个数字之后的新的sqrsum。枚举新的一位数字时不枚举7即可避开第一个条件。
• G
  • dp[i][j]表示i层的二叉树，有j条互不相交的路径的方案数。转移时新增一个根结点，考虑新方案不包括根结点/根结点形成新路径/根结点连接左右各一条路径/根结点接在左(右)某条路径的一端/根结点连接左(右)某两条路径，每种情况转移即可。由于每次转移最多将L,R的答案转移给L+R-1，最后要的答案又是dp[k][1]，所以过程中最多只需要用到j<=k的dp[i][j]。
• H
  • dp[i][0/1][j]表示i子树中选了j件物品，i这个点用不用减价的最小价格。最后枚举整棵树选几件的价格在b以内即可。合并子树时，只枚举到子树大小，任意两个点就只会在lca处产生一次转移，复杂度为N²。
• I
  • dp[i][j][k][0/1]表示选取了i个V，j个K，k个X，是否最后一个字母是V的最小次数。转移枚举下一个字母，代价就是这个字母前面还有多少个另外两个字母没有进入转移，预处理时记录即可。
• J
  • dp[i][0/1]表示i这棵子树，最后有没有回到父亲的最大答案。对于回到父亲的dp值，所有儿子取k-1个最大的回来的值即可，对于不回到的，再找一个下去之后不回来的即可。
• K
  • 可以发现，f0(n)=2^{(n的不同质因子个数)}，显然这是一个积性函数。fr+1(n)=sigma(fr(d)),d|n,这可以看成fr和g(n)=1的狄利克雷卷积，所以也是一个积性函数。于是fr(n)=fr(p1^k1)*fr(p2^k2)...*fr(pi^ki)，于是只需要求fr(p^x)，显然只和x有关，与p无关。于是求fr(2^x)的值，用R*log(N)的dp即可求出。
• L
  • 对于同一个Sy,对于子序列，预处理每个位置向后每种字母第一次出现位置。对于子串，建SAM。这样就能在O(min{len(Sx),len(Sy)})的时间里回答询问。对于不超过sqrt(n)的Sy，单次询问<=sqrt(n)。对于长度超过sqrt(n)的，将询问去重之后，总扫描长度<=n，这类串至多只有sqrt(n)个。所以总复杂度为nsqrt(n)。