目录

2017 湘潭市赛题解

---

(线代知识)

题意:求一个\((n-1) \times n\)的矩阵 去掉第每一列后的行列式的值

题解：

把该矩阵 随机n个数 补成 \(n \times n\)

假设补的是第n行，那么答案就是其伴随矩阵A的第i行n列 \((-1)^{i+n}\)

• A的伴随矩阵可按如下步骤定义：
  1.把D的各个元素都换成它相应的代数余子式；
  （代数余子式定义：在一个n阶行列式A中,把(i,j)元aij所在的第i行和第j列划去后，留下来的n-1阶行列式叫做(i,j)元aij的余子式，记Mij作 ;即\(Aij = -1^{(i+j)}Mij\)，叫做(i,j)元aij的代数余子式）
  注意：其中所求的Aij为一个数值，并非矩阵。
  2.将所得到的矩阵转置便得到A的伴随矩阵，
  补充：（实际求解伴随矩阵即A*=aij（A）：去除 A的行列式D中aij元素 对应的第 j 行和第 i列得到的新行列式D1代替 aij，这样就不用转置了）

由定理 \[A^{-1} = \frac{A^{*}}{|A|}\]得 \(A^{*} = |A| \cdot A^{-1}\)

现在问题就变成了求A的逆矩阵了 和 A的行列式了

线代书上有讲求逆矩阵的方式

在A的右边加一个同阶的单位矩阵E，两边同时消元，把左边消成单位矩阵时，右边就是A的逆矩阵

模板可见 算法与实现 Page 6

#include
    
     #define LL long long#define P pair
     
      using namespace std;const LL mod = 1e9 + 7;const int N = 220;int n;LL A[N][N],a[N][N],C[N][N];LL ext_gcd(LL a,LL b,LL &x,LL &y){    if(b==0)    {        x = 1, y = 0;        return a;    }    LL d = ext_gcd(b,a%b,y,x);    y -= a / b * x;    return d;}LL inverse(LL a){    LL x, y;    ext_gcd(a,mod,x,y);    return (x%mod+mod)%mod;}void add(LL &x ,LL y){    x += y;    if(x >= mod) x -= mod;}LL guass_inverse(){    for(int i = 0; i < n; i++)        for(int j = 0; j < n; j++)            C[i][j] = i == j?1:0;    for(int i = 0; i < n; i++)    {        int p = i;        for(int j = i; j < n; j++)            if(A[j][i] > A[p][i]) p = j;        swap(A[p],A[i]);        swap(C[p],C[i]);        if(A[i][i] == 0) return -1;        LL inva = inverse(A[i][i]);        for(int j = 0; j < n; j++)        {            C[i][j] = C[i][j] * inva % mod;            A[i][j] = A[i][j] * inva % mod;        }        for(int j = 0; j < n; j++)            if(j != i)            {                LL z = A[j][i];                for(int k = 0; k < n; k++)                {                    add(C[j][k],mod - C[i][k]*z%mod);                    add(A[j][k],mod - A[i][k]*z%mod);                }            }    }    return 1;}LL gauss(int n)///高斯消元求行列式的值  用到了逆元把除法变乘法 避免精度问题{    LL ret=1;    int flag=1;    for (int i=0; i
     
    

(最小生成树+全局最小割)

题意：求一个最小割，使得最小生成树的费用增加

思路：

最开始的做法是把所有可能导致最小生成树费用增加的边建图，跑全局最小割，WA

下面这组数据过不去

6 10

1 2 2

1 3 1

2 3 2

4 5 1

4 6 2

5 6 2

3 4 3

3 4 3

3 4 3

3 4 3

再来看叉姐的题解,才真正理解的做法

考虑 Kruskal 的过程，肯定是同样权值的边连通了一个点集。如

果要让 MST 变大，就是要让某个权值的边不再连通。

就是对于每一个相同权值的候选边构成的点集求最小割取小值，然后又WA了

真正做法是

假设新图的点集为S，边集为E，开始时S = {},E = {}

把权值第一小的所有候选边和点加入S和E

求出所有连通点集的最小割取最小值

再接着依次把第i小的候选边和点加入S和E，求最小割取最小

#include
    
     #define LL long long#define P pair
     
      using namespace std;const int inf = 0x3f3f3f3f;const int N = 55;struct Edge{    int u , v , w;    Edge(){};    bool operator<(const Edge &rhs)const{        return w < rhs.w;    }}e[N * N];int n , m;int pa[N];int Find(int x){    return pa[x] == x?x:pa[x] = Find(pa[x]);}int vis[N],combine[N],de[N],G[N][N];int vi[N];int S,T,mincut;int sz;void Search(int f){   int i ,j , Max,tmp;   memset(vis,0,sizeof(vis));   memset(de,0,sizeof(de));   S = T = -1;   for(i = 1; i <= n;i++){      if(vi[i] != f) continue;      Max = -inf;      for(j = 1;j<=n;j++){        if(vi[j] == f && !combine[j] && !vis[j] && Max < de[j]){///找出w(A,x)最大的x            tmp = j , Max = de[j];        }      }      if(T == tmp) return ;      S = T;T = tmp;      mincut = Max,vis[tmp] = 1;      for(j = 1; j <= n;j++)        if(vi[j] == f && !combine[j] && !vis[j]) de[j] += G[tmp][j];///不断将找到的x加入A，同时更新每个点的连通度   }}int SW(int f){  int i , j;  memset(combine,0,sizeof(combine));  int ans = inf;  for(int i = 1; i < sz;i++){///合并n-1次    Search(f);    if(mincut < ans) ans = mincut;    combine[T] = 1;    for(j = 1;j <= n;j++){        if(vi[j] == f && !combine[j]){            G[S][j] += G[T][j];///合并S,T为S            G[j][S] += G[j][T];        }    }  }  return ans;}vector
      
       E[300];void dfs(int u,int f){    sz++;    vi[u] = f;    for(int i = 1;i <= n;i++){        if(!vi[i] && G[u][i]) dfs(i,f);    }}int main(){    while(scanf("%d%d",&n,&m)==2){        for(int i = 1;i <= n;i++) pa[i] = i;        for(int i = 0;i < m;i++){            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);        }        sort(e,e + m);        memset(G,0,sizeof(G));        int cnt = 0;        for(int i = 0;i < m;){            for(int j = i;j < m &&e[i].w == e[j].w;j++){                int fx = Find(e[j].u),fy = Find(e[j].v);                if(fx != fy) E[cnt].push_back(j);            }            cnt++;            int j = i;            for(;i < m && e[i].w == e[j].w;i++){                int fx = Find(e[i].u),fy = Find(e[i].v);                if(fx != fy) pa[fx] = fy;            }        }        int ans = m;        for(int i = 0;i < cnt;i++){            for(int j = 0;j < E[i].size();j++){                int x =  E[i][j];                int u = e[x].u,v = e[x].v;                G[u][v]++,G[v][u]++;            }            memset(vi,0,sizeof(vi));            int ix = 1;            for(int j = 1;j <= n;j++){                if(!vi[j]){                     sz = 0;                     dfs(j,ix);                     if(sz > 1){                        int tmp = SW(ix);                        assert(tmp > 0);                        ans = min(ans,tmp);                     }                     ix++;                }            }        }        for(int i = 0;i < cnt;i++) E[i].clear();        printf("%d\n",ans);    }    return 0;}
      
     
    

---

(高斯消元)

题意：\(给A，B两个序列Ai,Bi，在A中找一个子集Sa，B中找一个子集Sb，使得Sa的异或和Sb的异或和同时等于x\)

\(问有多少个这样的x, 1 <= n <= 50, 0 <= Ai,Bi <= 2^{60}\)

题解: 求解这类问题需要用到异或高斯消元，具体资料可以看

为了保证方案数不重复

所以要先求出A，B的极大线性无关组(线性基)，即集合的所有子集异或的种类数可以用一组线性基所表示，线性基的大小其实也就是矩阵的秩的大小。

再把两个线性基列矩阵方程再求一次矩阵的秩d，自由元个数为\(c = 维数 - 秩,2^{c}\)就是答案

如果是求选择的方案数，那么直接列矩阵方程高斯消元，自由元个数为\(c = 维数 - 秩,2^{c}\)就是答案

简单讲一下如何消元

假设 n行 m列 （n个数，每个数62位)

对于第i个数 第j位，任意找一行第j位为1 与第i行 交换

然后 把所有第j位为1的行(除了自身) 都消掉这一位

处理得到的row个A[i]就是最后的线性基

#include
    
         #define LL long long        using namespace std;        LL A[100],B[100],C[200];        int guass(int z,LL A[]){        int row = 0;        int i , j;        for(i = 62;i >= 0;i--){            for(j = row;j < z;j++)                if(A[j] & (1LL<
     
      < z;j++)                 if(j != row && (A[j] & (1LL<
      
       < n;i++) scanf("%I64d",A + i);            for(int i = 0;i < n;i++) scanf("%I64d",B + i);            int a = guass(n,A);            int b = guass(n,B);            for(int i = 0;i < a;i++) C[i] = A[i];            for(int i = a;i < a + b;i++) C[i] = B[i - a];            int c = guass(a + b, C);            cout<<(1LL<<(a + b - c))<
      
     
    

---

(模拟签到题)

---

(想法题)

题意：给n个数，每次操作选择一个L,一个R，表示区间左右端点，该操作产生的贡献为[L+1,R]的和的绝对值-C。

0<=L<R<=n; 如果选过L,R这两个位置，那么以后选择的L,R都不可以再选择这两个位置。最多操作m次，求可以获得的最大贡献和。

思路：脑洞。原公式可以转化为|sum[r]-sum[l]|-c，sum[i]表示前i项的前缀和。

由于绝对值的影响，所以对前缀和排序，然后l从左边开始递增枚举，r从右边开始递减枚举，每次组成一对(sum[l],sum[r])作为贡献计算。

#include
    
     using namespace std;typedef long long LL;const int maxn = 1e5+100;int a[maxn], sum[maxn];int main(){    int n, m, c;    while(scanf("%d%d%d",&n,&m,&c)!=EOF)    {        //cout<<"yes"<
    

---

(模拟)

题意：在1-m中可重复的选三个数与a序列求lcs，分别求长度为0,1,2,3的lcs有多少个

思路：首先将a离散化，考虑将要枚举的子序列分成两部分，在a的数字集合里，不在此集合里

那么我们可以O(n^3)枚举在此集合里的数，计算与a的lcs，另一部分补上即可，这样计算可以保证不重复

用传统的求lcs，复杂度会变成O(n^4)

所以这里预处理next(i,c)表示i位置后c字符第一次出现的位置，来快速判断枚举的子序列与A的lcs长度

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define LL long long#define P pair
           
            using namespace std;const int MAXN = 1e6 + 10;const int N = 220;int n , m;int a[N],b[N];int vis[MAXN];int nxt[N][N];LL ans[4];void init(){ memset(nxt,-1,sizeof(nxt)); for(int i = 0;i < n;i++){ for(int j = i + 1;j <= n;j++){ int c = vis[a[j]]; if(nxt[i][c] == -1) nxt[i][c] = j; } }}void Add(int len,int k){ if(k == 0) {///子序列长度为0 补三个在集合外的数 ans[len] += 1LL * m * m * m; return ; } if(k == 1){///补两个 ans[len] += 1LL * m * m; return ; }if(k == 2){///补几个 ans[len] += m; return ; } ans[len]++;}void cal(int x,int y,int z){ int k = 0; int c[4]; if(x) c[k++] = x; if(y) c[k++] = y; if(z) c[k++] = z; int s = 0,len1 = 0,len2 = 0; if(k >= 1 && nxt[s][c[0]] != -1){ len1++; s = nxt[s][c[0]]; if(k >= 2&& nxt[s][c[1]] != -1){ len1++; s = nxt[s][c[1]]; if(k >= 3 && nxt[s][c[2]] != -1){ len1++; } }else if(k >= 3 && nxt[s][c[2]] != -1) len1++; } s = 0; if(k >= 2 && nxt[s][c[1]] != -1){ len2++; s = nxt[s][c[1]]; if(k >= 3&& nxt[s][c[2]] != -1) len2++; }else if(k >= 3 && nxt[s][c[2]] != -1) len2++; Add(max(len1,len2),k);}int main(){ while(scanf("%d%d",&n,&m)==2){ memset(vis,0,sizeof(vis)); int cnt = 0,mm = m; for(int i = 1;i <= n;i++){ scanf("%d",a + i); if(a[i] <= mm && !vis[a[i]]){ m--; vis[a[i]] = ++cnt; } } init(); memset(ans,0,sizeof(ans)); for(int i = 0;i <= cnt;i++) for(int j = 0;j <= cnt;j++) for(int k = 0;k <= cnt;k++){ cal(i,j,k); } printf("%lld %lld %lld %lld\n",ans[0],ans[1],ans[2],ans[3]); } return 0;}
           
          
         
        
       
      
     
    

---

(转化+贪心)

题意：给定n组括号，每组括号信息包括类型（要么是'('要么是')'）、数量和花费（将其翻转的权值），问让括号匹配的最小花费。

思路：

括号序列要求第k个前面至少要有 (k+1)/2 个左括号。 那么先把所有括号翻成右括号，之后重新翻回左括号（本题关键是想到这点）。

那么从左到右贪心，用一个堆维护现在左括号的数量和翻转的花费。

每次取翻转花费最小的左括号将其翻转为右括号，直到满足前k个里面有 (k+1)/2 个左括号。模拟即可。

注意这里是一组括号一组括号处理，而不是一个一个括号处理

#include
    
     #define LL long long#define P pair
     
      using namespace std;const int N = 1e5 + 10;int n;priority_queue
      
       
,greater
       
 > q;int main(){    while(scanf("%d", &n)==1)    {        while(!q.empty()) q.pop();        int cnt,cost;        char c[2];        int now = 0;        LL ans = 0;        for(int i = 0; i < n; i++)        {            scanf("%d%s%d",&cnt,c,&cost);            if(c[0] == '(')            {                ans += 1LL * cnt * cost;                cost = - cost;            }            q.push(make_pair(cost,cnt));            int res = (now + cnt + 1) / 2 - (now + 1) / 2;            while(!q.empty())            {                if(!res) break;                P cur = q.top();                q.pop();                int leave = min(cur.second,res);                ans += 1LL * leave * cur.first;                res -= leave;                if(leave < cur.second) q.push(make_pair(cur.first,cur.second - leave));            }            now += cnt;        }        printf("%lld\n",ans);    }    return 0;}
      
     
    

---

(树的直径)

题意：给一棵带边权的树，现在要求新建一棵树，新树里(u,v)的边权等于原树中(u,v)的唯一路径的距离

现在要你找出最大的花费来建造这颗新树

思路：很显然找出原树的直径两端点S,T，每个点要么和S连边，要么和T连边。

假设存在不是S，T的点v使得dis[u][v] > dis[S][u] && dis[u][v] > dis[T][u]

设u到v路径与直径的交点为x,

则有dis[S][x] + dis[x][u] < dis[u][x] + dis[x][v] -> dis[S][x] < dis[x][v]

所以dis[S][x] + dis[x][T] < dis[x][v] + dis[x][T] -> dis[S][T] < dis[v][T] 与S->T是直径矛盾

所以上述假设是不成立的

找树的直径的算法(bfs或者树形dp)

任意找一个点开始bfs找出最远的点，这是直径的一个端点，再做一次bfs，就可以求得另一个端点

#include
    
     #define LL long longusing namespace std;const int N = 1e5 + 10;LL disa[N],disb[N],dis[N];int n , vis[N];vector
     
      
        > G[N];int S,T;void bfs(int s,int &x){    x = s;    queue
       
         q;    q.push(s);    memset(vis,0,sizeof(vis));    dis[s] = 0;    while(!q.empty()){        int u = q.front();        q.pop();        vis[u] = 1;        if(dis[u] > dis[x]) x = u;        for(int i = 0;i < G[u].size();i++){            int v = G[u][i].first,w = G[u][i].second;            if(vis[v]) continue;            dis[v] = dis[u] + w;            q.push(v);        }    }}void dfs1(int u,LL d){    disa[u] = d;    vis[u] = 1;    for(int i = 0;i < G[u].size();i++){        int v = G[u][i].first,w = G[u][i].second;        if(vis[v]) continue;        dfs1(v,d + w);    }}void dfs2(int u,LL d){    disb[u] = d;    vis[u] = 1;    for(int i = 0;i < G[u].size();i++){        int v = G[u][i].first,w = G[u][i].second;        if(vis[v]) continue;        dfs2(v,d + w);    }}int main(){    while(scanf("%d",&n)==1){        for(int i =1 ;i <= n;i++) G[i].clear();        for(int i =1 ;i < n;i++){            int u ,v  , w;            scanf("%d%d%d",&u,&v,&w);            G[u].push_back(make_pair(v,w));            G[v].push_back(make_pair(u,w));        }        bfs(1,S);        bfs(S,T);        memset(vis,0,sizeof(vis));        dfs1(S,0);        memset(vis,0,sizeof(vis));        dfs2(T,0);        LL ans = 0;        for(int i = 1;i <= n;i++)  ans += max(disa[i],disb[i]);        ans -= disa[T];        cout<
        
         <
        
       
      
     
    

---

(数学)

题意：如题目所述。

**思路：

f(1/2+a) ,a可以为任意实数，所以实际上等价于f(a)； a为任意实数;

i/n - j/m = (mi-nj)/(nm); 分子看上去像是一个ax+by=c这样的式子，也就是x，y有解（i,j都为整数），那么c一定是gcd(a,b)的倍数。

所以mi-nj = kgcd(n,m)； k为整数。原式转化为求 min |kd/(nm) + a| 中的最大值。令Xk=kd/(nm)

那么相邻两个结果之间的距离为Xk+1-Xk=d/(nm)， 问题转化为a这个位置到最近的Xk(k为整数)的距离要最大，求这个最大距离，a应该为Xk+1,Xk（k为整数）的中间位置，这样a到最近的Xk（k为整数）距离最大为d/(2n*m)。**

#include
    
     using namespace std;typedef long long LL;typedef pair
     
       P;const int maxn = 1e5+100;LL gcd(LL a,LL b){    return b==0?a:gcd(b,a%b);}int main(){    LL n, m;    while(scanf("%I64d%I64d",&n,&m)==2)    {        printf("1/%I64d\n",n/gcd(n,m)*m*2);    }    return 0;}
     
    

---

(dp+树状数组优化)

题意：For given sequence \(A=(a_1,a_2,…,a_n)\), a sequence \(S=(s_1,s_2,…,s_n)\) has shape \(A\) if and only if:

\(s_i\)=min{

\(s_i,s_i+1,…,sn\)} for all \(a_i=0\);

\(s_i\)=max{

\(s_i,s_i+1,…,s_n\)} for all \(a_i=1\).

Given sequence \(B=(b_1,b_2,…,b_m)\), Bobo would like to know the number of subsequences of length n which have shape A modulo \((10^{9}+7).\)

就是在B中求有多少长度为n的子序列满足上述条件

题解：

\(定义dp[i][j][k]从后往前，a匹配到i，b匹配到j，最大/最小值为k的方案数\)

\(若a_i = 1，则k取i到n中的最小值，否则取最大值\)

则对于1<= i < n 有转移方程如下

\[dp[i][j][x] = \sum dp[i+1][k][y] \left\{\begin{matrix} b[j]<y<=x且b[k]=x &若a_i=0且a_{i+1}=1 \\ b[j]<b[k]<=x且y=x& 若a_i=0且a_{i+1}=0\\ x<=b[k]<b[j]且y=x& 若a_i=1且a_{i+1}=1 \\ x<=y<b[j]且b[k]=x& 若a_i=1且a_{i+1}=0 \end{matrix}\right.\]

暴力枚举\(O(nm^3)\),树状数组优化一维\(O(nm^2logm)\)

开了两个树状数组维护[i][x][]和[i][][x]这两种

#include
    
     #define LL long longusing namespace std;const int mod = 1e9 + 7;const int N = 550;int a[22],b[N],ix[N];int n , m;int s[2][22][N][N];void add(int &x,int y){    x += y;    if(x >= mod) x -= mod;}int lowbit(int x){    return x &(-x);}void up(int o,int i,int j,int pos,int val){    while(pos <= m){        add(s[o][i][j][pos] , val);        pos += lowbit(pos);    }}int getsum(int o,int i,int j,int pos){    int ans = 0;    while(pos){        add(ans,s[o][i][j][pos]);        pos -= lowbit(pos);    }    return ans;}int main(){    while(scanf("%d%d",&n,&m)==2){        for(int i = 1;i <= n;i++) scanf("%d",a + i);        for(int i = 1;i <= m;i++) scanf("%d",b + i),ix[b[i]] = i;        memset(s, 0, sizeof(s));        int res;        for(int j = m;j >= 1;j--){            for(int i = n;i >= 1;i--){                if(i == n){                    up(0,i,b[j],b[j],1);                    up(1,i,b[j],b[j],1);                }                else if(a[i]){                    if(a[i+1]){                        for(int x = 1;x < b[j];x++){                            res = getsum(1,i+1,x,b[j]-1) - getsum(1,i+1,x,x-1);                            if(res<0) res+=mod;                            up(0,i,b[j],x,res);                            up(1,i,x,b[j],res);                        }                    }else{                       for(int k = j + 1;k <= m;k++){                        if(b[k] < b[j]) res = getsum(0,i+1,b[k],b[j]-1) - getsum(0,i+1,b[k],b[k]-1);                        if(res < 0) res += mod;                        up(0,i,b[j],b[k],res);                        up(1,i,b[k],b[j],res);                       }                    }                }else{                    if(a[i+1]){                         for(int k = j + 1;k <= m;k++){                            if(b[k] > b[j]) res = getsum(0,i+1,b[k],b[k]) - getsum(0,i+1,b[k],b[j]);                            if(res < 0) res += mod;                            up(0,i,b[j],b[k],res);                            up(1,i,b[k],b[j],res);                       }                    }else{                        for(int x = b[j]+1;x <= m;x++){                            res = getsum(1,i+1,x,x) - getsum(1,i+1,x,b[j]);                            if(res<0) res+=mod;                            up(0,i,b[j],x,res);                            up(1,i,x,b[j],res);                        }                    }                }            }        }        int ans = 0;        for(int i = 1;i <= m;i++){            if(a[1])  add(ans,getsum(0,1,b[i],b[i]));            else add(ans,(mod+getsum(0,1,b[i],m) - getsum(0,1,b[i],b[i]-1))%mod);        }        printf("%d\n",ans);    }    return 0;}