A------------------------------------------------------------------------------------
题目链接:http://202.197.224.59/OnlineJudge2/index.php/problem/read/id/1260
题解:随机 n 个数把矩阵补全成 n × n 的。那么就是要算伴随矩阵的第一行,也就是逆矩阵的第一列,高斯消元即可。
源码:(Q神写的高斯消元,先贴一下诶,待补)
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 }
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 <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 }
E-------------------------------------------------------------------------------
题目链接:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1264
题解:
我的理解是:
题意:选取一段区间求和取绝对值,加在初始化为0的数值上,选了的区间不能再选,问最大的和是多少
解法:前缀和排序,最大和最小相减加起来就好了
源码:
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 }
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<bits/stdc++.h> 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<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 F
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 中较远的一个即可。
我的理解:
题意:要把所有的边都联通,并要求权值之和最大
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 }
I----------------------------------------------------------------------------------
题目链接:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1268
题解:
陷阱:此题好像用lld不会过,要用int64,我也不知道啥情况QAQ
源码:
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 }
J-----------------------------------------------------------------------------------
题目链接:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1269
题解:
源码:(来自某位学长)
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 }