前面的因为超字数发不了了，所以只好分成几篇发。。。

4. 搜索

4.1 DFS

4.1.1 图的深度优先遍历

编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含n个顶点，编号为0至n-1。本题限定在深度优先遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点0为遍历起点。

#include
using namespace std;
vector<int>t[20010];
int visited[20010];

void dfs(int p)
{
	if(visited[p])
	return;
	visited[p]=1;
	cout<<p<<' ';
	for(int i=0;i<t[p].size();i++)
	{
		if(visited[t[p][i]])
		continue;
		dfs(t[p][i]);
	}
}

int main()
{
	int n,e,i,j;
	cin>>n>>e;
	while(e--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		t[a].push_back(b);
	}
	for(i=0;i<n;i++)
	{
		for(int p=0;p<t[i].size();p++)
		{
			int temp=p;
			for(j=p+1;j<t[i].size();j++)
			{
				if(t[i][j]<t[i][temp]) 
				temp=j;
			}
			swap(t[i][p],t[i][temp]);
		}
	}
	for(i=0;i<n;i++)
	dfs(i);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

4.1.2 排列数和组合数

排列数
按照字典序输出n的全排列。

#include
using namespace std;
int vis[12],a[12],n;

void dfs(int cnt)
{
	if(cnt==n)
	{
		for(int i=0;i<n;i++)
			printf("%d ",a[i]);
		printf("\n");
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			vis[i]=1;
			a[cnt]=i;
			dfs(cnt+1);
			vis[i]=0;
		}
	}
	return;
}

int main()
{
	cin>>n;
	dfs(0);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

组合数

#include
using namespace std;

int n,m;
vector<int>vec;

void dfs(int k)
{
    if(vec.size()>m||vec.size()+(n-k+1)<m) return;
    //到达枚举边界，输出结果并结束。可以剪枝。
    if(k==n+1)
    {
        for(int i=0;i<vec.size();i++)
            cout<<vec[i]<<" ";
        cout<<endl;
        return;
    }
    //选择这个数
    vec.push_back(k);
    dfs(k+1);
    //回溯
    vec.pop_back();
    //不选择这个数
    dfs(k+1);
}

int main()
{
    cin>>n>>m;
    dfs(1);
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

Gosper’s Hack是一种生成n元集合所有k元子集的算法。

void Gospers_Hack(int k, int n)
{
    int cur=(1<<k)-1;
    while(cur<1<<n)
    {
        int lowbit=cur&-cur;
        int high=cur+lowbit;
        cur=(((high^cur)>>2)/lowbit)|high;
    }
}
1
2
3
4
5
6
7
8
9
10

Gospers_Hack(3,5)
{
	cur=00111;
	while(cur<100000)
	{
		lowbit=00001;
		high=01000;
		high^cur=01111;
		(high^cur)>>2)=00011;
		(high^cur)>>2)/lowbit)=00011;(抹掉末尾0)
		cur=01011;
		......
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.1.3 树的遍历

树的深度优先遍历
调用根结点$dfs(root)$

void dfs(int x)
{
	vis[x]=1;
	for(int i=head[x];i;i=nex[i])
	{
		int y=ver[i];
		if(vis[y]) continue;
		dfs(y);
	}
}
1
2
3
4
5
6
7
8
9
10

树的DFS序
对树进行深度优先遍历时，对于每个结点，在刚进入递归后以及即将回溯时各记录一次结点编号，每个结点x在序列中恰好出现两次。

void dfs(int x)
{
	a[++m]=x;
	vis[x]=1;
	for(int i=head[x];i;i=nex[i])
	{
		int y=ver[i];
		if(vis[y]) continue;
		dfs(y);
	}
	a[++m]=x;
}
1
2
3
4
5
6
7
8
9
10
11
12

树的深度

void dfs(int x)
{
	vis[x]=1;
	for(int i=head[x];i;i=nex[i])
	{
		int y=ver[i];
		if(vis[y]) continue;
		depth[y]=depth[x]+1;
		dfs(y);
	}
}
1
2
3
4
5
6
7
8
9
10
11

树的重心
有的时候题目不给明哪个是根结点（所有节点都可以是根结点），可以通过一次dfs找到树的重心来尽量避免“树大根深”的情况。
树的重心：设max_part(x)表示在删除结点x后产生的子树中，最大的一棵的大小。使得max_part取最小值的结点p即为树的重心。

void dfs(int x)
{
	vis[x]=1;size[x]=1;//子树x的大小 
	int max_part=0;
	for(int i=head[x];i;i=nex[i])
	{
		int y=ver[i]; 
		if(vis[y]) continue;
		dfs(y);
		size[x]+=size[y];
		max_part=max(max_part,size[y]);//找最大子树 
	}
	max_part=max(max_part,n-size[x]);
	if(max_part<ans)
	{
		ans=max_part;//记录重心对应的最大子树规模 
		pos=x;//记录重心 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

连通块划分

void dfs(int x)
{
	v[x]=cnt; 
	int max_part=0;
	for(int i=head[x];i;i=nex[i])
	{
		int y=ver[i]; 
		if(vis[y]) continue;
		dfs(y);
	}
}
int main()
{
	for(int i=1;i<=n;i++)
	{
		if(!v[i])
		{
			cnt++;
			dfs(i);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.1.4 剪枝

剪枝

1. 优化搜索顺序
2. 排除冗余信息
3. 可行性剪枝（照当前分支这样走后面不可能达成）
4. 最优性剪枝（照当前分支这样走的最优解都比当前解差）
5. 记忆化搜索

166. 数独

主要考虑优化搜索顺序，从可选的数少的空格开始试探。所以我们在每次搜索时都判断一下哪个格子的可选到数最小。

#include 
using namespace std;
const int N=9;
string str;
int mp[1<<N],nums[1<<N],row[N],col[N],cell[N][N];

inline int lowbit(int x)
{
	return x&(-x);
}

int get(int x,int y)
{
	return row[x]&col[y]&cell[x/3][y/3];//求出这一个位置可能会被填哪些数字 
}

void init()//初始化：所有位所有数字都可以填 
{
	for(int i=0;i<N;i++) 
		row[i]=col[i]=(1<<N)-1;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			cell[i][j]=(1<<N)-1;
}

bool dfs(int cnt)
{
	if(cnt==0) return true;//所有待填数字都已经被填上 
	int minn=10,x,y;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		{
			if(str[i*9+j]=='.')
			{
				int temp=nums[get(i,j)];
				if(temp<minn)
				{
					minn=temp;
					x=i,y=j;
				}
			}
		}//找到所有剩下的待填格中数字集合最小的一个，是一个剪枝过程 
	for(int i=get(x,y);i;i-=lowbit(i))//枚举这一格所有可能填的数字 
	{
		int t=mp[lowbit(i)];
		row[x]-=(1<<t);
		col[y]-=(1<<t);
		cell[x/3][y/3]-=(1<<t);
		str[x*9+y]='1'+t;
		if(dfs(cnt-1)) return true;
		row[x]+=(1<<t);
		col[y]+=(1<<t);
		cell[x/3][y/3]+=(1<<t);
		str[x*9+y]='.';//复原 
	}
	return false;
}


int main()
{
	for(int i=0;i<N;i++) mp[1<<i]=i;//预先存下二进制1所在的位置 
	for(int i=1;i<(1<<N);i++)
		for(int j=i;j;j-=lowbit(j)) nums[i]++;
		//预先存下每个之后可能会枚举到的二进制数内有几个1 
	while(cin>>str&&str[0]!='e')
	{
		init();
		int cnt=0;
		for(int i=0,k=0;i<9;i++)
			for(int j=0;j<9;j++,k++)
			{
				if(str[k]!='.')
				{
					int t=str[k]-'1';//1~9映射到0~8 
					row[i]-=(1<<t);
					col[j]-=(1<<t);
					cell[i/3][j/3]-=(1<<t);
				}//这一位数字是题给的，把它存进对应位置 
				else cnt++;//待填数字+1 
			}
		dfs(cnt);
		cout<<str<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

4.1.5 迭代加深

搜索树规模随着层次的深入增长很快，并且能够确保答案在一个较浅层的结点内——>限制搜索深度，每次在该深度内找不到答案就返回，增加一单位深度后再搜索。这会导致重复搜索浅层，但这比起庞大的子树来微不足道。比如是二叉树，$1+2+2^2+2^3+...+2^{depth-1}<2^{depth}$

170. 加成序列

#include
using namespace std;
const int N=10010;
int path[N],st[N],n;

bool dfs(int u,int depth)
{
	if(u==depth) return path[u-1]==n;//最后一个数是n即找到答案 
	bool st[N]={0};
	for(int i=u-1;i>=0;i--)
		for(int j=i;j>=0;j--)//优化搜索顺序，i和j从大到小枚举
		{
			int temp=path[i]+path[j];
			if(!st[temp]&&temp<=n&&path[u-1]<temp)
			//!st[temp]剪枝，因为有多种可能的 temp=path[i]+path[j]，但是只需要搜索一次
			//这个数一定<=n且比前一层的数大 
			{
				path[u]=temp;
				st[temp]=1;
				if(dfs(u+1,depth)) return true;
			}
		}
		
	return false;
}
int main()
{
	path[0]=1;
	while(cin>>n,n)
	{
		int depth=1;
		while(!dfs(1,depth)) depth++;//迭代加深的过程
		for(int i=0;i<depth;i++)
			cout<<path[i]<<' ';
		cout<<endl;
	}
	return 0; 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

4.1.6 双向搜索

从初态和终态出发各搜索一半状态，产生两棵深度减半的搜索树，在中间交会、组合成最终的答案。

171. 送礼物

把礼物分成前一半，后一半，对于前一半，就暴搜，记录每次搜索完成后的总重量；对于后一半，也暴搜，每次搜索完成后与前一半合并。怎么合并？在前一半二分出一个重量，这个重量和后一半暴搜完的重量加起来不超过w而且尽可能大。用ans记录最大的一个合并总重。

#include
#define llg long long
#define inf 0x3ffffff

using namespace std;

const int N=46;
llg weight[1<<24],ans,g[N],w,n,k,cnt,tot;

void dfs1(int v,int s)
{
	if(v==k)
	{
		weight[cnt++]=s;
		return;
	}
	if((llg)s+g[v]<=w) dfs1(v+1,s+g[v]);//选 
	dfs1(v+1,s);//不选 
}

void dfs2(int v,int s)
{
	if(v==n)
	{
		llg l=0,r=tot-1;
		while(l<r)
		{
			llg mid=(l+r+1)>>1;
			if(weight[mid]+(llg)s<=w) l=mid;
			else r=mid-1;
		}
		ans=max(ans,s+weight[l]);
		return;
	}
	if((llg)s+g[v]<=w) dfs2(v+1,s+g[v]);//选 
	dfs2(v+1,s);//不选 
}
int main()
{
	cin>>w>>n;
	for(int i=0;i<n;i++)
		scanf("%lld",&g[i]);
	sort(g,g+n);
	reverse(g,g+n);
	k=n/2;
	dfs1(0,0);
	sort(weight,weight+cnt);
	tot=unique(weight,weight+cnt)-weight;
	dfs2(k,0);
	cout<<ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

4.2 BFS

求最长路

// 1:50ms /  3.21MB /  863B C++14 (GCC 9) O2
// 2:48ms /  3.13MB /  877B C++14 (GCC 9) O2
#include 
using namespace std;
queue<int>q;
int n,m;
int maxn[1510],vis[1510];
//maxn：到当前结点之前的最长路 
 
struct Edge
{
	int from;
	int to;
	int w;
}edge[50010];
vector<Edge>vec[50010];//vec为Edge型的，在已知起点时可直接通过这个调用出边权和终点 
 
void SPFA1(int start)
{
	maxn[start]=0;
	q.push(start);
	while(q.size())
	{
		int now=q.front();//每次取出队首元素 
		q.pop();
		for(int j=0;j<vec[now].size();j++)//遍历队首元素指向的所有结点 
		{
			if(maxn[vec[now][j].to]<maxn[now]+vec[now][j].w)
			{
				maxn[vec[now][j].to]=maxn[now]+vec[now][j].w;
				//如果from之前的最长路加上边权大于之前获得的to之前的最长路，就更新一下 
				q.push(vec[now][j].to);
				//只有当需要更新的时候才需要将to压入队列，否则from的前驱中一定会有结点到 to的更长路径，而当时已经入队过了 
			} 
		}
	}
}
 
void SPFA2(int start)
{
	maxn[start]=0;
	vis[start]=1;
	q.push(start);
	while(q.size())
	{
		int now=q.front();
		q.pop();
		vis[now]=0;
		for(int i=0;i<vec[now].size();i++)
		{
			if(maxn[vec[now][i].to]<maxn[now]+vec[now][i].w)
			{
				maxn[vec[now][i].to]=maxn[now]+vec[now][i].w;
				if(!vis[vec[now][i].to])
				{
					vis[vec[now][i].to]=1;
					q.push(vec[now][i].to);
				}
			}
		}
	}
}
 
int main()
{
	int i;
	cin>>n>>m;
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].w);
		vec[edge[i].from].push_back(edge[i]);
	}
	memset(maxn,-1,sizeof(maxn));
	SPFA2(1);
	cout<<maxn[n];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

5.模块化

5.1 快读

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
1
2
3
4
5
6
7

5.2 二分

lower_bound(vec.begin(),vec.end(),x)查找>=x的元素中最小的一个，并返回该元素的迭代器。
upper_bound(vec.begin(),vec.end(),x)查找>x的元素中最小的一个，并返回该元素的迭代器。

二分查找

#include
using namespace std;
int a[1001],cnt=0,n;
int Binary(int a[],int x)
{
    int l=0,r=n-1,flag=0,mid;
    while(l<=r)
    {
        cnt++;
        int mid=(l+r)>>1;
        if(a[mid]<=x)
        {
            if(a[mid]==x) return mid;
            else l=mid+1;
        }
        else r=mid-1;
    }
    return -1;
}

int main()
{
    int x;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>x;
    sort(a,a+n);
    cout<<Binary(a,x)<<endl;
    cout<<cnt;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

三分
给出一个 N 次函数，保证在范围 [l, r] 内存在一点 x，使得 [l, x]上单调增，[x, r]上单调减。试求出 xx 的值。

#include
using namespace std;
int n;
double co[14],l,r;
double f(double x)
{
	double ans=0;
    for(int i=n;i>=0;i--) 
		ans=ans*x+co[i];
    return ans;
}
int main()
{
	cin>>n>>l>>r;
	for(int i=n;i>=0;i--)
		cin>>co[i];
	while(r-l>=1e-6)
	{
		double lmid=l+(r-l)/3.0;
		double rmid=r-(r-l)/3.0;
		if(f(lmid)<f(rmid)) l=lmid;
		else r=rmid;
	}
	cout<<l;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

5.3 倍增

给定一个长度为 NN 的数列，和 MM 次询问，求出每一次询问的区间内数字的最大值。

#include
using namespace std;
int n,m,f[100010][20];
 
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		f[i][0]=read();
	int t=log(n)/log(2);
	for(int j=1;j<=t;j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			//f[i][j]表示起始点为i，长度为2^{j}的区间
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	while(m--)
	{
		int r,l;
		l=read(),r=read();
		int k=log(r-l+1)/log(2);
		int ans=max(f[l][k],f[r-(1<<k)+1][k]);
		printf("%d\n",ans);
	}
	return 0;		
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

5.5 离散化

for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]),b[i]=a[i];
sort(b+1,b+n+1);
unique(b+1,b+n+1)-(b+1);
for(int i=1;i<=n;i++)
	a[i]=lower_bound(b+1,b+n+1,a[i])-b;
1
2
3
4
5
6

6.字符串

6.1 字符串哈希

给定 N 个字符串（第 i个字符串长度为$M_i$，字符串内包含数字、大小写字母，大小写敏感），请求出 N个字符串中共有多少个不同的字符串。

#include
using namespace std;
map<int,bool>vis;//or setsetting;
int mod=1e9+7;
int base=13331;
int turn(char ch)
{
	if(ch>='0'&&ch<='9')
	return ch-'0'+1;
	if(ch>='A'&&ch<='Z')
	return ch-'A'+11;
	if(ch>='a'&&ch<='z')
	return ch-'a'+37;
}
 
int main()
{
	int N,cnt=0;
	cin>>N;
	while(N--)
	{
		string s;
		cin>>s;
		int ha=0;
		for(int i=0;i<s.size();i++)
		{
			ha=(1ll*ha*base%mod+turn(s[i]))%mod;
		}
		if(!vis[ha])//setting.insert(ha);
		cnt++;
		vis[ha]=1;
	}
	cout<<cnt;//cout<
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

给定一个字符串 text 和一个模式串 pattern，求 pattern 在text 中的出现次数。text 和 pattern 中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern 可重叠。

#include 
using namespace std;
string str,S;
int hashh[1000005],hashstr=0;
long long subhash=0;
int base=13331,mod=1e9+7;
int cnt=0;
 
int main()
{
	cin>>S>>str;
	int i,j;
	//cout<<"base "<
	for(i=0;i<str.size();i++)
	{
		hashstr=(1ll*hashstr*base%mod+str[i]-'A'+1+mod)%mod;
		//一般而言需要-'A'+1，也就是'A'对应的hash值为1，如果'A'对应的hash值为0则容易冲突
	}
	int len=str.size();
	int p=1;
	for(i=1;i<=len;i++)
	{
		p=1ll*p*base%mod;
	}
	hashh[0]=(S[0]-'A'+1+mod)%mod;
	for(i=1;i<S.size();i++)
	{
		hashh[i]=(1ll*hashh[i-1]*base%mod+S[i]-'A'+1+mod)%mod;
		if(i>=len-1)
		{
			if(i==len-1)
			subhash=hashh[len-1];
			else if(i>len-1)
			{
				subhash=(mod+hashh[i]-1ll*hashh[i-len]*p%mod)%mod;
			}
			//cout<<"subhash "<
			if(subhash==hashstr)
				cnt++;
			//cout<
		}
	}
	cout<<cnt;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

6.2 KMP

#include 
using namespace std;
const int N=1000010;
char s1[N],s2[N];
int co[N],f[N];

int main()
{
	scanf("%s%s",s1+1,s2+1);
	int n=strlen(s1+1),m=strlen(s2+1);
	for(int i=2,j=0;i<=m;i++)
	{
		while(j>0&&s2[j+1]!=s2[i]) j=co[j];
		if(s2[j+1]==s2[i]) j++;
		co[i]=j;
	} 
	//ABABABC
	//ABA
	for(int i=1,j=0;i<=n;i++)
	{
		while(j>0&&(j==n||s2[j+1]!=s1[i])) j=co[j];
		if(s2[j+1]==s1[i]) j++;
		f[i]=j;
		if(f[i]==m) cout<<i-m+1<<endl;
	}
	for(int i=1;i<=m;i++)
		printf("%d ",co[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28