比赛链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=41856#overview
A.多种解法。可以dfs倒序染色，如mathlover神的代码：
#include<stdio.h> #include<algorithm> using namespace std; struct node { int x1,y1,x2,y2; bool color; } a[5010]; int n,m; int ans; void dfs(int x1,int y1,int x2,int y2,bool color,int num) { if(num==m) { if(color) ans+=(y2-y1+1)*(x2-x1+1); return; } if(x1>a[num].x2||x2<a[num].x1||y2<a[num].y1||y1>a[num].y2) { dfs(x1,y1,x2,y2,color,num+1); return; } if(x1<a[num].x1) dfs(x1,y1,a[num].x1-1,y2,color,num+1); if(x2>a[num].x2) dfs(a[num].x2+1,y1,x2,y2,color,num+1); if(y1<a[num].y1) dfs(max(x1,a[num].x1),y1,min(x2,a[num].x2),a[num].y1-1,color,num+1); if(y2>a[num].y2) dfs(max(x1,a[num].x1),a[num].y2+1,min(x2,a[num].x2),y2,color,num+1); } int main() { char temp; while(~scanf("%d%d",&n,&m)) { for(int i=0; i<m; ++i) { scanf("%d %d %d %d %c",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&temp); a[i].color=(temp==‘b‘); if(a[i].x1>a[i].x2) swap(a[i].x1,a[i].x2); if(a[i].y1>a[i].y2) swap(a[i].y1,a[i].y2); } ans=0; for(int i=m-1; i>=0; --i) dfs(a[i].x1,a[i].y1,a[i].x2,a[i].y2,a[i].color,i+1); printf("%d\n",n*n-ans); } } //GL && HF
但是暴力貌似也可以过，上暴力代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 1007 int a[N][N]; int main() { int n,m,i,j,tag,cnt; int x1,x2,y1,y2; char ss[4]; while(scanf("%d%d",&n,&m)!=EOF) { memset(a,0,sizeof(a)); cnt = 0; while(m--) { scanf("%d%d%d%d%s",&x1,&y1,&x2,&y2,ss); int maxx = max(x1,x2); int maxy = max(y1,y2); int minx = min(x1,x2); int miny = min(y1,y2); if(ss[0] == ‘b‘) tag = 1; else tag = 0; for(i=minx;i<=maxx;i++) for(j=miny;j<=maxy;j++) a[i][j] = tag; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) cnt += 1-a[i][j]; } printf("%d\n",cnt); } return 0; }
B.数学方法（等我弄懂了再写一个容易懂的）
C.生成排列，自行询问或找题解
D.归并排序或者树状数组求逆序对数
这个应该是非常经典的经典题，用归并排序求逆序数。
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and
Conquer)的一个非常典型的应用。
算法描述
归并操作的工作原理如下：
归并排序代码：（By hlove）
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long #define maxn 65555 using namespace std; int num[maxn],temp[maxn],n; long long Merge(int low,int mid,int high) { int i=low,j=mid+1,cnt=low; long long count=0;; while(i<=mid&&j<=high){ if(num[i]>num[j]){temp[cnt++]=num[j++];count+=mid-i+1;} else temp[cnt++]=num[i++]; } while(i<=mid)temp[cnt++]=num[i++]; while(j<=high)temp[cnt++]=num[j++]; for(i=low;i<=high;i++)num[i]=temp[i]; return count; } long long mergesort(int low,int high) { long long cnt=0; if(high>low){ int mid = (high+low)/2; cnt+=mergesort(low,mid); cnt+=mergesort(mid+1,high); cnt+=Merge(low,mid,high); } return cnt; } int main() { while(scanf("%d",&n)==1){ for(int i=0;i<n;i++){ scanf("%d",&num[i]); } printf("%lld\n",mergesort(0,n-1)); } return 0; }
树状数组代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 66007 lll c[N],k[N]; int n; struct node { lll val; int ind; }a[N]; int cmp(node ka,node kb) { return ka.val < kb.val; } lll lowbit(lll x) { return x&(-x); } void modify(lll x) { while(x <= n) { c[x]++; x += lowbit(x); } } lll sum(lll x) { lll res = 0; while(x > 0) { res += c[x]; x -= lowbit(x); } return res; } int main() { lll x,cnt; int i; while(scanf("%d",&n)!=EOF) { memset(c,0,sizeof(c)); cnt = 0; for(i=1;i<=n;i++) { scanf("%I64d",&a[i].val); a[i].ind = i; } sort(a+1,a+n+1,cmp); lll pre = -1000000,now = 1; for(i=1;i<=n;i++) { if(a[i].val != pre) { pre = a[i].val; a[i].val = now++; } else a[i].val = now-1; } for(i=1;i<=n;i++) k[a[i].ind] = a[i].val; for(i=1;i<=n;i++) { modify(k[i]); cnt += i - sum(k[i]); } printf("%I64d\n",cnt); } return 0; }
关于树状数组求逆序对数： http://hi.baidu.com/sculiunian/item/2d0c9bd6340396f2785daa71
E.找循环节，一直计算Xi,由于m在1000内，所以到某个时刻总会出现前面已出现的的值，即形成循环节，用con记录Xi何时出现，初始化为-1,con[A] = 0; 计算到Xi时，如果con[Xi]已经出现，说明开始循环了。找出循环起点与循环长度，然后看k在那一段，根据循环找出x[k]..具体键代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 1007 int con[N]; lll x[N]; int main() { lll alpha,beta,gamma,m; int k,a; while(scanf("%d%I64d%I64d%I64d%I64d%d",&a,&alpha,&beta,&gamma,&m,&k)!=EOF) { x[0] = a; int i = 1; int qi,len; memset(con,-1,sizeof(con)); con[a%m] = 0; if(k == 0) { printf("%d\n",a); continue; } i = 1; while(1) { x[i] = (alpha*x[i-1]*x[i-1] + beta*x[i-1] + gamma)%m; if(con[x[i]] == -1) con[x[i]] = i; else { qi = con[x[i]]; len = i-qi; if(k >= qi) k = qi+(k-qi)%len; break; } i++; } printf("%I64d\n",x[k]); } return 0; }
F.搜索，自寻题解
G.DP优化
mathlover代码：
#include <stdio.h> #include<algorithm> #define M 105 #define N 10005 int n, m,dp[M][M],c[N]; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%d",&c[i]); for (int i=1;i<=n+1;++i) for (int j=1;j<m;++j) { int tmp =(i-j+M)%M; dp[i%M][j]=dp[tmp][m-j]+c[i]; if (j != 1) dp[i%M][j]=std::min(dp[i%M][j],dp[i%M][j-1]); } printf("%d\n",dp[(n+1)%M][m-1]); return 0; }
H.大水题。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 1007 int main() { int p,m,c,k,r,v; while(scanf("%d%d%d%d%d%d",&p,&m,&c,&k,&r,&v)!=EOF) { int res1 = p/k; int res2 = m/r; int res3 = c/v; printf("%d\n",min(res1,min(res2,res3))); } return 0; }
I.网络流，自寻题解：https://www.google.com.hk/#newwindow=1&q=SGU+185&safe=strict
J.题目有点难懂，重点是理解，题目说的合并链子不是直接连上，而是要从别的地方取一个珠子来作为中介来连接两条链子，这样，每次在长度最短的链子中取珠子，说不定就可以减少链子的条数，岂不是可以减少时间。。好，就这么干。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 1007 int a[105]; int main() { int n,i,x; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); int head = 0; int tail = n-1; int step = 0; while(head < tail) { a[head]--; //最短的链子上的珠子减1 if(a[head] <= 0) //这条链没了 head++; int tmp = a[tail] + a[tail-1] + 1; //合并两条链，加不加1都可以 a[--tail] = tmp; step++; } printf("%d\n",step); } return 0; }
Mango Weekly Training Round #6 解题报告,布布扣,bubuko.com
Mango Weekly Training Round #6 解题报告
原文：http://www.cnblogs.com/whatbeg/p/3590444.html
