2017-Sp182-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，cjb表示会D，上机wa了两发终于tle了，淦。sub上机写构造题F，wa了，淦。cjb换了一种精妙的写法，'''D4y54'''，sub找到了问题，'''F2y57'''。cjb和yzc研究I，cjb丢了个做法给yzc，yzc上机'''I1y77'''。cjb和sub此前研究K，然后丢了算法给yzc，tle之后优化了常数，'''K2y110'''。sub上机操作H，'''H1y137'''。sub和yzc研究A，sub给出了牛逼做法，yzc上机'''A2y181'''。cjb和yzc研究G，得到了一种还行的写法，yzc上机又wa又tle，fix了各种bug之后'''G4y269'''。之后sub上机试图表演特技写B，wa27，tle24，tle26，wa27....特技失败。
== 总结 ==
=== chenjb ===
今天很多题目都是除了想到做法，还要想好写法，在编写效率和运行效率上都要注意各种细节。
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：建一个虚拟起点，向每个关键点连一条边，边权为inf-h[j]，跑最短路，一个点合法当且仅当他的最短路是inf，并且在最短路图上任意一个关键点都存在一条起点到他的最短路，在dag上跑dp即可。

 * B：

 * C：

 * D：开n个vector存储当前最远距离为i的点，然后降序枚举vector的点，每次取到合法的点出来，作为这次取出的位置，然后bfs，注意只往队列里塞relax成功的点，这样均摊大概是根号的。

 * E：

 * F：a[I]=a[n-i]，下标从0开始，I从1开始。

 * G：把链缩成点，在缩成点上暴力维护倍增数组，注意常数。

 * H：倍增构造，对于一个2^n^的方案，直接复制一遍，每个数字+2^n^就可以得到2^n+1^的方案，然后对于对应位置，如果符号相同，把他们swap即可。

 * I：跑出最小生成树，暴力取dfn序上连续的n/2个，遇到满足条件输出即可。

 * J：

 * K：枚举3个点，bitset维护边表并，如果边表中至少3个点，则K33，否则如果恰好2个点，则取出之后暴力判K5。

 * [https://wiki.icpc.camp/twsf/Ivan%20Smirnov%20Contest%201 The Way So Far]

 * [https://wiki.icpc.camp/dreadnought/Ivan%20Smirnov%20Contest%201 Dreadnought]

 * [https://wiki.icpc.camp/new-meta/Petrozavodsk%20Summer-2015.%20Ivan%20Smirnov%20Contest%201 New Meta]

 * [wiki:2018-Reconquista-T28 Reconquista]

流水账

出门各自看题，cjb表示会D，上机wa了两发终于tle了，淦。sub上机写构造题F，wa了，淦。cjb换了一种精妙的写法，D4y54，sub找到了问题，F2y57。cjb和yzc研究I，cjb丢了个做法给yzc，yzc上机I1y77。cjb和sub此前研究K，然后丢了算法给yzc，tle之后优化了常数，K2y110。sub上机操作H，H1y137。sub和yzc研究A，sub给出了牛逼做法，yzc上机A2y181。cjb和yzc研究G，得到了一种还行的写法，yzc上机又wa又tle，fix了各种bug之后G4y269。之后sub上机试图表演特技写B，wa27，tle24，tle26，wa27....特技失败。

总结

chenjb

今天很多题目都是除了想到做法，还要想好写法，在编写效率和运行效率上都要注意各种细节。

oipotato

subconscious

题解

• A：建一个虚拟起点，向每个关键点连一条边，边权为inf-h[j]，跑最短路，一个点合法当且仅当他的最短路是inf，并且在最短路图上任意一个关键点都存在一条起点到他的最短路，在dag上跑dp即可。
• B：
• C：
• D：开n个vector存储当前最远距离为i的点，然后降序枚举vector的点，每次取到合法的点出来，作为这次取出的位置，然后bfs，注意只往队列里塞relax成功的点，这样均摊大概是根号的。
• E：
• F：a[I]=a[n-i]，下标从0开始，I从1开始。
• G：把链缩成点，在缩成点上暴力维护倍增数组，注意常数。
• H：倍增构造，对于一个2ⁿ的方案，直接复制一遍，每个数字+2ⁿ就可以得到2ⁿ⁺¹的方案，然后对于对应位置，如果符号相同，把他们swap即可。
• I：跑出最小生成树，暴力取dfn序上连续的n/2个，遇到满足条件输出即可。
• J：
• K：枚举3个点，bitset维护边表并，如果边表中至少3个点，则K33，否则如果恰好2个点，则取出之后暴力判K5。
• The Way So Far
• Dreadnought
• New Meta
• Reconquista

附加文件

• 1.png by chenjb