2017-Sp252-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
yzc跑路，cjb和sub双机双打。
=== chenjb ===
感觉最近用pam突然多了起来...
=== oipotato ===

=== subconscious  ===

== 题解 == 
 * A：换根dp。

 * B：矩阵转置对角线xor 1后得到每一行代表这些位置异或和为0，这个东西能求交，线段树查询。

 * C：可以线性维护左侧的后缀最大或者最小和支配区间，O(n)扫一遍。

 * D：不是1就是2，2的方案枚举去掉最多两个2进制位，检查即可。

 * E：统计奇数和偶数2进制位上分别有多少个1，预处理dp求出单个位置有多少个方案，随便容斥。

 * F：2018 Petrozavodsk Summer Camp Day 3 MIPT Contest原题，对于归并，只需要保证每次一次归并完所有比ai/bi靠前的值即可，用平衡树维护。

 * G：

 * H：

 * I：将a反转后加$贴在原串后，用后缀数组求出不同子串个数(跨越$)的需要删去，之后用pam统计本质不同回文串个数，相加后除2。

 * J：f[i][j]表示到i，用了j次减免，dijkstra转移。

 * K：扫一遍，统计mod 300有多少个。

流水账

yzc跑路，cjb和sub双机双打。

chenjb

感觉最近用pam突然多了起来...

oipotato

subconscious

题解

  • A：换根dp。
  • B：矩阵转置对角线xor 1后得到每一行代表这些位置异或和为0，这个东西能求交，线段树查询。
  • C：可以线性维护左侧的后缀最大或者最小和支配区间，O(n)扫一遍。
  • D：不是1就是2，2的方案枚举去掉最多两个2进制位，检查即可。
  • E：统计奇数和偶数2进制位上分别有多少个1，预处理dp求出单个位置有多少个方案，随便容斥。
  • F：2018 Petrozavodsk Summer Camp Day 3 MIPT Contest原题，对于归并，只需要保证每次一次归并完所有比ai/bi靠前的值即可，用平衡树维护。
  • G：
  • H：
  • I：将a反转后加$贴在原串后，用后缀数组求出不同子串个数(跨越$)的需要删去，之后用pam统计本质不同回文串个数，相加后除2。
  • J：f[i][j]表示到i，用了j次减免，dijkstra转移。
  • K：扫一遍，统计mod 300有多少个。
附加文件