2020-team12-027

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-W6standings.png, 1000px)]]
[[Image(2021-W6status.png, 1000px)]]
[[Image(2021-W6status2.png, 1000px)]]

== 失利点 ==

ctcC题写了2h依然没有调试出来，代码能力有待提高；最后一段时间利用不佳；A题未读。

== 题解 == 

A:似乎是一个题目已经告诉你要怎么讨论的分类讨论，然而由于跟榜等原因此题成为唯一没读的题。有点遗憾。

B:签到，分数规划； whn由于不会二分限定次数TL93，以后写把while(l+eps<=r)改成for确定次数！

C:待补，ctc.（ctc：先枚举行轮换，对于列轮换用前缀后缀维护端点有的并查集状态，除去不合法的最多2*n个并查集，然后枚举中断列，合并并查集）

D:szb做法：

dp[i][j]表示清醒海盗在第i轮取到物品j的概率（两人操作一次算一轮）

则第j+1个物品在i轮醉酒海盗行动后被取走的总概率是从(n-j)个物品中进行(2*i-j)次随机抽取的概率p=(2*i-j)/(n-j).

则dp[i+1][j+1] = dp[i][j]*(1-p)，因为取不掉就表示第i+1轮清醒海盗可以获得物品j+1.

而如果已经取掉了，那么对于后面的状态来说状态和dp[i][j+1]等价，dp[i][j+1] = dp[i][j]*p. 

Ans = 所有的dp[1-n][j]*a[j]（从大到小排序），因转移特点需要在第i轮转移开始前加好。

whn做法：

倒着考虑，问题等价于在一个长条箱子里两个海盗轮流塞黑白球，清醒海盗每回合在最左边塞一个黑球，醉酒海盗在所有i+1个空隙中随机塞白球，最后第i个球是黑球表示第i大的物品被清醒海盗拿走。

则需要根据奇偶回合转移，清醒海盗转移有dp[i+1][j+1] = dp[i][j]，因为第j个球在其行动完后一定会变成j+1个

醉酒海盗则有dp[i+1][j+1] = dp[i][j]*j/(i+1)，dp[i+1][j] = dp[i][j]*(i+1-j)/(i+1), 因为要在第1-j个球前面塞球才会让其变成j+1个。

Ans = 所有的dp[n][i]*a[i]，第一回合谁先行动需要奇偶讨论从而让清醒海盗在原问题中先手。

E:待补

F:建图，szb.

G:签到

H:

I: 签到

J: 结论题

K: 打怪兽经典模型：加血怪按照血量升序，扣血怪按照对我的加血量降序。

L：较易题。

M：根据题意做。

N：神奇的国际象棋..

[/wiki/2020-team12 返回]

失利点

ctcC题写了2h依然没有调试出来，代码能力有待提高；最后一段时间利用不佳；A题未读。

题解

A:似乎是一个题目已经告诉你要怎么讨论的分类讨论，然而由于跟榜等原因此题成为唯一没读的题。有点遗憾。

B:签到，分数规划； whn由于不会二分限定次数TL93，以后写把while(l+eps<=r)改成for确定次数！

C:待补，ctc.（ctc：先枚举行轮换，对于列轮换用前缀后缀维护端点有的并查集状态，除去不合法的最多2*n个并查集，然后枚举中断列，合并并查集）

D:szb做法：

dp[i][j]表示清醒海盗在第i轮取到物品j的概率（两人操作一次算一轮）

则第j+1个物品在i轮醉酒海盗行动后被取走的总概率是从(n-j)个物品中进行(2*i-j)次随机抽取的概率p=(2*i-j)/(n-j).

则dp[i+1][j+1] = dp[i][j]*(1-p)，因为取不掉就表示第i+1轮清醒海盗可以获得物品j+1.

而如果已经取掉了，那么对于后面的状态来说状态和dp[i][j+1]等价，dp[i][j+1] = dp[i][j]*p.

Ans = 所有的dp[1-n][j]*a[j]（从大到小排序），因转移特点需要在第i轮转移开始前加好。

whn做法：

倒着考虑，问题等价于在一个长条箱子里两个海盗轮流塞黑白球，清醒海盗每回合在最左边塞一个黑球，醉酒海盗在所有i+1个空隙中随机塞白球，最后第i个球是黑球表示第i大的物品被清醒海盗拿走。

则需要根据奇偶回合转移，清醒海盗转移有dp[i+1][j+1] = dp[i][j]，因为第j个球在其行动完后一定会变成j+1个

醉酒海盗则有dp[i+1][j+1] = dp[i][j]*j/(i+1)，dp[i+1][j] = dp[i][j]*(i+1-j)/(i+1), 因为要在第1-j个球前面塞球才会让其变成j+1个。

Ans = 所有的dp[n][i]*a[i]，第一回合谁先行动需要奇偶讨论从而让清醒海盗在原问题中先手。

E:待补

F:建图，szb.

G:签到

H:

I: 签到

J: 结论题

K: 打怪兽经典模型：加血怪按照血量升序，扣血怪按照对我的加血量降序。

L：较易题。

M：根据题意做。

N：神奇的国际象棋..

附加文件