2021-team06-C210817

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

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

== submission ==

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


== 概述 ==

solved: 9/12  dirt: 43.75%

rank: 4



==  ==

== 总结 ==

这场节奏起飞点在于J没有花时间打表。不过老实说硬写打表可能并不好写有必要练。
总的来说算是平稳发挥，希望能保持位置。


== 题解 ==

A: 签到，直接DP。

B: 考虑到每次一定会填一个区间，所以顺序是没有关系的。令sum[i]表示前i个位置一共有多少石头，f[i]表示只用前缀i的石头填到前缀i，保证留有i-sum[i]个空位的方案数，num[x]表示之前所有的前缀中留下正好x个空位的方案数。每当枚举到一个保证留有非负个空位的位置i时，可以考虑从前面某个空位和他一样多的前缀j转移， 1到j留完1到i能留的空位，然后j+1到i显然会用其中的所有石头填满。这个转移用num累计一下之后便可以一起转移了。

C: 

D：CF原题简化版，可以直接把每个向量看成边，并查集判是否出现环即可。

E：贪心双指针处理出每个位置最远可以跟哪个音符构成同一个调的音乐，然后枚举首尾要哪首歌，去掉可以归属那首歌的前缀和后缀然后贪心跳即可。其实也可以直接倍长维护。

F：签到，0变1和1变0的方案可以贪心，然后枚举那些要使其先变成0再变回1的数的大小上界，用set维护即可。注意要用set比较稳健，排序理论上复杂度相近但是会T。

G：签到，以后注意遇到G.in之类的读入先看CF的输入格式要求。

H：待补

I：搜索，待补

J：打表或硬推后分情况讨论： 先手可胜，当且仅当①有且只有一堆大于1的石头②等于1的石头数%3不为0，且>1石头数<=2且有一堆为2

K：签到，从大到小从左到右填数，先填完前缀为1的再填2的，以此类推

L：考虑最后答案

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 9/12 dirt: 43.75%

rank: 4

总结

这场节奏起飞点在于J没有花时间打表。不过老实说硬写打表可能并不好写有必要练。

总的来说算是平稳发挥，希望能保持位置。

题解

A: 签到，直接DP。

B: 考虑到每次一定会填一个区间，所以顺序是没有关系的。令sum[i]表示前i个位置一共有多少石头，f[i]表示只用前缀i的石头填到前缀i，保证留有i-sum[i]个空位的方案数，num[x]表示之前所有的前缀中留下正好x个空位的方案数。每当枚举到一个保证留有非负个空位的位置i时，可以考虑从前面某个空位和他一样多的前缀j转移， 1到j留完1到i能留的空位，然后j+1到i显然会用其中的所有石头填满。这个转移用num累计一下之后便可以一起转移了。

C:

D：CF原题简化版，可以直接把每个向量看成边，并查集判是否出现环即可。

E：贪心双指针处理出每个位置最远可以跟哪个音符构成同一个调的音乐，然后枚举首尾要哪首歌，去掉可以归属那首歌的前缀和后缀然后贪心跳即可。其实也可以直接倍长维护。

F：签到，0变1和1变0的方案可以贪心，然后枚举那些要使其先变成0再变回1的数的大小上界，用set维护即可。注意要用set比较稳健，排序理论上复杂度相近但是会T。

G：签到，以后注意遇到G.in之类的读入先看CF的输入格式要求。

H：待补

I：搜索，待补

J：打表或硬推后分情况讨论： 先手可胜，当且仅当①有且只有一堆大于1的石头②等于1的石头数%3不为0，且>1石头数<=2且有一堆为2

K：签到，从大到小从左到右填数，先填完前缀为1的再填2的，以此类推

L：考虑最后答案

附加文件