Xiangtan Invitation Contest 2017（2017湘潭邀请赛）（Done）

约定不等于承诺〃 2022-06-15 08:41 184阅读 0赞

叉姐出的题。  
题目链接：  
[点击打开题目链接][Link 1] 或者去 CampOJ交吧。  
很多人问我代码：[github][]  
题号：1260−1269.  题 号 ： 1260 − 1269.

A.Determinant.（Accept）  A . D e t e r m i n a n t . （ A c c e p t ）   
题解：把矩阵补全成n∗n  n ∗ n 的。那么题目就是要你求逆矩阵的第一列，高斯消元就可以啦。

B.Roads.（Accept）  B . R o a d s . （ A c c e p t ）   
题解：  
考虑Kruskal  K r u s k a l 的过程，肯定是同样权值的边连通了一个点集。如果要让最小生成树变大，就是要让某个权值的边不再连通。这是全局最小割问题，直接网络流。也可以用Stoer–Wagner 算法求全局最小割。

C.Intersection.（Accept）  C . I n t e r s e c t i o n . （ A c c e p t ）   
题解：  
先求出A  A 的秩a a，再求出B  B 的秩b b,然后再把A  A 和B B组合在一起，再求这个的秩c  c ，高斯消元即可。那么答案就是2(a\+b−c) 2( a \+ b − c )。

D.SuperResolution.（Accept）  D . S u p e r R e s o l u t i o n . （ A c c e p t ）   
题解：签到题。直接输出。

E.PartialSum.（Accept）  E . P a r t i a l S u m . （ A c c e p t ）   
题解：感觉是脑洞题。直接对前缀和排序，枚举m  m 并更新答案。

F.LongestCommonSubsequence.（Accept） F . L o n g e s t C o m m o n S u b s e q u e n c e .（A c c e p t）  
题意：给定序列A  A ，含n n个数。和一个数m  m ；有一个X X序列x1,x2,x3  x 1 , x 2 , x 3 ，x1,x2,x3  x 1 , x 2 , x 3 来自\[1,m\]  \[ 1 , m \] 区间内的数。  
f(k)  f ( k ) 表示两个序列的最长公共子序列为k  k ，让你求序列X X和A  A 满足f(0),f(1),f(2),f(3) f ( 0 ) , f ( 1 ) , f ( 2 ) , f ( 3 )的X  X 各有多少种。

题解：设n n个数中在m  m 范围内的不同数的数量为count c o u n t，然后计算(m−count)3  ( m − c o u n t ) 3 即为f(0)  f ( 0 ) .  
首先对a  a 离散化，之后可以O(n3) O (n 3) 枚举序列X  X .如果之后用O(n) O ( n )的LCS  L C S ,dp  d p  会使复杂度变成O(n4).  O ( n 4 ) .   
解决方法是23  2 3  枚举X  X 的一个子序列，通过预处理一个next\[i\]\[c\]  n e x t \[ i \] \[ c \] 表示i  i 位置后c  c 字符第一次出现的位置，来O(1) O ( 1 ) 判断是否是A  A  的子序列。

G.Parentheses.（Accept） G . P a r e n t h e s e s .（A c c e p t）  
题意：从左到右有n个连续的组，每一组有Li  L i 个括号，要么全是左括号，要么全是右括号，以及该组的每一个左括号翻成右括号，或者右括号翻成左括号的花费Di  D i .可以对这n  n 个组的括号进行翻转，每一个括号都可以选择翻或者不翻，使整个括号序列是一个合法括号序列.

题解：贪心吧。  
括号序列就是要求前(2k\+1) ( 2 k \+ 1 ) 个里面至少要有k  k 个左括号。那么先把所有括号翻成右括号，之后重新翻回左括号。那么从左到右贪心，用一个堆维护现在可以翻回左括号的位置。每次相当于加两个当前段的字符，取一个最小的。所以事件只有最小的被拿完了，或者当前段拿完了。模拟即可。（std）  （ s t d ）

H.Highway.（Accept）  H . H i g h w a y . （ A c c e p t ）   
题解：  
假设初始点v0  v 0  是某条直径的端点。那么距离v0  v 0  最远的v1  v 1  必然是直径的另一个端点。  
又因为距离任意点最远的要么是v0  v 0  要么是v1  v 1 ，所以剩下的点只需要连往v0  v 0  和v1  v 1  中较远的一个即可。我直接dfs  d f s  3  3 次就过了。

I.StrangeOptimization.（Accept） I . S t r a n g e O p t i m i z a t i o n .（A c c e p t）  
题解：  
就是让你求：gcd(n,m)2nm  g c d ( n , m ) 2 n m ，约分一下就可以了。

J.SimilarSubsequence.（Accept）  J . S i m i l a r S u b s e q u e n c e . （ A c c e p t ）   
题解：dp题。  
设dp\[i\]\[j\]\[k\]  d p \[ i \] \[ j \] \[ k \] 中，i  i 表示a a串中第i  i 个元素，j j表示b  b 串中的第j j个元素，  
当a\[i\]==0时，k为第i~n个被匹配的元素中最大值。  
当a\[i\]==1时，k为第i~n个被匹配的元素中最小值。  
用树状数组可以优化到O(n∗m2∗log(m))  O ( n ∗ m 2 ∗ l o g ( m ) ) 。

官方题解是四维dp。  
设f(i,j,x,y)  f ( i , j , x , y )  表示分别匹配到ai  a i 和bj  b j ，数字的上界和下界分别是  
x  x 和y  y 的方案数。注意到x  x 和y  y 总有一个等于bj  b j ，所以状态数是  
nm2  n m 2 的。  
转移就是枚举ai\+1  a i + 1 匹配的是bk  b k ，要求bk  b k 落在\[x,y\]  \[ x , y \] 中。这个可  
以用树状数组优化。复杂度是O(n∗m2∗log(m))  O ( n ∗ m 2 ∗ l o g ( m ) ) .

[Link 1]: http://202.197.224.59/OnlineJudge2/index.php/Problem/index/p/13/
[github]: https://github.com/LzyRapx/Competitive-Programming