hdoj1147

判线段相交,写的比较累,就当是写了个模板,(虽然每次遇到模板题都是习惯全部自己手写一遍。。。)看到题目第一感觉是计算几何+并查集,后来调试的时候发现这样写是错误的,所以就不用并查集了,算法效率O(n^2),看数据规模,理论上应该过不了,但是过了,数据水??
代码如下,并查集部分就当无用代码。。懒得删了~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Point{
	double x,y;
	Point(double x=0,double y=0):x(x),y(y)
	{}
}Point;
typedef Point vect;
typedef struct segment{
	Point p1,p2;
}segment;
segment seg[100005];
int bin[100005];
vect operator +(vect a,vect b)
{
	return vect(a.x+b.x,a.y+b.y);
}
vect operator -(Point a,Point b)
{
	return vect(a.x-b.x,a.y-b.y);
}
vect operator *(vect a,double p)
{
	return vect(a.x*p,a.y*p);
}
vect operator /(vect a,double p)
{
	return vect(a.x/p,a.y/p);
}
double cross(vect v1,vect v2)
{
	return v1.x*v2.y-v2.x*v1.y;
}
int find(int x)
{
	int r=x;
	while(bin[r]!=r)
		r=bin[r];
	int p=x;
	while(bin[p]!=r)
	{
		int t=bin[p];
		bin[p]=r;
		p=t;
	}
	return r;
}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		bin[fx]=fy;
	return;
}
double dmax(double a,double b)
{
	return a>b?a:b;
}
double dmin(double a,double b)
{
	return a<b?a:b;
}
bool onseg(Point a,Point c,Point b)
{
	if(dmin(a.x,b.x)<=c.x && c.x<=dmax(a.x,b.x) && dmin(a.y,b.y)<=c.y && c.y<=dmax(a.y,b.y))
		return true;
	else
		return false;
}
bool seg_intersect(Point p1,Point p2,Point p3,Point p4)
{
	double d1=cross(p4-p3,p1-p3);
	double d2=cross(p4-p3,p2-p3);
	double d3=cross(p2-p1,p3-p1);
	double d4=cross(p2-p1,p4-p1);

	if(d1*d2<0 && d3*d4<0)
		return true;
	else if(d1==0 && onseg(p3,p1,p4))
		return true;
	else if(d2==0 && onseg(p3,p2,p4))
		return true;
	else if(d3==0 && onseg(p1,p3,p2))
		return true;
	else if(d4==0 && onseg(p1,p4,p2))
		return true;
	else
		return false;
}
bool istop[100005];
int main()
{
	int n,i;
	scanf("%d",&n);
	while(n!=0)
	{
		memset(istop,1,sizeof(istop));
		for(i=1;i<=n;i++)
			bin[i]=i;
		for(i=1;i<=n;i++)
		{
			double p1x,p1y,p2x,p2y;
			scanf("%lf %lf %lf %lf",&p1x,&p1y,&p2x,&p2y);
			seg[i].p1=Point(p1x,p1y);
			seg[i].p2=Point(p2x,p2y);
		}
		for(i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				if(seg_intersect(seg[i].p1,seg[i].p2,seg[j].p1,seg[j].p2))
				{
						//merge(j,i);
					istop[i]=0;
					break;

				}
			}
		}
		int count=0;
		printf("Top sticks:");
		for(i=1;i<=n;i++)
			if(istop[i])
			{
				count++;
				if(count!=1)
					printf(", %d",i);
				else
					printf(" %d",i);
			
			}
		printf(".\n");
	
		scanf("%d",&n);
	}

//system("pause");
return 0;
}

hdoj1086

开始学几何,好吧,献上一道计算几何最基础的题——线段相交判定,原理比较简单,但写程序的时候结构体里套着结构体,一边看自己画的草图,一边写代码,写的纠结。。

#include<stdio.h>
#include<stdlib.h>
typedef struct Point{
	double x;
	double y;
}Point;
typedef struct v{
	Point begin;
	Point end;
}v;
typedef struct seg{
	Point p1;
	Point p2;
}seg;
double max(double a,double b)
{
	return a>b?a:b;
}
double min(double a,double b)
{
	return a<b?a:b;
}
double cross_product(v a,v b)
{
	a.end.x=a.end.x-a.begin.x;
	a.end.y=a.end.y-a.begin.y;
	a.begin.x=a.begin.y=0;
	b.end.x=b.end.x-b.begin.x;
	b.end.y=b.end.y-b.begin.y;
	b.begin.x=b.begin.y=0;

	return a.end.x*b.end.y-b.end.x*a.end.y;
}
bool online(Point a,Point b,Point c)
{
	if((min(a.x,b.x)<=c.x && c.x<=max(a.x,b.x)) && (min(a.y,b.y)<=c.y && c.y<=max(a.y,b.y)))
		return true;
	return false;


}
bool seg_intersect(seg s1,seg s2)
{
	v vi,vj;
	v v1,v2,v3,v4;
	vi.begin.x=s1.p1.x;
	vi.begin.y=s1.p1.y;
	vi.end.x=s1.p2.x;
	vi.end.y=s1.p2.y;
	
	vj.begin.x=s2.p1.x;
	vj.begin.y=s2.p1.y;
	vj.end.x=s2.p2.x;
	vj.end.y=s2.p2.y;

	v1.begin.x=s1.p1.x;
	v1.begin.y=s1.p1.y;
	v1.end.x=s2.p1.x;
	v1.end.y=s2.p1.y;

	v2.begin.x=s1.p1.x;
	v2.begin.y=s1.p1.y;
	v2.end.x=s2.p2.x;
	v2.end.y=s2.p2.y;

	v3.begin.x=s2.p1.x;
	v3.begin.y=s2.p1.y;
	v3.end.x=s1.p2.x;
	v3.end.y=s1.p2.y;

	v4.begin.x=s2.p1.x;
	v4.begin.y=s2.p1.y;
	v4.end.x=s1.p1.x;
	v4.end.y=s1.p1.y;
	double d1=cross_product(v1,vi);
	double d2=cross_product(v2,vi);

	double d3=cross_product(v3,vj);
	double d4=cross_product(v4,vj);
	
	if(d1*d2<0 && d3*d4<0)
		return true;
	else if(d1==0)
	{
		if(online(s1.p1,s1.p2,s2.p1))
			return true;
	}
	else if(d2==0)
	{
		if(online(s1.p1,s1.p2,s2.p2))
			return true;
	}
	else if(d3==0)
	{
		if(online(s2.p1,s2.p2,s1.p2))
			return true;
	}
	else if(d4==0)
	{
		if(online(s2.p1,s2.p2,s1.p1))
			return true;
	}
	else
		return false;
}
int main()
{
	int n,i,j;
	scanf("%d",&n);
	while(n!=0)
	{
		seg s[110];
		for(i=1;i<=n;i++)
			scanf("%lf %lf %lf %lf",&s[i].p1.x,&s[i].p1.y,&s[i].p2.x,&s[i].p2.y);
		int count=0;
		for(i=1;i<=n-1;i++)
			for(j=i+1;j<=n;j++)
			{
				if(seg_intersect(s[i],s[j]))
					count++;
			}
		printf("%d\n",count);
		scanf("%d",&n);
	}
//system("pause");
return 0;
}

再说hdoj1143——用矩阵解决骨牌铺方格的递推问题

在Matrax67大神的博文中看到矩阵的几个应用中有一个是用来解决骨牌铺方格问题。思想相当巧妙。
首先画出8个状态及其转移,建立有向图,继而用矩阵解决。膜拜下Matrax67大神
用这个方法又做了一遍hdoj1143,下面是代码

#include<stdio.h>
#include<stdlib.h>
typedef struct Mat{
	int m[9][9];
}Mat;
Mat per;
void init()
{
	int i,j;
	for(i=1;i<=8;i++)
		for(j=1;j<=8;j++)
			per.m[i][j]=(i==j);
	return;
}
Mat multi(Mat a,Mat b)
{
	Mat c;
	int i,j,k;
	for(i=1;i<=8;i++)
		for(j=1;j<=8;j++)
		{
			c.m[i][j]=0;
			for(k=1;k<=8;k++)
				c.m[i][j]+=a.m[i][k]*b.m[k][j];
		}
	return c;
}
Mat power(Mat a,int k)
{
	init();
	Mat ans=per,p;
	p=a;
	while(k)
	{
		if(k&1)
		{
			ans=multi(ans,p);
			k--;
		
		}
		else
		{
			k/=2;
			p=multi(p,p);
		
		}
	}
	return ans;
}
int main()
{
	int i,j,n;
	Mat s;
	for(i=1;i<=8;i++)
		for(j=1;j<=8;j++)
			s.m[i][j]=(i+j==9);
	s.m[4][8]=1;
	s.m[8][4]=1;
	s.m[7][8]=1;
	s.m[8][7]=1;
	scanf("%d",&n);
	while(n!=-1)
	{
		Mat ans=power(s,n);
		printf("%d\n",ans.m[8][8]);
		


		scanf("%d",&n);
	}
//system("pause");
return 0;
}

hdoj3787

这是一道很水的水题,放在这主要是为了说明一个c函数的用法,这个函数很早就知道,但从未用过。。今天用它来做道题目,强化一下。

C语言库函数名: atoi
功 能: 把字符串转换成整型数。
名字来源:ASCII to integer 的缩写。
原型: int atoi(const char *nptr);
函数说明: 参数nptr字符串,如果第一个非空格字符存在或者不是数字也不是正负号则返回零,否则开始做类型转换,之后检测到非数字(包括结束符 \0) 字符时停止转换,返回整型数。
头文件: #include

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
	char s[25];
	while(gets(s))
	{
		int i,len=strlen(s);
		char s1[12],s2[12];
		int cur1=0,cur2=0;
		int flag=0;
		for(i=0;i<=len-1;i++)
		{
			if(s[i]==' ')
			{
				flag=1;
				continue;
			}
			if(!flag)
			{
				if(s[i]!=',')
					s1[cur1++]=s[i];
			
			}
			else
			{
				if(s[i]!=',')
					s2[cur2++]=s[i];
			
			}
		}
		s1[cur1]='\0';
		s2[cur2]='\0';
		int a=atoi(s1);
		int b=atoi(s2);
		printf("%d\n",a+b);
	}
//system("pause");
return 0;
}

十个利用矩阵乘法解决的经典题目(经典~)

心得:矩阵可以表示一次操作,当操作很多时,可以将所有操作合并成一个操作,因为矩阵乘法可以二分,所以效率就提高了。矩阵乘法与有向图中从点i走过k条边(可重复走一条边)到点j问题之间的对应,以及用矩阵解决骨骼牌铺方格为则十分有趣

转载自matrax67的博客:http://www.matrix67.com/blog/archives/276

 好像目前还没有这方面题目的总结。这几天连续看到四个问这类题目的人,今天在这里简单写一下。这里我们不介绍其它有关矩阵的知识,只介绍矩阵乘法和相关性质。
    不 要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中,一个矩阵说穿了就是一个二维数组。一个n行m列的矩阵可以乘以一个m行p列的矩阵,得到 的结果是一个n行p列的矩阵,其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。比 如,下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵,其结果是一个2行3列的矩阵。其中,结果的那个4等于2*2+0*1:
    
    下面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵,得到一个1 x 2的矩阵:
    

    矩阵乘法的两个重要性质:一,矩阵乘法不满足交 换律;二,矩阵乘法满足结合律。为什么矩阵乘法不满足交换律呢?废话,交换过来后两个矩阵有可能根本不能相乘。为什么它又满足结合律呢?仔细想想你会发现 这也是废话。假设你有三个矩阵A、B、C,那么(AB)C和A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和(枚 举所有的k和l)。

经典题目1 给定n个点,m个操作,构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转
    这 里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转(两种情况),旋转则以原点为中心。如果对每个点分别进行模拟,那么m个操作总共耗时 O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵,然后每个点与该矩阵相乘即可直接得出最终该点的位置,总共耗时O(m+n)。 假设初始时某个点的坐标为x和y,下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来,再乘以 (x,y,1),即可一步得出最终点的位置。
    

经典题目2 给定矩阵A,请快速计算出A^n(n个A相乘)的结果,输出的每个数都mod p。
    由 于矩阵乘法具有结合律,因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论:当n为偶数时,A^n = A^(n/2) * A^(n/2);当n为奇数时,A^n = A^(n/2) * A^(n/2) * A (其中n/2取整)。这就告诉我们,计算A^n也可以使用二分快速求幂的方法。例如,为了算出A^25的值,我们只需要递归地计算出A^12、A^6、 A^3的值即可。根据这里的一些结果,我们可以在计算过程中不断取模,避免高精度运算。

经典题目3 POJ3233 (感谢rmq)
    题目大意:给定矩阵A,求A + A^2 + A^3 + … + A^k的结果(两个矩阵相加就是对应位置分别相加)。输出的数据mod m。k<=10^9。
    这道题两次二分,相当经典。首先我们知道,A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。比如,当k=6时,有:
    A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)
    应用这个式子后,规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3,即可得到原问题的答案。

经典题目4 VOJ1049
    题目大意:顺次给出m个置换,反复使用这m个置换对初始序列进行操作,问k次置换后的序列。m<=10, k<2^31。
    首先将这m个置换“合并”起来(算出这m个置换的乘积),然后接下来我们需要执行这个置换k/m次(取整,若有余数则剩下几步模拟即可)。注意任意一个置换都可以表示成矩阵的形式。例如,将1 2 3 4置换为3 1 2 4,相当于下面的矩阵乘法:
    
    置换k/m次就相当于在前面乘以k/m个这样的矩阵。我们可以二分计算出该矩阵的k/m次方,再乘以初始序列即可。做出来了别忙着高兴,得意之时就是你灭亡之日,别忘了最后可能还有几个置换需要模拟。

经典题目5 《算法艺术与信息学竞赛》207页(2.1代数方法和模型,[例题5]细菌,版次不同可能页码有偏差)
    大家自己去看看吧,书上讲得很详细。解题方法和上一题类似,都是用矩阵来表示操作,然后二分求最终状态。

经典题目6 给定n和p,求第n个Fibonacci数mod p的值,n不超过2^31
    根 据前面的一些思路,现在我们需要构造一个2 x 2的矩阵,使得它乘以(a,b)得到的结果是(b,a+b)。每多乘一次这个矩阵,这两个数就会多迭代一次。那么,我们把这个2 x 2的矩阵自乘n次,再乘以(0,1)就可以得到第n个Fibonacci数了。不用多想,这个2 x 2的矩阵很容易构造出来:
    

经典题目7 VOJ1067
    我 们可以用上面的方法二分求出任何一个线性递推式的第n项,其对应矩阵的构造方法为:在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1,矩阵第 n行填对应的系数,其它地方都填0。例如,我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) – 3f(n-2) + 2f(n-4)的第k项:
    
    利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况。

经典题目8 给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值
    把 给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j。令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就 等于从点i到点j恰好经过2条边的路径数(枚举k为中转点)。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的 路径数,我们只需要二分求出A^k即可。

经典题目9 用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案,M<=5,N<2^31,输出答案mod p的结果
    
    我 们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上,从右往左一列一列地进行填充。其中前n-2列已经填满了,第n-1列参差不齐。现在我们 要做的事情是把第n-1列也填满,将状态转移到第n列上去。由于第n-1列的状态不一样(有8种不同的状态),因此我们需要分情况进行讨论。在图中,我把 转移前8种不同的状态放在左边,转移后8种不同的状态放在右边,左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复, 状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌(例如左边第2种状态不能转移到右边第4种状态),否则这将与另一种转移前的状态重复。把这8种状 态的转移关系画成一个有向图,那么问题就变成了这样:从状态111出发,恰好经过n步回到这个状态有多少种方案。比如,n=2时有3种方案,111-& gt;011->111、111->110->111和111->000->111,这与用多米诺骨牌覆盖3×2矩形的方 案一一对应。这样这个题目就转化为了我们前面的例题8。
    后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。

经典题目10 POJ2778
    题目大意是,检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段,每个片段长度不超过10。数据规模n<=2 000 000 000。
    下 面的讲解中我们以ATC,AAA,GGC,CT这四个病毒片段为例,说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀,把 n位DNA分为以下7类:以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”,它可以是任 一字母,只要这个字母不会让它所在的串成为某个病毒的前缀。显然,这些分类是全集的一个划分(交集为空,并集为全集)。现在,假如我们已经知道了长度为 n-1的各类DNA中符合要求的DNA个数,我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如,从 AT不能转移到AA,从AT转移到??有4种方法(后面加任一字母),从?A转移到AA有1种方案(后面加个A),从?A转移到??有2种方案(后面加G 或C),从GG到??有2种方案(后面加C将构成病毒片段,不合法,只能加A和T)等等。这个图的构造过程类似于用有限状态自动机做串匹配。然后,我们就 把这个图转化成矩阵,让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。
    题目中的数据规模保证前缀数不超过100,一次矩阵乘法是三方的,一共要乘log(n)次。因此这题总的复杂度是100^3 * log(n),AC了。

    最后给出第9题的代码供大家参考(今天写的,熟悉了一下C++的类和运算符重载)。为了避免大家看代码看着看着就忘了,我把这句话放在前面来说:
    Matrix67原创,转贴请注明出处。

#include <cstdio>
#define SIZE (1<<m)
#define MAX_SIZE 32
using namespace std;

class CMatrix
{
    public:
        long element[MAX_SIZE][MAX_SIZE];
        void setSize(int);
        void setModulo(int);
        CMatrix operator* (CMatrix);
        CMatrix power(int);
    private:
        int size;
        long modulo;
};

void CMatrix::setSize(int a)
{
    for (int i=0; i<a; i++)
        for (int j=0; j<a; j++)
            element[i][j]=0;
    size = a;
}

void CMatrix::setModulo(int a)
{
    modulo = a;
}

CMatrix CMatrix::operator* (CMatrix param)
{
    CMatrix product;
    product.setSize(size);
    product.setModulo(modulo);
    for (int i=0; i<size; i++)
        for (int j=0; j<size; j++)
            for (int k=0; k<size; k++)
            {
                product.element[i][j]+=element[i][k]*param.element[k][j];
                product.element[i][j]%=modulo;
            }

    return product;
}

CMatrix CMatrix::power(int exp)
{
    CMatrix tmp = (*this) * (*this);
    if (exp==1) return *this;
    else if (exp & 1) return tmp.power(exp/2) * (*this);
    else return tmp.power(exp/2);
}

int main()
{
    const int validSet[]={0,3,6,12,15,24,27,30};
    long n, m, p;
    CMatrix unit;
    
    scanf("%d%d%d", &n, &m, &p);
    unit.setSize(SIZE);
    for(int i=0; i<SIZE; i++)
        for(int j=0; j<SIZE; j++)
            if( ((~i)&j) == ((~i)&(SIZE-1)) )
            {
                bool isValid=false;
                for (int k=0; k<8; k++)isValid=isValid||(i&j)==validSet[k];
                unit.element[i][j]=isValid;
            }

    unit.setModulo(p);
    printf("%d", unit.power(n).element[SIZE-1][SIZE-1] );
    return 0;
}

hdoj1588

用矩阵计算fib数列,不知是算法太挫还是某个细节弄错,一直TLE。。明日再改
TLE代码:

#include<stdio.h>
#include<stdlib.h>
#define MAX 10
typedef struct Mat{
	int m[MAX][MAX];
}Mat;
Mat per;
void init(int x,int y)
{
	int i,j;
	for(i=1;i<=x;i++)
		for(j=1;j<=y;j++)
			per.m[i][j]=(i==j);
	return;
}
Mat multi(Mat a,Mat b,int x,int y,int z,int m)
{
	Mat c;
	int i,j,k;
	for(i=1;i<=x;i++)
		for(j=1;j<=z;j++)
		{
			c.m[i][j]=0;
			for(k=1;k<=y;k++)
				c.m[i][j]+=a.m[i][k]*b.m[k][j];
			c.m[i][j]%=m;
		}
	return c;
}
Mat power(Mat a,int k,int x,int m)
{
	init(x,x);
	Mat p,ans=per;
	p=a;
	while(k)
	{
		if(k&1)
		{
			ans=multi(ans,p,x,x,x,m);
			k--;
		}
		else
		{
			p=multi(p,p,x,x,x,m);
			k/=2;
		}
	}
	return ans;
}
Mat add(Mat a,Mat b,int x,int y,int m)
{
	int i,j;
	for(i=1;i<=x;i++)
		for(j=1;j<=y;j++)
		{
			a.m[i][j]=(a.m[i][j]+b.m[i][j])%m;
		}
	return a;
}
Mat f(Mat B,int n,int m)
{
	if(n==1)
		return B;
	if(n==2)
		return add(B,multi(B,B,2,2,2,m),2,2,m);
	if(n%2==1)
	{
		Mat tmp=power(B,n,2,m);
		return add(tmp,f(B,n-1,m),2,2,m);
	}
	else
	{
		Mat tmp2=power(B,n/2,2,m);
		return add(f(B,n/2,m),multi(tmp2,f(B,n/2,m),2,2,2,m),2,2,m);
	}
}
int main()
{
	int k,b,n,m;
	Mat A;
	A.m[1][1]=0;
	A.m[1][2]=1;
	A.m[2][1]=1;
	A.m[2][2]=1;
	while(scanf("%d %d %d %d",&k,&b,&n,&m)!=EOF)
	{
		Mat B=power(A,k,2,m);
		Mat C=power(A,b,2,m);
		Mat D;
		D.m[1][1]=0;
		D.m[2][1]=1;
		if(n==0)
		{
			Mat ans=multi(C,D,2,2,1,m);
			printf("%d\n",ans.m[1][1]);
			continue;
		
		}
		if(n==1)
		{
			Mat tmp3=multi(add(C,multi(B,C,2,2,2,m),2,2,m),D,2,2,1,m);
			printf("%d\n",tmp3.m[1][1]);
			continue;
		}
		Mat F=f(B,n-1,m);
		Mat tmp=multi(C,F,2,2,2,m);
		Mat result=add(C,tmp,2,2,m);

		result=multi(result,D,2,2,1,m);
		printf("%d\n",result.m[1][1]);

	}
system("pause");
return 0;
}

用矩阵求解递推式第n项(n非常大)

Problem A

Time Limit : 15000/5000ms (Java/Other)   Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 36   Accepted Submission(s) : 11

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

Chef Ciel lives in a long street which can be thought as of x-axis of coordinate system. Her house is at coordinate 0 whereas her restaurant is situated at coordinate N. Usually Ciel goes from home to restaurant taking a step of size 1 or 2 in forward direction. We all know how much Chef loves Fibonacci numbers.
But today, Ciel being little casual stepped in wrong direction on her way to her restaurant exactly once and of course she did not set her foot wrong at home. Now she wonders how many ways she can reach her restaurant provided that she stepped wrong once but not at home.
She does not go past her restaurant because it is altogether different world and once she reaches her restaurant she stops.

For example, if N is 3 then below ways are possible
0 -> 1 -> -1 -> 0 -> 1 -> 3,
0 -> 2 -> 1 -> 3

But below ways are not
0 -> -1 -> 1 -> 3, (She did not set her foot wrong at her home)
0 -> 1 -> 3, (She sets her foot wrong direction exactly once)
0 -> 1 -> 0 -> 3, (Her steps are always size 1 or 2)
0 -> 1 -> 2 -> 4 -> 3, (She does not go past her restaurant)
0 -> 1 -> 2 -> 3 -> 2 -> 3 (Once she reaches her restaurant, she stops)

Input

First line of input contains T, number of test cases which is at most 10000. Then T lines follows each containing a positive integer N which is at most 1000000000000000 (10^15).

Output

Number of ways Ciel can reach her restaurant modulo 1000000007 (10^9+7).

Sample Input

2
3
4

Sample Output

18
44

今天的练习赛让人欲哭无泪,开始一题都不会做,最后终于捣鼓出第一题的递推式,却因为n太大而不知怎么做,问了下威哥,威哥说要用矩阵解,好吧,没学过矩阵解递推。。于是上网狂搜相关资料。找到matrax67大牛的一篇文章,还好看懂了一些,,最后配出了相应的矩阵,可惜绝杀失败。。不过学到了新知识,还是很开心^_^
01316692 2013-01-25 17:01:07 Out Of Contest Time 1001 0 MS 0 KB Visual C++ shadow
。。也不知道代码写的对不对,,如下

#include<stdio.h>
#include<stdlib.h>
#define M 1000000007
typedef struct{
	__int64 m[5][5];

}Matrax;
typedef struct{
	__int64 m[5][2];
}Matrax2;
Matrax per;
Matrax multi(Matrax a,Matrax b)
{
	Matrax c;
	int k,i,j;
	for(i=1;i<=4;i++)
		for(j=1;j<=4;j++)
		{
			c.m[i][j]=0;
			for(k=1;k<=4;k++)
			{
				c.m[i][j]=c.m[i][j]+(a.m[i][k]*b.m[k][j]);	
			}
			c.m[i][j]%=M;
		}
		return c;
}
Matrax power(Matrax a,__int64 k)
{
	Matrax p,ans=per;
	p=a;
	while(k)
	{
		if(k&1)
		{
			ans=multi(ans,p);
			k--;
		}
		else
		{
			k/=2;
			p=multi(p,p);
		
		}
	}
	return ans;

}
Matrax2 multi2(Matrax a,Matrax2 b)
{
	Matrax2 c;
	__int64 i,j,k;
	for(i=1;i<=4;i++)
		for(j=1;j<=1;j++)
		{
			c.m[i][j]=0;
			for(k=1;k<=4;k++)
				c.m[i][j]+=a.m[i][k]*b.m[k][j];
			c.m[i][j]%=M;
		}
	return c;
}
int main()
{
	int i,j;
	for(i=1;i<=4;i++)
		for(j=1;j<=4;j++)
		per.m[i][j]=(i==j);
	Matrax a;

	a.m[1][1]=0;
	a.m[1][2]=1;
	a.m[1][3]=0;
	a.m[1][4]=0;
	a.m[2][1]=1;
	a.m[2][2]=1;
	a.m[2][3]=1;
	a.m[2][4]=1;
	a.m[3][1]=0;
	a.m[3][2]=0;
	a.m[3][3]=0;
	a.m[3][4]=1;
	a.m[4][1]=0;
	a.m[4][2]=0;
	a.m[4][3]=1;
	a.m[4][4]=1;
	int t;
	scanf("%d",&t);
	while(t--)
	{
		__int64 n;
		scanf("%I64d",&n);
		if(n==1)
			printf("0\n");
		else
		{
			Matrax result=power(a,n-1);
			Matrax2 tmp;
			tmp.m[1][1]=0;
			tmp.m[2][1]=5;
			tmp.m[3][1]=5;
			tmp.m[4][1]=8;

			Matrax2 re=multi2(result,tmp);
			printf("%I64d\n",re.m[1][1]);
		
		}
	
	}
//system("pause");
return 0;
}

hdoj1073

几点收获:
1.gets能读取回车,但是它会自动把回车改为’\0′
2.gets不能读取空行(因为空行只有一个’\n’,gets()会把它变成’\0′,这样,字符串长度为0,相当于什么也没读到)
3.如何将两篇文章(也就是行数不定,且可能有空行)进行比较:将文章转成一个字符串,因为可能有空行,所以不能用gets(如果用gets,则一篇文章空行,一篇无空行,其他地方相同,转化成的字符串会完全相同),这时应当自己写一个会读取回车的函数,类似于gets(),但不会将’\n’转化为’\0′,这样就保证了有无空行是不同的(有空行会在转化成的字符串中有一个’\n’)

#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<string.h>
using namespace std;
void getline(char*s)
{
	int x=0;
	char c=getchar();
	while(c!='\n')
	{
		s[x++]=c;
		c=getchar();
	}
	s[x++]='\n';
	s[x]='\0';
	return;

}
int main()
{
	int t;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		char s[5003],s1[5003],s2[5003],ss1[5003],ss2[5003],c;
		int i=0,j=0,k;
		getline(s);
		getline(s);
		while(strcmp(s,"END\n")!=0)
		{
			int len=strlen(s);
			for(k=0;k<=len-1;k++)
			{
				ss1[j++]=s[k];
				if(s[k]!=' ' && s[k]!='\n' && s[k]!='\t')
					s1[i++]=s[k];
			}
			getline(s);
		}
		s1[i++]='\0';
		ss1[j++]='\0';
		getline(s);
		getline(s);
		i=0;
		j=0;
		while(strcmp(s,"END\n")!=0)
		{
			int len=strlen(s);
			for(k=0;k<=len-1;k++)
			{
				ss2[j++]=s[k];
				if(s[k]!=' ' && s[k]!='\n' && s[k]!='\t')
					s2[i++]=s[k];
			}
			getline(s);
		}
		s2[i++]='\0';
		ss2[j++]='\0';
		string str1(s1);
		string str2(s2);
		string sstr1(ss1);
		string sstr2(ss2);
		if(str1==str2)
		{
			if(sstr1==sstr2)
				printf("Accepted\n");
			else
				printf("Presentation Error\n");
		}
		else
			printf("Wrong Answer\n");
		
	}
	//system("pause");
	return 0;
}

hdoj1062

此乃水题,但字符串类型的操作始终是我的弱项。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		char s[1003],tmp[1003];
		gets(s);
		int len=strlen(s);
		int i=0,j,k=0;
		while(s[i]==' ' && i<=len-1)
		{
			printf(" ");
			i++;
		}
		for(j=i;j<=len-1;)
		{
			while(s[j]!=' ' && j<=len-1)
			{
				tmp[k++]=s[j];
				j++;
			}
			tmp[k++]='\0';
			string ss(tmp);
			reverse(ss.begin(),ss.end());
			cout<<ss;
			k=0;
			while(s[j]==' ' && j<=len-1)
			{
				printf(" ");
				j++;
			}
		}
		printf("\n");	

	}
//system("pause");
return 0;
}

今天练习赛的两点收获

    0.如果第二天有比赛,前一天晚上必须早睡,,否则睡过头的概率上升到99%(这 次起床吃完午饭练习已经开始2个小时左右了。。)

    1.学到了STL中algorithm的reverse函数的用法,用它来反转string真方便,哈哈(参数是起始和结束迭代器)

    2.更重要的今天知道了c++里面原来有bitset这么个好东西,在内存卡的很紧的时候可以用它来做标记

bitset用法:

    (1)头文件:<bitset>

    (2)定义:bitset<N>  bits(M)

                           N:bitset变量的二进制位数(编号N-1——0

                           bits:变量名

                           M:初始化

                (M)可以省略

                      bitset变量可以像数组一样访问它的每一位。

      (3)方法:

        set():set(0):将变量的第0位设为1,当不加参数时,表示将变量的所有位设为1

        reset():设为0,用法同上

        any():当变量中至少有1位是1时返回true

         none():当变量的所有位全部为0时返回true

         count()返回bitset变量中为1的位的个数

         翻转:

                          bits.flip(0):翻转bits的第1位

                          bits[0].flip():同上

                          bits.flip():将bits的所有位翻转

hdoj1104——bfs+数论

    这题着实做了很久,主要是数论不扎实。。

    首先来说说c语言的%和数学的mod的关系:两者其实并不相同,a%b的结果可能是负的,取决于a的符号,而a mod b的结果一定是正的,也就是数学中的余数(上述所论,前提:除数b都是正的)。

    两者之间可以转化:a mod b=(a%b+b)%b     括号里的是为了将负数转化为正数

    实际上我认为可以这样去理解:当被除数是负数时,例如:a=-3  b=2  -3%2=-1   相当于abs(-3)除以2等于2余-1,这样说不太规范,换言之,当被除数为负数时,a%b的意义是abs(a)比(abs(a)/b+1)*b少了多少。好吧这样还是不够明了,简短的来说,就是数学中的mod或者说余数的含义是余多少,而对于%,当左操作数为正时,和mod意义相同,当左操作数为负时,%含义为缺多少(当然缺多少是对于左操作数的绝对值而言的)。

  第二个问题是n经过运算可能很大,这时需要每步取余,但是对于这道题不能%k,而要%(k*m),因为有一个操作是mod m,%k'后再mod m会导致结果错误。

  第三个问题是防止重复,设置visit数组,visit[这里应该是每步结果mod k]。

  

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Point{
	int n_now;
	char opt;
	int depth;
	int fa;
}Point;
Point queue[1000010];
void print(Point queue[],int now)
{
	if(now==0)
		return;
	print(queue,queue[now].fa);
	printf("%c",queue[now].opt);
	return;

}
int main()
{
	int n,k,m;
	scanf("%d %d %d",&n,&k,&m);
	while(!(n==0 && k==0 && m==0))
	{
		int i;
		int km=k*m;
		int visit[1010];
		memset(visit,0,sizeof(visit));
		int scr=((n+1)%k+k)%k;

		int iq=0;
		queue[iq].n_now=n;
		queue[iq].depth=0;
		queue[iq].fa=-1;
		queue[iq++].opt='0';
		bool flag=false;
		visit[(queue[iq-1].n_now%k+k)%k]=1;
		for(i=0;i<=iq-1;i++)
		{

			queue[iq].n_now=(queue[i].n_now+m)%km;
			queue[iq].depth=queue[i].depth+1;
			queue[iq].fa=i;
			queue[iq++].opt='+';
			if((queue[iq-1].n_now%k+k)%k==scr)
			{
				flag=true;
				break;
			}
			if(!visit[(queue[iq-1].n_now%k+k)%k])
			{
				visit[(queue[iq-1].n_now%k+k)%k]=1;
			}
			else
				iq=iq-1;

			queue[iq].n_now=(queue[i].n_now-m)%km;
			queue[iq].depth=queue[i].depth+1;
			queue[iq].fa=i;
			queue[iq++].opt='-';
			if((queue[iq-1].n_now%k+k)%k==scr)
			{
				flag=true;
				break;
			}
			if(!visit[(queue[iq-1].n_now%k+k)%k])
			{
				visit[(queue[iq-1].n_now%k+k)%k]=1;
			}
			else
				iq=iq-1;

			queue[iq].n_now=(queue[i].n_now*m)%km;
			queue[iq].depth=queue[i].depth+1;
			queue[iq].fa=i;
			queue[iq++].opt='*';
			if((queue[iq-1].n_now%k+k)%k==scr)
			{
				flag=true;
				break;
			}
			if(!visit[(queue[iq-1].n_now%k+k)%k])
			{
				visit[(queue[iq-1].n_now%k+k)%k]=1;
			}
			else
				iq=iq-1;

			queue[iq].n_now=((queue[i].n_now%m+m)%m)%km;
			queue[iq].depth=queue[i].depth+1;
			queue[iq].fa=i;
			queue[iq++].opt='%';
			if((queue[iq-1].n_now%k+k)%k==scr)
			{
				flag=true;
				break;
			}
			if(!visit[(queue[iq-1].n_now%k+k)%k])
			{
				visit[(queue[iq-1].n_now%k+k)%k]=1;
			}
			else
				iq=iq-1;
		}
		if(flag)
		{
			printf("%d\n",queue[iq-1].depth);
			print(queue,iq-1);
			printf("\n");
		}
		else
		{
			printf("0\n");
		}
		scanf("%d %d %d",&n,&k,&m);
	}


//system("pause");
return 0;
}

hdoj1242——bfs

有的格子停留2 unit times,那么只需对应入队时深度+2即可。
进一步:如果题目中有的格子停留时间不定,则只需入队时根据条件将自己入队即可。

#include<stdio.h>
#include<stdlib.h>
typedef struct Point{
	int x;
	int y;
	int depth;
}Point;
int a[5],b[5];
int main()
{
	int n,m;
	a[1]=-1,b[1]=0;
	a[2]=0,b[2]=-1;
	a[3]=1,b[3]=0;
	a[4]=0,b[4]=1;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		getchar();
		char map[210][210];
		int i,j,k;
		int visit[210][210];
		Point queue[50000];
		int iq=0;
		int xs,ys;
		for(i=0;i<=n+1;i++)
			for(j=0;j<=m+1;j++)
				visit[i][j]=1;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%c",&map[i][j]);
				if(map[i][j]=='.'||map[i][j]=='x'||map[i][j]=='r')
					visit[i][j]=0;
				if(map[i][j]=='a')
				{
					visit[i][j]=0;
					xs=i;
					ys=j;
				}
			}
			getchar();
		}
		visit[xs][ys]=1;
		queue[iq].x=xs;
		queue[iq].y=ys;
		queue[iq++].depth=0;
		bool flag=false;
		for(i=0;i<iq;i++)
		{
			int curx=queue[i].x;
			int cury=queue[i].y;
			for(j=1;j<=4;j++)
			{
				if(!visit[curx+a[j]][cury+b[j]])
				{
					queue[iq].x=curx+a[j];
					queue[iq].y=cury+b[j];
					queue[iq++].depth=map[curx+a[j]][cury+b[j]]=='x'?queue[i].depth+2:queue[i].depth+1;
					visit[curx+a[j]][cury+b[j]]=1;
					if(map[curx+a[j]][cury+b[j]]=='r')
					{
						flag=true;
						break;
					}
				}
			}
			if(flag)
				break;
		}
		if(flag)
			printf("%d\n",queue[iq-1].depth);
		else
			printf("Poor ANGEL has to stay in the prison all his life.\n");
	}
//system("pause");
return 0;
}

hdoj1207

T(n)=min(2*T(k)+pow(2,n-k)-1) (1<=k && k<=n-1)
设杆子为ABCD,要把盘子从A移到C,那么移动次数为
先把k个盘子从A经B、C移到D(移动次数为T(k))
然后把n-k个盘子从A经B移到C(也就是普通的三根柱子的情况,移动次数为pow(2,n-k)-1)
之后再把k个盘子从D经A、B移到C(移动次数为T(k))
可见本题是动态规划题,状态转移方程为:
T(n)=min(2*T(k)+pow(2,n-k)-1) (1<=k && k<=n-1)

下面是代码,注意长整形溢出(WA了一次。。)

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<limits.h>
__int64 f[66];
__int64 fact[66];
int main()
{
	f[1]=1;
	f[2]=3;
	fact[0]=1;
	fact[1]=2;
	int i,j;
	for(i=2;i<=65;i++)
		fact[i]=fact[i-1]*2;
	fact[63]=9223372036854775807;
	for(i=0;i<=62;i++)
		fact[i]–;
	for(i=3;i<=65;i++)
	{
		__int64 min1=INT_MAX,min2=INT_MAX;
		__int64 tmp1,tmp2;
		for(j=1;j<=i-1;j++)
		{
			tmp1=2*f[j];
			tmp2=fact[i-j];
			if((tmp1-min1)+(tmp2-min2)<0)
			{
				min1=tmp1;
				min2=tmp2;
			}
	
		}
		f[i]=min1+min2;
	}
	
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		printf("%I64d\n",f[n]);
	}


//system("pause");
return 0;
}

hdoj1997

递归真是好东西,就是想不到,下面是网上的摘录过来的思路:
1) 最初我们要判断一下是不是已经完全放好了,这样就不用考虑是不是最优化了, 因为都已经放好了,肯定是最合法的! 或者说全部在A上,这是还没开始动作的一个状态,所以也是合法的!
2) 否则我们 要对每次状态的最大的那个进行判断,因为我们知道,汉诺塔最大的那个不可能停在B上,(假设 最初的时候都在A上,要移到C上去!),只可能在A或者C上面!如果是放在B上面,停止判断,直接断定他非法~这样我们得出了第二个判段依据!
3)如果最大的在A上面,我可以想到的是,他还没有放在C上,此时这个状态的上面一系列状态都是想把其他的放在B上,然后就可以把A放到C上了,所以我们在这里做出更新,因为他上面一系列动作都是想让A上面的除最大的外都放到B上面去,所以,我们这个时候往上考虑,对N-1进行 判断!这个时候动作的方向是A->B所以为了统一操作,我们得把B跟C互换!
4)如果最大的在C上面,这时候倒数第二大的不是放在B上就是C上,我们要把要把倒数第二大的以及其他的放在C上,这时候的动作方向是B—>C;所以把A跟B交换一下!

下面是代码:

#include<stdio.h>
#include<stdlib.h>
bool fun(int n,int x[],int y[],int z[],int lenx,int leny,int lenz)
{
	int i;
	if(n==0)
		return true;
	for(i=1;i<=leny;i++)
		if(y[i]==n)
			return false;
	for(i=1;i<=lenx;i++)
		if(x[i]==n)
			return fun(n-1,x,z,y,lenx,lenz,leny);
	for(i=1;i<=lenz;i++)
		if(z[i]==n)
			return fun(n-1,y,x,z,leny,lenx,lenz);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,i;
		scanf("%d",&n);
		int m,p,q,a[70],b[70],c[70];
		scanf("%d",&m);
		for(i=1;i<=m;i++)
			scanf("%d",&a[i]);
		scanf("%d",&p);
		for(i=1;i<=p;i++)
			scanf("%d",&b[i]);
		scanf("%d",&q);
		for(i=1;i<=q;i++)
			scanf("%d",&c[i]);
		if(m==n||q==n)
			printf("true\n");
		else
		{
			if(fun(n,a,b,c,m,p,q))
				printf("true\n");
			else
				printf("false\n");
		}
	}
//system("pause");
return 0;
}

hdoj1143

难度值为1的一道题,可是,,,想了好久。。不过还是想出来了
思路:叙述起来比较困难(主要是不知道怎么作图。。),好吧,只给出我推出来的递推式:
f[0]=1
f[n]=f[n-2]+2*(f[n-2]+f[n-4]+……+f[0]]) n>=2
提示:考虑最后3*2方格,还有一种不能只考虑最后3*2方格的情况
(这题最奇怪的是,我认为f[0]=0,但是题目人为的是f[0]=1。。)

#include<stdio.h>
#include<stdlib.h>
__int64 f[31];
int main()
{
	f[0]=1;
	f[2]=3;
	int i,j;
	for(i=4;i<=30;i+=2)
	{
		f[i]=f[i-2];
		for(j=i-2;j>=0;j-=2)
			f[i]+=2*f[j];
	}

	int n;
	scanf("%d",&n);
	while(n!=-1)
	{
		printf("%I64d\n",f[n]);
		scanf("%d",&n);
	}
return 0;
}