2014 ACM/ICPC Asia Regional Shanghai Online 题解

负责出了一场网络赛，勉勉强强算是顺利过去了，虽然产生了很多意外~~

本场共有12道题，教练提供了3个题给我，学弟shumj出的1011的LCT。 然后本来这场是11个题的，开场前教练担心爆零的比较多，临时叫我加了一个水题，就是1012了。 搞完这场网络赛，估计被喷出翔了, 虽然有个别题我卡的比较紧，但是也算卡的合理的，其他题目的时限都是比较宽的了. 出题一般我都会弃掉恶心的模拟，代码量很大的题，这里的题目感觉代码量都比较小。。 但是我一般出题也出模板题, 就是来拼模板的，怕不怕！！ 比较抱歉的就是1001和1008的Rejudge. 出题最不应该rejudge了, 但是因为没有好的tester. 大部分题是我自己出，自己当的tester. 1001数据是没有问题的，是OJ数据上传出现问题，然后及时加上数据。 主要是1008，因为这题我暴力对拍过的，感觉数据是正确的，也没有仔细检查。 然后比赛过程中发现我的暴力对拍写错，标程也犯了一样的错误，然后修正后两个吻合了！ 然后就出现了1008的Rejudge！ 为两次Rejudge以及各种卡常数，表示深深的歉意！ 我就是这么弱！ 没办法。 这也算是退役前出的最后一场比赛吧！ 下面是简单题解。

1001： HDU5042 这一题其实主要就是因为GCD是分段的，所以分成一段一段去搞就可以了。 就是说，可能 [l,r1] ….[l,r2] 的gcd都是一样的。 因为如果 是 [l,r]之间的gcd的话， 随着r的增大，这个值是不增的，所以最多分成了log(10^5)段. 然后就可以胡搞了，当然也可以使用ST去求gcd,然后也可以搞出来。 这一题前面出现一片RE， 然后检查数据发现OJ没传上数据，然后进行了修正。

/* ***************

Author        :kuangbin

Created Time  :2014/9/5 15:28:45

File Name     :A.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int MAXN = 100010;

long long gcd(long long a,long long b){

	if(b == 0)return a;

	return gcd(b,a%b);

}

int F[MAXN];

int find(int x){

	if(F[x] == -1)return x;

	return F[x] = find(F[x]);

}

void bing(int x,int y){

	int t1 = find(x);

	int t2 = find(y);

	if(t1 != t2)F[t2] = t1;

}

int a[MAXN];

struct Node1{

	int r1,r2;

	int val;

	Node1(int _r1 = 0,int _r2 = 0,int _val = 0){

		r1 = _r1;

		r2 = _r2;

		val = _val;

	}

	bool operator <(const Node1 &b)const{

		if(r1 != b.r1)return r1 < b.r1;

		else r2 < b.r2;

	}

};

vector<Node1>vec1[MAXN];

struct Node2{

	int l,r1,r2;

	long long sum;

	Node2(int _l = 0,int _r1 = 0,int _r2 = 0){

		l = _l;

		r1 = _r1;

		r2 = _r2;

	}

	bool operator <(const Node2 &b)const{

		if(l != b.l)return l < b.l;

		else return r1 < b.r1;

	}

};

vector<Node2>vec2[MAXN];

int num1[MAXN];

int b[MAXN];

int main()

{

    //freopen("A.in","r",stdin);

    //freopen("A.out","w",stdout);

    int T;

	scanf("%d",&T);

	assert(T <= 10);

	int n,Q;

	int iCase = 0;

	while(T--){

		iCase++;

		printf("Case #%d:\n",iCase);

		scanf("%d%d",&n,&Q);

		assert(n >= 1 && n <= 100000 && Q >= 1 && Q <= 100000);

		int Max = 1;

		for(int i = 1;i <= n;i++){

			scanf("%d",&a[i]);

			assert(a[i] >= 1 && a[i] <= 100000);

			vec1[i].clear();

			Max = max(Max,a[i]);

		}

		for(int i = 1;i <= Max;i++)vec2[i].clear();

		F[n+1] = -1;

		for(int i = n;i >= 1;i--){

			F[i] = -1;

			int start = i;

			int pre = i;

			b[i] = a[i];

			for(int j = find(i+1);j <= n;j = find(j+1)){

				b[j] = gcd(a[i],b[j]);

				if(b[j] != b[pre]){

					vec1[i].push_back(Node1(start,pre,b[pre]));

					vec2[b[pre]].push_back(Node2(i,start,pre));

					start = pre+1;

				}

				else bing(j,pre);

				pre = j;

			}

			vec1[i].push_back(Node1(start,n,b[n]));

			vec2[b[n]].push_back(Node2(i,start,n));

			sort(vec1[i].begin(),vec1[i].end());

			/*

			printf("i  %d\n",i);

			int sz = vec1[i].size();

			for(int j = 0;j < sz;j++)

				printf("%d %d %d\n",vec1[i][j].r1,vec1[i][j].r2,vec1[i][j].val);

				*/

		}

		num1[0] = 0;

		for(int i = 1;i <= Max;i++){

			sort(vec2[i].begin(),vec2[i].end());

			int sz = vec2[i].size();

			if(sz)num1[i] = num1[i-1]+1;

			else num1[i] = num1[i-1];

			for(int j = 0;j < sz;j++){

				if(j == 0)vec2[i][j].sum = 0;

				else vec2[i][j].sum = vec2[i][j-1].sum;

				vec2[i][j].sum += vec2[i][j].r2-vec2[i][j].r1+1;

			}

			/*

			printf("i: %d\n",i);

			printf("num1:%d\n",num1[i]);

			for(int j = 0;j < sz;j++)

				printf("%d %d %d %I64d\n",vec2[i][j].l,vec2[i][j].r1,vec2[i][j].r2,vec2[i][j].sum);

				*/

		}

		char op[20];

		long long k1,k2;

		while(Q--){

			scanf("%s%I64d%I64d",op,&k1,&k2);

			if(op[0] == 'R'){

				assert(k1 >= 1 && k1 <= k2 && k2 <= n);

				int id ;

				int sz = vec1[k1].size();

				int l = 0, r = sz-1;

				while(l <= r){

					int mid = (l+r)/2;

					if(vec1[k1][mid].r1 <= k2 && k2 <= vec1[k1][mid].r2){

						id = mid;

						break;

					}

					else if(vec1[k1][mid].r2 < k2)l = mid+1;

					else r = mid-1;

				}

				int val = vec1[k1][id].val;

				int ans1 = num1[val];

				id = lower_bound(vec2[val].begin(),vec2[val].end(),Node2(k1,0,0)) - vec2[val].begin();

				long long ans2;

				if(id == 0)ans2 = k2 - vec2[val][id].r1 + 1;

				else ans2 = vec2[val][id-1].sum + k2 - vec2[val][id].r1 + 1;

				printf("%d %I64d\n",ans1,ans2);

			}

			else {

				assert(k1 >= 1 && k1 <= (long long)n(n+1)/2 && k2 >= 1 && k2 <= (long long)n(n+1)/2);

				int id1 = lower_bound(num1+1,num1+Max+1,k1) - num1;

				if(id1 > Max || num1[id1] != k1){

					printf("-1\n");

					continue;

				}

				int sz = vec2[id1].size();

				if(k2 > vec2[id1][sz-1].sum){

					printf("-1\n");

					continue;

				}

				int l = 0, r = sz-1;

				int id2 = 0;

				while(l <= r){

					int mid = (l+r)/2;

					long long ss = vec2[id1][mid].sum - (vec2[id1][mid].r2 - vec2[id1][mid].r1 + 1);

					if(k2 > ss){

						id2 = mid;

						l = mid+1;

					}

					else r = mid-1;

				}

				k2 -= vec2[id1][id2].sum - (vec2[id1][id2].r2 - vec2[id1][id2].r1 + 1);

				printf("%d %d\n",vec2[id1][id2].l,(int)(vec2[id1][id2].r1 + k2 - 1));

			}

		}

	}

    return 0;

}

1002题： [HDU5043](http://acm.hdu.edu.cn/showproblem.php?pid=5043) 这个题就是Lucas定理的简单应用啊~~ 数位DP可搞。 这题是5倍以后标程啊，我没卡常数~ 小问题答案其实是 C(M,k1) * C(M-k1,k2) * C(M-k1-k2,k3)*********** M = k1+k2+k3+.. 如果要模P不等于0，就是k1,k2,...kn的P进制的和不能有进位。 然后就是数位DP可搞。

/* ***************

Author        :kuangbin

Created Time  :2014/9/25 0:07:36

File Name     :1002.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int MOD = 1e8+9;

void Add(int &a,int b){

	a += b;

	if(a >= MOD)a -= MOD;

}

int vis[10][33][22][1<<10];

int dp[10][33][22][1<<10];

int TT;

int prime;

int n;

int bit[10][33];

int dfs(int id,int pos,int sum,int s){

	if(id == n){

		id = 0;

		pos--;

		sum = 0;

		if(pos == -1)return 1;

	}

	if(vis[id][pos][sum][s] == TT)return dp[id][pos][sum][s];

	int end = (s&(1<<id))?bit[id][pos]:prime-1;

	int ans = 0;

	for(int i = 0;i <= end;i++){

		if(sum + i >= prime)break;

		Add(ans,dfs(id+1,pos,sum+i,i == end? s : (s & (~(1<<id)))));

	}

	vis[id][pos][sum][s] = TT;

	return dp[id][pos][sum][s] = ans;

}

int x[10];

int solve(){

	memset(bit,0,sizeof(bit));

	int Max = 0;

	for(int i = 0;i < n;i++){

		int cnt = 0;

		do{

			bit[i][cnt++] = x[i]%prime;

			x[i] /= prime;

		}

		while(x[i]);

		Max = max(Max,cnt);

	}

	return dfs(0,Max-1,0,(1<<n)-1);

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

	TT = 0;

	memset(vis,0,sizeof(vis));

    int T;

	scanf("%d",&T);

	assert(T <= 50 && T >= 1);

	int iCase = 0;

	while(T--){

		iCase++;

		TT++;

		scanf("%d%d",&n,&prime);

		assert(n >= 1 && n <= 10);

		assert(prime == 2

				|| prime == 3

				|| prime == 5

				|| prime == 7

				|| prime == 11

				|| prime == 13

				|| prime == 17

				|| prime == 19);

		long long tot = 1;

		for(int i = 0;i < n;i++){

			scanf("%d",&x[i]);

			assert(x[i] >= 1 && x[i] <= 1000000000);

			tot = tot*(1+x[i])%MOD;

		}

		tot -= solve();

		tot = (tot%MOD+MOD)%MOD;

		printf("Case #%d: %d\n",iCase,(int)tot);

	}

    return 0;

}

1003： 很简单的题目, 因为我卡常数了，让大家的罚时大增~~ 原意是想卡掉LCT或者其他的什么nlogn, n longnlogn算法的，后来发现O(n+m)的比不上nlogn的算法。因为常数好大。 然后就变成了谁的姿势好，谁就可过。 至于出现有很多的PE，是我故意安排的。 我要求输出3行的，你们的程序n=1的时候输出2行，能不PE吗？   一种做法是Tarjan进行LCA,然后进行加减啊，然后扫一遍。 或者进行树链剖分转为线性，然后搞。 其余算法也可能可以卡过~ 但是本题要输入输出挂，标程也无耻地用了~~尽力吐槽吧

/* ***************

Author        :kuangbin

Created Time  :2014/9/9 15:33:50

File Name     :C.cpp

 ************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int MAXN = 100010;

struct Edge{

	int to,next;

	int index;

}edge[MAXN*2];

int head[MAXN],tot;

void init(){

	tot = 0;

	memset(head,-1,sizeof(head));

}

inline void addedge(int u,int v,int index){

	edge[tot].to = v;

	edge[tot].next = head[u];

	edge[tot].index = index;

	head[u] = tot++;

}

int F[MAXN];

inline int find(int x){

	if(F[x] == -1)return x;

	return F[x] = find(F[x]);

}

inline void bing(int x,int y){

	int t1 = find(x);

	int t2 = find(y);

	if(t1 != t2)F[t1] = t2;

}

long long PF[MAXN],EF[MAXN];

struct Node{

	int id;

	int v,val;

	int next;

	Node(int _id = 0,int _v = 0,int _val = 0){

		id = _id;

		v = _v;

		val = _val;

	}

}query[MAXN*2];

int h[MAXN];

int tt;

inline void init2(){

	tt = 0;

	memset(h,-1,sizeof(h));

}

inline void add_query(int u,int v,int id,int val){

	query[tt].id = id;

	query[tt].next = h[u];

	query[tt].v = v;

	query[tt].val = val;

	h[u] = tt++;

}

bool vis[MAXN];

int fa[MAXN];

bool ff[MAXN];

int sta[MAXN];

int cur[MAXN];

void dfs1(int u,int pre){

	memcpy(cur,head,sizeof(head));

	memset(ff,false,sizeof(ff));

	fa[1] = -1;

	int top = 0;

	sta[top++] = 1;

	while(top != 0){

		u = sta[top-1];

		if(!ff[u])ff[u] = true;

		bool flag = false;

		for(int i = cur[u];i != -1;i = edge[i].next){

			int v = edge[i].to;

			if(ff[v])continue;

			fa[v] = u;

			sta[top++] = v;

			flag = true;

			cur[u] = edge[i].next;

			break;

		}

		if(!flag){

			top--;

			for(int i = h[u];i != -1;i = query[i].next){

				int v = query[i].v;

				int type = query[i].id;

				int w = query[i].val;

				if(vis[v]){

					if(type == 1){

						PF[find(v)] -= w;

						if(fa[find(v)] != -1)PF[fa[find(v)]] -= w;

						PF[v] += w;

					}

					else {

						EF[find(v)] -= 2*w;

						EF[v] += w;

					}

				}

				else {

					if(type == 1)PF[v] += w;

					else EF[v] += w;

				}

			}

			if(fa[u] != -1)bing(u,fa[u]);

			vis[u] = true;

		}

	}

}

long long a[MAXN];

long long ans1[MAXN],ans2[MAXN];

int gg[MAXN];

void dfs2(int u,int pre){

	int l,r;

	gg[l = r = 1] = 1;

	for(;l <= r;l++)

		for(int i = head[gg[l]];i != -1;i = edge[i].next){

			int v = edge[i].to;

			if(v == fa[gg[l]])continue;

			gg[++r] = v;

		}

	for(l--;l;l--){

		u = gg[l];

		for(int i = head[u];i != -1;i = edge[i].next){

			int v = edge[i].to;

			if(v == fa[u])continue;

			EF[u] += EF[v];

			PF[u] += PF[v];

			ans2[edge[i].index] = EF[v];

		}

		ans1[u] = PF[u] + a[u];

	}

}

//适用于正负整数

template <class T>

inline bool scan_d(T &ret) {

	char c; int sgn;

	if(c=getchar(),c==EOF) return 0; //EOF

	while(c!='-'&&(c<'0'||c>'9')) c=getchar();

	sgn=(c=='-')?-1:1;

	ret=(c=='-')?0:(c-'0');

	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');

	ret*=sgn;

	return 1;

}

inline void out(long long x) {

	if(x>9) out(x/10);

	putchar(x%10+'0');

}

int main()

{

	//freopen("C.in","r",stdin);

	//freopen("C.out","w",stdout);

	//freopen("in.txt","r",stdin);

	//freopen("out1.txt","w",stdout);

	int n,m;

	int T;

	scanf("%d",&T);

	int iCase = 0;

	while(T--){

		iCase++;

		init();

		//scanf("%d%d",&n,&m);

		scan_d(n);

		scan_d(m);

		assert(n >= 1 && n <= 100000 && m >= 1 && m <= 100000);

		memset(a,0,sizeof(a));

		int u,v,w;

		for(int i = 1;i < n;i++){

			//scanf("%d%d",&u,&v);

			scan_d(u);

			scan_d(v);

			addedge(u,v,i);

			addedge(v,u,i);

		}

		char op[20];

		init2();

		while(m--){

			//scanf("%s%d%d%d",op,&u,&v,&w);

			scanf("%s",op);

			scan_d(u);

			scan_d(v);

			scan_d(w);

			assert(u >= 1 && u <= n);

			assert(v >= 1 && v <= n);

			assert(abs(w) <= 100000);

			if(op[3] == '1'){

				if(u == v)a[u] += w;

				else {

					//	vec[u].push_back(Node(1,v,w));

					//vec[v].push_back(Node(1,u,w));

					add_query(u,v,1,w);

					add_query(v,u,1,w);

				}

			}

			else {

				if(u == v)continue;

				else {

					//vec[u].push_back(Node(2,v,w));

					//vec[v].push_back(Node(2,u,w));

					add_query(u,v,2,w);

					add_query(v,u,2,w);

				}

			}

		}

		memset(PF,0,sizeof(PF));

		memset(EF,0,sizeof(EF));

		memset(F,-1,sizeof(F));

		memset(vis,false,sizeof(vis));

		dfs1(1,-1);

		//for(int i = 1;i <= n;i++)

		//printf("%I64d  %I64d\n",PF[i],EF[i]);

		//memset(ans1,0,sizeof(ans1));

		//memset(ans2,0,sizeof(ans2));

		dfs2(1,-1);

		printf("Case #%d:\n",iCase);

		for(int i = 1;i <= n;i++){

			//printf("%I64d",ans1[i]);

			out(ans1[i]);

			if(i < n)printf(" ");

			else printf("\n");

		}

		for(int i = 1;i < n;i++){

			//printf("%I64d",ans2[i]);

			out(ans2[i]);

			if(i < n-1)printf(" ");

		}

		printf("\n");

	}

	return 0;

}

树链剖分：

/* ***************

Author        :kuangbin

Created Time  :2014/9/24 14:12:20

File Name     :F:\题目_上海网络赛\2014上海网络赛题目\C\标程\C3.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 100010;

struct Edge{

	int to,next;

}edge[MAXN*2];

int head[MAXN],tot;

int top[MAXN];

int fa[MAXN];

int deep[MAXN];

int num[MAXN];

int p[MAXN];

int fp[MAXN];

int son[MAXN];

int pos;

void init(){

	tot = 0;

	memset(head,-1,sizeof(head));

	pos = 1;

	memset(son,-1,sizeof(son));

}

inline void addedge(int u,int v){

	edge[tot].to = v;

	edge[tot].next = head[u];

	head[u] = tot++;

}

inline void dfs1(int u,int pre,int d){

	deep[u] = d;

	fa[u] = pre;

	num[u] = 1;

	for(int i = head[u];i != -1;i = edge[i].next){

		int v = edge[i].to;

		if(v != pre){

			dfs1(v,u,d+1);

			num[u] += num[v];

			if(son[u] == -1 || num[v] > num[son[u]])

				son[u] = v;

		}

	}

}

inline void getpos(int u,int sp){

	top[u] = sp;

	p[u] = pos++;

	fp[p[u]] = u;

	if(son[u] == -1)return;

	getpos(son[u],sp);

	for(int i = head[u];i != -1;i = edge[i].next){

		int v = edge[i].to;

		if(v != son[u] && v != fa[u])

			getpos(v,v);

	}

}

long long w1[MAXN];

void add1(int u,int v,int w){

	int f1 = top[u],f2 = top[v];

	while(f1 != f2){

		if(deep[f1] < deep[f2]){

			swap(f1,f2);

			swap(u,v);

		}

		w1[p[f1]] += w;

		w1[p[u]+1] -= w;

		u = fa[f1];

		f1 = top[u];

	}

	if(deep[u] > deep[v])swap(u,v);

	w1[p[u]] += w;

	w1[p[v]+1] -= w;

}

long long w2[MAXN];

void add2(int u,int v,int w){

	int f1 = top[u], f2 = top[v];

	while(f1 != f2){

		if(deep[f1] < deep[f2]){

			swap(f1,f2);

			swap(u,v);

		}

		w2[p[f1]] += w;

		w2[p[u]+1] -= w;

		u = fa[f1];

		f1 = top[u];

	}

	if(u == v)return;

	if(deep[u] > deep[v])swap(u,v);

	w2[p[son[u]]] += w;

	w2[p[v]+1] -= w;

}

//适用于正负整数

template <class T>

inline bool scan_d(T &ret) {

   char c; int sgn;

   if(c=getchar(),c==EOF) return 0; //EOF

   while(c!='-'&&(c<'0'||c>'9')) c=getchar();

   sgn=(c=='-')?-1:1;

   ret=(c=='-')?0:(c-'0');

   while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');

   ret*=sgn;

   return 1;

}

inline void out(long long x) {

   if(x>9) out(x/10);

   putchar(x%10+'0');

}

pair<int,int>pp[MAXN];

int link[MAXN];

long long ans1[MAXN],ans2[MAXN];

int main()

{

	int __size__ = 256 << 20;

char * __p__ = (char *) malloc(__size__) + __size__;

__asm__("movl %0,%%esp\n"::"r"(__p__));

    //freopen("in.txt","r",stdin);

    //freopen("out2.txt","w",stdout);

    int n,m;

	int T;

	int iCase = 0;

	scanf("%d",&T);

	while(T--){

		iCase++;

		init();

		scan_d(n);

		scan_d(m);

		memset(w1,0,sizeof(w1));

		memset(w2,0,sizeof(w2));

		int u,v,w;

		for(int i = 1;i < n;i++){

			scan_d(u);

			scan_d(v);

			addedge(u,v);

			addedge(v,u);

			pp[i] = make_pair(u,v);

		}

		dfs1(1,0,0);

		getpos(1,1);

		for(int i = 1;i < n;i++){

			if(deep[pp[i].first] > deep[pp[i].second])

				swap(pp[i].first,pp[i].second);

			link[pp[i].second] = i;

		}

		char op[10];

		while(m--){

			scanf("%s",op);

			scan_d(u);

			scan_d(v);

			scan_d(w);

			if(op[3] == '1'){

				add1(u,v,w);

			}

			else add2(u,v,w);

		}

		for(int i = 1;i <= n;i++){

			w1[i] += w1[i-1];

			w2[i] += w2[i-1];

			ans1[fp[i]] = w1[i];

			ans2[link[fp[i]]] = w2[i];

		}

		printf("Case #%d:\n",iCase);

		for(int i = 1;i <= n;i++){

			//printf("%I64d",ans1[i]);

			out(ans1[i]);

			if(i < n)printf(" ");

			else printf("\n");

		}

		for(int i = 1;i < n;i++){

			//printf("%I64d",ans2[i]);

			out(ans2[i]);

			if(i < n-1)printf(" ");

		}

		printf("\n");

	}

    return 0;

}

1004 HDU5045 直接状压DP。 可能题意好多人没理解，但是该表述的都表述清楚了，英语太渣了。

/* ***************

Author        :kuangbin

Created Time  :2014/9/10 20:04:53

File Name     :D.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

double dp[1010][1<<10];

bool vis[1010][1<<10];

double p[10][1010];

int n,m;

double solve(int id,int s){

	if(s == (1<<n)-1)s = 0;

	if(vis[id][s])return dp[id][s];

	vis[id][s] = true;

	dp[id][s] = 0;

	if(id == m)return dp[id][s];

	for(int i = 0;i < n;i++){

		if(s&(1<<i))continue;

		dp[id][s] = max(dp[id][s],(1-p[i][id])*solve(id+1,s|(1<<i))+p[i][id]*(solve(id+1,s|(1<<i))+1));

	}

	return dp[id][s];

}

int main()

{

    //freopen("D.in","r",stdin);

    //freopen("D.out","w",stdout);

    int T;

	int iCase = 0;

	scanf("%d",&T);

	while(T--){

		iCase++;

		scanf("%d%d",&n,&m);

		for(int i = 0;i < n;i++)

			for(int j = 0;j < m;j++)

				scanf("%lf",&p[i][j]);

		memset(vis,false,sizeof(vis));

		printf("Case #%d: %.5lf\n",iCase,solve(0,0));

	}

    return 0;

}

1005： HDU5046 直接DLX模板题！！！ 有点裸！ 而且貌似好多人被卡了！！！模板不够优啊！ 这题3倍标程了，感觉也够了。

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int maxnode = 4000;

const int MaxM = 70;

const int MaxN = 70;

int K;

struct DLX

{

	int n,m,size;

	int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];

	int H[MaxN],S[MaxM];

	int ands,ans[MaxN];

	void init(int _n,int _m)

	{

		n = _n;

		m = _m;

		for(int i = 0;i <= m;i++)

		{

			S[i] = 0;

			U[i] = D[i] = i;

			L[i] = i-1;

			R[i] = i+1;

		}

		R[m] = 0; L[0] = m;

		size = m;

		for(int i = 1;i <= n;i++)

			H[i] = -1;

	}

	void Link(int r,int c)

	{

		++S[Col[++size]=c];

		Row[size] = r;

		D[size] = D[c];

		U[D[c]] = size;

		U[size] = c;

		D[c] = size;

		if(H[r] < 0)H[r] = L[size] = R[size] = size;

		else

		{

			R[size] = R[H[r]];

			L[R[H[r]]] = size;

			L[size] = H[r];

			R[H[r]] = size;

		}

	}

	void remove(int c)

	{

		for(int i = D[c];i != c;i = D[i])

			L[R[i]] = L[i], R[L[i]] = R[i];

	}

	void resume(int c)

	{

		for(int i = U[c];i != c;i = U[i])

			L[R[i]]=R[L[i]]=i;

	}

	bool v[maxnode];

	int f()

	{

		int ret = 0;

		for(int c = R[0];c != 0;c = R[c])v[c] = true;

		for(int c = R[0];c != 0;c = R[c])

			if(v[c])

			{

				ret++;

				v[c] = false;

				for(int i = D[c];i != c;i = D[i])

					for(int j = R[i];j != i;j = R[j])

						v[Col[j]] = false;

			}

		return ret;

    }
    bool Dance(int d)
    {
    	if(d + f() > K)return false;
    	if(R\[0\] == 0)return d <= K;
    	int c = R\[0\];
    	for(int i = R\[0\];i != 0;i = R\[i\])
    		if(S\[i\] < S\[c\])
    			c = i;
    	for(int i = D\[c\];i != c;i = D\[i\])
    	{
    		remove(i);
    		for(int j = R\[i\];j != i;j = R\[j\])remove(j);
    		if(Dance(d+1))return true;
    		for(int j = L\[i\];j != i;j = L\[j\])resume(j);
    		resume(i);
    	}
    	return false;
    }

};

DLX g;

struct Point

{

	int x,y;

	void input()

	{

		scanf("%d%d",&x,&y);

	}

}city[MaxM];

long long dis(Point a,Point b)

{

	return (long long)abs(a.x-b.x)+(long long)abs(a.y-b.y);

}

int main()

{

    //freopen("E.in","r",stdin);

    //freopen("E.out","w",stdout);

    int T;

	int n;

	scanf("%d",&T);

	int iCase = 0;

	while(T--)

	{

		iCase++;

		scanf("%d%d",&n,&K);

		assert(n >= 1 && n <= 60 && K >= 1 && K <= n);

		for(int i = 0;i < n;i++){

			city[i].input();

			assert(abs(city[i].x) <= 1000000000);

			assert(abs(city[i].y) <= 1000000000);

		}

		long long l = 0, r = 100000000000LL;

		long long ans = 0;

		while(l <= r)

		{

			long long mid = (l+r)/2;

			g.init(n,n);

			for(int i = 0;i < n;i++)

				for(int j = 0;j < n;j++)

					if(dis(city[i],city[j]) <= mid)

						g.Link(i+1,j+1);

			if(g.Dance(0)){r = mid-1;ans = mid;}

			else l = mid+1;

		}

		printf("Case #%d: %I64d\n",iCase,ans);

	}

    return 0;

}

1006： [HDU5047](http://acm.hdu.edu.cn/showproblem.php?pid=5047) 直接根据多少个交点，多少个边，然后就是推公式。 很简单，故意组数比较多，可能少数JAVA.         sorry.  

/* ***************

Author        :kuangbin

Created Time  :2014/9/11 13:19:51

File Name     :F.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

/*

 * 高精度，支持乘法和加法

 */

struct BigInt

{

	const static int mod = 10000;

	const static int DLEN = 4;

	int a[600],len;

	BigInt()

	{

		memset(a,0,sizeof(a));

		len = 1;

	}

	BigInt(long long v)

	{

		memset(a,0,sizeof(a));

		len = 0;

		do

		{

			a[len++] = v%mod;

			v /= mod;

		}while(v);

	}

	BigInt(const char s[])

	{

		memset(a,0,sizeof(a));

		int L = strlen(s);

		len = L/DLEN;

		if(L%DLEN)len++;

		int index = 0;

		for(int i = L-1;i >= 0;i -= DLEN)

		{

			int t = 0;

			int k = i - DLEN + 1;

			if(k < 0)k = 0;

			for(int j = k;j <= i;j++)

				t = t*10 + s[j] - '0';

			a[index++] = t;

		}

	}

	BigInt operator +(const BigInt &b)const

	{

		BigInt res;

		res.len = max(len,b.len);

		for(int i = 0;i <= res.len;i++)

			res.a[i] = 0;

		for(int i = 0;i < res.len;i++)

		{

			res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);

			res.a[i+1] += res.a[i]/mod;

			res.a[i] %= mod;

		}

		if(res.a[res.len] > 0)res.len++;

		return res;

	}

	BigInt operator *(const BigInt &b)const

	{

		BigInt res;

		for(int i = 0; i < len;i++)

		{

			int up = 0;

			for(int j = 0;j < b.len;j++)

			{

				int temp = a[i]*b.a[j] + res.a[i+j] + up;

				res.a[i+j] = temp%mod;

				up = temp/mod;

			}

			if(up != 0)

				res.a[i + b.len] = up;

		}

		res.len = len + b.len;

		while(res.a[res.len - 1] == 0 &&res.len > 1)res.len--;

		return res;

	}

	void output()

	{

		printf("%d",a[len-1]);

		for(int i = len-2;i >=0 ;i--)

			printf("%04d",a[i]);

		printf("\n");

	}

};

BigInt A,B;

int main()

{

    //freopen("F.in","r",stdin);

    //freopen("F.out","w",stdout);

    int iCase = 0;

	int T;

	scanf("%d",&T);

	assert(T >= 1 && T <= 100000);

	assert(T == 100000);

	long long n;

	while(T--){

		iCase++;

		scanf("%I64d",&n);

		assert(n >= 0 && n <= 1000000000000LL);

		if(n == 0){

			printf("Case #%d: 1\n",iCase);

			continue;

		}

		A = (BigInt(n)*BigInt(8*n-7))+1;

		printf("Case #%d: ",iCase);

		A.output();

	}

    return 0;

}

1007: [HDU5048](http://acm.hdu.edu.cn/showproblem.php?pid=5048) 比较水的几何了。 只要解方程去求线段和椭球的交点。

/* ***************

Author        :kuangbin

Created Time  :2014/9/15 17:56:58

File Name     :E:\2014ACM\题目_上海网络赛\color\标程\G.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const double eps = 1e-8;

inline double sqr(double x){return x*x;}

struct Point{

	double x,y,z;

	void input(){

		scanf("%lf%lf%lf",&x,&y,&z);

		assert(fabs(x) <= 10000);

		assert(fabs(y) <= 10000);

		assert(fabs(z) <= 10000);

	}

};

struct Line{

	Point s,e;

	void input(){

		s.input();

		e.input();

	}

	double len(){

		return sqrt((s.x-e.x)(s.x-e.x)+(s.y-e.y)(s.y-e.y)+(s.z-e.z)*(s.z-e.z));

	}

};

struct Ellipsoid{

	double x,y,z,a,b,c;

	char color[5];

	void input(){

		scanf("%lf%lf%lf%lf%lf%lf%s",&x,&y,&z,&a,&b,&c,color);

		assert(fabs(x) <= 10000);

		assert(fabs(y) <= 10000);

		assert(fabs(z) <= 10000);

		assert(a >= 1 && a <= 10000);

		assert(b >= 1 && b <= 10000);

		assert(c >= 1 && c <= 10000);

		assert(color[0] == 'R' || color[0] == 'G' || color[0] == 'B');

	}

	void output(){

		printf("%lf %lf %lf %lf %lf %lf %s\n",x,y,z,a,b,c,color);

	}

};

double calc(vector<Line>line,vector<Ellipsoid>el){

	//for(int i = 0; i < el.size();i++)

		//el[i].output();

	double ans = 0;

	int sz1 = line.size();

	for(int i = 0;i < sz1;i++){

		vector<pair<double,int> >vec;

		vec.push_back(make_pair(0.0,0));

		vec.push_back(make_pair(1.0,0));

		double len = line[i].len();

		if(fabs(len) < eps)continue;

		double x1 = line[i].s.x;

		double y1 = line[i].s.y;

		double z1 = line[i].s.z;

		double dx = line[i].e.x - line[i].s.x;

		double dy = line[i].e.y - line[i].s.y;

		double dz = line[i].e.z - line[i].s.z;

		//printf("%lf %lf %lf %lf %lf %lf\n",line[i].s.x,line[i].s.y,line[i].s.z,line[i].e.x,line[i].e.y,line[i].e.z);

		int sz = el.size();

		for(int j = 0;j < sz;j++){

			double a = sqr(dx)/sqr(el[j].a) + sqr(dy)/sqr(el[j].b) + sqr(dz)/sqr(el[j].c);

			double b = 2*dx*(x1-el[j].x)/sqr(el[j].a) + 

				2*dy*(y1-el[j].y)/sqr(el[j].b) + 2*dz*(z1-el[j].z)/sqr(el[j].c);

			double c = sqr(x1-el[j].x)/sqr(el[j].a) + sqr(y1-el[j].y)/sqr(el[j].b)

				\+ sqr(z1-el[j].z)/sqr(el[j].c) - 1;

			double delta = b*b - 4*a*c;

			//cout<<delta<<endl;

			if(delta < eps)continue;

			double k1 = (-b+sqrt(delta))/(2*a);

			double k2 = (-b-sqrt(delta))/(2*a);

			//printf("a  %.10lf  b %.10lf  c %.10lf \n",a,b,c);

			//printf("%.10lf  %.10lf\n",k1,k2);

			if(k1 > k2)swap(k1,k2);

			k1 = max(0.0,k1);

			k2 = min(1.0,k2);

			//printf("%.10lf  %.10lf\n",k1,k2);

			if(k1 >= k2)continue;

			vec.push_back(make_pair(k1,1));

			vec.push_back(make_pair(k2,-1));

		}

		int cnt = 0;

		sort(vec.begin(),vec.end());

		int sz2 = vec.size();

		double pre = 0;

		for(int j = 0;j < sz2;j++){

			if(cnt > 0)

				ans += (vec[j].first - pre)*len;

			pre = vec[j].first;

			cnt += vec[j].second;

		}

	}

	return ans;

}

Line line[110];

Ellipsoid el[110];

vector<Line>vec1;

vector<Ellipsoid>vec2;

int main()

{

    //freopen("G.in","r",stdin);

    //freopen("G.out","w",stdout);

	int T;

	scanf("%d",&T);

	assert(T >= 1 && T  <= 100);

	int iCase = 0;

	int n,m;

	while(T--){

		iCase++;

		scanf("%d%d",&n,&m);

		for(int i = 0;i < n;i++)line[i].input();

		for(int i = 0;i < m;i++){

			el[i].input();

		//	printf("i %d  %c\n",i,el[i].color[0]);

		}

		vec1.clear();

		for(int i = 0;i < n;i++)vec1.push_back(line[i]);

		double tot = 0;

		for(int i = 0;i < n;i++)tot += line[i].len();

		vec2.clear();

		for(int i = 0;i < m;i++)

			if(el[i].color[0] == 'R')

				vec2.push_back(el[i]);

		double R = calc(vec1,vec2);

		vec2.clear();

		for(int i = 0;i < m;i++)

			if(el[i].color[0] == 'G')

				vec2.push_back(el[i]);

		double G = calc(vec1,vec2);

		vec2.clear();

		for(int i = 0;i < m;i++)

			if(el[i].color[0] == 'B')

				vec2.push_back(el[i]);

		double B = calc(vec1,vec2);

		vec2.clear();

		for(int i = 0;i < m;i++)

			if(el[i].color[0] == 'R' || el[i].color[0] == 'G')

				vec2.push_back(el[i]);

		double RG = calc(vec1,vec2);

		vec2.clear();

		for(int i = 0;i < m;i++)

			if(el[i].color[0] == 'R' || el[i].color[0] == 'B')

				vec2.push_back(el[i]);

		double RB = calc(vec1,vec2);

		vec2.clear();

		for(int i = 0;i < m;i++)

			if(el[i].color[0] == 'G' || el[i].color[0] == 'B')

				vec2.push_back(el[i]);

		double GB = calc(vec1,vec2);

		vec2.clear();

		for(int i = 0;i < m;i++)

			if(el[i].color[0] == 'R' || el[i].color[0] == 'G' || el[i].color[0] == 'B')

				vec2.push_back(el[i]);

		double RGB = calc(vec1,vec2);

		//printf("tot  %.6lf  R  %lf  G %lf  B %lf RG %lf RB %lf GB %lf RGB %lf\n",tot,R,G,B,RG,RB,GB,RGB);

		double ans1 = RGB - GB;

		double ans2 = RGB - RB;

		double ans3 = RGB - RG;

		double ans4 = RGB - B - ans1 - ans2;

		double ans5 = RGB - G - ans1 - ans3;

		double ans6 = RGB - R - ans2 - ans3;

		double ans7 = R + G - RG - ans4;

		double aa = tot-RGB;

		if(fabs(aa) < eps)aa = 0;

		if(fabs(ans1) < eps)ans1 = 0;

		if(fabs(ans2) < eps)ans2 = 0;

		if(fabs(ans3) < eps)ans3 = 0;

		if(fabs(ans4) < eps)ans4 = 0;

		if(fabs(ans5) < eps)ans5 = 0;

		if(fabs(ans6) < eps)ans6 = 0;

		if(fabs(ans7) < eps)ans7 = 0;

		//printf("Case #%d:\n",iCase);

		printf("%.10lf\n",aa);

		printf("%.10lf\n",ans1);

		printf("%.10lf\n",ans2);

		printf("%.10lf\n",ans3);

		printf("%.10lf\n",ans4);

		printf("%.10lf\n",ans5);

		printf("%.10lf\n",ans6);

		printf("%.10lf\n",ans7);

	}

    return 0;

}

1008： [HDU5049](http://acm.hdu.edu.cn/showproblem.php?pid=5049) 就是一个简单的DP。 使用矩阵去优化。  故意把范围设的不大的，太大一想就是矩阵了。 注意特判一些情况。 还有答案为0，可能不是 Impossible. 故意造的数据。

/* ***************

Author        :kuangbin

Created Time  :2014/9/16 22:41:06

File Name     :E:\2014ACM\题目_上海网络赛\Guess\标程\H.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int MOD = 20140927;

struct Matrix{

	int mat[2][2];

	void init(){

		memset(mat,0,sizeof(mat));

	}

	Matrix operator *(const Matrix &b)const{

		Matrix ret;

		for(int i = 0;i < 2;i++)

			for(int j = 0;j < 2;j++){

				ret.mat[i][j] = 0;

				for(int k = 0;k < 2;k++){

					ret.mat[i][j] += (long long)mat[i][k]*b.mat[k][j]%MOD;

					if(ret.mat[i][j] >= MOD)

						ret.mat[i][j] -= MOD;

				}

			}

		return ret;

	}

	void output(){

		printf("%d %d\n%d %d\n",mat[0][0],mat[0][1],mat[1][0],mat[1][1]);

	}

};

Matrix pow_M(Matrix A,int n){

	Matrix ret;

	ret.mat[0][0] = ret.mat[1][1] = 1;

	ret.mat[0][1] = ret.mat[1][0] = 0;

	Matrix tmp = A;

	while(n){

		if(n&1)ret = ret*tmp;

		tmp = tmp*tmp;

		n >>= 1;

	}

	return ret;

}

Matrix A[11*11*11 + 100];

vector<int>vec;

Matrix B;

Matrix C;

struct Matrix2{

	int mat[2][2];

	void init(){

		memset(mat,0,sizeof(mat));

	}

	Matrix2 operator *(const Matrix2 &b)const{

		Matrix2 ret;

		for(int i = 0;i < 2;i++)

			for(int j = 0;j < 2;j++){

				ret.mat[i][j] = 0;

				for(int k = 0;k < 2;k++)

					if(mat[i][k] && b.mat[k][j])

						ret.mat[i][j] = 1;

			}

		return ret;

	}

};

Matrix2 pow_M(Matrix2 A,int n){

	Matrix2 ret;

	ret.mat[0][0] = ret.mat[1][1] = 1;

	ret.mat[0][1] = ret.mat[1][0] = 0;

	Matrix2 tmp = A;

	while(n){

		if(n&1)ret = ret*tmp;

		tmp = tmp*tmp;

		n >>= 1;

	}

	return ret;

}

Matrix2 A2[11*11*11 + 100];

Matrix2 B2;

Matrix2 C2;

void Add(int &a,int b){

	if(a || b)a = 1;

}

int main()

{

    //freopen("H.in","r",stdin);

    //freopen("H.out","w",stdout);

    for(int i = 0;i < 11*11*11;i++)A[i].init();

    for(int i = 0;i < 11*11*11;i++)A2[i].init();

	for(int x = 0;x < 11;x++)

		for(int y = 0;y < 11;y++)

			for(int z = 0; z < 11;z++){

				int id = x*11*11 + y*11 + z;

				for(int i = 0;i < 10;i++){

					if(x != 10 && x != i)continue;

					for(int j = 0;j < 10;j++){

						if(y != 10 && y != j)continue;

						for(int k = 0;k < 10;k++){

							if(z != 10 && z != k)continue;

							if(i + j == k)A[id].mat[0][0]++;

							if(i + j == 10 + k)A[id].mat[0][1]++;

							if(i + j + 1 == k)A[id].mat[1][0]++;

							if(i + j + 1 == 10 + k)A[id].mat[1][1]++;

							if(i + j == k)Add(A2[id].mat[0][0],1);

							if(i + j == 10 + k)Add(A2[id].mat[0][1],1);

							if(i + j + 1 == k)Add(A2[id].mat[1][0],1);

							if(i + j + 1 == 10 + k)Add(A2[id].mat[1][1],1);

						}

					}

				}

			}

	int T;

	int iCase = 0;

	int n1,m1,n2,m2,n3,m3;

	scanf("%d",&T);

	while(T--){

		iCase++;

		scanf("%d%d",&n1,&m1);

		assert(n1 >= 1 && n1 <= 10000000);

		assert(m1 >= 0 && m1 <= n1);

		map<int,int>mp1;

		map<int,int>mp2;

		map<int,int>mp3;

		bool flag = true;

		vec.clear();

		int id,x;

		while(m1--){

			scanf("%d%d",&id,&x);

			id = n1 - 1 - id;

			vec.push_back(id);

			if(mp1.find(id) != mp1.end()){

				if(mp1[id] != x)flag = false;

			}

			else mp1[id] = x;

		}

		scanf("%d%d",&n2,&m2);

		assert(n2 >= 1 && n2 <= 10000000);

		assert(m2 >= 0 && m2 <= n2);

		while(m2--){

			scanf("%d%d",&id,&x);

			id = n2 - 1 - id;

			vec.push_back(id);

			if(mp2.find(id) != mp2.end()){

				if(mp2[id] != x)flag = false;

			}

			else mp2[id] = x;

		}

		scanf("%d%d",&n3,&m3);

		assert(n3 >= 1 && n3 <= 10000000);

		assert(m3 >= 0 && m3 <= n3);

		while(m3--){

			scanf("%d%d",&id,&x);

			id = n3 - 1 - id;

			vec.push_back(id);

			if(mp3.find(id) != mp3.end()){

				if(mp3[id] != x)flag = false;

			}

			else mp3[id] = x;

		}

		if((!flag) || (n1 < max(n2,n3)) || (n1 > max(n2,n3)+1)){

			printf("Case #%d: IMPOSSIBLE\n",iCase);

			continue;

		}

		//vec.push_back(n1-1);

		vec.push_back(n2-1);

		vec.push_back(n3-1);

		sort(vec.begin(),vec.end());

		vec.erase(unique(vec.begin(),vec.end()),vec.end());

		int mn = max(n2,n3);

		B.init();

		B.mat[0][0] = B.mat[1][1] = 1;

		B2.init();

		B2.mat[0][0] = B2.mat[1][1] = 1;

		if(vec[0] > 0)B = B * pow_M(A[10*11*11+10*11+10],vec[0]);

		if(vec[0] > 0)B2 = B2 * pow_M(A2[10*11*11+10*11+10],vec[0]);

		int sz = vec.size();

		for(int i = 0;i < sz;i++){

			//printf("%d\n",vec[i]);

			//B.output();

			if(i > 0){

				B = B * pow_M(A[10*11*11+10*11+10],vec[i]-vec[i-1]-1);

			}

			int x,y,z;

			if(mp2.find(vec[i]) == mp2.end())x = 10;

			else x = mp2[vec[i]];

			if(vec[i] >= n2)x = 0;

			if(mp3.find(vec[i]) == mp3.end())y = 10;

			else y = mp3[vec[i]];

			if(vec[i] >= n3)y = 0;

			if(mp1.find(vec[i]) == mp1.end())z = 10;

			else z = mp1[vec[i]];

			if(vec[i] >= n1)z = 0;

			if(vec[i] != n2-1 && vec[i] != n3-1){

				B = B * A[x*11*11+y*11+z];

				B2 = B2 * A2[x*11*11+y*11+z];

			}

			else {

				C.init();

				C2.init();

				for(int p = 0;p < 10;p++)

					for(int q = 0;q < 10;q++)

						for(int r = 0;r < 10;r++){

							if(x != 10 && p != x)continue;

							if(y != 10 && q != y)continue;

							if(z != 10 && r != z)continue;

							if(n2 != 1 && vec[i] == n2-1 && p == 0)continue;

							if(n3 != 1 && vec[i] == n3-1 && q == 0)continue;

							if(vec[i] >= n2 && p != 0)continue;

							if(vec[i] >= n3 && q != 0)continue;

							if(p+q == r)C.mat[0][0]++;

							if(p+q == r+10)C.mat[0][1]++;

							if(p+q+1 == r)C.mat[1][0]++;

							if(p+q+1 == r + 10)C.mat[1][1]++;

    						if(p+q == r)Add(C2.mat\[0\]\[0\],1);
    						if(p+q == r+10)Add(C2.mat\[0\]\[1\],1);
    						if(p+q+1 == r)Add(C2.mat\[1\]\[0\],1);
    						if(p+q+1 == r + 10)Add(C2.mat\[1\]\[1\],1);
    					}
    			//C.output();
    			B = B*C;
    			B2 = B2*C2;
    		}
    	}
    	int ans = 0;
    	int ans2 = 0;
    	if(n1 == max(n2,n3)){
    		ans = B.mat\[0\]\[0\];
    		ans2 = B2.mat\[0\]\[0\];
    	}
    	else{
    		if(mp1.find(n1-1) != mp1.end() && mp1\[n1-1\] != 1){
    			printf("Case #%d: IMPOSSIBLE\\n",iCase);
    			continue;
    		}
    		ans = B.mat\[0\]\[1\];
    		ans2 = B2.mat\[0\]\[1\];
    	}
    	//printf("%d %d\\n",ans,ans2);
    	if(ans2 == 0)printf("Case #%d: IMPOSSIBLE\\n",iCase);
    	else printf("Case #%d: %d\\n",iCase,ans);
    }
    return 0;

}

1009： [HDU5050](http://acm.hdu.edu.cn/showproblem.php?pid=5050) 就是求两个大数的GCD。 JAVA可以随便搞！ 本题定位就是签到题。当然C++也可以搞。

/* ***************

Author        :kuangbin

Created Time  :2014/9/18 16:43:54

File Name     :F:\题目_上海网络赛\dividedland\标程\I.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

struct BigNum{

	int a[10100];

	int n;

	void input(char str[]){

		n = strlen(str);

		for(int i = 0;i < n;i++)

			a[i] = str[n-1-i]-'0';

	}

	bool operator <(const BigNum &b)const{

		if(n < b.n)return true;

		if(n > b.n)return false;

		for(int i = n-1;i >= 0;i--){

			if(a[i] < b.a[i])return true;

			if(a[i] > b.a[i])return false;

		}

		return true;

	}

	BigNum operator -(const BigNum &b)const{

		BigNum ret;

		ret.n = n;

		int mu = 0;

		for(int i = 0;i < n;i++){

			int tmp;

			if(i < b.n)tmp = a[i] - b.a[i] - mu;

			else tmp = a[i] - mu;

			if(tmp >= 0){

				mu = 0;

				ret.a[i] = tmp;

			}

			else {

				mu = 1;

				ret.a[i] = tmp+2;

			}

		}

		while(ret.n > 0 && ret.a[ret.n-1] == 0)ret.n--;

		return ret;

	}

	BigNum div2(){

		BigNum ret;

		ret.n = n-1;

		for(int i = 0;i < n-1;i++)

			ret.a[i] = a[i+1];

		return ret;

	}

	void output(){

		for(int i = n-1;i >= 0;i--)

			printf("%d",a[i]);

	}

};

void gcd(BigNum a,BigNum b){

	int c2 = 0;

	while(a.n && b.n){

		if(a.a[0]){

			if(b.a[0]){

				if(b < a)a = a-b;

				else b = b-a;

			}

			else b = b.div2();

		}

		else {

			if(b.a[0])a = a.div2();

			else{

				a = a.div2();

				b = b.div2();

				c2++;

			}

		}

	}

	if(a.n)a.output();

	else b.output();

	while(c2--){

		printf("0");

	}

	printf("\n");

}

char str[10010];

BigNum a,b,c;

int main()

{

    //freopen("I.in","r",stdin);

    //freopen("I.out","w",stdout);

    int T;

	scanf("%d",&T);

	int iCase = 0;

	while(T--){

		iCase++;

		scanf("%s",str);

		a.input(str);

		scanf("%s",str);

		b.input(str);

		printf("Case #%d: ",iCase);

		gcd(a,b);

	}

    return 0;

}

1010： [HDU5051](http://acm.hdu.edu.cn/showproblem.php?pid=5051) Benford's law http://baike.baidu.com/view/1405011.htm?from_id=11319476&type=syn&fromtitle=Benford%27s+law&fr=aladdin http://zh.wikipedia.org/wiki/%E6%9C%AC%E7%A6%8F%E7%89%B9%E5%AE%9A%E5%BE%8B 这个教练提供的题。 特判一些情况就可以AC了。

/* ***************

Author        :kuangbin

Created Time  :2014/9/18 20:01:40

File Name     :F:\题目_上海网络赛\fraction\标程\J.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

int main()

{

    //freopen("J.in","r",stdin);

    //freopen("J.out","w",stdout);

    int T;

	int iCase = 0;

	scanf("%d",&T);

	int n,b,q;

	while(T--){

		iCase++;

		scanf("%d%d%d",&n,&b,&q);

		printf("Case #%d: ",iCase);

		if(q == 1){

			bool flag = false;

			while(b){

				if(n == b){

					flag = true;

					break;

				}

				b /= 10;

			}

			if(flag)printf("1.00000\n");

			else printf("0.00000\n");

		}

		else if(q == 10 || q == 100 || q == 1000){

			b *= 100000;

			bool flag = false;

			while(b){

				if(n == b){

					flag = true;

					break;

				}

				b /= 10;

			}

			if(flag)printf("1.00000\n");

			else printf("0.00000\n");

		}

		else {

			double ans = (log(n+1)-log(n))/log(10);

			printf("%.5lf\n",ans);

		}

	}

    return 0;

}

1011： [HDU5052](http://acm.hdu.edu.cn/showproblem.php?pid=5052) shumj出的LCT题。 直接LCT搞就可以了。 LCT的姿势不够优美可能被卡。

/* ***************

Author        :kuangbin

Created Time  :2014/9/18 21:59:15

File Name     :K.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#include <assert.h>

using namespace std;

const int MAXN = 50010;

const int INF = 0x3f3f3f3f;

struct Node *null;

struct Node{

	Node *fa,*ch[2];

	int val;

	int Max,Min;

	int mm;

	int rmm;

	int rev,add;

	inline void clear(int _val){

		fa = ch[0] = ch[1] = null;

		val = Max = Min = _val;

		mm = 0;

		rmm = 0;

		rev = 0;

		add = 0;

	}

	inline void push_up(){

		if(this == null)return;

		mm = 0;

		mm = max(mm,ch[0]->mm);

		mm = max(mm,ch[1]->mm);

		mm = max(mm,max(val,ch[1]->Max)-ch[0]->Min);

		mm = max(mm,ch[1]->Max-min(ch[0]->Min,val));

		rmm = 0;

		rmm = max(rmm,ch[0]->rmm);

		rmm = max(rmm,ch[1]->rmm);

		rmm = max(rmm,max(val,ch[0]->Max)-ch[1]->Min);

		rmm = max(rmm,ch[0]->Max-min(ch[1]->Min,val));

		Max = max(val,max(ch[0]->Max,ch[1]->Max));

		Min = min(val,min(ch[0]->Min,ch[1]->Min));

	}

	inline void setc(Node *p,int d){

		ch[d] = p;

		p->fa = this;

	}

	inline bool d(){

		return fa->ch[1] == this;

	}

	inline bool isroot(){

		return fa == null || fa->ch[0] != this && fa->ch[1] != this;

	}

	inline void flip(){

		if(this == null)return;

		swap(ch[0],ch[1]);

		swap(mm,rmm);

		rev ^= 1;

	}

	inline void update_add(int w){

		if(this == null)return;

		val += w;

		Min += w;

		Max += w;

		add += w;

	}

	inline void push_down(){

		if(this == null)return;

		if(rev){

			ch[0]->flip(); ch[1]->flip(); rev = 0;

		}

		if(add){

			ch[0]->update_add(add);ch[1]->update_add(add);

			add = 0;

		}

	}

	inline void go(){

		if(!isroot())fa->go();

		push_down();

	}

	inline void rot(){

		Node *f = fa, *ff = fa->fa;

		int c = d(), cc = fa->d();

		f->setc(ch[!c],c);

		this->setc(f,!c);

		if(ff->ch[cc] == f)ff->setc(this,cc);

		else this->fa = ff;

		f->push_up();

	}

	inline Node* splay(){

		go();

		while(!isroot()){

			if(!fa->isroot())

				d()==fa->d() ? fa->rot() : rot();

			rot();

		}

		push_up();

		return this;

	}

	inline Node* access(){

		for(Node *p = this, *q = null; p != null; q = p, p = p->fa){

			p->splay()->setc(q,1);

			p->push_up();

		}

		return splay();

	}

	inline void make_root(){

		access()->flip();

	}

};

Node pool[MAXN],*tail;

Node *node[MAXN];

struct Edge{

	int to,next;

}edge[MAXN*2];

int head[MAXN],tot;

void init(){

	tot = 0;

	memset(head,-1,sizeof(head));

}

inline void addedge(int u,int v){

	edge[tot].to = v;

	edge[tot].next = head[u];

	head[u] = tot++;

}

int g[MAXN];

int fa[MAXN];

void bfs(int s){

	int l,r;

	g[l=r=1] = s;

	fa[s] = s;

	while(l <= r){

		int u = g[l++];

		for(int i = head[u];i != -1;i = edge[i].next){

			int v = edge[i].to;

			if(v == fa[u])continue;

			fa[v] = u;

			node[v]->fa = node[u];

			g[++r] = v;

		}

	}

}

int main()

{

    //freopen("big1.in","r",stdin);

    //freopen("out1.txt","w",stdout);

    int T;

	int n,m;

	scanf("%d",&T);

	assert(T > 0 && T <= 10);

	while(T--){

		scanf("%d",&n);

		//assert(n > 0 && n <= 50000);

		tail = pool;

		null = tail++;

		null->fa = null->ch[0] = null->ch[1] = null;

		null->Max = -INF;

		null->Min = INF;

		null->mm = 0;

		null->add = null->rev = 0;

		int w;

		for(int i = 1;i <= n;i++){

			scanf("%d",&w);

			//assert(w > 0 && w <= 10000);

			node[i] = tail++;

			node[i]->clear(w);

		}

		init();

		int u,v;

		for(int i = 1;i < n;i++){

			scanf("%d%d",&u,&v);

			addedge(u,v);

			addedge(v,u);

		}

		bfs(1);

		scanf("%d",&m);

		while(m--){

			scanf("%d%d%d",&u,&v,&w);

			//assert(u >= 1 && u <= n && v >= 1 && v <= n);

			//assert(w > 0 && w <= 10000);

			node[u]->make_root();

			node[v]->access();

			printf("%d\n",node[v]->mm);

			node[v]->update_add(w);

		}

	}

    return 0;

}

1012： [HDU5053](http://acm.hdu.edu.cn/showproblem.php?pid=5053) 签到题！

/* ***************

Author        :kuangbin

Created Time  :2014/9/27 10:51:53

File Name     :E:\2014ACM\题目_上海网络赛\cube\标程\L.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

int main()

{

    //freopen("L.in","r",stdin);

    //freopen("L.out","w",stdout);

    int T;

	int iCase = 0;

	scanf("%d",&T);

	long long a,b;

	while(T--){

		iCase++;

		scanf("%I64d%I64d",&a,&b);

		a--;

		long long ans = (b(b+1)/2)(b(b+1)/2) - (a(a+1)/2)(a(a+1)/2);

		printf("Case #%d: %I64d\n",iCase,ans);

	}

    return 0;

}

再次为两次Rejudge深表歉意！