A------------------------------------------------------------------------------------
题目链接：http://202.197.224.59/OnlineJudge2/index.php/problem/read/id/1260
题解：随机 n 个数把矩阵补全成 n × n 的。那么就是要算伴随矩阵的第一行，也就是逆矩阵的第一列，高斯消元即可。
源码：(Q神写的高斯消元，先贴一下诶，待补)
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=;
const int Mod=;
int a[MAXN][MAXN],b[MAXN][MAXN];
int get_rand(int x)//[0,x)
{
int t=;
while((<<t)<x)t++;
int res=x;
while(res>=x)
{
res=;
for(int i=;i<t;i++)
res|=(rand()%)<<i;
}
return res;
}
int fp(int a,int k)
{
int res=;
while(k)
{
if(k&)res=1LL*res*a%Mod;
a=1LL*a*a%Mod;
k>>=;
}
return res;
}
void solve(int n)
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
b[i][j]=(i==j);
int det=;
for(int i=;i<=n;i++)
{
int t=i;
for(int k=i;k<=n;k++)
if(a[k][i])t=k;
if(t!=i)det*=-;
for(int j=;j<=n;j++)
{
swap(a[i][j],a[t][j]);
swap(b[i][j],b[t][j]);
}
det=1LL*a[i][i]*det%Mod;
int inv=fp(a[i][i],Mod-);
for(int j=;j<=n;j++)
{
a[i][j]=1LL*inv*a[i][j]%Mod;
b[i][j]=1LL*inv*b[i][j]%Mod;
}
for(int k=;k<=n;k++)
{
if(k==i)continue;
int tmp=a[k][i];
for(int j=;j<=n;j++)
{
a[k][j]=(a[k][j]-1LL*a[i][j]*tmp%Mod+Mod)%Mod;
b[k][j]=(b[k][j]-1LL*b[i][j]*tmp%Mod+Mod)%Mod;
}
}
}
det=(det+Mod)%Mod;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
b[i][j]=1LL*det*b[i][j]%Mod;
}
int main()
{
srand(time(NULL));
int n;
while(scanf("%d",&n)!=EOF)
{
for(int j=;j<=n;j++)
a[][j]=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&a[i][j]);
solve(n);
for(int i=;i<=n;i++)
printf("%d%c",(i& ? b[i][] : (Mod-b[i][])%Mod)," \n"[i==n]);
}
return ;
}
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倍，然后直接输出，此题只要模拟即可
源码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m,a,b;
while(cin>>n>>m>>a>>b)
{
string s[];
for(int i=;i<n;i++)
{
cin>>s[i];
}
for(int i=;i<n*a;i++)
{
for(int j=;j<m*b;j++)
{
cout<<s[i/a][j/b];
}
cout<<endl;
}
}
return ;
}
E-------------------------------------------------------------------------------
题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1264
题解：
我的理解是：
题意：选取一段区间求和取绝对值，加在初始化为0的数值上，选了的区间不能再选，问最大的和是多少
解法：前缀和排序，最大和最小相减加起来就好了
源码：
#include<bits/stdc++.h>
#define INF 1000000000
#define ll long long
using namespace std;
ll x[];
ll sum;
int main()
{
std::ios::sync_with_stdio(false);
ll n,m,a,b;
while(cin>>n>>m>>a)
{
sum=;
ll ans[];
ans[]=;
for(int i=;i<=n;i++)
{
ll num;
cin>>num;
ans[i]=ans[i-]+num;
}
ll cnt=;
ll Max=;
Max=max(Max,sum);
sort(ans,ans++n);
while(m--)
{
ll Pmax=ans[n--];
ll Pmin=ans[cnt++];
// cout<<Pmax<<" "<<Pmin<<endl;
sum+=abs(Pmax-Pmin)-a;
if(abs(Pmax-Pmin)-a<) break;
Max=max(Max,sum);
}
cout<<Max<<endl;
}
return ;
}
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了很久
源码:(来自某位学长)
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double Pi = acos(-1.0);
const int N = 2e2+, M = 1e3+, mod = 1e9+,inf = 2e9; LL n,m,a[N],c,b[N],nex[N][N];
LL v[N];
LL f[N];
LL query(LL x) {
return lower_bound(b+,b+c+,x) - b;
}
int main() {
while(scanf("%lld%lld",&n,&m)!=EOF) {
for(int i = ; i <= n; ++i)
scanf("%lld",&a[i]),b[i] = a[i];
sort(b+,b+n+);
c = unique(b+,b+n+) - b - ;
for(int i = c; i >= ; --i) {
if(b[i] > m) c--;
else break;
}
for(int i = ; i <= ; ++i) f[i] = ;
for(int i = ; i <= n; ++i) a[i] = query(a[i]);
memset(nex,,sizeof(nex));
memset(v,,sizeof(v)); for(int i = ; i <= n; ++i) {
for(int j = ; j <= c; ++j) {
for(int k = i+; k <= n; ++k) {
if(a[k] == j) {
nex[i][j] = k;
break;
}
}
}
} for(int i = ; i <= c; ++i) v[i] = ; v[c+] = m - c; for(int i = ; i <= c+; ++i) {
for(int j = ; j <= c+; ++j) {
for(int k = ; k <= c+; ++k) { int fi = , se = , th = ; for(int C = ; C < ; ++C) {
int now = ;
if(C&()) {
if(!nex[now][i]) {continue;}
else now = nex[now][i];
}
if(C&()) {
if(!nex[now][j]) {continue;}
else now = nex[now][j];
}
if(C&()) {
if(!nex[now][k]) {continue;}
else now = nex[now][k];
} if(C == ) fi = ;
else if(C == || C == || C == ) se = ;
else if(C)th = ; } if(fi){
f[] += v[i]*v[j]*v[k];
}
else if(se) {
f[] += v[i]*v[j]*v[k];
}
else if(th) {
f[] += v[i]*v[j]*v[k];
}
else {
f[] += v[i]*v[j]*v[k];
} }
}
} for(int i = ; i < ; ++i) cout<<f[i]<<" ";
cout<<f[]<<endl; }
return ;
} 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 中较远的一个即可。
我的理解：
题意：要把所有的边都联通，并要求权值之和最大
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int inf=(<<);
const int maxn=;
ll pos;
ll n,ans,vis[maxn],in[maxn];
vector<pair<int,int>>e[maxn];
ll sum;
void dfs(int v,ll cnt)
{
if(ans<cnt)
{
ans=cnt;
pos=v;
}
if(vis[v])return;
vis[v]=;
for(int i=; i<e[v].size(); i++)
// cout<<e[v][i].first;
if(!vis[e[v][i].first])
dfs(e[v][i].first,cnt+e[v][i].second);
}
ll dis1[],dis2[];
void DFS(int v,ll cnt,ll dis[])
{
if(vis[v]) return;
vis[v]=;
dis[v]=cnt;
for(int i=; i<e[v].size(); i++)
// cout<<e[v][i].first;
if(!vis[e[v][i].first])
DFS(e[v][i].first,cnt+e[v][i].second,dis);
}
int main()
{
int n,m;
ans=;
while(~scanf("%d",&n))
{
ans=;
memset(dis1,,sizeof(dis1));
memset(dis2,,sizeof(dis2));
memset(in,,sizeof(in));
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
{
e[i].clear();
}
for(int i=; i<n; i++)
{
ll u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[u].push_back({v,w});
e[v].push_back({u,w});
}
dfs(,);
ll cnt=ans;
ans=;
memset(vis,,sizeof(vis));
ans=;
DFS(pos,,dis1);
memset(vis,,sizeof(vis));
ans=;
dfs(pos,); memset(vis,,sizeof(vis));
DFS(pos,,dis2);
memset(vis,,sizeof(vis));
ll cot=ans;
//cout<<cot<<" "<<cnt<<endl;
ll Max=max(cnt,cot);
//cout<<Max<<endl;
sum=;
for(int i=;i<=n;i++)
{
sum+=max((ll)dis1[i],(ll)dis2[i]);
}
printf("%lld\n",sum-Max);
}
return ;
}
I----------------------------------------------------------------------------------
题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1268
题解：
陷阱：此题好像用lld不会过，要用int64，我也不知道啥情况QAQ
源码：
#include <bits/stdc++.h>
using namespace std;
__int64 gcd(__int64 a,__int64 b)
{
return b==?a:gcd(b,a%b);
}
int main()
{
__int64 n,m;
while(scanf("%I64d%I64d",&n,&m)!=EOF)
{
printf("1/%I64d\n",n*m/gcd(n,m)*);
}
return ;
}
J-----------------------------------------------------------------------------------
题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1269
题解：
源码：(来自某位学长)
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
using namespace std; typedef long long ll;
typedef double db; const int mod=; int t,n,m;
int A[],B[];
int dp[][][];
int a[][][]; int lowbit(int x)
{
return x&(-x);
} void add(int id,int bd,int x,int v)
{
while(x)
{
a[id][bd][x]+=v;
if(a[id][bd][x]>=mod) a[id][bd][x]-=mod;
if(a[id][bd][x]<) a[id][bd][x]+=mod;
x-=lowbit(x);
}
} int sum(int id,int bd,int x)
{
int res=;
while(x<=m)
{
res+=a[id][bd][x];
if(res>=mod) res-=mod;
x+=lowbit(x);
}
return res;
} int main()
{
#ifdef Haha
//freopen("in.in","r",stdin);
#endif // Haha
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=; i<=n; i++) scanf("%d",&A[i]);
for(int i=; i<=m; i++) scanf("%d",&B[i]);
memset(dp,,sizeof(dp));
memset(a,,sizeof(a));
if(A[]==) add(,m,m,);
else add(,,m,);
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
for(int k=; k<=m; k++)
{
dp[i][j][k]=sum(i,k,B[j]);
//printf("%d %d %d %d\n",i,j,k,dp[i][j][k]);
}
if(i==) continue;
for(int k=; k<=m; k++)
{
if(dp[i-][j][k]==) continue;
int L,R;
if(A[i-]==) L=B[j],R=k;
else L=k,R=B[j];
if(L>R) continue; if(A[i]==)
{
add(i,R,R,dp[i-][j][k]);
add(i,R,L-,-dp[i-][j][k]);
}
else
{
add(i,L,R,dp[i-][j][k]);
add(i,L,L-,-dp[i-][j][k]);
}
}
}
}
int ans=;
for(int i=; i<=m; i++)
{
for(int j=; j<=m; j++)
{
ans+=dp[n][i][j];
if(ans>=mod) ans-=mod;
}
}
printf("%d\n",ans);
}
return ;
}