2017-Sp229-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门yzc让cjb上机写K，忘记文件读写'''K2y11'''。sub写E，忘记文件读写'''E2y46'''。yzc上机写F，'''F1y54'''。yzc和sub搞A，'''A1y84'''。cjb和sub猜测大力带花树能过G，cjb用力写了一下tle了。yzc和sub讨论H，调整了好久，yzc上机辛苦地写，'''H2y174'''。cjb想到了正确做法，'''G2y185'''。三人开出了D，让yzc上机写，之后sub开出了J，D wa了之后sub上机，'''J1y249'''。yzc fix了一下'''D2y252'''。最后cjb上机打C的表，但是打不完，如果能成功打完就过C了。
== 总结 ==
=== chenjb ===
C表还差一点才打出来TAT 打出来就过了，下次应该注意打表里const啊O2啊，还有尽早开始打。'''UPD:'''其实基本打不完，应该打出一定表后观察到规律，重新调整打表代码才对，下次要更加果断。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：积化和差，问题转化为有多少种拆分成两组合的方案使得两组合相等，跑dp。

 * B：sub

 * C：场上做法为加数和和均小于1e15时暴力，存在一维大于等于1e15事先跑暴力打表，有两千多个。打表过程可发现规律是加数的底数必定为2的幂次。

 * D：返祖边和树边组成偶环，或者两条返祖边支配了共同的树边，可构造出一个偶环，暴力即可，注意图不连通。

 * E：经典倍增，f[x][p]表示从2x+1到2x+2p+1的关于x的42次多项式，二项式展开，倍增即可。

 * F：不断取能取的一大段，每次显然能让x少掉一半，显然只用log次能结束。

 * G：每次假意tarjan，对于桥边，若两点未匹配且子树为奇数时取出来作为解，不停重复该过程。

 * H：每一个可扩展的点显然只会取周围点中最小的那个字母，维护当前字符串的终点的集合，如果某个时刻没有下一步可以走，又还没到终点，则GG。

 * I：cjb

 * J：先dp求出大小为i的竞赛图，是同一个联通分量的方案数，然后f[i][j]代表大小为j的竞赛图，i等于0,1,2表示是否包含1和2的情况。最后所有情况减去f[3][n]。

 * K：dfs过程用树状数组计数。

流水账

出门yzc让cjb上机写K，忘记文件读写K2y11。sub写E，忘记文件读写E2y46。yzc上机写F，F1y54。yzc和sub搞A，A1y84。cjb和sub猜测大力带花树能过G，cjb用力写了一下tle了。yzc和sub讨论H，调整了好久，yzc上机辛苦地写，H2y174。cjb想到了正确做法，G2y185。三人开出了D，让yzc上机写，之后sub开出了J，D wa了之后sub上机，J1y249。yzc fix了一下D2y252。最后cjb上机打C的表，但是打不完，如果能成功打完就过C了。

总结

chenjb

C表还差一点才打出来TAT 打出来就过了，下次应该注意打表里const啊O2啊，还有尽早开始打。UPD:其实基本打不完，应该打出一定表后观察到规律，重新调整打表代码才对，下次要更加果断。

oipotato

subconscious

题解

  • A：积化和差，问题转化为有多少种拆分成两组合的方案使得两组合相等，跑dp。
  • B：sub
  • C：场上做法为加数和和均小于1e15时暴力，存在一维大于等于1e15事先跑暴力打表，有两千多个。打表过程可发现规律是加数的底数必定为2的幂次。
  • D：返祖边和树边组成偶环，或者两条返祖边支配了共同的树边，可构造出一个偶环，暴力即可，注意图不连通。
  • E：经典倍增，f[x][p]表示从2x+1到2x+2p+1的关于x的42次多项式，二项式展开，倍增即可。
  • F：不断取能取的一大段，每次显然能让x少掉一半，显然只用log次能结束。
  • G：每次假意tarjan，对于桥边，若两点未匹配且子树为奇数时取出来作为解，不停重复该过程。
  • H：每一个可扩展的点显然只会取周围点中最小的那个字母，维护当前字符串的终点的集合，如果某个时刻没有下一步可以走，又还没到终点，则GG。
  • I：cjb
  • J：先dp求出大小为i的竞赛图，是同一个联通分量的方案数，然后f[i][j]代表大小为j的竞赛图，i等于0,1,2表示是否包含1和2的情况。最后所有情况减去f[3][n]。
  • K：dfs过程用树状数组计数。
附加文件