hdoj1228

不错的字符串模拟题。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
using namespace std;
string number[10]={"zero","one","two","three","four","five","six","seven","eight","nine"};
int changeadd(char add[])
{
	int i=0,j,cnt,part=0;
	while(add[i]!='\0')
	{
		char tmp[1000];
		cnt=0;
		while(add[i]!=' ' && add[i]!='\0')
		{
			tmp[cnt++]=add[i];
			i++;
		}
		tmp[cnt]='\0';
		string str=tmp;
		for(j=0;j<=9;j++)
			if(number[j]==str)
			{
				part=part*10+j;
				break;
			}
		if(add[i]!='\0')
			i++;
	}
	return part;
}
int main()
{
	char s[1000];
	gets(s);
	while(strcmp(s,"zero + zero =")!=0)
	{
		int i,j;
		int len=strlen(s);
		char add1[1000],add2[1000];
		int cnt1=0,cnt2=0;
		bool flag=0;
		for(i=0;i<=len-2;i++)
		{
			if(!flag)
			{
				if(s[i]!='+')
					add1[cnt1++]=s[i];
				else
					flag=1;
			}
			else
			{
				if(s[i-1]!='+')
					add2[cnt2++]=s[i];
			}
		}
		add1[cnt1++]='\0';
		add2[cnt2++]='\0';
		int part1=changeadd(add1);
		int part2=changeadd(add2);
		printf("%d\n",part1+part2);
		gets(s);
	}
        //system("pause");
        return 0;
}

hdoj1054——树的最小点覆盖

注意只有一个点的情况。。

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define maxn 1600
using namespace std;
vector<int> son[maxn];
int now;
int vex[maxn];
int fa[maxn];
int n;
void dfs(int u,int father)
{
	fa[u]=father;
	vex[++now]=u;
	int i,d=son[u].size();
	for(i=0;i<=d-1;i++)
	{
		int v=son[u][i];
		dfs(v,u);	
	}
	return;
}
int min_cover()
{
	bool s[maxn]={0};
	bool set[maxn]={0};
	int ans=0;
	int i;
	for(i=n;i>=2;i--)
	{
		int t=vex[i];
		if(!s[t] && !s[fa[t]])
		{
			set[fa[t]]=1;
			ans++;
			s[t]=1;
			s[fa[t]]=1;
		}
	}
	return ans;
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		int i;
		now=0;
		if(n==1)
		{
			printf("1\n");
			continue;
		}
		for(i=0;i<=n-1;i++)
		{
			son[i].clear();
		}
		int node,root,num,a;
		for(i=1;i<=n;i++)
		{
			scanf("%d:(%d)",&node,&num);
			if(i==1)
				root=node;
			for(int j=1;j<=num;j++)
			{
				scanf("%d",&a);
				son[node].push_back(a);
			}
		}
		dfs(root,-1);
		int ans=min_cover();
		printf("%d\n",ans);
	}
system("pause");
return 0;
}

树的最小支配集,最小覆盖集和最大独立集

最大独立集+最小覆盖集=V

最大团=补图的最大独立集
/*
何为补图以及如何得到原图的补图?
(来自wiki)在图论里面,一个图G的补图(complement)或者反面(inverse)是一个图有着跟G相同的点,而且这些点之间有边相连当且仅当在G里面他们没有边相连。在制作图的时候,你可以先建立一个有G所有点的完全图,然后清除G里面已经有的边来得到补图。
*/
最小覆盖集=最大匹配

#include<stdio.h>
#include<stdlib.h>
#define maxn 10010
typedef struct Edge{
	int to;
	int w;
	int next;
}Edge;
Edge edge[maxn];
int head;
int fa[maxn];
int now=0;
int vex[maxn];
int n,m;
void dfs(int u,int father)
{
	fa[u]=father;
	vex[++now]=u;
	int k;
	for(k=head[u];k!=-1;k=edge[k].next)
	{
		int v=edge[k].to;
		if(v!=father)
			dfs(v,u);
	
	}
	return;
}
int min_control()//最小支配集
{
	bool set[maxn]={0};
	bool s[maxn]={0};
	int ans=0;
	int i;
	for(i=n;i>=1;i--)//按先序遍历的倒序遍历结点
	{
		int t=vex[i];
		if(!s[t])
		{
			if(!set[fa[t]])
			{
				set[fa[t]]=1;
				ans++;
			}
			s[t]=1;
			s[fa[t]]=1;
			s[fa[fa[t]]]=1;
		}
	}
	return ans;
}
int min_cover()//最小覆盖集
{
	bool set[maxn]={0};
	bool s[maxn]={0};
	int ans=0;
	int i;
	for(i=n;i>=2;i--)
	{
		int t=vex[i];
		if(!s[t] && !s[fa[t]])
		{
			set[fa[t]]=1;
			ans++;
			s[t]=1;
			s[fa[t]]=1;
		}
	}
	return ans;
}
int max_duli()//最大独立集
{
	bool set[maxn]={0};
	bool s[maxn]={0};
	int ans=0;
	int i;
	for(i=n;i>=1;i--)
	{
		int t=vex[i];
		if(!s[t])
		{
			set[t]=1;
			ans++;
			s[t]=1;
			s[fa[t]]=1;
		}
	}
	return ans;
}
int main()
{
	//读入图信息
	now=0;
	dfs(1,-1);
	int ans1=min_control();
	int ans2=min_cover();
	int ans3=max_duli();
system("pause");
return 0;
}

hdoj2874

    首先,因为题目的图时无向图且没有环,所以这题的图是=一棵树或者一个森林,这个题思路很巧妙,加上一个结点,这个结点到每棵树的根(可以用并查集先求出原图有几棵树,以及树的根的编号)都有一条边,且比边权为0.如果询问的两个点的最近公共祖先是这个虚设的结点,说明这两个点在两棵树中,not connected,否则就是普通的LCA问题。

    但是这题变态的地方在卡内存,试了很多方法都不行,于是尝试着变化数组大小,终于不再MLE了,可是不知何故WA。。下面第一份代码WA,第二份代码MLE。。

 

#include<stdio.h>
#include<stdlib.h>
#define maxn 10010
#define limit 225
typedef struct Pair{
	int vex;
	int num;
	Pair(int vex=0,int num=0):vex(vex),num(num)
	{}
}Pair;
typedef struct Edge{
	int to;
	int w;
	int next;
}Edge;
typedef struct Q{
	int u,v;
	int anc;
}Q;
int n,m,c;
int bin[maxn];
Edge edge[2*maxn];
Q q[1000010];
bool visit[maxn];
int dist[maxn];
int head[maxn];
Pair query[maxn][limit];
int find(int x)
{
	int r=x;
	while(bin[r]!=r)
		r=bin[r];
	int t=x,tmp;
	while(t!=r)
	{
		tmp=bin[t];
		bin[t]=r;
		t=tmp;
	}
	return r;
}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		bin[fx]=fy;
	return;
}
void lca(int u,int father)
{
	int i;
	visit[u]=1;
	if(father==-1)
		dist[u]=0;
	else
	{
		for(i=head[father];i!=-1;i=edge[i].next)
		{
			if(edge[i].to==u)
			{
				dist[u]=dist[father]+edge[i].w;
			}
		}
	}
	for(i=1;i<=query[u][0].vex;i++)
	{
		int v=query[u][i].vex;
		int num=query[u][i].num;
		if(visit[v])
			q[num].anc=find(v);
			
	}
	for(i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v!=father)
		{
			lca(v,u);
			merge(v,u);
		}
	}
	return;
}
int main()
{
	int i;
	while(scanf("%d %d %d",&n,&m,&c)!=EOF)
	{
		int a,b,k;

		for(i=1;i<=n+1;i++)
		{
			visit[i]=0;
			bin[i]=i;
			head[i]=-1;
			query[i][0].vex=0;

		}
		int cnt=0;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&k);
			merge(a,b);
			edge[++cnt].to=b;
			edge[cnt].w=k;
			edge[cnt].next=head[a];
			head[a]=cnt;

			edge[++cnt].to=a;
			edge[cnt].w=k;
			edge[cnt].next=head[b];
			head[b]=cnt;
		}
		for(i=1;i<=c;i++)
		{
			scanf("%d %d",&a,&b);
			q[i].u=a;
			q[i].v=b;
			Pair tmp;
			tmp.num=i;
			tmp.vex=b;
			int count=query[a][0].vex;
			query[a][++count]=tmp;
			query[a][0].vex=count;
			tmp.vex=a;
			count=query[b][0].vex;
			query[b][++count]=tmp;
			query[b][0].vex=count;
		}
		for(i=1;i<=n;i++)
		{
			if(bin[i]==i)
			{
				edge[++cnt].to=i;
				edge[cnt].w=0;
				edge[cnt].next=head[n+1];
				head[n+1]=cnt;
			}
		}
		for(i=1;i<=n+1;i++)
			bin[i]=i;
		lca(n+1,-1);
		for(i=1;i<=c;i++)
		{
			int u=q[i].u,v=q[i].v,anc=q[i].anc;
			if(anc==n+1)
				printf("Not connected\n");
			else
			{
				int ans=dist[u]+dist[v]-2*dist[anc];
				printf("%d\n",ans);
			}
		}
	}
system("pause");
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define maxn 10010
using namespace std;
typedef struct Pair{
    int vex;
    int num;
}Pair;
vector<Pair> query[maxn];
typedef struct Edge{
    int to;
    int w;
    int next;
}Edge;
typedef struct Q{
    int u,v;
    int anc;
}Q;
Q q[1000010];
Edge edge[2*maxn];
bool visit[maxn];
int dist[maxn];
int fa[maxn];
int bin[maxn];
int head[maxn];
int n,m,c;
int find(int x)
{
    int r=x;
    while(bin[r]!=r)
        r=bin[r];
    int t=x,tmp;
    while(t!=r)
    {
        tmp=bin[t];
        bin[t]=r;
        t=tmp;
    }
    return r;
}
void merge(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
        bin[fx]=fy;
    return;
}
void lca(int u,int father)
{
    int i;
    visit[u]=1;
    if(father==-1)
        dist[u]=0;
    else
    {
        for(i=head[father];i!=-1;i=edge[i].next)
        {
            if(edge[i].to==u)
            {
                dist[u]=dist[father]+edge[i].w;
            }
        }
    }
    int d=query[u].size();
    for(i=0;i<=d-1;i++)
    {
        int v=query[u][i].vex;
        int num=query[u][i].num;
        if(visit[v])
            q[num].anc=find(v);
            
    }
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v!=father)
        {
            fa[v]=u;
            lca(v,u);
            merge(v,u);
        }
    }
    return;
}
int main()
{
    int i;
    while(scanf("%d %d %d",&n,&m,&c)!=EOF)
    {
        int a,b,k;
        for(i=1;i<=n+1;i++)
        {
            visit[i]=0;
            bin[i]=i;
            fa[i]=-1;
            head[i]=-1;
            query[i].clear();

        }
        int cnt=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&a,&b,&k);
            merge(a,b);
            edge[++cnt].to=b;
            edge[cnt].w=k;
            edge[cnt].next=head[a];
            head[a]=cnt;

            edge[++cnt].to=a;
            edge[cnt].w=k;
            edge[cnt].next=head[b];
            head[b]=cnt;
        }
        for(i=1;i<=c;i++)
        {
            scanf("%d %d",&a,&b);
            q[i].u=a;
            q[i].v=b;
            Pair tmp;
            tmp.num=i;
            tmp.vex=b;
            query[a].push_back(tmp);
            tmp.vex=a;
            query[b].push_back(tmp);
        }
        for(i=1;i<=n;i++)
        {
            if(bin[i]==i)
            {
                edge[++cnt].to=i;
                edge[cnt].w=0;
                edge[cnt].next=head[n+1];
                head[n+1]=cnt;
            }
        }
        for(i=1;i<=n+1;i++)
            bin[i]=i;
        lca(n+1,-1);
        for(i=1;i<=c;i++)
        {
            int u=q[i].u,v=q[i].v,anc=q[i].anc;
            if(anc==n+1)
                printf("Not connected\n");
            else
            {
                int ans=dist[u]+dist[v]-2*dist[anc];
                printf("%d\n",ans);
            }
        }
    }
return 0;
}

小技巧,手动加大栈区,以及x&-x

    前文所述那道LCA的题,用c++提交居然爆栈,于是学到一个小技巧。

    手动加大栈区:#pragma comment(linker, “/STACK:102400000,102400000″)

    语法:/STACK:reserve,commit       前者为栈大小(vc6.0默认为1M),后者为保留在虚拟内存的页文件

以下摘录一段有用的文字(来自http://blog.csdn.net/sftxlin/article/details/6751190)

刚学树状数组,看到这里的时候懵了。经过询问,发现,原来在程序运行时,数据用的都是补码,于是解决了

int Lowbit(x)

{

  return x&(-x);

}

如:

x =1: 1 &-1(设位数为8)0000 0001 & 1111 1111 = 1

 x = 6:6 & -6   0000 0110

           &1111 1010 = 2

总结一下,其实就是:

求出2^p(其中p: x 的二进制表示数中, 右向左数第一个1的位置),如6的二进制表示为110,向左数第零个为0,第一个为1,则p=1,故Lowbit(6) = 2^1 = 2

看了这段文字,瞬间可以明白x&-x可以用来快速求出一个数的二进制表示其末尾有几个0

 

 

hdoj2586

    LCA的模板题,可是做了好几个钟头,当然都是在找错。。开始最近公共祖先用anc[maxn][maxn]存储,结果无情的无法运行。。the array  anc is too large。。然后果断用结构体数组来存储询问及对应的答案,提交结果RE,结果就这样RE到死了。。到最后才发现错在一个冷僻的角落,见下面代码,不过到现在我还是不明白为什么会错。。

    大体思路:先以点1为根dfs一遍转化成以1为根的有根树,同时确定每个点与根的距离,存入dist[]数组,再求lca

 distance of (u,v)=dist[u]+dist[v]-2*dist[lca(u,v)]

 

#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
#define maxn 40010
vector<int> query[maxn];
int dist[maxn];
int fa[maxn];
typedef struct Q{
	int u;
	int v;
	int anc;
}Q;
Q q[300];
typedef struct Edge{
	int to;
	int w;
	int next;
}Edge;
Edge edge[2*maxn];
int head[maxn];
int bin[maxn];
bool visit[maxn];
int m;
int find(int x)
{
	int r=x;
	while(bin[r]!=r)
		r=bin[r];
	int t=x,tmp;
	while(t!=r)
	{
		tmp=bin[t];
		bin[t]=r;
		t=tmp;
	}
	return r;
}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		bin[fx]=fy;
	return;
}
void dfs(int u,int father)
{
	int i;
	if(father==-1)
		dist[u]=0;
	else
	{
		for(i=head[father];i!=-1;i=edge[i].next)
		{
			if(edge[i].to==u)
			{
				dist[u]=dist[father]+edge[i].w;
				break;
            }
		}
	}
	for(i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v!=father)
		{
			fa[v]=u;
			dfs(v,u);
		}
	}
	return;
}
void lca(int u)
{
	int i;
	visit[u]=1;
	int d=query[u].size();
	for(i=0;i<=d-1;i++)//原来写成i<=query[u].size()-1,结果无限RE。。
	{
		int v=query[u][i];
		if(visit[v])
		{
			for(int j=1;j<=m;j++)
			{
 			    if((q[j].u==u && q[j].v==v)||(q[j].u==v && q[j].v==u))
        		{
					q[j].anc=find(v);
                    break; 			  
                }
 			}
        }
	}
	for(i=head[u];i!=-1;i=edge[i].next)
	{
        int v=edge[i].to;
		if(v!=fa[u])
		{
			lca(v);
			merge(v,u);
		}
	}
	return;
}
int main()
{
	int t,i,j;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d %d",&n,&m);
		for(i=1;i<=n;i++)
		{
			query[i].clear();
			head[i]=-1;
			fa[i]=-1;
			bin[i]=i;
			visit[i]=0;
		}
		int a,b,k,cnt=0;
		for(i=1;i<=n-1;i++)
		{
			scanf("%d %d %d",&a,&b,&k);
			edge[++cnt].to=b;
			edge[cnt].w=k;
			edge[cnt].next=head[a];
			head[a]=cnt;

			edge[++cnt].to=a;
			edge[cnt].w=k;
			edge[cnt].next=head[b];
			head[b]=cnt;
		}
		for(i=1;i<=m;i++)
		{
			scanf("%d %d",&a,&b);
			q[i].u=a;
			q[i].v=b;
			query[a].push_back(b);
			query[b].push_back(a);
		}
		fa[1]=-1;
		dfs(1,-1);
		lca(1);
		for(i=1;i<=m;i++)
		{
			int u=q[i].u,v=q[i].v;
			int ans=dist[u]+dist[v]-2*dist[q[i].anc];
			printf("%d\n",ans);
		}
	}
	//system("pause");
	return 0;
}

一个不错的计划(转载)

转载自:http://llvsi.com/lvsi%E7%9A%84acm%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92/

Lvsi的ACM训练计划

1 排序算法(平方排序算法的应用,Accepted快速排序,Accepted归并排序,时间复杂度下界,三种线性时间排序,外部排序)

2 数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余方程,中国剩余定理)
Running

3 搜索(BFS,优先队列,DFS)
Pending

4 矩阵(矩阵的概念和运算,二分求解线性递推方程,多米诺骨牌棋盘覆盖方案数,高斯消元)
Pending

5 字符串处理(AcceptedKMP,后缀树,有限状态自动机,Huffman编码,简单密码学)
Pending

6 组合数学(排列与组合,鸽笼原理,容斥原理,递推,Fibonacci数列,Catalan数列,Stirling数,差分序列,生成函数,置换,Polya原理)
Pending

7 动态规划(单调队列,凸完全单调性,树型动规,多叉转二叉,状态压缩类动规,四边形不等式)
Pending

8 概率论(简单概率,条件概率,Bayes定理,期望值)
Pending

9 博奕论(Nim取子游戏,博弈树,Shannon开关游戏)
Pending

10 指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示)
按位运算(and,or,xor,shl,shr,一些应用)
Pending

11 图论(图论模型的建立,平面图,欧拉公式与五色定理,求强连通分量,求割点和桥,欧拉回路,AOV问题,AOE问题,最小生成树的三种算法,最短路的三种 算法,标号法,差分约束系统,验证二分图,Konig定理,匈牙利算法,KM算法,稳定婚姻系统,最大流算法,最小割最大流定理,最小费用最大流算法)
Pending

12 计算几何(平面解几及其应用,向量,点积及其应用,叉积及其应用,半平面相交,求点集的凸包,最近点对问题,凸多边形的交,离散化与扫描)
Pending

13 数据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,斜堆,二项堆, 二叉查找树,AVL,Treap,Splay,静态二叉查找树,2-d树,线段树,二维线段树,矩形树,Trie树,块状链表)
Pending

14 微积分初步(极限思想,导数,积分,定积分,立体解析几何)
Pending

下面这个也不错额。
OJ上的一些水题(可用来练手和增加自信)
(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)

初期:
一.基本算法:
(1)枚举. (poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)
(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)
(6)堆
(7)trie树(静态建树、动态建树) (poj2513)
四.简单搜索
(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题. (poj1837,poj1276)
(2)型如下表的简单DP(可参考lrj的书 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学
(1)组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
(2)数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
(3)计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
(1)几何公式.
(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)

中级:
一.基本算法:
(1)C++的标准模版库的应用. (poj3096,poj3007)
(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
二.图算法:
(1)差分约束系统的建立和求解. (poj1201,poj2983)
(2)最小费用最大流(poj2516,poj2516,poj2195)
(3)双连通分量(poj2942)
(4)强连通分支及其缩点.(poj2186)
(5)图的割边和割点(poj3352)
(6)最小割模型、网络流规约(poj3308, )
三.数据结构.
(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)静态二叉检索树. (poj2482,poj2352)
(3)树状树组(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)并查集的高级应用. (poj1703,2492)
(6)KMP算法. (poj1961,poj2406)
四.搜索
(1)最优化剪枝和可行性剪枝
(2)搜索的技巧和优化 (poj3411,poj1724)
(3)记忆化搜索(poj3373,poj1691)

五.动态规划
(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)
(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)
六.数学
(1)组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.

(2)数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
(3)计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)随机化算法(poj3318,poj2454)
(5)杂题.
(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.
(1)坐标离散化.
(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多边形的内核(半平面交)(poj3130,poj3335)
(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级:
一.基本算法要求:
(1)代码快速写成,精简但不失风格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保证正确性和高效性. poj3434
二.图算法:
(1)度限制最小生成树和第K最短路. (poj1639)
(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最优比率生成树. (poj2728)
(4)最小树形图(poj3164)
(5)次小生成树.
(6)无向图、有向图的最小环
三.数据结构.
(1)trie图的建立和应用. (poj2778)
(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法
(RMQ+dfs)).(poj1330)
(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的
目的). (poj2823)
(4)左偏树(可合并堆).
(5)后缀树(非常有用的数据结构,也是赛区考题的热点).
(poj3415,poj3294)
四.搜索
(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.动态规划
(1)需要用数据结构优化的动态规划.
(poj2754,poj3378,poj3017)
(2)四边形不等式理论.
(3)较难的状态DP(poj3133)
六.数学
(1)组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
(2)博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.
(1)半平面求交(poj3384,poj2540)
(2)可视图的建立(poj2966)
(3)点集最小圆覆盖.
(4)对踵点(poj2079)

八.综合题.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

———————————————————————————————–
———————————————————————————————–
以及补充
Dp状态设计与方程总结
1.不完全状态记录
<1>青蛙过河问题
<2>利用区间dp
2.背包类问题
<1> 0-1背包,经典问题
<2>无限背包,经典问题
<3>判定性背包问题
<4>带附属关系的背包问题
<5> + -1背包问题
<6>双背包求最优值
<7>构造三角形问题
<8>带上下界限制的背包问题(012背包)
3.线性的动态规划问题
<1>积木游戏问题
<2>决斗(判定性问题)
<3>圆的最大多边形问题
<4>统计单词个数问题
<5>棋盘分割
<6>日程安排问题
<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)
<8>方块消除游戏(某区间可以连续消去求最大效益)
<9>资源分配问题
<10>数字三角形问题
<11>漂亮的打印
<12>邮局问题与构造答案
<13>最高积木问题
<14>两段连续和最大
<15>2次幂和问题
<16>N个数的最大M段子段和
<17>交叉最大数问题
4.判定性问题的dp(如判定整除、判定可达性等)
<1>模K问题的dp
<2>特殊的模K问题,求最大(最小)模K的数
<3>变换数问题
5.单调性优化的动态规划
<1>1-SUM问题
<2>2-SUM问题
<3>序列划分问题(单调队列优化)
6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)
<1>凸多边形的三角剖分问题
<2>乘积最大问题
<3>多边形游戏(多边形边上是操作符,顶点有权值)
<4>石子合并(N^3/N^2/NLogN各种优化)
7.贪心的动态规划
<1>最优装载问题
<2>部分背包问题
<3>乘船问题
<4>贪心策略
<5>双机调度问题Johnson算法
8.状态dp
<1>牛仔射击问题(博弈类)
<2>哈密顿路径的状态dp
<3>两支点天平平衡问题
<4>一个有向图的最接近二部图
9.树型dp
<1>完美服务器问题(每个节点有3种状态)
<2>小胖守皇宫问题
<3>网络收费问题
<4>树中漫游问题
<5>树上的博弈
<6>树的最大独立集问题
<7>树的最大平衡值问题
<8>构造树的最小环

lca tarjan算法

    在LCA问题中,当询问量较小时可以用前文所述方法解决,但是当询问量很大时就行不通了,这时候大名鼎鼎的lca tarjan算法就登场了。

    tarjan算法基于dfs,今天从凌晨开始看这个算法,一直有点晕,但后来看到一个flash动画,顿时彻悟。。

    主要参考博文:http://comzyh.tk/blog/archives/492/    (里面的动画让我颇为受益)

    具体步骤如下:

           

  • 先用随便一种数据结构(链表就行),把关于某个点的所有询问标在节点上,保证遍历到一个点,能得到所有有关这个节点LCA 查询
  • 建立并查集.注意:这个并查集只可以把叶子节点并到根节点,即getf(x)得到的总是x的祖先
  • 深度优先遍历整棵树,用一个Visited数组标记遍历过的节点,每遍历到一个节点将Visite[i]设成True 处理关于这个节点(不妨设为A)的询问,若另一节点(设为B)的Visited[B]==True,则回应这个询问,这个询问的结果就是getf(B). 否则什么都不做
  • 当A所有子树都已经遍历过之后,将这个节点用并查集并到他的父节点(其实这一步应该说当叶子节点回溯回来之后将叶子节点并到自己,并DFS另一子树)
  • 当一颗子树遍历完时,这棵子树的内部查询(即LCA在这棵子树内部)都已经处理了

    其实我还看到网上一些博文包括wiki对这个算法的描述与上述步骤有出入,主要不同在于先递归的dfs当前点的子树,子树全递归访问完才设置当前点为已访问并处理lca询问,其实这两种方案都是可以的,两者的差别仅在于处理lca(u,v)的时机不一样(设当前点为u,v为u的子孙结点)(大家可以对照上面给出链接中的动画分析一下),希望我理解没有错。。

比较重要的一点是:当当前点的一棵子树遍历完返回当前点时,此时要将该子树的集合与当前点的集合合并,注意合并的时候一定要子树集合并到当前点集合(也就是让子树并到父亲结点,这样才能保证回答询问时给出正确的答案)

    通过上述表述,相信大家也都看到了,lca tarjan算法显然是个离线的算法,必须先知道所有询问,而且回答的顺序(指的是得到答案的顺序)和询问顺序可能不同(其实往往是不同的)。由于只要遍历整棵树一次(O(m))就能回答所有询问,又因为路径压缩后的并查集效率可以看做常数,所以回答q个询问的时间为O(q),总的为O(m+q),同时应当注意到m=n-1。所以总的渐进时间复杂度是O(n+q)。比起前文的“土办法”,相当高效了吧

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#define maxn 1010
using namespace std;
vector<int> son[maxn];//存放树
vector<int> query[maxn];//query[u][v]为一个lca询问
int bin[maxn];
bool visit[maxn];//标示结点是否已经被访问
int ans[maxn][maxn];//ans[u][v]标示lca(u,v),即答案
int find(int x)
{
	int r=x;
	while(bin[r]!=r)
		r=bin[r];
	int t=x,tmp;
	while(t!=r)
	{
		tmp=bin[t];
		bin[t]=r;
		t=tmp;
	}
	return r;
}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		bin[fx]=fy;
	return;
}
void lca(int u)
{
	int i;
	bin[u]=u;
	visit[u]=1;
	int d=query[u].size();
	for(i=0;i<=d-1;i++)
	{
		int v=query[u][i];
		if(visit[v])
			ans[u][v]=find(v);
	}
	d=son[u].size();
	for(i=0;i<=d-1;i++)
	{
		lca(son[u][i]);
		merge(son[u][i],u);//当一棵子树遍历完了,就把子树并到父结点。注意顺序,一定是子树并到父结点
	}
	return;

}
int main()
{
	memset(visit,0,sizeof(visit));
	//读入图
	lca(root);
	//system("pause");
	return 0;
}

poj1330——dfs+LCA

    今天凌晨开始看LCA问题。。

    对于询问不多的情况,不需要用lca—tarjan算法,dfs即可。

    具体思路:

        1.先对整棵树dfs一遍,为每个结点标上深度。

        2.读入边数据的时候将每个点的父结点存入fa[]数组,这样一来可以方便的找到根结点(fa[root]=-1),二来后面求LCA有用。

        3.最后就是求LCA(u,v)了:如果u的深度大于v,则u向上一步(u=fa[u]),否则v向上一步,重复这个操作直到u=v。这时的u就是所求最近公共祖先

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#define maxn 10010
using namespace std;
int depth[maxn];
vector<int> head[maxn];
void dfs(int u,int dep)
{
	int i;
	int d=head[u].size();
	depth[u]=dep;
	for(i=0;i<=d-1;i++)
		dfs(head[u][i],dep+1);
	return;
}
int main()
{
	int t,i;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		int fa[maxn];
		memset(fa,-1,sizeof(fa));
		memset(depth,0,sizeof(depth));
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			head[i].clear();
		for(i=1;i<=n-1;i++)
		{
			int a,b;
			scanf("%d %d",&a,&b);
			head[a].push_back(b);
			fa[b]=a;
		}
		int u,v;
		scanf("%d %d",&u,&v);
		for(i=1;i<=n;i++)
			if(fa[i]==-1)
				break;
		dfs(i,1);
		int x=u,y=v;
		while(x!=y)
		{
			if(depth[x]>depth[y])
				x=fa[x];
			else
				y=fa[y];
		}
		printf("%d\n",x);
	}
	//system("pause");
	return 0;
}

无根树转成有根树

/*
输入无根树的结点总数n,以及n-1条边,输出把点u作为根的有根树的各点的父结点
*/
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define maxn 1010
using namespace std;
vector<int> head[maxn];//用做邻接表
int fa[maxn];
void read_tree()
{
	int n,i;
	int u,v;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&u,&v);
		head[u].push_back(v);
		head[v].push_back(u);
	}
	return;
}
//以u为根,计算各点的父结点
void dfs(int u,int father)
{
	int i;
	int d=head[u].size();
	for(i=0;i<=d-1;i++)
	{
		if(head[u][i]!=fa)
		{
			fa[i]=u;
			dfs(i,u);
		}
	}
	return;
}
int main()
{
	fa[root]=-1;
	read_tree();
	dfs(root,-1);//以root为根

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

hdoj2112

这题题意很明确,就是求最短路,但是顶点不是整数表示,而是字符串,这个有点拙计,于是上网看到了一个不错的解决办法(代码中的find()):
1.设置name数组,数组元素为字符串,用于保存站点
2.设置变量cnt表示站点数,初始为0
3.每次读入两个字符串,然后从name数组中寻找,如果找到,则返回下标,否则++cnt,返回cnt

本题另外一个要注意的问题是平行边。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 160
int map[maxn][maxn];
char name[160][40];
int cnt=0;
int find(char str[])//新学到的小技巧。。
{
	int i;
	for(i=1;i<=cnt;i++)
		if(strcmp(name[i],str)==0)
			return i;
	if(cnt==0||i==cnt+1)
	{
		strcpy(name[++cnt],str);
		return cnt;
	}
}
bool spfa(int s,int n,int map[][maxn],int* dist)
{
	int i;
	int outque[maxn];
	int queue[maxn*maxn+10];
	bool visit[maxn];
	memset(outque,0,sizeof(outque));
	memset(visit,0,sizeof(visit));
	int iq=0,front=0;
	for(i=1;i<=n;i++)
	{
		dist[i]=100;
	}
	dist[s]=0;
	queue[iq++]=s;
	visit[s]=1;
	int top;
	while(front!=iq)
	{
		top=queue[front++];
		visit[top]=0;
		outque[top]++;
		if(outque[top]>n-1) return false;
		for(i=1;i<=n;i++)
		{
			if(map[top][i]!=100 && top!=i && dist[top]+map[top][i]<dist[i])
			{
				dist[i]=dist[top]+map[top][i];
				if(!visit[i])
				{
					queue[iq++]=i;
					visit[i]=1;
				}
			}
		}
	}
	return true;
}
int main()
{
	int n,i,j;
	scanf("%d",&n);
	getchar();
	while(n!=-1)
	{
		char start[40],end[40];
		scanf("%s %s",start,end);
		getchar();
		cnt=0;
		int k=n;
		for(i=1;i<=150;i++)
			for(j=1;j<=150;j++)
			{
				map[i][j]=(i==j?0:100);
			}
		while(k--)
		{
			char str1[40],str2[40];
			int w;
			scanf("%s %s %d",str1,str2,&w);
			int a=find(str1);
			int b=find(str2);
			if(map[a][b]>w)
			{
				map[a][b]=w;
				map[b][a]=w;
			}
		}
		int s,d;
		s=find(start);
		d=find(end);
		int dist[maxn];
		spfa(s,cnt,map,dist);
		if(dist[d]==100)
			printf("-1\n");
		else
			printf("%d\n",dist[d]);

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

hdoj1596

最短路变形,边权不是加起来而是乘起来,其实一样的,初始化要改动一下。当然这题完全可以用dij来做,但为了熟悉spfa,所以就用spfa来写了。就当写个模板。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 1010
double map[maxn][maxn];
int queue[maxn*maxn];
bool spfa(int s,int n,double map[][maxn],double* dist)
{
	int i,k;
	int visit[maxn];
	int iq=0;
	int top;
	int outque[maxn];
	for(i=1;i<=n;i++)
	{
		dist[i]=0;
	}
	memset(visit,0,sizeof(visit));
	memset(outque,0,sizeof(outque));
	queue[iq++]=s;
	visit[s]=1;
	dist[s]=1;
	int front=0;
	while(front!=iq)
	{
		top=queue[front++];
		visit[top]=0;
		outque[top]++;
		if(outque[top]>n-1) return false;
		for(i=1;i<=n;i++)
		{
			if(map[top][i]!=0 && i!=top && dist[top]*map[top][i]>dist[i])
			{
				dist[i]=dist[top]*map[top][i];
				if(!visit[i])
				{
					visit[i]=1;
					queue[iq++]=i;
				}
			}
		}
	}
	return true;

}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int i,j,q;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				scanf("%lf",&map[i][j]);
			}
		scanf("%d",&q);
		for(i=1;i<=q;i++)
		{
			int s,d;
			scanf("%d %d",&s,&d);
			double dist[maxn];
			spfa(s,n,map,dist);
			if(dist[d]==0)
				printf("What a pity!\n");
			else
				printf("%.3lf\n",dist[d]);

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

hdoj1222

不难得到有安全hole的条件是:
(1)n>=m:n能被m整除且m!=1
(2)m>n:
1)m%n!=0:n能被(m%n)整除且(m%n)!=1
2)m%n==0(因为这个没考虑导致run time error一次。。)
(3)注意特殊情况n=1,此时不管m是多少一定没有安全hole。。(因为这个WA一次。。)
起初在想一个比较傻的问题:n>m时是否可能出现第二(也可以是三、四等等)圈时没有走到访问过的点(错开了),而之后走第k圈的时候走到了一个以前访问过的点,之后循环访问这些点?
其实这是不可能的,这个问题有点二。。用反证可以证明:假设之后第k圈的时候访问了以前已经访问的某点,那么从这个时刻往前反推,当反推到第二圈时,可以发现推出的点并不是原来第二圈时走过的点(错开的点),矛盾。可知第二圈时不可能错开。(k=3试试,这样更好理解)

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int m,n;
		scanf("%d %d",&m,&n);
		if(n==1)
			printf("NO\n");
		else if(n>=m)
		{
			if(n%m==0 && m!=1)
				printf("YES\n");
			else
				printf("NO\n");
		}
		else
		{
			if(m%n==0)
				printf("YES\n");
			else if((n%(m%n))==0 && m%n!=1)
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
/system("pause");
return 0;
}

扩展欧几里得算法

温故一下,好久没做数论题,都快忘光了。看下扩展欧几里得

/*
1.如果ax+by=c的一组解为(x0,y0),则它的任意整数解都可以写成(x0+kb',y0-ka'),其中a'=a/gcd(a,b),b'=b/gcd(a,b),k取任意整数
2.如何求ax+by=c的一组解(x0,y0)?
	设a、b、c为任意整数,ax+by=gcd(a,b)的一组解是(x0,y0),则
	(1)当c是gcd(a,b)的倍数时,ax+by=c的一组解是(x0*(c/gcd(a,b)),y0*(c/gcd(a,b)))
	(2)当c不是gcd(a,b)的倍数时,ax+by=c无整数解
*/
//计算使ax+by=gcd(a,b)的x、y(x、y可以为负)
//a、b中有一个为0时特殊考虑
void exgcd(int a,int b,int& d,int& x,int& y)
{
	if(!b)
	{
		d=a;
		x=1;
		y=0;
	}
	else
	{
		exgcd(b,a%b,d,y,x);
		y-=x*(a/b);
	}
	return;
}