FOJ有奖月赛-2015年10月 题解

FOJ有奖月赛-2015年10月 比赛链接： here 注意此乃非官方题解，只是个人解法，如有不对，敬请指出。 A题： 题目链接：http://acm.fzu.edu.cn/problem.php?pid=2198 很水，一看就是写递推式，然后矩阵递推。 递推式为 t[n] = 6*t[n-1] - t[n-2]. 然后对t[n]从1~n求和。 所以需要3*3的矩阵。 然后快速敲完，非常遗憾，TLE了。。。。 怎么办？？？？？ 暴力打一些表，然后飘过~~~ 为何要卡矩阵乘法！！！！！！ 代码君：

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

Author        :kuangbin

Created Time  :2015/10/6 13:04:18

File Name     :F:\ACM\2015ACM\比赛练习\2015-10-6\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>

using namespace std;

const int MOD = 1e9+7;

struct Matrix {

	int mat[3][3];

	void  init() {

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

	}

	Matrix operator *(const Matrix &b)const {

		Matrix ret;

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

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

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

				for(int k = 0;k < 3;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;

	}

};

Matrix mm[70];

Matrix pow_M(Matrix a,long long n) {

	Matrix ret;

	ret.init();

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

	int cnt = 0;

	while(n) {

		if(n&1)ret = ret*mm[cnt];

		cnt++;

		n >>= 1;

	}

	return ret;

    /*
    Matrix tmp = a;
    while(n) {
    	if(n&1)ret = ret*tmp;
    	tmp = tmp*tmp;
    	n >>= 1;
    }
    */
    return ret;

}

int main()

{

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

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

	int T;

	long long n;

	scanf("%d",&T);

	Matrix b;

	b.init();

	b.mat[0][0] = 0;

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

	b.mat[0][1] = MOD-1;

	b.mat[1][1] = 6;

	b.mat[2][2] = 1;

	b.mat[0][2] = 0;

	b.mat[1][2] = 1;

	mm[0] = b;

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

		mm[i] = mm[i-1]*mm[i-1];

	while(T--) {

		Matrix a;

		scanf("%I64d",&n);

		a = pow_M(b,n);

		printf("%d\n",(int) ((a.mat[0][2] + 6LL*a.mat[1][2])%MOD));

	}

	return 0;

}

B题： 题目链接：http://acm.fzu.edu.cn/problem.php?pid=2199 本场比赛的压轴题，比赛期间无人AC，因为中间题目不清，改题意了，我是赛后改了下才AC的。 题目要求一口气吃完所以萝卜。 就是你从起点开始，可以先不吃萝卜，一旦碰到萝卜，就要一直吃完，然后走到洞口走人。 所以你首先枚举第一个吃到的是哪个萝卜！ 从起点进行一遍bfs, 就是知道从起点可以到哪个萝卜了，距离和种数都知道了。 假如吃萝卜的起点和终点都确定了，就是单路径问题。 非常裸的插头DP就可以解决。 插头DP参考：here 我是按照ZOJ3213代码进行修改的，而且简化了，因为起点和终点都确定了。 走的距离其实可以不用记录的，我一开始理解错 了，加了记录，后面发现没有必要。 代码君：

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

Author        :kuangbin

Created Time  :2015/10/6 14:26:33

File Name     :F:\ACM\2015ACM\比赛练习\2015-10-6\B.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 MAXD=18;

const int HASH=10007;

const int STATE=2000010;

const int MOD = 1e9+7;

void Add(int &a,int b) {

	a += b;

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

}

int N,M;

char maze[MAXD][MAXD];

int code[MAXD];

int ch[MAXD];

struct HASHMAP

{

	int head[HASH],next[STATE],size;

	int state[STATE],dp[STATE];

	int num[STATE];

	void init()

	{

		size=0;

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

	}

	void push(int st,int ans, int nn)

	{

		int i,h=st%HASH;

		for(i=head[h];i!=-1;i=next[i])

			if(state[i]==st)

			{

				if(num[i] > nn) {

					num[i] = nn;

					dp[i] = ans;

				} else if(num[i] == nn) {

					Add(dp[i],ans);

				}

				return;

			}

		state[size]=st;

		dp[size]=ans;

		num[size] = nn;

		next[size]=head[h];

		head[h]=size++;

	}

}hm[2];

void decode(int *code,int m,int st)

{

	for(int i=m;i>=0;i--)

	{

		code[i]=st&7;

		st>>=3;

	}

}

int encode(int *code,int m)

{

	int cnt=1;

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

	ch[0]=0;

	int st=0;

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

	{

		if(ch[code[i]]==-1)ch[code[i]]=cnt++;

		code[i]=ch[code[i]];

		st<<=3;

		st|=code[i];

	}

	return st;

}

void shift(int *code,int m)

{

	for(int i=m;i>0;i--)code[i]=code[i-1];

	code[0]=0;

}

//没有萝卜的

void dpblank(int i,int j,int cur)

{

	int k,left,up;

	for(k=0;k<hm[cur].size;k++)

	{

		decode(code,M,hm[cur].state[k]);

		left=code[j-1];

		up=code[j];

		if(left&&up)

		{

		}

		else if(left||up)

		{

		}

		else

		{

			code[j-1]=code[j]=0;

			hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].dp[k], hm[cur].num[k]);

		}

	}

}

//有萝卜的

void dpluobo(int i,int j,int cur)

{

	int k,left,up;

	for(k=0;k<hm[cur].size;k++)

	{

		decode(code,M,hm[cur].state[k]);

		left=code[j-1];

		up=code[j];

		if(left&&up)

		{

			if(left!=up)

			{

				code[j-1]=code[j]=0;

				for(int t=0;t<=M;t++)

					if(code[t]==up)

						code[t]=left;

				hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].dp[k], hm[cur].num[k]+1);

			}

		}

		else if(left||up)

		{

			int t;

			if(left)t=left;

			else t=up;

			if(maze[i][j+1])

			{

				code[j-1]=0;

				code[j]=t;

				hm[cur^1].push(encode(code,M),hm[cur].dp[k], hm[cur].num[k]+1);

			}

			if(maze[i+1][j])

			{

				code[j-1]=t;

				code[j]=0;

				hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].dp[k], hm[cur].num[k]+1);

			}

		}

		else

		{

			if(maze[i][j+1]&&maze[i+1][j])

			{

				code[j-1]=code[j]=15;

				hm[cur^1].push(encode(code,M),hm[cur].dp[k], hm[cur].num[k]+1);

			}

		}

	}

}

//起点和终点

void dpstart(int i,int j,int cur)

{

	int k,left,up;

	for(k=0;k<hm[cur].size;k++)

	{

		decode(code,M,hm[cur].state[k]);

		left=code[j-1];

		up=code[j];

		if(left&&up)

		{

		}

		else if(left||up)

		{

			code[j-1]=code[j]=0;

			hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].dp[k], hm[cur].num[k]+1);

		}

		else

		{

			if(maze[i][j+1])

			{

				code[j]=15;

				code[j-1]=0;

				hm[cur^1].push(encode(code,M),hm[cur].dp[k], hm[cur].num[k]+1);

			}

			if(maze[i+1][j])

			{

				code[j-1]=15;

				code[j]=0;

				hm[cur^1].push(encode(code,j==M?M-1:M),hm[cur].dp[k], hm[cur].num[k]+1);

			}

		}

	}

}

int dp1[20][20];

int dp2[20][20];

int sx,sy;

int ex,ey;

int Move[][2] = { {0,1},{0,-1},{1,0},{-1,0}};

void bfs() {

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

		for(int j = 1;j <= M;j++) {

			if(maze[i][j] == 'X') {

				sx = i;

				sy = j;

			}

			if(maze[i][j] == 'O') {

				ex = i;

				ey = j;

			}

		}

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

	memset(dp2,0,sizeof(dp2));

	queue<pair<int,int> >q;

	q.push(make_pair(sx,sy));

	dp1[sx][sy] = 0;

	dp2[sx][sy] = 1;

	while(!q.empty()) {

		pair<int,int>tmp = q.front();

		q.pop();

		int x = tmp.first;

		int y = tmp.second;

		if(maze[x][y] == '#' || maze[x][y] == 'O')continue;

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

			int nx = x+Move[i][0];

			int ny = y+Move[i][1];

			if(nx < 1 || nx > N)continue;

			if(ny < 1 || ny > M)continue;

			if(dp1[nx][ny] == -1) {

				dp1[nx][ny] = dp1[x][y]+1;

				dp2[nx][ny] = dp2[x][y];

				q.push(make_pair(nx,ny));

			} else if (dp1[nx][ny] == dp1[x][y]+1)

				Add(dp2[nx][ny],dp2[x][y]);

		}

	}

}

void init()

{

	scanf("%d%d",&N,&M);

	memset(maze,0,sizeof(maze));

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

		scanf("%s",maze[i]+1);

	}

	bfs();

}

pair<int,int> solve()

{

	int i,j,cur=0;

	hm[cur].init();

	hm[cur].push(0,1,0);

	for(i=1;i<=N;i++)

		for(int j=1;j<=M;j++)

		{

			hm[cur^1].init();

			if(maze[i][j] == '.')dpblank(i,j,cur);

			else if(maze[i][j] == '#')dpluobo(i,j,cur);

			else dpstart(i,j,cur);

			cur^=1;

		}

	int ans = 10000000;

	int ans2 = 0;

	for(i=0;i<hm[cur].size;i++) {

		int num = hm[cur].num[i];

		if(num < ans) {

			ans = num;

			ans2 = hm[cur].dp[i];

		} else if(num == ans) {

			ans2 += hm[cur].dp[i];

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

		}

	}

	if(ans > 10000)return make_pair(-1,-1);

	else return make_pair(ans-1,ans2);

}

void gao() {

	int cnt = 0;

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

		for(int j = 1;j <= M;j++)

			if(maze[i][j] == '#')cnt++;

	if(cnt == 0) {

		if(dp1[ex][ey] == -1)printf("-1\n");

		else printf("%d %d\n",dp1[ex][ey],dp2[ex][ey]);

		return;

	}

	pair<int,int>ans = make_pair(-1,-1);

	pair<int,int>tmp = solve();

	if(tmp.first != -1) {

		if(ans.first == -1 || ans.first > tmp.first) {

			ans = tmp;

		} else if(ans.first == tmp.first)

			Add(ans.second,tmp.second);

	}

	if(ans.first != -1) {

		if(ans.first == -1)printf("-1\n");

		else printf("%d %d\n",ans.first,ans.second);

		return;

	}

	maze[sx][sy] = '.';

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

		for(int j = 1;j <= M;j++)

			if(maze[i][j] == '#' && dp1[i][j] != -1) {

				maze[i][j] = 'X';

				pair<int,int>tmp = solve();

				if(tmp.first == -1) {

					maze[i][j] = '#';

					continue;

				}

				if(ans.first == -1 || ans.first > tmp.first + dp1[i][j]) {

					ans = make_pair(tmp.first+dp1[i][j],((long long)dp2[i][j]*tmp.second)%MOD);

				} else if(ans.first == tmp.first + dp1[i][j])

					Add(ans.second, (long long)dp2[i][j]*tmp.second%MOD);

				maze[i][j] = '#';

			}

	if(ans.first == -1)printf("-1\n");

	else printf("%d %d\n",ans.first,ans.second);

}

int main()

{

	int T;

	scanf("%d",&T);

	int iCase = 0;

	while(T--)

	{

		iCase++;

		init();

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

		gao();

	}

	return 0;

}

C题： 题目链接：http://acm.fzu.edu.cn/problem.php?pid=2200 题目讲得很清楚了，但是因为是个环！ 如果是线性的，比较好办，直接DP。 环的换，就枚举前两个点，这样就分割成了一个线性的，然后进行DP。 DP的时候，我记录了最前面的状态，以及结束的状态 。转移非常裸。 这题思路和G类似了。

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

Author        :kuangbin

Created Time  :2015/10/6 13:55:42

File Name     :F:\ACM\2015ACM\比赛练习\2015-10-6\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>

using namespace std;

const int MOD = 1e9+7;

int dp[2][2][1010][1010][2][2];

void Add(int &a,int b) {

	a += b;

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

}

int a[10];

int main()

{

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

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

	int T;

	scanf("%d",&T);

	int n,k;

	memset(dp,0,sizeof(dp));

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

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

			dp[i][j][0][0][i][j] = 1;

		}

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

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

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

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

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

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

							if(!dp[t1][t2][i][j][x][y])continue;

							Add(dp[t1][t2][i+1][j][y][0],dp[t1][t2][i][j][x][y]);

							if(x == 0)

								Add(dp[t1][t2][i+1][j+1][y][1],dp[t1][t2][i][j][x][y]);

						}

		}

	while(T--) {

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

		if(n <= 5) {

			int ans = 0;

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

				int cnt = 0;

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

					if(i & (1<<j)){a[j] = 1;cnt++;}

					else a[j] = 0;

				}

				if(cnt != k)continue;

				bool flag = true;

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

					if(a[j] && a[(j+2)%n])flag = false;

				if(flag)ans++;

			}

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

			continue;

		}

		int ans = 0;

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

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

				int tt = (i==1)+(j==1);

				if(k < tt)continue;

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

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

						if(x && i)continue;

						if(y && j)continue;

						Add(ans,dp[i][j][n-2][k-tt][x][y]);

					}

			}

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

	}

	return 0;

}

D题： 题目链接：http://acm.fzu.edu.cn/problem.php?pid=2201 非常显然要用数据结构！ 怎么维护呢？ 关键就是第一个操作了。 如何求 gcd(c-a,c-b) ? 可以发现是 gcd(c-a,c-b) = gcd(c-a,a-b). 如果有很多数呢？ 如何求 gcd(c-a[1], c-a[2], …. c-a[n]) ? 可以发现是这样的 gcd(c-a[1], a[1]-a[2], …. a[n-1]-a[n]) 发现就是差分和其中一个数了。 所以用线段树搞，记录第一个和最后一个就可以维护差分了， 然后GCD就出来了。 本题我int就不过了，没有上long long….. 数据范围比较小吧。 英神教我的，英神果然牛逼！。

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

Author        :kuangbin

Created Time  :2015/10/6 19:00:42

File Name     :F:\ACM\2015ACM\比赛练习\2015-10-6\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;

const int MAXN = 100010;

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

	if(b == 0)return a;

	return gcd(b,a%b);

}

struct Node {

	int l,r;

	int a,b;

	int first,last;

	int g;

	int val;

}segTree[MAXN<<2];

void push_up(int i) {

	segTree[i].first = segTree[i<<1].first;

	segTree[i].last = segTree[(i<<1)|1].last;

	segTree[i].val = gcd(segTree[i<<1].val,segTree[(i<<1)|1].val);

	segTree[i].val = gcd(segTree[i].val,abs(segTree[i<<1].last-segTree[(i<<1)|1].first));

	segTree[i].g = gcd(segTree[i].val,segTree[i].first);

}

void Update_node(int i,int a,int b) {

	segTree[i].first = a*segTree[i].first+b;

	segTree[i].last = a*segTree[i].last+b;

	segTree[i].g = gcd(segTree[i].first,segTree[i].val);

	segTree[i].a *= a;

	segTree[i].b = a*segTree[i].b+b;

}

void push_down(int i) {

	if(segTree[i].l == segTree[i].r)return;

	int a = segTree[i].a;

	int b = segTree[i].b;

	if(a != 1 || b != 0) {

		Update_node(i<<1,a,b);

		Update_node((i<<1)|1,a,b);

		a = 1;

		b = 0;

	}

}

int a[MAXN];

void build(int i,int l,int r) {

	segTree[i].l = l;

	segTree[i].r = r;

	segTree[i].a = 1;

	segTree[i].b = 0;

	if(l == r) {

		segTree[i].first = a[l];

		segTree[i].last = a[l];

		segTree[i].val = 0;

		segTree[i].g = a[l];

		return;

	}

	int mid = (l+r)/2;

	build(i<<1,l,mid);

	build((i<<1)|1,mid+1,r);

	push_up(i);

}

void update(int i,int l,int r,int a,int b) {

	if(segTree[i].l == l && segTree[i].r == r) {

		Update_node(i,a,b);

		return;

	}

	push_down(i);

	int mid = (segTree[i].l+segTree[i].r)/2;

	if(r <= mid)update(i<<1,l,r,a,b);

	else if(l > mid)update((i<<1)|1,l,r,a,b);

	else {

		update(i<<1,l,mid,a,b);

		update((i<<1)|1,mid+1,r,a,b);

	}

	push_up(i);

}

int query(int i,int l,int r) {

	if(segTree[i].l == l && segTree[i].r == r)

		return segTree[i].g;

	push_down(i);

	int mid = (segTree[i].l+segTree[i].r)/2;

	if(r <= mid)return query(i<<1,l,r);

	else if (l > mid)return query((i<<1)|1,l,r);

	else return gcd(query(i<<1,l,mid),query((i<<1)|1,mid+1,r));

}

int main()

{

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

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

    int n,m;

	while(scanf("%d%d",&n,&m) == 2) {

		for(int i = 1;i <= n;i++)scanf("%d",&a[i]);

		build(1,1,n);

		int op;

		int l,r,x;

		while(m--) {

			scanf("%d",&op);

			if(op == 1) {

				scanf("%d%d%d",&l,&r,&x);

				update(1,l,r,-1,x);

			} else {

				scanf("%d%d",&l,&r);

				printf("%d\n",query(1,l,r));

			}

		}

	}

    return 0;

}

E题： 题目链接：http://acm.fzu.edu.cn/problem.php?pid=2202 题目也很清楚，最后要输出每个人是不是可以确定说真话还是假话。 首先枚举，加上第 i 个人犯罪了，那么你要判断是不是说真话的有m个。 判断的时候肯定要 O(1) 啦， 其实如果i是犯罪的，说别人犯罪的都是说假话的，说别人不犯罪的也是假话的，直接就求出了有多少人说真话。 然后输出时候特判就可以了。 具体不分析了，自己看看代码。 代码君：

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

Author        :kuangbin

Created Time  :2015/10/6 13:28:08

File Name     :F:\ACM\2015ACM\比赛练习\2015-10-6\E.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;

int a[MAXN];

int n,m;

int numa[MAXN],numb[MAXN];

bool can[MAXN];

int main()

{

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

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

    int T;

	scanf("%d",&T);

	while(T--) {

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

		memset(numa,0,sizeof(numa));

		int sa = 0;

		int sb = 0;

		memset(numb,0,sizeof(numb));

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

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

			if(a[i] > 0) {

				numa[a[i]]++;

				sa++;

			}

			else {

				numb[-a[i]]++;

				sb++;

			}

		}

		memset(can,false,sizeof(can));

		int ret = 0;

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

			if (numa[i] + sb - numb[i] == m) {

				ret++;

				can[i] = true;

			}

		}

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

			if(a[i] > 0) {

				if(can[a[i]]) {

					if(ret == 1)puts("Truth");

					else puts("Not defined");

				} else puts("Lie");

			}

			else {

				if(can[-a[i]]) {

					if(ret == 1)puts("Lie");

					else puts("Not defined");

				}

				else puts("Truth");

			}

		}

	}

    return 0;

}

F题： 题目链接：[http://acm.fzu.edu.cn/problem.php?pid=2203](http://acm.fzu.edu.cn/problem.php?pid=2203) 很水。全场最水。 二分，然后判断就可以了。

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

Author        :kuangbin

Created Time  :2015/10/6 20:04:50

File Name     :F:\ACM\2015ACM\比赛练习\2015-10-6\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>

using namespace std;

const int MAXN = 200010;

int N,K,A;

bool used[MAXN];

int a[MAXN];

bool check(int n) {

	memset(used,false,sizeof(used));

	for(int i = 0;i < n;i++)used[a[i]] = true;

	int cnt = 0;

	int num = 0;

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

		if(used[i]) {

			num += (cnt+1)/(A+1);

			cnt = 0;

		} else cnt++;

	}

	num += (cnt+1)/(A+1);

	return num >= K;

}

int main()

{

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

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

    while(scanf("%d%d%d",&N,&K,&A) == 3) {

		int m;

		scanf("%d",&m);

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

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

		}

		int ans = 0;

		int l = 0, r = m;

		while(l <= r) {

			int mid = (l+r)/2;

			if(check(mid)) {

				ans = mid;

				l = mid+1;

			}

			else r = mid-1;

		}

		if(ans == m)printf("-1\n");

		else printf("%d\n",ans+1);

	}

    return 0;

}

G题： 题目链接：http://acm.fzu.edu.cn/problem.php?pid=2204 要对n个点的环进行黑白染色，没有>=7个连续的都是黑或者白。 一样的思路，环转化为线性。 假设第一个是黑色的。 （如果第一个是白色的，情况是对称的，结果乘于2就OK了） 所以可以算第一个是黑色的。 你首先要枚举前x个是黑色的，第x+1个是白色的，枚举肯定 x <7了。 这样你对剩下部分进行DP转移，注意这个时候DP的时候，你要默认第一个一定涂白色。（这里的第一个其实是第x+1个）。 然后转移 n-x 个，看最后的状态合并起来不会冲突，不冲突就累加了。

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

Author        :kuangbin

Created Time  :2015/10/6 13:23:07

File Name     :F:\ACM\2015ACM\比赛练习\2015-10-6\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>

using namespace std;

const int MOD = 2015;

int dp[100010][7][2];

void Add(int &a,int b) {

	a += b;

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

}

int main()

{

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

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

    memset(dp,0,sizeof(dp));

	dp[0][0][0] = 1;

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

		for(int j = 0;j <= i && j < 7;j++)

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

				if(dp[i][j][c] == 0)continue;

				if(c == 0 && j+1 < 7)

					Add(dp[i+1][j+1][0],dp[i][j][c]);

				if(c == 1)

					Add(dp[i+1][1][0],dp[i][j][c]);

				if(i == 0)continue;

				if(c == 1 && j+1 < 7)

					Add(dp[i+1][j+1][1],dp[i][j][c]);

				if(c == 0)

					Add(dp[i+1][1][1],dp[i][j][c]);

			}

	int T;

	int n;

	scanf("%d",&T);

	int iCase = 0;

	while(T--) {

		iCase++;

		scanf("%d",&n);

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

		if(n <= 6) {

			printf("%d\n",(1<<n)%MOD);

			continue;

		}

		int ans = 0;

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

			for(int j = 0;j < 7 && j <= n-i;j++)

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

					if(dp[n-i][j][c] == 0)continue;

					if(i + (c==1)*j >= 7)continue;

					Add(ans,dp[n-i][j][c]);

				}

		}

		Add(ans,ans);

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

	}

    return 0;

}