2017-Sp209-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门发现E是old题，让yzc上机写，wa了之后cjb上机签A，'''A1y29'''，yzc和sub讨论了一下'''E2y31'''。然后cjb又丢了H给yzc，'''H2y56'''。cjb和sub讨论好了博弈题，上机wa了3发，sub上机写B，'''B1y87'''。之后cjb终于想到了天稳的fix，'''J5y101'''。之后yzc上机写D，'''D1y112'''。cjb和sub讨论好了C，让yzc抄费用流板子，上机'''C1y160'''。yzc和sub讨论好了I，上机写了很久，牛逼地一发'''I1y216'''。sub上机写F，需要几何+缘分暴搜，结果一下子就'''F1y248'''。剩下一个题一直都是0/0，开不动。
== 总结 ==
=== chenjb ===
今天打得有点爽的~yzc和sub这两个1A非常牛逼啊？博弈题对于一些细节还是应该更稳重一点啊，有时候把试探的值直接带回去check反而效果更好啊。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：bfs序列后把相邻两点距离加起来。

 * B：考虑一维的情况，由于相邻的只偏移1，可以用O(n)计算出答案。二维情况同样做两次，三维情况做三次即可。

 * C：将字符作为边权，写一个cost类然后跑费用流。

 * D：f[i][j]表示i到j这个区间的答案，每次枚举当中的逗号，直接转移即可。

 * E：先把左右括号消掉，每个串剩下连续右括号和连续左括号，左括号比较多的排在前面，一样多的排在中间，比较少的排在后面，左括号比较多的串中，按照右括号升序排；左括号比较少的时候按照左括号降序排。

 * F：大力用边和点判定能不能看到，状压map存dp即可。

 * G：

 * H：枚举开头，暴力即可，注意特判第二个串只有1的情况。

 * I：预处理出任意两个点对中的最短路，f[i][j][k][mask]代表i这种连通区域从第j个房间出发，最后停在第k个房间，经过房间状态为mask的最小步数，g[i][j][mask]表示从给定的起点出发，最后停留在第i个连通区域的第j个房间，经过的连通区域的二进制状态为mask的最小步数，h[i][mask]表示前i个waiter完成的连通区域的二进制状态为mask的时间，输出h的最后答案即可。

 * J：设M=min(A,B)，平衡游戏下sg值是x % (M+1)，如果所有堆都<=M或者A=B则公平，反之如果A>B且sg>0 A必胜，若sg=0，因为先手一定可以取一个m+1的状态使得sg值依然为0传给后手，所以必胜；A<B的时候如果sg=0则后手必胜，反之当且仅当只存在一堆>M的石子并且能取一次之后变成所有都<=M且sg=0时先手胜，反之后手胜。

流水账

出门发现E是old题，让yzc上机写，wa了之后cjb上机签A，A1y29，yzc和sub讨论了一下E2y31。然后cjb又丢了H给yzc，H2y56。cjb和sub讨论好了博弈题，上机wa了3发，sub上机写B，B1y87。之后cjb终于想到了天稳的fix，J5y101。之后yzc上机写D，D1y112。cjb和sub讨论好了C，让yzc抄费用流板子，上机C1y160。yzc和sub讨论好了I，上机写了很久，牛逼地一发I1y216。sub上机写F，需要几何+缘分暴搜，结果一下子就F1y248。剩下一个题一直都是0/0，开不动。

总结

chenjb

今天打得有点爽的~yzc和sub这两个1A非常牛逼啊？博弈题对于一些细节还是应该更稳重一点啊，有时候把试探的值直接带回去check反而效果更好啊。

oipotato

subconscious

题解

  • A：bfs序列后把相邻两点距离加起来。
  • B：考虑一维的情况，由于相邻的只偏移1，可以用O(n)计算出答案。二维情况同样做两次，三维情况做三次即可。
  • C：将字符作为边权，写一个cost类然后跑费用流。
  • D：f[i][j]表示i到j这个区间的答案，每次枚举当中的逗号，直接转移即可。
  • E：先把左右括号消掉，每个串剩下连续右括号和连续左括号，左括号比较多的排在前面，一样多的排在中间，比较少的排在后面，左括号比较多的串中，按照右括号升序排；左括号比较少的时候按照左括号降序排。
  • F：大力用边和点判定能不能看到，状压map存dp即可。
  • G：
  • H：枚举开头，暴力即可，注意特判第二个串只有1的情况。
  • I：预处理出任意两个点对中的最短路，f[i][j][k][mask]代表i这种连通区域从第j个房间出发，最后停在第k个房间，经过房间状态为mask的最小步数，g[i][j][mask]表示从给定的起点出发，最后停留在第i个连通区域的第j个房间，经过的连通区域的二进制状态为mask的最小步数，h[i][mask]表示前i个waiter完成的连通区域的二进制状态为mask的时间，输出h的最后答案即可。
  • J：设M=min(A,B)，平衡游戏下sg值是x % (M+1)，如果所有堆都<=M或者A=B则公平，反之如果A>B且sg>0 A必胜，若sg=0，因为先手一定可以取一个m+1的状态使得sg值依然为0传给后手，所以必胜；AM的石子并且能取一次之后变成所有都<=M且sg=0时先手胜，反之后手胜。
附加文件