2017-Sp271-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
出门各自看题，sub不太会做看K，yzc教育了一下'''K3y60'''。yzc算好了H的分段大小，'''H1y67'''。cjb和yzc此前理论了F，丢给sub，sub上机'''F1y90'''。cjb和sub理论了I，cjb上机'''I1y114'''。cjb和yzc开了G，yzc推细节后'''G1y122'''。之后sub做J，很辛苦很用力。cjb和yzc理论了半天B，决定写个dp去搞贪心，最后'''J4y251'''，'''B2y254'''。最后sub发现其实E更好做，rush，来不及了。
=== chenjb ===
感觉tourist题目真的很牛逼....我觉得我和yzc这个B非常机智，不知道具体贪心是怎么搞的呢？感觉E有点可惜，sub的J确实做太久了，但是当时看榜似乎J更科学，但是最后E过的更多，有点像上次dm的多校，有时候要考虑榜的延时反馈性，沉进题目前更谨慎，这也需要读题做到位。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：yzc

 * B：f[s1][p1][s2][p2]表示A用了前s1小，前p1大，B用了前s2小，前p2大之后的最优解，用bfs转移，有效状态只有O(n^3^)。可认为这个dp方式能囊括所有该类贪心状态的决策。

 * C：cjb

 * D：sub

 * E：sub

 * F：线线图的点是原图上两条有公共点的边，边是有共同边的新点连接，边权为共同边的边权。考虑每次加入边的贡献是两边还没有扫到的边数+左边是否存在扫到的边+右边是否存在扫到的边-两边是否已经连通，从小到大做即可。

 * G：每次加一个数字，删一个数字都只会插入和删除一个dp值，用线段树维护。

 * H：分段二分，段数取到100。

 * I：实现题目里的cmp函数，对所有点暴力排序，之后输出前p个。(It produces an order in which problem i is more preferred than problem i+1 (maybe indirectly). Even if i+1 is more preferred than i in some other way, it doesn't really matter since there's a "plausible" chance i will be selected once again. by MofK)

 * J：分为有一个1，没有1有46...69，没有1没有4至少有一个9，然后没有1没有9，前两种情况需要暴力出约100个前缀。

 * K：显然，最优方案一定有两条线是重合的，从重合这条线出发状压dp，非法状态要跳过。

流水账

出门各自看题，sub不太会做看K，yzc教育了一下K3y60。yzc算好了H的分段大小，H1y67。cjb和yzc此前理论了F，丢给sub，sub上机F1y90。cjb和sub理论了I，cjb上机I1y114。cjb和yzc开了G，yzc推细节后G1y122。之后sub做J，很辛苦很用力。cjb和yzc理论了半天B，决定写个dp去搞贪心，最后J4y251，B2y254。最后sub发现其实E更好做，rush，来不及了。

chenjb

感觉tourist题目真的很牛逼....我觉得我和yzc这个B非常机智，不知道具体贪心是怎么搞的呢？感觉E有点可惜，sub的J确实做太久了，但是当时看榜似乎J更科学，但是最后E过的更多，有点像上次dm的多校，有时候要考虑榜的延时反馈性，沉进题目前更谨慎，这也需要读题做到位。

oipotato

subconscious

题解

  • A：yzc
  • B：f[s1][p1][s2][p2]表示A用了前s1小，前p1大，B用了前s2小，前p2大之后的最优解，用bfs转移，有效状态只有O(n3)。可认为这个dp方式能囊括所有该类贪心状态的决策。
  • C：cjb
  • D：sub
  • E：sub
  • F：线线图的点是原图上两条有公共点的边，边是有共同边的新点连接，边权为共同边的边权。考虑每次加入边的贡献是两边还没有扫到的边数+左边是否存在扫到的边+右边是否存在扫到的边-两边是否已经连通，从小到大做即可。
  • G：每次加一个数字，删一个数字都只会插入和删除一个dp值，用线段树维护。
  • H：分段二分，段数取到100。
  • I：实现题目里的cmp函数，对所有点暴力排序，之后输出前p个。(It produces an order in which problem i is more preferred than problem i+1 (maybe indirectly). Even if i+1 is more preferred than i in some other way, it doesn't really matter since there's a "plausible" chance i will be selected once again. by MofK)
  • J：分为有一个1，没有1有46...69，没有1没有4至少有一个9，然后没有1没有9，前两种情况需要暴力出约100个前缀。
  • K：显然，最优方案一定有两条线是重合的，从重合这条线出发状压dp，非法状态要跳过。
附加文件