2019-team11/0008
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
=== 2019.06.15 Extra Practice 3 for Acyclic_SD by chenjb+AcFast 总结 By 1em0n Team ===
=== Part 1 流水账 ===
=== Part 2 队员总结 ===
=== 孔畅 ===
=== 夏天鑫 ===
=== 黄彦玮 ===
（CJB说这是CF坑题合集）
质量还不错的一套题。可能是当时做的时候头脑不是很清晰加上之前被多校虐的有点惨，补题的时候在想比赛时到底在干啥，就很自闭，现在看来其实很多题都非常可做，以后想题还是不能轻易放弃。
=== 补题 ===
|| Contest Name || A || B || C || D || E || F || G || H || I || J || K || L || M ||
|| Extra Practice 3 for Acyclic_SD by chenjb+AcFast || Ø || O || Ø || O || . || Ø || . || . || Ø || Ø || Ø || X || X ||
O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的
=== 题解 ===
A：（Trick）给定一个串，单点修改+动态查询给定串在给定区间中出现次数。————按字母Bitset存。
B：（计算几何）平面上给出一些点（注意数据范围），求一个最小的圆的半径，满足此圆覆盖所有点并且与x轴相切。————三分即可。注意精度。
C：（树上点对统计）给定一棵树，在所有树上距离为2的点间连一条边，求树上所有点对最短距离和。————等价于，原树上距离为奇数的点对距离+1再除以2，原树上距离为偶数的点对距离除以2。从每条边被覆盖的次数考虑，考虑每条边被多少个奇距离点对和偶距离点对覆盖，统计出所有偶距离点对间距离和以及所有奇距离点对间距离和，对于偶距离直接除以2，奇距离需要加上奇距离点对数再除以2。最后加起来即可。（这题真的不难）
D：（优先队列+模拟）一个股票市场，可以挂单（买/卖）或成交，已知挂单信息和成交信息但不知道每一个信息是买还是卖，求所有可能的情况数。————根据题意模拟。细节比较多，想起来比较复杂。
F：（主席树）求一个按照输入顺序且边权递增的路径，最大化路径上的边数。————对于每条边依次加入主席树，根据起点查询，把终点信息更新。
I：（★后缀数组+单调队列/线段树）给定一个括号串，每次可以在任意位置添加任意一种括号，或者把结尾的字符移到开头，求能得到的字典序最小的匹配的括号序列。————很明显最后串长是原串长+abs(左括号数-右括号数)，即要找一个匹配的循环串，在前面补上左括号或者后面补上右括号（如果补左括号，只要满足补上左括号后匹配即可）。于是将原串复制一份开后缀数组，很容易求出字典序最小的。但是题目还要求匹配，于是把左括号视为1，右括号视为-1，先预处理一下前缀和，记为pre[i]，然后如果从min(pre[i..i+n-1])>=pre[i-1]+要添加的左括号数则说明原串中从[i,i+n)添上左括号后是匹配的。其中最小值可以用单调队列求，也可以线段树。（这题网上好像还有一种hash做法也可）
J：（Trick+dp）一个很长的循环串，给出循环节和循环次数k，求LIS。————注意数据范围，循环次数超过循环节中不同字符的个数则答案就是后者，否则暴力构造序列dp。
K：（★dp）给定一个矩阵，求最大的每个数都不相同的子矩阵，长宽<=400，每个数<=160000。————设f[i][l][r]表示下界为i，左右界为l,r的上界最小值，p[i][j]表示第i列中j这个数出现的行的最大值。则有转移方程f[i][l][r]=max(f[i-1][l][r-1],f[i-1][l+1][r],p[l][a[i][r]],p[r][a[i][l]])。区间dp即可。（数据范围刚好，有一点trick在里面，解法有点巧妙）2019.06.15 Extra Practice 3 for Acyclic_SD by chenjb+AcFast 总结 By 1em0n Team
Part 1 流水账
Part 2 队员总结
孔畅
夏天鑫
黄彦玮
（CJB说这是CF坑题合集）
质量还不错的一套题。可能是当时做的时候头脑不是很清晰加上之前被多校虐的有点惨，补题的时候在想比赛时到底在干啥，就很自闭，现在看来其实很多题都非常可做，以后想题还是不能轻易放弃。
补题
| Contest Name | A | B | C | D | E | F | G | H | I | J | K | L | M |
| Extra Practice 3 for Acyclic_SD by chenjb+AcFast | Ø | O | Ø | O | . | Ø | . | . | Ø | Ø | Ø | X | X |
O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的
题解
A：（Trick）给定一个串，单点修改+动态查询给定串在给定区间中出现次数。————按字母Bitset存。
B：（计算几何）平面上给出一些点（注意数据范围），求一个最小的圆的半径，满足此圆覆盖所有点并且与x轴相切。————三分即可。注意精度。
C：（树上点对统计）给定一棵树，在所有树上距离为2的点间连一条边，求树上所有点对最短距离和。————等价于，原树上距离为奇数的点对距离+1再除以2，原树上距离为偶数的点对距离除以2。从每条边被覆盖的次数考虑，考虑每条边被多少个奇距离点对和偶距离点对覆盖，统计出所有偶距离点对间距离和以及所有奇距离点对间距离和，对于偶距离直接除以2，奇距离需要加上奇距离点对数再除以2。最后加起来即可。（这题真的不难）
D：（优先队列+模拟）一个股票市场，可以挂单（买/卖）或成交，已知挂单信息和成交信息但不知道每一个信息是买还是卖，求所有可能的情况数。————根据题意模拟。细节比较多，想起来比较复杂。
F：（主席树）求一个按照输入顺序且边权递增的路径，最大化路径上的边数。————对于每条边依次加入主席树，根据起点查询，把终点信息更新。
I：（★后缀数组+单调队列/线段树）给定一个括号串，每次可以在任意位置添加任意一种括号，或者把结尾的字符移到开头，求能得到的字典序最小的匹配的括号序列。————很明显最后串长是原串长+abs(左括号数-右括号数)，即要找一个匹配的循环串，在前面补上左括号或者后面补上右括号（如果补左括号，只要满足补上左括号后匹配即可）。于是将原串复制一份开后缀数组，很容易求出字典序最小的。但是题目还要求匹配，于是把左括号视为1，右括号视为-1，先预处理一下前缀和，记为pre[i]，然后如果从min(pre[i..i+n-1])>=pre[i-1]+要添加的左括号数则说明原串中从[i,i+n)添上左括号后是匹配的。其中最小值可以用单调队列求，也可以线段树。（这题网上好像还有一种hash做法也可）
J：（Trick+dp）一个很长的循环串，给出循环节和循环次数k，求LIS。————注意数据范围，循环次数超过循环节中不同字符的个数则答案就是后者，否则暴力构造序列dp。
K：（★dp）给定一个矩阵，求最大的每个数都不相同的子矩阵，长宽<=400，每个数<=160000。————设f[i][l][r]表示下界为i，左右界为l,r的上界最小值，p[i][j]表示第i列中j这个数出现的行的最大值。则有转移方程f[i][l][r]=max(f[i-1][l][r-1],f[i-1][l+1][r],p[l][a[i][r]],p[r][a[i][l]])。区间dp即可。（数据范围刚好，有一点trick在里面，解法有点巧妙）