Difference between revisions of "CCPC-Wannafly Winter Camp Day3 (Div 1)"

From EOJ Wiki
Jump to navigation Jump to search
Line 54: Line 54:
  
 
每一次比赛都建立一个新的节点,这样整场比赛可以变成一棵二叉树,左孩子作为 $x$ 出战,右孩子作为 $y$ 出战。实际上,不考虑留的是谁,每一个节点上留下来的人出三种拳的可能性是一直相等的,$x$ 胜利的概率是 $\frac{2}{3}$,$y$ 胜利的概率是 $\frac{1}{3}$,因此每一次作为 $x$ 出战,出拳方案总数就乘上 $\frac{2}{3}$,否则乘上 $\frac{1}{3}$。
 
每一次比赛都建立一个新的节点,这样整场比赛可以变成一棵二叉树,左孩子作为 $x$ 出战,右孩子作为 $y$ 出战。实际上,不考虑留的是谁,每一个节点上留下来的人出三种拳的可能性是一直相等的,$x$ 胜利的概率是 $\frac{2}{3}$,$y$ 胜利的概率是 $\frac{1}{3}$,因此每一次作为 $x$ 出战,出拳方案总数就乘上 $\frac{2}{3}$,否则乘上 $\frac{1}{3}$。
 +
 +
这样,我们只要维护每一个点到当前根路径当了多少次左孩子和右孩子,只要用并查集维护即可。
  
 
== Problem J ==
 
== Problem J ==
  
 
Unsolved.
 
Unsolved.

Revision as of 05:27, 9 March 2019

CCPC-Wannafly Winter Camp Day3 (Div 1)

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved.

题意:一堆定义。

题解:直接贪心。显然 $1$ 的位置放 $1$ ,那么 $1$ 后面的数都比 $1$ 大(废话)。

$2$ 的位置如果在 $1$ 之后,显然这个位置先不放 $2$ ,因为 $2$ 放越前面,字典序越小。

于是贪心策略就出来了。

先贪心的从 $1$ 开始往后放,从 $1$ 的位置开始枚举,每次只往前放,直到放在第一个位置上,第一阶段结束。

剩下没有填数的位置,显然怎么填都成立,于是,贪心的把剩下的数从前往后填。

Problem H

Unsolved.

Problem I

Solved.

题意:$n$ 个人石头剪刀布,每次选两个人 $x,y$,$x$ 胜或平则 $x$ 留,否则 $y$ 留。每一个人的出拳都不会改变,最初一共有 $3^n$ 种出拳方案,在游戏进行的过程中,多次询问能让 $x$ 留下的出拳方案数量。

题解:要让一个人留下,只要看他要留下,需要作为 $x$ 赢多少次,和作为 $y$ 赢多少次。

每一次比赛都建立一个新的节点,这样整场比赛可以变成一棵二叉树,左孩子作为 $x$ 出战,右孩子作为 $y$ 出战。实际上,不考虑留的是谁,每一个节点上留下来的人出三种拳的可能性是一直相等的,$x$ 胜利的概率是 $\frac{2}{3}$,$y$ 胜利的概率是 $\frac{1}{3}$,因此每一次作为 $x$ 出战,出拳方案总数就乘上 $\frac{2}{3}$,否则乘上 $\frac{1}{3}$。

这样,我们只要维护每一个点到当前根路径当了多少次左孩子和右孩子,只要用并查集维护即可。

Problem J

Unsolved.