A————————————————————————————

Title link: http://202.197.224.59/OnlineJudge2/index.php/problem/read/id/1260

A random n number completes the matrix to n by n. So the first row of the adjoint, the first column of the inverse, is gaussian elimination.

Source code :(Q god written gaussian elimination, first posted ah, to be filled)

1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cmath> 5 #include<ctime> 6 #include<iostream> 7 #include<algorithm> 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<<t)<x)t++; 16 int res=x; 17 while(res>=x) 18 { 19 res=0; 20 for(int i=0;i<t;i++) 21 res|=(rand()%2)<<i; 22 } 23 return res; 24 } 25 int fp(int a,int k) 26 { 27 int res=1; 28 while(k) 29 { 30 if(k&1)res=1LL*res*a%Mod; 31 a=1LL*a*a%Mod; 32 k>>=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 }Copy the code

B——————————————————————————————

Title link: http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1261

Solution: Considering the Kruskal process, there must be an edge of the same weight connected to a set of points. If you want to make MST bigger, you want to make some weight edge disconnected. This is a global least cut problem, either with network flow or with Stoer — Wagner algorithm.

C——————————————————————————————

Title link: http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1262

Answer key:

D——————————————————————————————

Title link: http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1263

Solution: Enlarge n*m photo a* B times, and output directly

Source:

1 #include <bits/stdc++.h> 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<n; i++) 10 { 11 cin>>s[i]; 12 } 13 for(int i=0; i<n*a; i++) 14 { 15 for(int j=0; j<m*b; j++) 16 { 17 cout<<s[i/a][j/b]; 18 } 19 cout<<endl; 20 } 21 } 22 return 0; 23}Copy the code

E——————————————————————————-

Title link: http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1264

Answer key:

My understanding is:

Take the absolute value of an interval and add it to the value initialized to 0

Solution: prefix and sort, maximum and minimum subtraction add up

Source:

1 #include<bits/stdc++.h> 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<<Pmax<<" "<<Pmin<<endl; 31 sum+=abs(Pmax-Pmin)-a; 32 if(abs(Pmax-Pmin)-a<0) break; 33 Max=max(Max,sum); 34 } 35 cout<<Max<<endl; 36 } 37 return 0; 38}Copy the code

 

F——————————————————————————-

Title link: http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1265

First discretize a, then O(n^3) enumerates the sequence X. Dp will change the complexity to O(n^4) if the LCS of O(n) is then used. STD uses 2^3 to enumerate a subsequence of X, preprocessing a next(I,c) to indicate the first occurrence of the C character after position I. Let’s say O(1) is A subsequence of A.

An upperclassman’s interpretation:

Discretize array A, enumerate three elements, n^3

It costs n times 3 to find the LCS, and now the total complexity is n to the fourth

The LCS step can be optimized. We preprocess nex[I][c]. Where is the first C after the current I position

So we can solve for the LCS at order 1 of 2 to the third

The hole is that a[I] may be greater than m, wa for a long time

Source code :(from an upperclassman)

1 #include<bits/stdc++.h> 2 using namespace std; 3 #pragma comment(linker, "/ STACK: 102400000102000 00") 4 # define ls I < < 5 # define rs ls | 1 6 # define mid (+ rr (ll) > > 1) 7 # define pii pair<int,int> 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<<f[i]<<" "; 97 cout<<f[3]<<endl; 98 99 } 100 return 0; 101 } 102 103 FCopy the code

 

G——————————————————————————-

Title link: http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1266

A sequence of parentheses requires at least k open parentheses in the first (2k + 1). So I’m going to close all the parentheses, and then I’m going to go back to the open parentheses. So greedy from left to right, with a heap maintenance you can now flip back to the open bracket. Each time is equivalent to adding two characters of the current paragraph, taking the smallest one. So only the smallest event is finished, or the current segment is finished. Simulation.

H——————————————————————————–

Title link: http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1267

The spanning tree is calculated according to Prim algorithm. Let’s say the starting point v 0 is the endpoint of some diameter. So v one, which is furthest away from v zero, must be the other end of the diameter. And since the farthest point from any point is either v 0 or v 1, the rest of the points only have to go to the farther one of v 0 and v 1.

My understanding:

All the edges must be connected and the sum of the weights must be maximum

Solution: Since it is a tree, there is no need to discuss the shortest circuit of two points (after all, trees have no loops), so the focus is on how to find the method with the largest sum of weights

We find the two farthest points (diameter of the tree) A and B, and the remaining point is the one furthest from A or B, which requires two DFS, and the one with the largest distance is saved

And then we just add them up, because we added A to B, and subtract that is the result!

Source:

1 #include <bits/stdc++.h> 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<pair<int,int>>e[maxn]; 9 ll sum; 10 void dfs(int v,ll cnt) 11 { 12 if(ans<cnt) 13 { 14 ans=cnt; 15 pos=v; 16 } 17 if(vis[v])return; 18 vis[v]=1; 19 for(int i=0; i<e[v].size(); i++) 20 // cout<<e[v][i].first; 21 if(! vis[e[v][i].first]) 22 dfs(e[v][i].first,cnt+e[v][i].second); 23 } 24 ll dis1[123456],dis2[123456]; 25 void DFS(int v,ll cnt,ll dis[]) 26 { 27 if(vis[v]) return; 28 vis[v]=1; 29 dis[v]=cnt; 30 for(int i=0; i<e[v].size(); i++) 31 // cout<<e[v][i].first; 32 if(! vis[e[v][i].first]) 33 DFS(e[v][i].first,cnt+e[v][i].second,dis); 34 } 35 int main() 36 { 37 int n,m; 38 ans=0; 39 while(~scanf("%d",&n)) 40 { 41 ans=0; 42 memset (dis1, 0, sizeof (dis1)); 43 memset (dis2, 0, sizeof (dis2)); 44 memset(in,0,sizeof(in)); 45 memset(vis,0,sizeof(vis)); 46 for(int i=0; i<=n; i++) 47 { 48 e[i].clear(); 49 } 50 for(int i=1; i<n; i++) 51 { 52 ll u,v,w; 53 scanf("%d%d%d",&u,&v,&w); 54 e[u].push_back({v,w}); 55 e[v].push_back({u,w}); 56} 57 DFS (1, 0); 58 ll cnt=ans; 59 ans=0; 60 memset(vis,0,sizeof(vis)); 61 ans=0; 62 DFS(pos,0,dis1); 63 memset(vis,0,sizeof(vis)); 64 ans=0; 65 dfs(pos,0); 66 67 memset(vis,0,sizeof(vis)); 68 DFS(pos,0,dis2); 69 memset(vis,0,sizeof(vis)); 70 ll cot=ans; 71 //cout<<cot<<" "<<cnt<<endl; 72 ll Max=max(cnt,cot); 73 //cout<<Max<<endl; 74 sum=0; 75 for(int i=1; i<=n; i++) 76 { 77 sum+=max((ll)dis1[i],(ll)dis2[i]); 78 } 79 printf("%lld\n",sum-Max); 80 } 81 return 0; 82}Copy the code

 

I———————————————————————————-

Title link: http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1268

Answer key:

Trap: this topic seems to use LLD won’t pass, want to use INT64, I also don’t know what situation QAQ

Source:

1 #include <bits/stdc++.h> 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}Copy the code

 

J———————————————————————————–

Title link: http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1269

Answer key:

Source code :(from an upperclassman)

1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<vector> 6 #include<queue> 7 #include<map> 8 #include<set> 9 #include<algorithm> 10 using namespace std; 11 12 typedef long long ll; 13 typedef double db; 14 15 const int mod=1000000007; 16 17 int t,n,m; 18 int A[25],B[510]; 19 int dp[25][510][510]; 20 int a[25][510][510]; 21 22 int lowbit(int x) 23 { 24 return x&(-x); 25 } 26 27 void add(int id,int bd,int x,int v) 28 { 29 while(x) 30 { 31 a[id][bd][x]+=v; 32 if(a[id][bd][x]>=mod) a[id][bd][x]-=mod; 33 if(a[id][bd][x]<0) a[id][bd][x]+=mod; 34 x-=lowbit(x); 35 } 36 } 37 38 int sum(int id,int bd,int x) 39 { 40 int res=0; 41 while(x<=m) 42 { 43 res+=a[id][bd][x]; 44 if(res>=mod) res-=mod; 45 x+=lowbit(x); 46 } 47 return res; 48 } 49 50 int main() 51 { 52 #ifdef Haha 53 //freopen("in.in","r",stdin); 54 #endif // Haha 55 while(scanf("%d%d",&n,&m)! =EOF) 56 { 57 for(int i=1; i<=n; i++) scanf("%d",&A[i]); 58 for(int i=1; i<=m; i++) scanf("%d",&B[i]); 59 memset(dp,0,sizeof(dp)); 60 memset(a,0,sizeof(a)); 61 if(A[1]==0) add(1,m,m,1); 62 else add (1, 1, m, 1); 63 for(int i=1; i<=n; i++) 64 { 65 for(int j=1; j<=m; j++) 66 { 67 for(int k=1; k<=m; k++) 68 { 69 dp[i][j][k]=sum(i,k,B[j]); 70 //printf("%d %d %d %d\n",i,j,k,dp[i][j][k]); 71 } 72 if(i==1) continue; 73 for(int k=1; k<=m; k++) 74 { 75 if(dp[i-1][j][k]==0) continue; 76 int L,R; 77 if(A[i-1]==0) L=B[j],R=k; 78 else L=k,R=B[j]; 79 if(L>R) continue; 80 81 if(A[i]==0) 82 { 83 add(i,R,R,dp[i-1][j][k]); 84 add(i,R,L-1,-dp[i-1][j][k]); 85 } 86 else 87 { 88 add(i,L,R,dp[i-1][j][k]); 89 add(i,L,L-1,-dp[i-1][j][k]); 90 } 91 } 92 } 93 } 94 int ans=0; 95 for(int i=1; i<=m; i++) 96 { 97 for(int j=1; j<=m; j++) 98 { 99 ans+=dp[n][i][j]; 100 if(ans>=mod) ans-=mod; 101 } 102 } 103 printf("%d\n",ans); 104 } 105 return 0; 106}Copy the code