2019-team666-0008

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]

== 概述 ==

七月集训第8场

 [[Image(submissions.png,1000px)]]

 [[Image(rank.png,1000px)]]

'''tjcnb!!!

== 流水账 ==

开场tjc读了K的假题没看到输出字典序最大wa了两发，然后hyw给了个G的假做法喊yyc去写挂了一发，拉开了爆炸的序幕。G挂了以后hyw上机写A，写A的过程中众人发现了G做法的问题，弃之，这时'''A1y53'''，然而由于开不出题，场上除了B已经无题可写。tjc上机写B，喜提tle，由于纸质试题上写的5s而实际时限开的1s，要了一发clarification，果然是被卡了，下机改。期间hyw和yyc讨论出了C的暴力做法，hyw上机写C，挂了一发再交，再次被卡，期间'''B2y141'''，然而依然几乎没有开出任何题目，hyw在机上调C调了近1小时，改了五六个细节，终于在打算重构代码之前过了C，'''C3y200'''，这时排名是倒数第二。A快调完的时候tjc开出E，上机写E，其余人继续开题，依然非常自闭，但很快'''E1y235'''稳住全队心态，众人重拾信心开始捡起场上只剩我们队没过的签到题G。期间yyc开出K并上机写了一会儿，tjc开出D，hyw有一个G的思路说了一下，tjc改了一下马上就想出了正确的做法，hyw上机写G，终于'''G2y257'''。yyc继续写K，没过样例，期间tjc在纸上写好了D的代码，K挂了以后tjc上机抄了一遍D，又改了好几个细节，提交，竟然过了，'''D1y299'''，比赛结束。（此处应有掌声）



== 总结 ==

=== yyc ===

开场签到题想复杂了让队友写了很长的代码和这场比赛罚时爆炸有很大关系，提出做法前还是要想一想这么做是不是很麻烦。（但是感觉并不是很好判断...

=== tjc  ===


=== hyw  ===

首先感谢队友，这场所有人都非常不容易，大家是最棒的！

本来以为之前两场开场已经很不顺利了，没想到这场才是真·逆风局，前3个小时几乎完全处于全队自闭状态，居然让我打出了之前多校的感觉qaq。

这场后来之所以能翻盘我认为很大程度上归功于200分钟的C题和235分钟的E题，前者是前前后后调了近90分钟还被卡了两次而且场上很多人都过的题，后者是一道在我们之前完全没有正式队过的题。

开场一个假题一个假算法一个卡时外加一个三个小时都没过的签到，暴露除了我们队开场节奏不稳的很大问题，之前看别的队也写过，但没想到这次这么真实地落到我们队头上。

这场比赛我写了三个题A、C、G，没有一个是一遍过样例的，尤其是C改到怀疑人生，今天写代码前很多细节都没有想清楚，以后上机前最好花两三分钟想一下可能的细节，可以省去不少麻烦。

G题的做法是把小的数尽可能往两边扔，看上去不难想但我们队三个人想了四个小时也没有想出来，然而大家都过了，我个人也比较无能为力，可能是真的菜吧。

C题其实只要处理出每个人排名然后把并列的往后排就行了，然而当时我并没有冷静下来思考，脑子里都是队伍落后了这么多怎么办才能赶紧追上去，最后选择了暴力，虽然过了但是写了200+行浪费了很多时间。

I、F等几个题最后和队友一起口胡出了做法，可惜已经没时间写了。

K题想到了二分，但是没想到可能有两段合法区间，以为不具备二分性就弃了。

这次逆风场也算是全队一次非常宝贵的经验，面对不利的开场最重要是心态不能崩，即使3小时时倒数第二也不能放弃开题。

七月集训结束得好快，希望八月能打得更好~



=== 题解 ===


A: 根据题意模拟即可

B: 枚举等差数列前两项，不断hash查找下一项是否出现并标记，如果已经被标记就不再枚举（最后一步不加n^3^也能跑过，，，）

C: 算出每个人逃离所需要的时间，相同时间贪心往后移。

D: 判断一个串是否是模板串的子序列时可以每次找尽量近的一个对应字符并跳转过去。根据这个性质f(i,j)代表第一个串匹配到i，第二个串匹配到j之后还需要的最短长度，预处理出dp数组。输出方案时贪心选取字典序小的方案即可

E: 第一步先dfs匹配所有奇度点，重复选取的边可以消去；第二步如果只剩一个连通块则结束；对于有三个以上连通块的情况，从每个连通块中选一个点连成一个环；对于两个连通块的情况，如果是一个孤立点+一个原图中的团则无解，否则如果是一个孤立点+另一个较大连通块则选一条不在原图中的边与孤立点连成三元环，否则每个连通块中至少有两个点，连成四元环即可

F: 可以证明最大线段过端点，最小线段在边上，旋转卡壳+三分。

G: 思路是把小的数尽可能往两边扔，对于每个数用树状数组算出它左边和右边分别有几个数比它大，取较小值相加即可

H: 观察到右下角的点至多只有四条出边，且如果四条出边对应的颜色互不相同则一定可以通过调整使其中两个点的颜色相同，最后将右下角的点填上剩下的颜色即可

I: 分治+高斯消元处理线性基（n^3^log/w）

J: 虚树边数=(dfs序相邻两点距离之和+dfs序首尾距离)/2，set维护

K: 先把b排序，然后对a的每一位二分，注意合法区间可能有两段，先从能赢的区间里二分，找最大的不会使胜场数改变的值，如果找不到再从不能赢的区间里二分。

[/wiki/2019-team666 返回]

概述

七月集训第8场

'''tjcnb!!!

流水账

开场tjc读了K的假题没看到输出字典序最大wa了两发，然后hyw给了个G的假做法喊yyc去写挂了一发，拉开了爆炸的序幕。G挂了以后hyw上机写A，写A的过程中众人发现了G做法的问题，弃之，这时A1y53，然而由于开不出题，场上除了B已经无题可写。tjc上机写B，喜提tle，由于纸质试题上写的5s而实际时限开的1s，要了一发clarification，果然是被卡了，下机改。期间hyw和yyc讨论出了C的暴力做法，hyw上机写C，挂了一发再交，再次被卡，期间B2y141，然而依然几乎没有开出任何题目，hyw在机上调C调了近1小时，改了五六个细节，终于在打算重构代码之前过了C，C3y200，这时排名是倒数第二。A快调完的时候tjc开出E，上机写E，其余人继续开题，依然非常自闭，但很快E1y235稳住全队心态，众人重拾信心开始捡起场上只剩我们队没过的签到题G。期间yyc开出K并上机写了一会儿，tjc开出D，hyw有一个G的思路说了一下，tjc改了一下马上就想出了正确的做法，hyw上机写G，终于G2y257。yyc继续写K，没过样例，期间tjc在纸上写好了D的代码，K挂了以后tjc上机抄了一遍D，又改了好几个细节，提交，竟然过了，D1y299，比赛结束。（此处应有掌声）

总结

yyc

开场签到题想复杂了让队友写了很长的代码和这场比赛罚时爆炸有很大关系，提出做法前还是要想一想这么做是不是很麻烦。（但是感觉并不是很好判断...

tjc

hyw

首先感谢队友，这场所有人都非常不容易，大家是最棒的！

本来以为之前两场开场已经很不顺利了，没想到这场才是真·逆风局，前3个小时几乎完全处于全队自闭状态，居然让我打出了之前多校的感觉qaq。

这场后来之所以能翻盘我认为很大程度上归功于200分钟的C题和235分钟的E题，前者是前前后后调了近90分钟还被卡了两次而且场上很多人都过的题，后者是一道在我们之前完全没有正式队过的题。

开场一个假题一个假算法一个卡时外加一个三个小时都没过的签到，暴露除了我们队开场节奏不稳的很大问题，之前看别的队也写过，但没想到这次这么真实地落到我们队头上。

这场比赛我写了三个题A、C、G，没有一个是一遍过样例的，尤其是C改到怀疑人生，今天写代码前很多细节都没有想清楚，以后上机前最好花两三分钟想一下可能的细节，可以省去不少麻烦。

G题的做法是把小的数尽可能往两边扔，看上去不难想但我们队三个人想了四个小时也没有想出来，然而大家都过了，我个人也比较无能为力，可能是真的菜吧。

C题其实只要处理出每个人排名然后把并列的往后排就行了，然而当时我并没有冷静下来思考，脑子里都是队伍落后了这么多怎么办才能赶紧追上去，最后选择了暴力，虽然过了但是写了200+行浪费了很多时间。

I、F等几个题最后和队友一起口胡出了做法，可惜已经没时间写了。

K题想到了二分，但是没想到可能有两段合法区间，以为不具备二分性就弃了。

这次逆风场也算是全队一次非常宝贵的经验，面对不利的开场最重要是心态不能崩，即使3小时时倒数第二也不能放弃开题。

七月集训结束得好快，希望八月能打得更好~

题解

A: 根据题意模拟即可

B: 枚举等差数列前两项，不断hash查找下一项是否出现并标记，如果已经被标记就不再枚举（最后一步不加n3也能跑过，，，）

C: 算出每个人逃离所需要的时间，相同时间贪心往后移。

D: 判断一个串是否是模板串的子序列时可以每次找尽量近的一个对应字符并跳转过去。根据这个性质f(i,j)代表第一个串匹配到i，第二个串匹配到j之后还需要的最短长度，预处理出dp数组。输出方案时贪心选取字典序小的方案即可

E: 第一步先dfs匹配所有奇度点，重复选取的边可以消去；第二步如果只剩一个连通块则结束；对于有三个以上连通块的情况，从每个连通块中选一个点连成一个环；对于两个连通块的情况，如果是一个孤立点+一个原图中的团则无解，否则如果是一个孤立点+另一个较大连通块则选一条不在原图中的边与孤立点连成三元环，否则每个连通块中至少有两个点，连成四元环即可

F: 可以证明最大线段过端点，最小线段在边上，旋转卡壳+三分。

G: 思路是把小的数尽可能往两边扔，对于每个数用树状数组算出它左边和右边分别有几个数比它大，取较小值相加即可

H: 观察到右下角的点至多只有四条出边，且如果四条出边对应的颜色互不相同则一定可以通过调整使其中两个点的颜色相同，最后将右下角的点填上剩下的颜色即可

I: 分治+高斯消元处理线性基（n3log/w）

J: 虚树边数=(dfs序相邻两点距离之和+dfs序首尾距离)/2，set维护

K: 先把b排序，然后对a的每一位二分，注意合法区间可能有两段，先从能赢的区间里二分，找最大的不会使胜场数改变的值，如果找不到再从不能赢的区间里二分。

附加文件