2021-team06-C211007

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

[[Image(211007-standing.png,800px)]]

== submission ==

[[Image(211007-submission2.png,800px)]]
[[Image(211007-submission1.png,800px)]]


== 概述 ==

solved: 6/10  dirt: 57.14%

rank: 5



==  ==

== 总结 ==

whn:
A题虽然本来也不会，但也反应一个队伍一般需要有一个会写python大数的人，否则会花比较多的时间
I题属于有板子就行的题？看来得多看看板子了。


== 题解 ==

A: 待whn补

B: 通过每次赢钱的概率<50%知钱会越来越少，大胆猜想每次应该全都下注下满，于是就对了..

C: 考虑三步：①任意两两交换整个序列中的0和1 ②取出整个序列最靠前的1，把剩余n-1个位置通过冒泡排序排好 ③在找出序列中最靠后的0，把其前面所有位置冒泡排序排好
lxy一开始想到了②③，后来发现对于和原序列1的数量和最靠前1的位置相同的那些串会无法分离，于是whn就多添了①那一步。

D：先以1为根初始化。若根在两点lca的子树外，则lca不变。否则，把现在的根和询问的两点分别求lca，取deep较大的那个。

E: 搜索，yja有什么细节记得写...

F：同样需要大力猜想：两人一定是不停的把当前最小的蛋糕不停的切，在那块蛋糕分出胜负之后会发现输的人在一路上切出来的蛋糕上也都只能输，因此直接比较两个数质因子多少即可。

G：二分答案。考虑把序列倒过来做topo，保证有解。

H：不会

I：原串倒过来建SAM，题目要求可以转化为在相同的首字母或相同right集合的后缀间只能选择一个。建二分图，一边26个字母，另一边不同的right集合。跑最大费用流即可。

J: 正解应该是分块bitset直接求，然而whn写了个重复计算的程序直接过了

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 6/10 dirt: 57.14%

rank: 5

总结

whn:

A题虽然本来也不会，但也反应一个队伍一般需要有一个会写python大数的人，否则会花比较多的时间

I题属于有板子就行的题？看来得多看看板子了。

题解

A: 待whn补

B: 通过每次赢钱的概率<50%知钱会越来越少，大胆猜想每次应该全都下注下满，于是就对了..

C: 考虑三步：①任意两两交换整个序列中的0和1 ②取出整个序列最靠前的1，把剩余n-1个位置通过冒泡排序排好 ③在找出序列中最靠后的0，把其前面所有位置冒泡排序排好

lxy一开始想到了②③，后来发现对于和原序列1的数量和最靠前1的位置相同的那些串会无法分离，于是whn就多添了①那一步。

D：先以1为根初始化。若根在两点lca的子树外，则lca不变。否则，把现在的根和询问的两点分别求lca，取deep较大的那个。

E: 搜索，yja有什么细节记得写...

F：同样需要大力猜想：两人一定是不停的把当前最小的蛋糕不停的切，在那块蛋糕分出胜负之后会发现输的人在一路上切出来的蛋糕上也都只能输，因此直接比较两个数质因子多少即可。

G：二分答案。考虑把序列倒过来做topo，保证有解。

H：不会

I：原串倒过来建SAM，题目要求可以转化为在相同的首字母或相同right集合的后缀间只能选择一个。建二分图，一边26个字母，另一边不同的right集合。跑最大费用流即可。

J: 正解应该是分块bitset直接求，然而whn写了个重复计算的程序直接过了

附加文件