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 中较远的一个即可。
我的理解:
题意:要把所有的边都联通,并要求权值之和最大
解法:因为是颗树,那就没必要讨论两点的最短路了(毕竟树是没有回路的),那么重点是落在了如何找到权值之和最大的方法
我们找到这颗树相距最远的两个点(树的直径)A,B 剩余的点取距离A或者B最远的那条,需要进行两次dfs,距离保存最大的
然后加起来就行,因为A到B我们多加了一次,再减去就是结果!
源码:
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 }