2017-Sp87-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场把所有题读完了，不怎么会做，大家纷纷过C，依然不会，sub表示会做G，上机写G，wa。yzc会做A了，上机写A，'''A1y83'''。sub一直在调G，cjb和yzc终于强行理论了C，wa。cjb开出了H，'''H1y179'''。sub终于搞定了G，'''G5y185'''。最后sub点醒了C，'''C3y210'''。
== 总结 ==
=== chenjb ===
晕晕晕...菜菜菜....sub要好好休息
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * B:
  * 题意：3*n(n<=2000)的棋盘，有些格子放了棋子，你要放棋子把棋盘填满，要求棋子能放当且仅当它左右或者上下的两个格子有棋子才能放，求不同的放置方案数。
  * 题解：首先判断是否无解，四个边角必须有棋子，上下边界不能有连续的空白，否则不存在方案填满。然后分析如何计算方案数。假如中间一行只能通过上下相邻来填满，那么显然每列是独立的，可以把每列的偏序给排在一起算出答案。现在考虑可以通过左右相邻来填，那么会使得中间一行的格子之间产生先后的限制，于是我们用f[i][j][0/1]表示前i列已经填满，第i列的中间的格子是第j个被填上的，是否要求第i+1列的中间的格子在其之前被填上。转移的时候要分该列中间格子是否能放来讨论，还要考虑前i列的空格子个数和该列空格子个数的关系来确定转移系数(P(n,0..2)，实现的时候可以n++，加多一行满的来方便实现。时间复杂度是O(n*sumx)，sumx为空格子个数。
 * E：
  * 题意：2*n个人排队上厕所，男生只能去男女共用的厕所，女生优先去女厕所，也能去男女共用的厕所。如果一个男生在队头但是男女共用厕所有人，女厕所空着，他就会让后面的女生先上厕所。问能否重排队列使得所有人在n的时间内上完厕所，同时使得每个人被别人排在前面的次数最大值最小。
  * 题解：显然要做到时间n内上完厕所，上男女共用厕所的女生数+男生总数要恰好等于n。男生多余n个则显然无解，否则设男生人数a，女生比男生多y=2*n-2*a人，设初始队列前缀中女生比男生多的最大值为x。则最后答案显然为x-y-1。
 * F：
  * 题意：n个人，每次选择一个区间和一个数，扫一遍区间，遇到一个比手里数字大的就交换，输出最后的数字。询问产生的交换对后续询问有效。
  * 题解：暴力分块。“容易”发现①一个操作通过一个块时，相当于将这个块中最大的数换出来（如果其比块中最大数小）；②一群操作通过一个数时，相当于将这群操作中的最小数换出（当这个数比最小数大时）。于是这个题只需每个块将整体操作记录下来，当需要重建时利用性质②重建即可。
 * [https://wiki.icpc-camp.org/new-meta/2017/3/4%20Japanese%20OI%20Team%20Selection New Meta]
 * [https://wiki.icpc-camp.org/dreadnought/MIPTCamp%202016%20Day5%20-%20Japanese%20OI%20Selection%20Test%202016 Dreadnought]
 * [wiki:2016-E39-team1  Siunaus]
== 补题 ==
 * ~~B~~ by cjb
 * ~~E~~ by yzc
 * ~~F~~ by yzc
 * ~~I~~ by yzc

流水账

开场把所有题读完了，不怎么会做，大家纷纷过C，依然不会，sub表示会做G，上机写G，wa。yzc会做A了，上机写A，A1y83。sub一直在调G，cjb和yzc终于强行理论了C，wa。cjb开出了H，H1y179。sub终于搞定了G，G5y185。最后sub点醒了C，C3y210。

总结

chenjb

晕晕晕...菜菜菜....sub要好好休息

oipotato

subconscious

题解

• B:
  • 题意：3*n(n<=2000)的棋盘，有些格子放了棋子，你要放棋子把棋盘填满，要求棋子能放当且仅当它左右或者上下的两个格子有棋子才能放，求不同的放置方案数。
  • 题解：首先判断是否无解，四个边角必须有棋子，上下边界不能有连续的空白，否则不存在方案填满。然后分析如何计算方案数。假如中间一行只能通过上下相邻来填满，那么显然每列是独立的，可以把每列的偏序给排在一起算出答案。现在考虑可以通过左右相邻来填，那么会使得中间一行的格子之间产生先后的限制，于是我们用f[i][j][0/1]表示前i列已经填满，第i列的中间的格子是第j个被填上的，是否要求第i+1列的中间的格子在其之前被填上。转移的时候要分该列中间格子是否能放来讨论，还要考虑前i列的空格子个数和该列空格子个数的关系来确定转移系数(P(n,0..2)，实现的时候可以n++，加多一行满的来方便实现。时间复杂度是O(n*sumx)，sumx为空格子个数。
• E：
  • 题意：2*n个人排队上厕所，男生只能去男女共用的厕所，女生优先去女厕所，也能去男女共用的厕所。如果一个男生在队头但是男女共用厕所有人，女厕所空着，他就会让后面的女生先上厕所。问能否重排队列使得所有人在n的时间内上完厕所，同时使得每个人被别人排在前面的次数最大值最小。
  • 题解：显然要做到时间n内上完厕所，上男女共用厕所的女生数+男生总数要恰好等于n。男生多余n个则显然无解，否则设男生人数a，女生比男生多y=2*n-2*a人，设初始队列前缀中女生比男生多的最大值为x。则最后答案显然为x-y-1。
• F：
  • 题意：n个人，每次选择一个区间和一个数，扫一遍区间，遇到一个比手里数字大的就交换，输出最后的数字。询问产生的交换对后续询问有效。
  • 题解：暴力分块。“容易”发现①一个操作通过一个块时，相当于将这个块中最大的数换出来（如果其比块中最大数小）；②一群操作通过一个数时，相当于将这群操作中的最小数换出（当这个数比最小数大时）。于是这个题只需每个块将整体操作记录下来，当需要重建时利用性质②重建即可。
• New Meta
• Dreadnought
• Siunaus

补题

• B by cjb
• E by yzc
• F by yzc
• I by yzc

附加文件

• 1.png by chenjb