2017-Sp75-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，cjb读了A，和sub讨论出了一个结论，让yzc上机写着A，过了一会儿sub读了K，丢了sb式子给cjb，cjb上机'''A1y19'''。之后yzc A wa了，sub上机写sb题I，也wa了，cjb和yzc研究了一下A，调整了做法，还是wa，sub上机'''I2y29'''。yzc怀疑要int128，修改后'''A3y35'''。sub和yzc讨论了E，yzc上机写了一个算法，结果发现题读错了，之后sub上机，'''E1y80'''。cjb和yzc讨论了F，cjb上机写tarjan，yzc上机补完，获得wa后cjb上机写对拍，改了好多bug后发现算法有问题，sub给出了一个算法，yzc改完后'''F2y207'''。sub此前深思熟虑J，上机wa了后写了对拍，最后'''J2y277'''。此前cjb和yzc讲了D常数很小的做法，yzc上机tle了一发，修改后在结束之后1min获得通过。
== 总结 ==
=== chenjb ===
F给出了一个错误的算法浪费了好多时间，果然还是要提高姿势水平啊QAQ 今天yzc的那发D挺可惜的，不过放在hdu上就肯定过不了了....本来想做icpc camp 2016，结果误打误撞做了多校2016....要开学啦好烦啊....
=== oipotato ===

=== subconscious  ===
== 题解 ==
 * D
  * 题意：两个序列a，b，长度为n。操作1：l，r，x，将a[l..r]均改为x，操作2：l,r，询问l到r之内有多少个i满足ai>=bi。操作数m。其中，n<=1e5，m<=3e6。
  * 题解：考虑用线段树套有序表维护b数组，由于b数组是静态的，每次修改显然只需在区间的有序表上二分即可。复杂度O((n+m)log^2^n)。考虑到这棵线段树的有序表是静态的，那么我们可以很方便的预处理出答案为有序表中某个数时，左右区间的答案是多少，于是预处理之后标记下放可以O(1)完成，只需在打标记时二分一次即可。复杂度((n+m)logn)。
 * G
  * 题意：给一张图，已经黑白染色了，每次可以交换相邻，求最少步数使得正确二分图黑白染色。
  * 题解：考虑要把一个黑换到另外一个地方去，可以构造出一个不影响中途颜色的换法，而且cost就是dist，所以用二分图染色判定，然后floyd预处理后跑二分图最小权匹配，然后打印过程就好了(这个很多细节)，具体构造看bestcoder题解。
 * L
  * 题意：给出长度为n的串s和长度为m的串p，一次操作可以将p中的相邻元素交换，但每个元素只能被换一次。对于s中每一个长度为m的子串，是否能经过对p进行一次操作使得子串与p相等。n<=1e5,m<=5e4
  * 题解：考虑dp状态f[i][j][k]，表示匹配到s串的前i个字符，p的前j个字符，k=0表示向前交换，1表示不交换，2表示向后交换。DP方程显然：
   * '''f[i][j][0]=f[i-1][j-1][2] and (s[i]=p[j-1])'''
   * '''f[i][j][1]=(f[i-1][j-1][0] or f[i-1][j-1][1]) and (s[i]=p[j])'''
   * '''f[i][j][2]=(f[i-1][j-1][0] or f[i-1][j-1][1]) and (s[i]=p[j+1])'''
   * 将第一维压入bitset，第二维滚动数组即可，复杂度O(nm/64)
 * [http://bestcoder.hdu.edu.cn/blog/2016-multi-university-training-contest-2-solutions-by-zimpha/ Official]
 * [https://wiki.icpc-camp.org/new-meta/2016/07/24%202016%20Multi-University%20Training%20Contest%202 New Meta]
== 补题 ==
 * ~~D~~ by yzc
 * ~~G~~ by cjb
 * ~~L~~ by yzc

流水账

开场各自看题，cjb读了A，和sub讨论出了一个结论，让yzc上机写着A，过了一会儿sub读了K，丢了sb式子给cjb，cjb上机A1y19。之后yzc A wa了，sub上机写sb题I，也wa了，cjb和yzc研究了一下A，调整了做法，还是wa，sub上机I2y29。yzc怀疑要int128，修改后A3y35。sub和yzc讨论了E，yzc上机写了一个算法，结果发现题读错了，之后sub上机，E1y80。cjb和yzc讨论了F，cjb上机写tarjan，yzc上机补完，获得wa后cjb上机写对拍，改了好多bug后发现算法有问题，sub给出了一个算法，yzc改完后F2y207。sub此前深思熟虑J，上机wa了后写了对拍，最后J2y277。此前cjb和yzc讲了D常数很小的做法，yzc上机tle了一发，修改后在结束之后1min获得通过。

总结

chenjb

F给出了一个错误的算法浪费了好多时间，果然还是要提高姿势水平啊QAQ 今天yzc的那发D挺可惜的，不过放在hdu上就肯定过不了了....本来想做icpc camp 2016，结果误打误撞做了多校2016....要开学啦好烦啊....

oipotato

subconscious

题解

D
- 题意：两个序列a，b，长度为n。操作1：l，r，x，将a[l..r]均改为x，操作2：l,r，询问l到r之内有多少个i满足ai>=bi。操作数m。其中，n<=1e5，m<=3e6。
- 题解：考虑用线段树套有序表维护b数组，由于b数组是静态的，每次修改显然只需在区间的有序表上二分即可。复杂度O((n+m)log²n)。考虑到这棵线段树的有序表是静态的，那么我们可以很方便的预处理出答案为有序表中某个数时，左右区间的答案是多少，于是预处理之后标记下放可以O(1)完成，只需在打标记时二分一次即可。复杂度((n+m)logn)。
G
- 题意：给一张图，已经黑白染色了，每次可以交换相邻，求最少步数使得正确二分图黑白染色。
- 题解：考虑要把一个黑换到另外一个地方去，可以构造出一个不影响中途颜色的换法，而且cost就是dist，所以用二分图染色判定，然后floyd预处理后跑二分图最小权匹配，然后打印过程就好了(这个很多细节)，具体构造看bestcoder题解。
L
- 题意：给出长度为n的串s和长度为m的串p，一次操作可以将p中的相邻元素交换，但每个元素只能被换一次。对于s中每一个长度为m的子串，是否能经过对p进行一次操作使得子串与p相等。n<=1e5,m<=5e4
- 题解：考虑dp状态f[i][j][k]，表示匹配到s串的前i个字符，p的前j个字符，k=0表示向前交换，1表示不交换，2表示向后交换。DP方程显然：
  - f[i][j][0]=f[i-1][j-1][2] and (s[i]=p[j-1])
  - f[i][j][1]=(f[i-1][j-1][0] or f[i-1][j-1][1]) and (s[i]=p[j])
  - f[i][j][2]=(f[i-1][j-1][0] or f[i-1][j-1][1]) and (s[i]=p[j+1])
  - 将第一维压入bitset，第二维滚动数组即可，复杂度O(nm/64)
Official
New Meta

补题

D by yzc
G by cjb
L by yzc

附加文件

1.png by chenjb