2020-team8-0403

从 Trac 迁移的文章

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

原文章内容如下：

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

TYPE: contest

NAME: 2021 ICPC 昆明

PLAT: win-pintia

MODE: online

TIME: 2020.04.03 11:00~16:00

TEAM: 林加德[詹哲远, 郑皓蔚, 陈逸]

RANK: 21/813 2.58%

SOLVE: 7/13

C 04:26:12

H 00:03:07

I 02:17:57(-1)

J 02:52:06

K 04:07:12(-1)

L 00:27:04

M 01:25:51

== 流水账 ==

开场发现H是弱智签到题，先过了H，随后跟榜很快过了L，之后cy上机写M，但是写了挺久，过M之后KanaD和szy一起开J，cy过I，过I后KanaD先上机写了一会麻将，Szy开出J后cy上机写J，之后KanaD开始卡麻将，Szy开C，cy开D，卡到4h时发现szy转述的麻将题意有点小问题，改完过了，szy开出C，cy上机很快过C，szy已经精疲力尽，最后cy和KanaD没能开出D


== 个人总结 ==

Szy:首先是前场大家都不太顺，题目不是很适合我们队的打法，我们比较难多点开花，速度很慢，J消耗了3个人很多的精力，然后K的卡题也带来了很大的伤害，第三个后面虚空之梦快速进展也让我觉得压力很大，这场大家状态都不是很好，也没关系，在逆境中还是回到了金牌区，好好调整状态备战EC-FINAL.

cy:感觉这场打的有点慌，上机时写的也不是很快，导致没有很多时间想题，开的题不够多，原本G题大概是能写的。

zhw:打比赛全程有点慌，也没啥自信，bug没调出来的时候也很痛苦，再加上签到题签的不够快，导致全程贡献较低

== 题解 ==

A:可以wqs二分，也可以把题意转化为一排数字，不能取相邻的，花费不超过K，最少能取几个，考虑贪心，取完一个后相当于把边上两个合并，代价为边上两个的代价减去这个的代价，可以证明这个贪心是对的

B:

C:G[i][j]表示i和j颜色相同合并成此颜色的最小代价，f[i][j]表示i到j合并的最小代价，g[i][j]=min(f[i+1][j-1]+1,g[p][t]+f[i+1][p-1]+f[t+1][j-1]+(i+1<=p-1)+(t+1<=j-1)),f[i][j]=min(g[i][p]+f[p+1][j])，也有不同的dp方式
可能g[i][j]=min(f[i+1][j-1],g[i][p]+g[p][j])

D:

E:

F:

G:

H:签到

I:计算几何签到

J:考虑每个环独立，每个环可以发现只要换两次

K:爆搜剪枝

L:答案为最长下降子序列的长度，每个数字为以他开头的最长下降子序列

M:考虑每次可能会有找不出的数字只可能在和>2*当前和的时候，所以在主席树上暴力查log次即可

Rank

TYPE: contest

NAME: 2021 ICPC 昆明

PLAT: win-pintia

MODE: online

TIME: 2020.04.03 11:00~16:00

TEAM: 林加德[詹哲远, 郑皓蔚, 陈逸]

RANK: 21/813 2.58%

SOLVE: 7/13

C 04:26:12

H 00:03:07

I 02:17:57(-1)

J 02:52:06

K 04:07:12(-1)

L 00:27:04

M 01:25:51

流水账

开场发现H是弱智签到题，先过了H，随后跟榜很快过了L，之后cy上机写M，但是写了挺久，过M之后KanaD和szy一起开J，cy过I，过I后KanaD先上机写了一会麻将，Szy开出J后cy上机写J，之后KanaD开始卡麻将，Szy开C，cy开D，卡到4h时发现szy转述的麻将题意有点小问题，改完过了，szy开出C，cy上机很快过C，szy已经精疲力尽，最后cy和KanaD没能开出D

个人总结

Szy:首先是前场大家都不太顺，题目不是很适合我们队的打法，我们比较难多点开花，速度很慢，J消耗了3个人很多的精力，然后K的卡题也带来了很大的伤害，第三个后面虚空之梦快速进展也让我觉得压力很大，这场大家状态都不是很好，也没关系，在逆境中还是回到了金牌区，好好调整状态备战EC-FINAL.

cy:感觉这场打的有点慌，上机时写的也不是很快，导致没有很多时间想题，开的题不够多，原本G题大概是能写的。

zhw:打比赛全程有点慌，也没啥自信，bug没调出来的时候也很痛苦，再加上签到题签的不够快，导致全程贡献较低

题解

A:可以wqs二分，也可以把题意转化为一排数字，不能取相邻的，花费不超过K，最少能取几个，考虑贪心，取完一个后相当于把边上两个合并，代价为边上两个的代价减去这个的代价，可以证明这个贪心是对的

B:

C:G[i][j]表示i和j颜色相同合并成此颜色的最小代价，f[i][j]表示i到j合并的最小代价，g[i][j]=min(f[i+1][j-1]+1,g[p][t]+f[i+1][p-1]+f[t+1][j-1]+(i+1<=p-1)+(t+1<=j-1)),f[i][j]=min(g[i][p]+f[p+1][j])，也有不同的dp方式

可能g[i][j]=min(f[i+1][j-1],g[i][p]+g[p][j])

D:

E:

F:

G:

H:签到

I:计算几何签到

J:考虑每个环独立，每个环可以发现只要换两次

K:爆搜剪枝

L:答案为最长下降子序列的长度，每个数字为以他开头的最长下降子序列

M:考虑每次可能会有找不出的数字只可能在和>2*当前和的时候，所以在主席树上暴力查log次即可

附加文件