连通情况
4连通
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1} 

8连通
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};

日连通
int dx[]={-2,-2,-1,-1,1,1,2,2};
int dy[]={-1,1,-2,2,-2,2,-1,1};

//象连通
int dx[]={-2,-2,2,2};
int dy[]={-2,2,-2,2} 

宽度优先搜索
 
// 连通块模型 
void bfs(int x,int y)
{
	queue<Node> q;
	q.push({x,y});
	st[x][y]=1;
	while(q.size())
	{
		Node t=q.front();
		q.pop();
		int x=t.x,y=t.y;
		for(int i=0;i<8;i++)
		{
			int a=x+dx[i],b=y+dy[i];
			if(a<0 || a>=n || b<0 || b>=m)//越界 
			{
				continue;
			}
			if(g[a][b]=='.')//不能走 
			{
				continue;
			}
			if(st[a][b])//已经走过 
			{
				continue;
			}
			st[a][b]=1;//标记 
			q.push({a,b});//入队 
		}
	}
}

//最短路模型

int bfs()
{
    queue<PII> q;
    q.push({sx,sy}); //起点入队 
    memset(dist,0x3f,sizeof dist); //初始化距离 
    dist[sx][sy]=0; //起点距离 
    while(q.size())
    {
        PII t=q.front(); //出队 
        q.pop();
        if(t.x==ex&&t.y==ey) //找到终点 
        {
            return dist[ex][ey];
        }
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<1||a>n||b<1||b>m) continue;
            if(g[a][b]=='#') continue;
            if(dist[a][b]!=0x3f3f3f3f) continue;
            dist[a][b]=dist[t.x][t.y]+1;
            q.push({a,b});
        }
    }
    return -1; //走完了也没有找到终点 
}


//最短步数问题
int bfs(string s)
{
    queue<string> q;
    map<string,int> dist;
    q.push(s);
    dist[s]=0;
    string es="12345678x";
    while(q.size())
    {
        string t=q.front();
        q.pop();
        if(t==es) //找到终点 
        {
            return dist[es];
        }  
        int k=t.find('x'); //寻找x的位置 
        int x=k/3,y=k%3; //映射 
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<0||a>=3||b<0||b>=3) continue;
            string str=t;
            int kk=a*3+b;
            swap(str[kk],str[k]); //得到由t走到的字符串 
            if(dist.count(str)==0) //没有在哈希表中出现过 
            {
                dist[str]=dist[t]+1;
                q.push(str);
            }
             
        }
    }
    return -1; //走不到 
}

深度优先搜索 
//选择问题

void dfs(int u,int s)
{
    if(u==n+1)
    {
        if(s<=m) //没有超过手里的钱 
        {
            ans=max(ans,s);  //保留最大值 
        }
        return ;
    }
    dfs(u+1,s); //不选 
    dfs(u+1,s+w[u]); //选 
} 


// 排列模型 
void dfs(int u)
{
    if(u==n+1) //找到答案
    {
        for(int i=1;i<=n;i++)
        {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i]) //当前分支i还没有使用过
        {
            ans[u]=i; //第u个数填i
            st[i]=1;
            dfs(u+1);//往下走的分支的i已经使用过了。
            st[i]=0;//接下来会换个分支，清除标记
        }
    }
}

//组合模型

void dfs(int u,int x)
{
    if(u==m+1) //找到答案
    {
        for(int i=1;i<=m;i++)
        {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
        return ;
    }
    for(int i=x;i<=n;i++)
    {
        if(!st[i]) //当前分支i还没有使用过
        {
            ans[u]=i; //第u个数填i
            st[i]=1;
            dfs(u+1,i+1);//往下走的分支的i已经使用过了。
            st[i]=0;//接下来会换个分支，清除标记
        }
    }
}

//连通块模型
void dfs(int x,int y)
{
	st[x][y]=1;
	cnt++;
	for(int i=0;i<4;i++)
	{
		int a=x+dx[i],b=y+dy[i];
		if(a<0||a>=n||b<0||b>=m) continue;
		if(g[a][b]=='#') continue;
		if(st[a][b]) continue;
		dfs(a,b);
	}
}

//棋盘问题
void dfs(int r) //当前枚举第r行的填法 
{
    if(r==n) //找到了n行 
    {
        for(int i=0;i<n;i++)
        {
            cout<<g[i]<<endl;
        }
        cout<<endl;
    }
    for(int c=0;c<n;c++) //枚举第r行的第c列 
    {
        if(col[c]==0&&dg[r+c]==0&&ndg[r-c+n]==0) //第c列没有，左下到右上的对角线没有，左上到右下的对角线没有 
        {
            col[c]=dg[r+c]=ndg[r-c+n]=1;
            g[r][c]='Q';
            dfs(r+1); //填好了枚举下一行 
            g[r][c]='.';
            col[c]=dg[r+c]=ndg[r-c+n]=0;
        }
    }
} 
 
贪心

1.均值问题
int ave=s/n;//计算平均纸牌数 
if(ave*n!=s) //不能够均分 
{
    res=-1; 
} 
else
{
    for(int i=1;i<=n;i++)
    {
        if(ave!=a[i]) //当前不是平均值 
        {
            res++;
            a[i+1]=a[i+1]-(ave-a[i]); //从a[i+1] 移动差值过来 
        }
    }
 
}


2.绝对值不等式 
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int sum=0;
for(int i=0;i<n;i++)
{
    sum+=abs(a[i]-a[n/2]);
}
 
3.排序不等式 
typedef pair<int,int> PII;
PII q[N];
for(int i=0;i<n;i++)
{
    int w,s;
    cin>>w>>s;
    q[i]={w+s,w}; //按照w+s从小到大排序
}
sort(q,q+n);
int ans=-2e9;
int sum=0;
for(int i=0;i<n;i++)
{
    int w=q[i].second,s=q[i].first-w;
    ans=max(ans,sum-s); //更新每头牛的危险值
    sum+=w;
}

4.哈夫曼
while (q.size()>1)
{
	int a=q.top();q.pop();
	int b=q.top();q.pop();
	res+=a+b;
	q.push(a+b);
} 

5.区间选点, 最大不相交区间数量
struct Node{ //定义一种结构体，按照区间右端点从小到大排序
    int l,r;
    bool operator<(const Node& W)
    {
        return r<W.r;
    }
}range[N];


6.区间分组,区间覆盖
typedef pair<int,int> PII;
#define l first
#define r second
for(int i=0;i<n;i++)
{
    cin>>q[i].l>>q[i].r;
}
sort(q,q+n); //按照区间左端点排序