可达性统计

思路

一个点能去的点是:所有子节点能去的点之和+1

那么要用什么顺序遍历图呢？

当然是拓扑排序(反)

先拓扑排序，再按反着的顺序得到每个点能去的点的数量

但点可能重复,开个30010*30010也不现实,怎么办呢？

用bitset!

bitset是一个多位的二进制数,可以进行位运算，自选位数，空间还是$O(1)$，这样我们就可以用每一位存是否有这个点 再用count()得到1的个数

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,dist[30010],cd[30010],tpst[30010];
queue<int> tpst2;
vector<int> e[30010];
map<pair<int,int>,int> flag;
bitset<30001> ans[30001];
void topsort()
{
    for(int i=1;i<=n;i++) if(cd[i]==0) tpst2.push(i);
    int idx=0;
    while(tpst2.size())
    {
        int node=tpst2.front();
        for(int i=0;i<e[node].size();i++)
        {
            cd[e[node][i]]--;
            if(cd[e[node][i]]==0) tpst2.push(e[node][i]);
        }
		tpst2.pop();
        tpst[++idx]=node;
    }
    return;
}
int main()                          
{
	cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if(flag[make_pair(x,y)]) continue;
        e[x].push_back(y);
        cd[y]++;
        flag[make_pair(x,y)]=1;
    }
    topsort();
	for(int i=n;i>=1;i--)
	{
		int node=tpst[i];
		for(int j=0;j<e[node].size();j++) ans[node]=ans[node]|ans[e[node][j]];
		ans[node].set(node,1);
	}
	for(int i=1;i<=n;i++) cout<<ans[i].count()<<endl;
}

小猫爬山

思路

我们可以先想暴搜,对于每一只猫,要么放入当前任意一个的缆车中，要么在坐一辆新的缆车.

但时间复杂度有点高，我们要想剪枝.

剪枝有四种

优化搜索顺序
排除亢余信息
可行性剪枝
最优性剪枝

我们可以想到一个可行性剪枝:如果当前缆车不能装小猫就不装.

一个最优性剪枝:当前用的缆车比当前最少的缆车多就不继续搜索.

代码

#include<bits/stdc++.h>
using namespace std;
long long n,w,a[20],dt[20],idx,ans=2e9;
void dfs(int u)
{
    if(idx>=ans) return;
    if(u==n+1)
    {
        ans=min(ans,idx);
        return;
    } 
    for(int i=1;i<=idx;i++)
    {
        if(dt[i]+a[u]<=w)
        {
            dt[i]+=a[u];
            dfs(u+1);
            dt[i]-=a[u];
        }
    }
    dt[++idx]=a[u];
    dfs(u+1);
    idx--;
}
int main()
{
    cin>>n>>w;
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(1);
    cout<<ans;
}

数独

思路 我们可以先想暴搜,枚举每个空位置,填上能填的数，如果有位置不能填就回溯。

怎么找到能填的数呢,我们可以用二进制.

用row[i]来表示第i行能填的

用col[j]来表示第j列能填的

用sqrae[i][j]来表示第i行第j列的区块能填的

哪一位有1就能填那个数,于是第i行第j列的格子能填的是row[i]&col[j]&sqrae[i/3][j/3],再用lowbit取出每一位

可是会超时,怎么办呢?

我们可以剪枝,每个空格能填数字少的先填。

代码

#include<bits/stdc++.h>
using namespace std;
int row[9],col[9],sqrae[3][3];
int bin_1[(1<<9)],num[(1<<9)];
string s;
int lowbit(int x)
{
	return x&-x;
 } 
void db()
{
	int sum=1;
	for(int i=0;i<9;i++)
	{
		num[sum]=i;
		sum*=2;
	}
	for(int i=0;i<(1<<9);i++)
	{
		 for(int j=i;j;j-=lowbit(j))
		 {
			bin_1[i]++;
		 }
	}
	return;
}
void db2()
{
	for(int i=0;i<9;i++)
	{
		row[i]=(1<<9)-1;
		col[i]=(1<<9)-1;
		sqrae[i/3][i%3]=(1<<9)-1;
	}
	return;
}
int get(int x,int y)
{
	int sum=(row[x]&col[y]&sqrae[x/3][y/3]);
	return sum;
}
bool dfs(int cnt)
{
	if(cnt==0) return true;
	int i,j,minn=20;
	for(int x=0;x<9;x++)
	{
		for(int y=0;y<9;y++)
		{
			if(s[x*9+y]=='.')
			{
				if(bin_1[get(x,y)]<minn)
				{
					i=x;
					j=y;
					minn=bin_1[get(x,y)];
				}
			}
		}
	}
	for(int k=get(i,j);k;k-=lowbit(k))
	{
		int num2=num[lowbit(k)];
		row[i]-=1<<num2;
		col[j]-=1<<num2;
		sqrae[i/3][j/3]-=1<<num2;
		s[i*9+j]='1'+num2;
		if(dfs(cnt-1)) return true;
		row[i]+=1<<num2;
		col[j]+=1<<num2;
		sqrae[i/3][j/3]+=1<<num2;
		s[i*9+j]='.';
	}
	return false;
}
int main()
{
	db();//初始化
	while(cin>>s&&s!="end")
	{
		db2();//每一次的初始化
		int cnt=0;
		for(int i=0;i<9;i++)
		{
			for(int j=0;j<9;j++)
			{
				if(s[i*9+j]!='.')
				{
					int num=s[i*9+j]-'1';
					row[i]-=1<<num;
					col[j]-=1<<num;
					sqrae[i/3][j/3]-=1<<num;
				}
				else cnt++;
			}
		}
		dfs(cnt);
		cout<<s<<endl; 
	}
}