2021-team5-004

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team5 返回]

[[Image(Standings.png)]][[BR]]
[[Image(Submissions.png)]][[BR]]

== 概述 ==

2021 Nowcoder Training - Chenjb and His Friends Contest

== 流水账 ==

今天大家依旧按照国际惯例开题，fx看出A是原题加强后开始思考如何卡空间，ckr在中间随机开题，czyh跟榜签到。'''H1Y18'''，'''F1Y54'''，之后fx开始写A的卡空间做法，czyh和ckr到处开题，fx写完后WA了5，并且对拍失败，之后fx随手造了样例把自己叉了，然后获得了MLE30，继续卡空间，在终于卡好的时候空间限制调大，所以尽管try了6发，'''A3Y143'''。之后ckr信仰C，fx和czyh狂推K，都GG了。


== 总结 ==

=== Orange_User ===


=== functionendles ===


== 题解 ==

A: BFS建trie树，保证除叶节点每个节点都有分岔

B: 

C: 

D: 

E: 

F: 

G: 先考虑集合DP，f（S）表示被枪毙的恰好是S里的人的概率，g（S）表示被枪毙的是S的子集的概率。那么求g（S），对每个人来说，要么他的一枪打不中，要么打中S里的人，由于自己不能射自己，后一部分的概率要分成两部分。求出g之后集合容斥易得f，求出f之后根据S的size来选易得答案。

H: 

I: 

J: 

K:

[/wiki/2021-team5 返回]



概述

2021 Nowcoder Training - Chenjb and His Friends Contest

流水账

今天大家依旧按照国际惯例开题，fx看出A是原题加强后开始思考如何卡空间，ckr在中间随机开题，czyh跟榜签到。H1Y18，F1Y54，之后fx开始写A的卡空间做法，czyh和ckr到处开题，fx写完后WA了5，并且对拍失败，之后fx随手造了样例把自己叉了，然后获得了MLE30，继续卡空间，在终于卡好的时候空间限制调大，所以尽管try了6发，A3Y143。之后ckr信仰C，fx和czyh狂推K，都GG了。

总结

Orange_User

functionendles

题解

A: BFS建trie树，保证除叶节点每个节点都有分岔

B:

C:

D:

E:

F:

G: 先考虑集合DP，f（S）表示被枪毙的恰好是S里的人的概率，g（S）表示被枪毙的是S的子集的概率。那么求g（S），对每个人来说，要么他的一枪打不中，要么打中S里的人，由于自己不能射自己，后一部分的概率要分成两部分。求出g之后集合容斥易得f，求出f之后根据S的size来选易得答案。

H:

I:

J:

K:

附加文件