A------------------------------------------------------------------------------------

题目链接：http://202.197.224.59/OnlineJudge2/index.php/problem/read/id/1260

题解：随机 n 个数把矩阵补全成 n × n 的。那么就是要算伴随矩阵的第一行，也就是逆矩阵的第一列，高斯消元即可。

源码：(Q神写的高斯消元，先贴一下诶，待补)

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 const int MAXN=205;10 const int Mod=1000000007;11 int a[MAXN][MAXN],b[MAXN][MAXN];12 int get_rand(int x)//[0,x)13 {14 int t=1;15 while((1<
            
             
              =x)18 {19 res=0;20 for(int i=0;i
              
               >=1;33 }34 return res;35 }36 void solve(int n)37 {38 for(int i=1;i<=n;i++)39 for(int j=1;j<=n;j++)40 b[i][j]=(i==j);41 int det=1;42 for(int i=1;i<=n;i++)43 {44 int t=i;45 for(int k=i;k<=n;k++)46 if(a[k][i])t=k;47 if(t!=i)det*=-1;48 for(int j=1;j<=n;j++)49 {50 swap(a[i][j],a[t][j]);51 swap(b[i][j],b[t][j]);52 }53 det=1LL*a[i][i]*det%Mod;54 int inv=fp(a[i][i],Mod-2);55 for(int j=1;j<=n;j++)56 {57 a[i][j]=1LL*inv*a[i][j]%Mod;58 b[i][j]=1LL*inv*b[i][j]%Mod;59 }60 for(int k=1;k<=n;k++)61 {62 if(k==i)continue;63 int tmp=a[k][i];64 for(int j=1;j<=n;j++)65 {66 a[k][j]=(a[k][j]-1LL*a[i][j]*tmp%Mod+Mod)%Mod;67 b[k][j]=(b[k][j]-1LL*b[i][j]*tmp%Mod+Mod)%Mod;68 }69 }70 }71 det=(det+Mod)%Mod;72 for(int i=1;i<=n;i++)73 for(int j=1;j<=n;j++)74 b[i][j]=1LL*det*b[i][j]%Mod;75 }76 int main()77 {78 srand(time(NULL));79 int n;80 while(scanf("%d",&n)!=EOF)81 {82 for(int j=1;j<=n;j++)83 a[1][j]=2;84 for(int i=2;i<=n;i++)85 for(int j=1;j<=n;j++)86 scanf("%d",&a[i][j]);87 solve(n);88 for(int i=1;i<=n;i++)89 printf("%d%c",(i&1 ? b[i][1] : (Mod-b[i][1])%Mod)," \n"[i==n]);90 }91 return 0;92 }
              
             
            
           
          
         
        
       
      
     

B------------------------------------------------------------------------------------------

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1261

题解：考虑 Kruskal 的过程，肯定是同样权值的边连通了一个点集。如果要让 MST 变大，就是要让某个权值的边不再连通。这是全局最小割问题，可以网络流也可以用 Stoer–Wagner 算法。

C------------------------------------------------------------------------------------------

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1262

题解：

D------------------------------------------------------------------------------------------

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1263

题解：将n*m的照片放大a*b倍，然后直接输出，此题只要模拟即可

源码：

1 #include 
     
       2 using namespace std; 3 int main() 4 { 5     int n,m,a,b; 6     while(cin>>n>>m>>a>>b) 7     { 8         string s[300]; 9         for(int i=0;i
      
       >s[i];12         }13         for(int i=0;i
      
     

E-------------------------------------------------------------------------------

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1264

题解：

我的理解是：

题意：选取一段区间求和取绝对值，加在初始化为0的数值上，选了的区间不能再选，问最大的和是多少

解法：前缀和排序，最大和最小相减加起来就好了

源码：

1 #include
     
       2 #define  INF 1000000000 3 #define ll long long 4 using namespace std; 5 ll x[123456]; 6 ll sum; 7 int main() 8 { 9      std::ios::sync_with_stdio(false);10     ll n,m,a,b;11     while(cin>>n>>m>>a)12     {13         sum=0;14         ll ans[123456];15         ans[0]=0;16         for(int i=1;i<=n;i++)17         {18             ll num;19             cin>>num;20             ans[i]=ans[i-1]+num;21         }22         ll cnt=0;23         ll Max=0;24         Max=max(Max,sum);25         sort(ans,ans+1+n);26         while(m--)27         {28             ll Pmax=ans[n--];29             ll Pmin=ans[cnt++];30            // cout<
      
       <<" "<
       
        <
       
      
     

 

F-------------------------------------------------------------------------------

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1265

题解：首先对 a 离散化，之后可以 O(n^3 ) 枚举序列 X.如果之后用 O(n) 的 LCS dp 会使复杂度变成 O(n^4 ).

std 用的方法是 2^3 枚举 X 的一个子序列，通过预处理一个next(i,c) 表示 i 位置后 c 字符第一次出现的位置，来 O(1) 判断是否是 A 的子序列。

某位学长的理解：

将a数组离散化，枚举三元素，n^3

求LCS，花费n*3，现在总体复杂度是n^4的

求LCS这步可以 优化，我们预处理吃nex[i][c]，当前i位置后面第一个c在哪里

就可以在2^3下O(1)求出LCS了

有个坑的地方就是 a[i]可能会大于m，wa了很久

源码:(来自某位学长)

1 #include
     
        2 using namespace std;  3 #pragma comment(linker, "/STACK:102400000,102400000")  4 #define ls i<<1  5 #define rs ls | 1  6 #define mid ((ll+rr)>>1)  7 #define pii pair
      
         8 #define MP make_pair  9 typedef long long LL; 10 const long long INF = 1e18+1LL; 11 const double Pi = acos(-1.0); 12 const int N = 2e2+10, M = 1e3+20, mod = 1e9+7,inf = 2e9; 13  14  15 LL n,m,a[N],c,b[N],nex[N][N]; 16 LL v[N]; 17 LL f[N]; 18 LL query(LL x) { 19     return lower_bound(b+1,b+c+1,x) - b; 20 } 21 int main() { 22     while(scanf("%lld%lld",&n,&m)!=EOF) { 23         for(int i = 1; i <= n; ++i) 24             scanf("%lld",&a[i]),b[i] = a[i]; 25         sort(b+1,b+n+1); 26         c = unique(b+1,b+n+1) - b - 1; 27         for(int i = c; i >= 1; --i) { 28             if(b[i] > m) c--; 29             else break; 30         } 31         for(int i = 0; i <= 5; ++i) f[i] = 0; 32         for(int i = 1; i <= n; ++i) a[i] = query(a[i]); 33         memset(nex,0,sizeof(nex)); 34         memset(v,0,sizeof(v)); 35          36         for(int i = 0; i <= n; ++i) { 37             for(int j = 1; j <= c; ++j) { 38                 for(int k = i+1; k <= n; ++k) { 39                     if(a[k] == j) { 40                         nex[i][j] = k; 41                         break; 42                     } 43                 } 44             } 45         } 46          47         for(int i = 1; i <= c; ++i) v[i] = 1; 48          49         v[c+1] = m - c; 50          51         for(int i = 1; i <= c+1; ++i) { 52             for(int j = 1; j <= c+1; ++j) { 53                 for(int k = 1; k <= c+1; ++k) { 54  55                     int fi = 0, se = 0, th = 0; 56  57                     for(int C = 1; C < 8; ++C) { 58                         int now = 0; 59                         if(C&(4)) { 60                             if(!nex[now][i]) {
   continue;} 61                             else now = nex[now][i]; 62                         } 63                         if(C&(2)) { 64                             if(!nex[now][j]) {
   continue;} 65                             else now = nex[now][j]; 66                         } 67                         if(C&(1)) { 68                             if(!nex[now][k]) {
   continue;} 69                             else now = nex[now][k]; 70                         } 71  72                         if(C == 7) fi = 1; 73                         else if(C == 6 || C == 5 || C == 3) se = 1; 74                         else if(C)th = 1; 75                          76                     } 77  78                     if(fi){ 79                         f[3] += v[i]*v[j]*v[k]; 80                     } 81                     else if(se) { 82                         f[2] += v[i]*v[j]*v[k]; 83                     } 84                     else if(th) { 85                         f[1] += v[i]*v[j]*v[k]; 86                     } 87                     else { 88                         f[0] += v[i]*v[j]*v[k]; 89                     } 90                      91                      92                 } 93             } 94         } 95  96         for(int i = 0; i < 3; ++i) cout<
       
        <<" "; 97         cout<
        
         <
        
       
      
     

 

G-------------------------------------------------------------------------------

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1266

题解：括号序列就是要求前 (2k + 1) 个里面至少要有 k 个左括号。那么先把所有括号翻成右括号，之后重新翻回左括号。

那么从左到右贪心，用一个堆维护现在可以翻回左括号的位置。每次相当于加两个当前段的字符，取一个最小的。所以事件只有最小的被拿完了，或者当前段拿完了。模拟即可。

H--------------------------------------------------------------------------------

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1267

题解：按照 Prim 算法计算生成树。假设初始点 v 0 是某条直径的端点。那么距离 v 0 最远的 v 1 必然是直径的另一个端点。

又因为距离任意点最远的要么是 v 0 要么是 v 1 ，所以剩下的点只需要连往 v 0 和 v 1 中较远的一个即可。

我的理解：

题意：要把所有的边都联通，并要求权值之和最大

解法：因为是颗树，那就没必要讨论两点的最短路了（毕竟树是没有回路的），那么重点是落在了如何找到权值之和最大的方法

我们找到这颗树相距最远的两个点（树的直径）A，B 剩余的点取距离A或者B最远的那条，需要进行两次dfs，距离保存最大的

然后加起来就行，因为A到B我们多加了一次，再减去就是结果！

源码：

1 #include 
      
        2 using namespace std; 3 #define ll long long 4 const int inf=(1<<30); 5 const int maxn=100005; 6 ll pos; 7 ll n,ans,vis[maxn],in[maxn]; 8 vector
       
        
         >e[maxn]; 9 ll sum;10 void dfs(int v,ll cnt)11 {12     if(ans
        
       
      

 

I----------------------------------------------------------------------------------

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1268

题解：

陷阱：此题好像用lld不会过，要用int64，我也不知道啥情况QAQ

源码：

1 #include 
     
       2 using namespace std; 3 __int64 gcd(__int64 a,__int64 b) 4 { 5     return b==0?a:gcd(b,a%b); 6 } 7 int main() 8 { 9     __int64 n,m;10     while(scanf("%I64d%I64d",&n,&m)!=EOF)11     {12         printf("1/%I64d\n",n*m/gcd(n,m)*2);13     }14     return 0;15 }
     

 

J-----------------------------------------------------------------------------------

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1269

题解：

源码：(来自某位学长)

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include