2020-team0x06-034

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team0x06 返回]

[[Image(Standings.png, 1000px)]][[BR]][[Image(Submissions.png, 600px)]]

== 概述 ==

2021 - ICPC - Kunming

== 流水账 ==

    清明线上训练赛, H'''H1Y1'''签到完毕后三人各自找题看, fx看了A觉得可做, 但看到0/47望而却步于是继续看别的题. czyh和lmh想L但没什么进展. A thousand years later... lmh决定对着L题的SPJ思路想正解, czyh胡了B的上下界网络流但感觉不会写, fx胡了J的做法但被czyh叉掉了. A thousand years later... fx纠正了J的做法并丢给czyh写'''J1Y94''',A掉此题后czyh转战I题, fx帮lmh想他的已经几乎完成的思路. 看着榜上300+人过L,30+人过J,fx陷入沉思并大胆猜结论然后丢给lmh写'''L1Y136''', czyh继续写I'''I1Y142'''. fx觉得A比较有想法于是去正面刚A, czyh感觉D是Dark结论题于是开始想D, lmh观察榜单并开始看M. czyh利用了某些外部资源(3B1B)加上奇思妙想干掉了D,震惊队友一百年.'''D1Y186''' fx感到自己胡出了A, 跟lmh讲了后觉得没什么大问题于是开始写.fx再次展现其惊人的代码能力,经过若干debug终于过了A,'''A3Y272''',在此期间lmh和czyh胡出了M并将fx拽下机写M, 但WA了.在距离比赛还有10min不到的赛艇时刻,lmh发现自己的离散化又假了(上次是在哪来着?), 于是'''M3Y294'''. 

== 总结 ==

=== ntwbvdbl_oe ===

 * CGK都没时间做，如果L早过说不定能多一个题


=== Orange_User ===


=== functionendless ===

贪心大好.jpg

== 题解 ==

A: 考虑求出出现k个"ac"需要修改的最少字符. 可"后悔"贪心, 定义ai:将s[i],s[i+1]拼成"ac"的代价. 则转化为:选k个a,且不能相邻,最小化其代价和.
    贪心: 每次选择的代价="连通块"奇偶交换并左右扩展1格的代价. 丢到set里维护每次取最小即可,注意合并的细节.

B: 

C: 

D:　判断n|k^n^

E: 

F: 

G: 

H: 签到

I: (czyh)

J: 考虑排列的经典"环"结构,即每个i向p[i]连边, 形成若干环,每个环独立考虑. 且环长相等则同质.
对于环长为偶数,一步到位. 环长是奇数, 先全部反转(1和n,2和n-1....), 再2-n按偶数处理即可. 即该情况总共2步

K:

L: 输出每个点结尾的最长下降子序列

M: 对一个有序序列，若sum[i-1]+1<a[i]且i最小，则答案为sum[i-1]+1。对于一个区间，若1到sum可表示，则查询sum+1的lowerbound是否满足要求，最多查询log次，主席树维护

[/wiki/2020-team0x06 返回]


概述

2021 - ICPC - Kunming

流水账

清明线上训练赛, HH1Y1签到完毕后三人各自找题看, fx看了A觉得可做, 但看到0/47望而却步于是继续看别的题. czyh和lmh想L但没什么进展. A thousand years later... lmh决定对着L题的SPJ思路想正解, czyh胡了B的上下界网络流但感觉不会写, fx胡了J的做法但被czyh叉掉了. A thousand years later... fx纠正了J的做法并丢给czyh写J1Y94,A掉此题后czyh转战I题, fx帮lmh想他的已经几乎完成的思路. 看着榜上300+人过L,30+人过J,fx陷入沉思并大胆猜结论然后丢给lmh写L1Y136, czyh继续写II1Y142. fx觉得A比较有想法于是去正面刚A, czyh感觉D是Dark结论题于是开始想D, lmh观察榜单并开始看M. czyh利用了某些外部资源(3B1B)加上奇思妙想干掉了D,震惊队友一百年.D1Y186 fx感到自己胡出了A, 跟lmh讲了后觉得没什么大问题于是开始写.fx再次展现其惊人的代码能力,经过若干debug终于过了A,A3Y272,在此期间lmh和czyh胡出了M并将fx拽下机写M, 但WA了.在距离比赛还有10min不到的赛艇时刻,lmh发现自己的离散化又假了(上次是在哪来着?), 于是M3Y294.

总结

ntwbvdbl_oe

  • CGK都没时间做，如果L早过说不定能多一个题

Orange_User

functionendless

贪心大好.jpg

题解

A: 考虑求出出现k个"ac"需要修改的最少字符. 可"后悔"贪心, 定义ai:将s[i],s[i+1]拼成"ac"的代价. 则转化为:选k个a,且不能相邻,最小化其代价和.

贪心: 每次选择的代价="连通块"奇偶交换并左右扩展1格的代价. 丢到set里维护每次取最小即可,注意合并的细节.

B:

C:

D:　判断n|kn

E:

F:

G:

H: 签到

I: (czyh)

J: 考虑排列的经典"环"结构,即每个i向p[i]连边, 形成若干环,每个环独立考虑. 且环长相等则同质.

对于环长为偶数,一步到位. 环长是奇数, 先全部反转(1和n,2和n-1....), 再2-n按偶数处理即可. 即该情况总共2步

K:

L: 输出每个点结尾的最长下降子序列

M: 对一个有序序列，若sum[i-1]+1

附加文件