2020-team12-023

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(Standings.png, 1000px)]]

== 题解 ==

A: 大——模拟

B: 签到

C: 签到

D: 考虑在每个加油点只有两种决策：加满；或者恰好加到可以跑到下一个点的地方。

dp(x,y,k=0/1)表示到达第x个点，加了y次油，油空或油满。

预处理g(i,j)表示从i满油出发，经过一个中转站到j油空的花费=min(w[k]*(dis(i,k)+dis(k,j)-vol))(dis(i,k)<=vol&&dis(k,j)<=vol)（由前知不需要考虑更多）

四种转移： dp(x,y+1,1)=dp(x,y,0)+w[x]*vol(在本站加满）

dp(x1,y+1,k)=dp(x,y,k)+w[x]*vol(在本站加油跑到近点）

dp(x1,y+1,1)=dp(x,y,1)+w[x1]*vol(本站满油跑到近点在那一站加满）

dp(x1,y+1,0)=dp(x,y,1)+g(x,x1)（本站满油通过预处理数据跑到远点）

ctc补题失误：dp预置-1用来更新了

whn补题失误：忽略“在那一站加满”转移，预处理g忘记取min，写循环时枚举加油次数没有写在外面

E: 读题+dp

F: 支配树板子，不可做题，待补

G: 稍微写一下式子就发现是一堆斜率为1的绝对值函数叠加，格式为|a-x|按a排序，最大的减最小的除以二就是最大值最小的情况，比赛失误:ctc没有想到等差序列还有递减的情况，续了很久，被读了样例的szb发现。

H: FFT裸题，然鹅whn先抄了一个假板子，然后在输出转double为ll时忘了+0.4于是罚时+2。。 szb:板子撕了，还有以后能用ntt就不要fft

I: 二维线段树，ofast大法好

J: 读题+转化为矩阵求逆

K: whn在场内没读到“每个点至少有两条边相连”然后糊了个先填3*1然后黑白染色直接图的做法，事后发现由于涂黑白染色必须保证联通做法假了。
正解不唯一，cjb做法是一个奇妙的dfs：先对超过2格的横行贪心放置，枚举到只有连续一格的地方转化成上下；涂完上下以后再从左右列找到格子继续dfs。

L: whn发现只需要考虑单调和单峰状态后暂时放置；后来复（xian)习(xue)了决策单调性，结合之前的结论想到取出上峰下峰做决策单调性分治dp通过。

[/wiki/2020-team12 返回]

题解

A: 大——模拟

B: 签到

C: 签到

D: 考虑在每个加油点只有两种决策：加满；或者恰好加到可以跑到下一个点的地方。

dp(x,y,k=0/1)表示到达第x个点，加了y次油，油空或油满。

预处理g(i,j)表示从i满油出发，经过一个中转站到j油空的花费=min(w[k]*(dis(i,k)+dis(k,j)-vol))(dis(i,k)<=vol&&dis(k,j)<=vol)（由前知不需要考虑更多）

四种转移： dp(x,y+1,1)=dp(x,y,0)+w[x]*vol(在本站加满）

dp(x1,y+1,k)=dp(x,y,k)+w[x]*vol(在本站加油跑到近点）

dp(x1,y+1,1)=dp(x,y,1)+w[x1]*vol(本站满油跑到近点在那一站加满）

dp(x1,y+1,0)=dp(x,y,1)+g(x,x1)（本站满油通过预处理数据跑到远点）

ctc补题失误：dp预置-1用来更新了

whn补题失误：忽略“在那一站加满”转移，预处理g忘记取min，写循环时枚举加油次数没有写在外面

E: 读题+dp

F: 支配树板子，不可做题，待补

G: 稍微写一下式子就发现是一堆斜率为1的绝对值函数叠加，格式为|a-x|按a排序，最大的减最小的除以二就是最大值最小的情况，比赛失误:ctc没有想到等差序列还有递减的情况，续了很久，被读了样例的szb发现。

H: FFT裸题，然鹅whn先抄了一个假板子，然后在输出转double为ll时忘了+0.4于是罚时+2。。 szb:板子撕了，还有以后能用ntt就不要fft

I: 二维线段树，ofast大法好

J: 读题+转化为矩阵求逆

K: whn在场内没读到“每个点至少有两条边相连”然后糊了个先填3*1然后黑白染色直接图的做法，事后发现由于涂黑白染色必须保证联通做法假了。

正解不唯一，cjb做法是一个奇妙的dfs：先对超过2格的横行贪心放置，枚举到只有连续一格的地方转化成上下；涂完上下以后再从左右列找到格子继续dfs。

L: whn发现只需要考虑单调和单峰状态后暂时放置；后来复（xian)习(xue)了决策单调性，结合之前的结论想到取出上峰下峰做决策单调性分治dp通过。

附加文件