zkx06111's Blog

http://blog.csdn.net/dark_scope/article/details/8880547

真心推荐这个，非常好懂。二分图匹配的难点不在于算法，而在于应用。

比如XJOI1579这题。我一开始根本想不到二分图匹配，是看了题解之后才想到的。

不存在两个星球i,j,既能从i到达j，又能从j到达i。这说明是有向无环图。

把原图作为二分图的两个点集进行最大匹配。

为什么可以这样呢？

假如i匹配到了j，j匹配到了k，k找不到匹配，就找到了一条可行的路径，找不到匹配的k就是该路径的终点，而终点的个数（点的总数减去匹配的点个数）就是路径的条数。

由于一个点只能被匹配一次，所以不会出现路径相交的情况。由于是最大匹配，所以路径条数最少。

目前我只能理解到这一层，但感觉太妙了。

//O(n^2)动态规划,f[i][j]前后分别表示以(i,j)为右下角的最多条数
//预处理出数组r[i][j]前后分别表示(i,j)左边和右边鱼的条数
//rn[i][j]表示(i,j)上方鱼的条数
//为了省空间只好回收利用数组了。。。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int ans=0,n,m,f[2505][2505];
unsigned short r[2505][2505],rn[2505][2505],pond[2505][2505];
int main(){
	scanf("%d%d",&n,&m);
	
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j){
			scanf("%d",&pond[i][j]);
			r[i][j]=r[i][j-1]+pond[i][j];
			//printf("r%d,%d=%d\n",i,j,r[i][j]);
		}
	for (int j=1;j<=n;++j)
		for (int i=1;i<=m;++i){
			rn[j][i]=rn[j-1][i]+pond[j][i];
			//printf("rm%d,%d=%d\n",j,i,rn[j][i]);
		}
	
	for (int i=1;i<=m;++i) f[1][i]=pond[1][i];
	for (int j=1;j<=n;++j) f[j][1]=pond[j][1];
	
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j){
			if (i==1 || j==1){
				ans=max(ans,f[i][j]);
				continue;
			}
			if (pond[i][j]==0){
				f[i][j]=0;
				continue;
			}
			f[i][j]=1;
			if (r[i][j-1]==r[i][j-f[i-1][j-1]-1]
				&& rn[i-1][j]==rn[i-f[i-1][j-1]-1][j])
				f[i][j]=f[i-1][j-1]+1;
			//printf("f%d,%d=%d\n",i,j,f[i][j]);
			ans=max(ans,f[i][j]);
		}
	
	memset(f,0,sizeof(f));
	
	for (int i=1;i<=m;++i) f[1][i]=pond[1][i];
	for (int j=1;j<=n;++j) f[j][m]=pond[j][m];
	
	for (int i=1;i<=n;++i)
		for (int j=m;j>0;--j){
			r[i][j]=r[i][j+1]+pond[i][j];
			//printf("r%d,%d=%d\n",i,j,r[i][j]);
		}
	
	for (int i=1;i<=n;++i)
		for (int j=m;j>0;--j){
			if (i==1 || j==m){
				ans=max(ans,f[i][j]);
				continue;
			}
			if (pond[i][j]==0){
				f[i][j]=0;
				continue;
			}
			f[i][j]=1;
			if (i==2 && j==3) {
				//printf("  %d,%d=%d\n",i-1,j,rn[i-1][j]);
				//printf("  %d,%d=%d\n",i-g[i-1][j+1]-1,j,rn[i-g[i-1][j+1]-1][j]);
			}
			if (r[i][j+f[i-1][j+1]+1]==r[i][j+1]
				&& rn[i-1][j]==rn[i-f[i-1][j+1]-1][j]){
				//printf("!!%d,%d!!\n%d,",i,j,f[i-1][j+1]);
				f[i][j]=f[i-1][j+1]+1;
			}	
			//printf("g%d,%d=%d\n",i,j,f[i][j]);
			ans=max(ans,f[i][j]);
		}
	
	printf("%d",ans);
	
	return 0;
}

#include <iostream>
using namespace std;

int main(){
	int n;
	cin>>n;
	while (n){
		long long x=1,ans=0,k;
		cin>>k;
		while (k){
			ans+=k%2*x;
			x*=3;
			k/=2;
		}
		cout<<ans<<endl;
		--n;
	}
	return 0;
}