2019-team666-0007

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
七月集训第7场
出门hyw签掉C，'''C1y18'''，看了一眼榜发现有人过A，yyc和hyw说了一下A的题意，两人讨论出可以倒着做，hyw上机写A，码了快100行没过样例，这时全场大部分队都过了L，tjc上机写了一发L，一开始交成了python，再交过了，'''L2y56'''。很快hyw改完A，这时网又双叒叒炸了，换机，'''A1y75'''。看榜，yyc上机写D，tjc给hyw讲了大部分题的题意，期间发现K读了假题，讲完后tjc想H，hyw想I和J。D题挂了一发后tjc帮yyc一起查代码，很快改完，'''D2y96'''。这时全场大部分队过了H，tjc上机写H，yyc和hyw看I和J，讨论出了I大致做法，这时'''H2y143'''，tjc想了一会儿很快给出了J的解法，不过这时yyc在写I，挂了一发以后tjc也开始帮yyc调I，'''I2y200'''。写I的时候hyw发现了E的性质，但复杂度一直降不下来，拉yyc过来讨论。这时F和J过的人差不多，由于两个题解法都比较贴近时限，权衡了一下tjc决定写F。yyc给出了一种优化的方法，hyw觉得可行，这时'''F1y219'''。hyw打算把E的细节想清楚再写，tjc写J，Wa on 46. hyw上机写E，yyc帮忙查J的代码。E写完直接过样例就交了，改了好几次一直wa。三个人最终都没有改完。（赛后：'''J题写背包输出方案不可以直接省掉第一维物品数量，可以考虑bitset'''。E题是一开始一个性质推错了，以及代码当中一个细节出了问题。赛后日常过两题.jpg）

== 总结 ==
=== yyc ===
=== tjc  ===
'''pitfall'''：背包输出方案时，记录方案的数组不能滚动
这个J题三人一起查错都没查出方法不对（而不是代码写错），下次再遇到这种情况时一定要注意
'''pitfall'''：机房的电脑上装的是python2，提交到python3上可能会和本地结果跑出来不一样
赛时怕爆long long拿python交了一发WA1，上OJ尝试customtest发现OJ的customtest功能运行不了，于是只好拿cpp重写了一份。赛后把python代码拿到cf上交才发现python2和python3跑出来的结果不一样
=== hyw  ===
今天E和J赛时都没过挺可惜的，像E这种题其实还是应该对拍一下。
cjb说要提高静态查错能力。orz
感觉如果一个人看30分钟或者两个人看20分钟还看不出来就要想一下是不是解法出问题了。
希望有解法的题以后都能写出来。
UPD：补完M发现状压dp应该不难想，只是比赛时根本没去想，比赛中尽可能每道题都要去想一下，不能轻易放弃
UPDD： 感觉这两天签到题开得有点奇怪，虽然三个人分别从前中后读但是还是开的比较慢，今天除了C以外完全是看榜在开题，而且错误地估计了A的代码量。开场的时候可做题或者有想法的题发现了要及时跟队友说，并且做好代码量的估计，便于分配上机写题顺序。
=== 题解 ===
A：倒着做，如果某一行或者某一列除了问号以外都一样就涂色。最后把没涂过的行随便涂一个颜色，输出的时候先输出就行了。
B：求出所有边界的方程以及是上边界还是下边界后d(y^2/2)积分除以dy积分可以找到一个方向的重心所在直线。对另一个方向再做一次求出重心。最后使重心在固定点正下方并旋转多边形即可
C：类似筛法筛一遍就行了
D：枚举，复杂度分析
E：容易发现性质：小于等于k的必须放偶数位，大于k的必须放奇数位。直接枚举偶数位是O(k!)的，考虑降低复杂度。发现小于等于k/2的数在偶数位任意的放都不会对奇数位产生影响（因为大于2x或者小于x/2的数可以放在x的两边，奇数位都大于k，肯定大于这些数的2倍），于是我们只需要枚举(k/2)+1到k这些数的位置，然后统计奇数位的方案数，最后乘一个小于等于k/2的数的个数的阶乘就行了。统计时先预处理出一个数组表示最小放x的空有几个，然后从k+1开始从小到大枚举数，依次累加并减掉之前放了几个数算出当前数一共有几个空可以放，乘法原理算一下就行了，总复杂度O(k^(k/2)^*k)，最坏情况需要A(6,13)*13次，实际只用了93ms，跑的飞快。注意细节，已经放好的数就不要再统计了。
F：枚举环上的一点，对出边二进制分组，去掉连向某一位为1的顶点的边并跑n^2+m的dijkstra、更新最小环
G：
H：拿各种map和unordered_map维护
I：根据前60次询问的结果推断出随机数种子
J：做两次背包，第一次判断∑a<p时∑b>=q是否可行，第二次判断∑b<q时∑a>=p是否可行，都不可行则YES
K：以每个点为中心对其它点极角排序，数据结构维护连边是否可行，连完后跑最小生成树
L：找规律，2k+1个a经过2k+2次操作变为3k+2个a，2k个a经过2k次操作变为k个a，暴力计算答案即可，答案不会太大
M:设dp[i][mask]表示当前处理到第i行，已经填好的部分每一列的状态为mask(每一位0/1/2表示：从上到下还没有填1，已经填了1且还可以继续填，填过1了后面只能填0）。转移的时候要从下往上转移，即i从n到1循环，按每一格转移，边界条件dp[n+1][pow(3,n)-1]=1。对于每个询问，从上到下每一行暴力枚举这一行的状态(共2^n^个)，先判断是否合法，然后根据dp数组recover出这一行应该是多少，复杂度O( 3^n^ * n^2^+q* n^2^ * 2^n^)。

[/wiki/2019-team666 返回]

概述

七月集训第7场

出门hyw签掉C，C1y18，看了一眼榜发现有人过A，yyc和hyw说了一下A的题意，两人讨论出可以倒着做，hyw上机写A，码了快100行没过样例，这时全场大部分队都过了L，tjc上机写了一发L，一开始交成了python，再交过了，L2y56。很快hyw改完A，这时网又双叒叒炸了，换机，A1y75。看榜，yyc上机写D，tjc给hyw讲了大部分题的题意，期间发现K读了假题，讲完后tjc想H，hyw想I和J。D题挂了一发后tjc帮yyc一起查代码，很快改完，D2y96。这时全场大部分队过了H，tjc上机写H，yyc和hyw看I和J，讨论出了I大致做法，这时H2y143，tjc想了一会儿很快给出了J的解法，不过这时yyc在写I，挂了一发以后tjc也开始帮yyc调I，I2y200。写I的时候hyw发现了E的性质，但复杂度一直降不下来，拉yyc过来讨论。这时F和J过的人差不多，由于两个题解法都比较贴近时限，权衡了一下tjc决定写F。yyc给出了一种优化的方法，hyw觉得可行，这时F1y219。hyw打算把E的细节想清楚再写，tjc写J，Wa on 46. hyw上机写E，yyc帮忙查J的代码。E写完直接过样例就交了，改了好几次一直wa。三个人最终都没有改完。（赛后：J题写背包输出方案不可以直接省掉第一维物品数量，可以考虑bitset。E题是一开始一个性质推错了，以及代码当中一个细节出了问题。赛后日常过两题.jpg）

总结

yyc

tjc

pitfall：背包输出方案时，记录方案的数组不能滚动

这个J题三人一起查错都没查出方法不对（而不是代码写错），下次再遇到这种情况时一定要注意

pitfall：机房的电脑上装的是python2，提交到python3上可能会和本地结果跑出来不一样

赛时怕爆long long拿python交了一发WA1，上OJ尝试customtest发现OJ的customtest功能运行不了，于是只好拿cpp重写了一份。赛后把python代码拿到cf上交才发现python2和python3跑出来的结果不一样

hyw

今天E和J赛时都没过挺可惜的，像E这种题其实还是应该对拍一下。

cjb说要提高静态查错能力。orz

感觉如果一个人看30分钟或者两个人看20分钟还看不出来就要想一下是不是解法出问题了。

希望有解法的题以后都能写出来。

UPD：补完M发现状压dp应该不难想，只是比赛时根本没去想，比赛中尽可能每道题都要去想一下，不能轻易放弃

UPDD： 感觉这两天签到题开得有点奇怪，虽然三个人分别从前中后读但是还是开的比较慢，今天除了C以外完全是看榜在开题，而且错误地估计了A的代码量。开场的时候可做题或者有想法的题发现了要及时跟队友说，并且做好代码量的估计，便于分配上机写题顺序。

题解

A：倒着做，如果某一行或者某一列除了问号以外都一样就涂色。最后把没涂过的行随便涂一个颜色，输出的时候先输出就行了。

B：求出所有边界的方程以及是上边界还是下边界后d(y^2/2)积分除以dy积分可以找到一个方向的重心所在直线。对另一个方向再做一次求出重心。最后使重心在固定点正下方并旋转多边形即可

C：类似筛法筛一遍就行了

D：枚举，复杂度分析

E：容易发现性质：小于等于k的必须放偶数位，大于k的必须放奇数位。直接枚举偶数位是O(k!)的，考虑降低复杂度。发现小于等于k/2的数在偶数位任意的放都不会对奇数位产生影响（因为大于2x或者小于x/2的数可以放在x的两边，奇数位都大于k，肯定大于这些数的2倍），于是我们只需要枚举(k/2)+1到k这些数的位置，然后统计奇数位的方案数，最后乘一个小于等于k/2的数的个数的阶乘就行了。统计时先预处理出一个数组表示最小放x的空有几个，然后从k+1开始从小到大枚举数，依次累加并减掉之前放了几个数算出当前数一共有几个空可以放，乘法原理算一下就行了，总复杂度O(k^(k/2)*k)，最坏情况需要A(6,13)*13次，实际只用了93ms，跑的飞快。注意细节，已经放好的数就不要再统计了。

F：枚举环上的一点，对出边二进制分组，去掉连向某一位为1的顶点的边并跑n^2+m的dijkstra、更新最小环

G：

H：拿各种map和unordered_map维护

I：根据前60次询问的结果推断出随机数种子

J：做两次背包，第一次判断∑a=q是否可行，第二次判断∑b=p是否可行，都不可行则YES

K：以每个点为中心对其它点极角排序，数据结构维护连边是否可行，连完后跑最小生成树

L：找规律，2k+1个a经过2k+2次操作变为3k+2个a，2k个a经过2k次操作变为k个a，暴力计算答案即可，答案不会太大

M:设dp[i][mask]表示当前处理到第i行，已经填好的部分每一列的状态为mask(每一位0/1/2表示：从上到下还没有填1，已经填了1且还可以继续填，填过1了后面只能填0）。转移的时候要从下往上转移，即i从n到1循环，按每一格转移，边界条件dp[n+1][pow(3,n)-1]=1。对于每个询问，从上到下每一行暴力枚举这一行的状态(共2ⁿ个)，先判断是否合法，然后根据dp数组recover出这一行应该是多少，复杂度O( 3ⁿ * n²+q* n² * 2ⁿ)。