2017-Sp304-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
=== chenjb ===
这套题就是在考验机时的运用，最后C半小时搞定很不错。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：dp。

 * B：对角和相等，随便找一个。

 * C：f[i]=min(max(f[j],diff(i..j)))，对f[i]维护递增的单调队列，由于决策单调，所以每次弹队头，树状数组/单调队列维护极差。

 * D：不是质数分成2类因子，就pow一下就没了，其实需要反演一下下。

 * E：暴力枚举2个二进制位，贡献就是满足条件的两个二进制位均不同的点对数量，用长链剖分维护dp，注意常数。

 * F：根号内外分别处理，直接求和即可。

 * G：只有2、3、5、7四种质因子，线段树维护。

 * H：第一类边组成的联通块用dij来跑，对第二类边维护一个topsort。

 * I：进制转换裸题。

 * J：f[0/2]代表目前子树是否额外有个1站在树根，转移环上的时候要算前缀影响。

 * K：先计算1*n和n*1的答案，然后考虑每个数字左和上数字是否相同，变成01矩阵，用悬线法计算出n,m>1的答案，取max。

 * L：对于任意两个人得到他们之间至多存在的两种路径中分别有哪些别人压成二进制直接状压dp即可。

 * M：tls牛逼 sub快学学

 * N：用PHP输出1 1 2 3 5

流水账

chenjb

这套题就是在考验机时的运用，最后C半小时搞定很不错。

oipotato

subconscious

题解

  • A：dp。
  • B：对角和相等，随便找一个。
  • C：f[i]=min(max(f[j],diff(i..j)))，对f[i]维护递增的单调队列，由于决策单调，所以每次弹队头，树状数组/单调队列维护极差。
  • D：不是质数分成2类因子，就pow一下就没了，其实需要反演一下下。
  • E：暴力枚举2个二进制位，贡献就是满足条件的两个二进制位均不同的点对数量，用长链剖分维护dp，注意常数。
  • F：根号内外分别处理，直接求和即可。
  • G：只有2、3、5、7四种质因子，线段树维护。
  • H：第一类边组成的联通块用dij来跑，对第二类边维护一个topsort。
  • I：进制转换裸题。
  • J：f[0/2]代表目前子树是否额外有个1站在树根，转移环上的时候要算前缀影响。
  • K：先计算1*n和n*1的答案，然后考虑每个数字左和上数字是否相同，变成01矩阵，用悬线法计算出n,m>1的答案，取max。
  • L：对于任意两个人得到他们之间至多存在的两种路径中分别有哪些别人压成二进制直接状压dp即可。
  • M：tls牛逼 sub快学学
  • N：用PHP输出1 1 2 3 5
附加文件