发布于

lp2622 关灯问题II

显然，对于某个状态，按下某个按钮之后，一定会得到另一个状态。
而灯的状态最大只有\(2^10\)。
故而考虑建一张图，2^n个点，m条边，那么答案就是从0到2^n-1的最短距离。
直接BFS即可。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int INF=0x3f3f3f3f;
int n,m;
queue<int> q;
int dep[1025],vis[1025];
int a[15],b[105],c[105];
inline int bfs(){
	for(int i=0;i<(1<<n);++i){
		dep[i]=INF;
	}
	q.push(0);
	dep[0]=0;
	int p,v;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=1;i<=m;++i){
			v=(p|b[i])&c[i];
			if(dep[v]>dep[p]+1){
				dep[v]=dep[p]+1;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return (dep[(1<<n)-1]^INF)?dep[(1<<n)-1]:-1;
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		b[i]=c[i]=0;
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<n;++j){
			scanf("%d",&a[j]);
			if(a[j]==1){
				b[i]|=(1<<j);
				c[i]|=(1<<j);
			}
			if(a[j]==0){
				c[i]|=(1<<j);
			}
		}
	}
	printf("%d\n",bfs());
}
int main(){
	init();
	return 0;
}
发布于

CF1098B Nice table

话说考场上这题距离正解只差一步了，可惜我走错方向变成枚举左上角的block然后瞎鸡儿乱搞求min了。
事实上这一题猜到结论之后可以想到另一个更科学的做法。
具体来说，可以考虑，要么是行上两种字符交替出现而列上随意，要么是列上两种字符交替出现而行上随意。
所以我们可以枚举这些信息，然后检验一下即可。
顺便提一句，这一题的数据范围真的是恶意满满。考场上是瞎jb哈希，但是现在个人觉得还是string比较科学。

#include<iostream>
#include<cstdio>
#include<cstring>

#define MAXN 300005
char lst[6][2]={{'A','G'},{'A','C'},{'A','T'},{'C','T'},{'G','T'},{'C','G'}};
std::string ch[MAXN],out[MAXN];
int n,m,cnt[MAXN][2],val[MAXN][6][2],nw[2];

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		std::cin>>ch[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=m;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[i][k-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[i][k-1]);
			}
			val[i][j][0]=(int)(nw[0]>=nw[1]);
			cnt[j][0]+=std::min(nw[0],nw[1]);
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=n;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[k][i-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[k][i-1]);
			}
			val[i][j][1]=(int)(nw[0]>=nw[1]);
			cnt[j][1]+=std::min(nw[0],nw[1]);
		}
	}
	int ans=0x3f3f3f3f;
	int pi,pj;
	for(int i=0;i<2;++i){
		for(int j=0;j<6;++j){
			ans=(cnt[j][i]<ans)?pi=i,pj=j,cnt[j][i]:ans;
		}
	}
	if(!pi){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				putchar(lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][0])]); 
			}
			puts("");
		}
	}else{
		for(int i=1;i<=m;++i){
			for(int j=1;j<=n;++j){
				out[j]+=lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][1])];
			}
		}
		for(int i=1;i<=n;++i){
			std::cout<<out[i]<<std::endl;
		}
	}
}

int main(){
	init();
	return 0;
}
发布于

lp2150 NOI2015 寿司晚宴

将2~n的整数划分到两个集合，使得两个集合中任意两个元素互质，求方案数。
对于n<=30的情况是很容易想到的，将每个数\(i\)求出它的质因子集合\(K_{i}\)。
很容易可以发现，30以内的质数仅有10种。故而我们就有了一个\(O(2^{202}n)\)的做法。
对于n<=500的情况，似乎用上述的做法并不是十分可行，无论是时间复杂度还是空间复杂度都是不可接受的。
但是我们发现，有且仅有7个质数，在500以内会作为因数出现多次。我们是不是可以用一种奇技淫巧把大于19的质数处理掉呢？
我们惊讶地发现，由于所有较大的质数会且只会出现一次，那么很显然所有最大质因子是较大质数且最大质因子相同的数只能放到一个集合里。
故而我们把所有数按照最大质因子排序，然后从小到大遍历。当最大质因子成为较大质数的时候，不再使用原来的数组，而是将「这个质因子一个都没选」的情况复制到两个新的数组f2[2][1<<7][1<<7]。
每一次更换最大质因子的时候都从原数组继承DP值，然后在这里面对每一个是放在A还是放在B的情况来更新：

$$f_{S_1,S_2} = f2_{0,S_1,S_2} + f2_{1,S_1,S_2} – f_{S_1,S_2}$$

之所以最后还要减去原来的值是因为，两个新数组的最终结果各自都是从原来的「这个质因子一个都没选」的情况复制过来的，因此「这个质因子一个都没选」的情况就会被统计两次。

#include<iostream>
#include<cstdio>
#include<algorithm>
/*

*/ 
const int P[8]={2,3,5,7,11,13,17,19};
const int MAX=1<<8;
long long MOD;
long long f[MAX][MAX],f2[2][MAX][MAX];
struct data{
	int v;
	int big;
	int K;
	inline void init(int X){
		v=X,big=0;
		int nw=v;K=0;
		for(int i=0;i<8;++i){
			if(!(nw%P[i])){
				K|=(1<<i);
			}
			while(!(nw%P[i])){
				nw/=P[i];
			}
		}
		if(nw>1){
			big=nw;
		}
	}
	inline bool operator<(const data &B)const{
		return big<B.big;
	}
}a[505];
int n;
void init(){
	scanf("%d%lld",&n,&MOD);
	--n;
	for(int i=1;i<=n;++i){
		a[i].init(i+1);
	}
	std::sort(a+1,a+1+n);
	int lst=0x3f3f3f3f;
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		if(a[i].big){
			lst=i;
			break;
		}
		for(int j=MAX-1;~j;--j){
//			注意这里要-1 
			for(int k=MAX-1;~k;--k){
				f[j][k|a[i].K]+=f[j][k];f[j|a[i].K][k]+=f[j][k];
				f[j][k|a[i].K]%=MOD;f[j|a[i].K][k]%=MOD;
			}
		}
	}
	for(int i=lst;i<=n;++i){
		if(a[i].big!=a[i-1].big){
			for(int j=0;j<MAX;++j){
				for(int k=0;k<MAX;++k){
					f2[0][j][k]=f2[1][j][k]=f[j][k];
				}
			}
		}
		for(int j=MAX-1;~j;--j){
			for(int k=MAX-1;~k;--k){
				if(j&k){
					continue;
				}
				if(!(k&a[i].K)){
					f2[0][j|a[i].K][k]+=f2[0][j][k];
					f2[0][j|a[i].K][k]%=MOD;
				}
				if(!(j&a[i].K)){
					f2[1][j][k|a[i].K]+=f2[1][j][k];
					f2[1][j][k|a[i].K]%=MOD;
				}
			}
		}
		if(a[i].big!=a[i+1].big){
			for(int j=0;j<MAX;++j){
				for(int k=0;k<MAX;++k){
					f[j][k]=(f2[0][j][k]+f2[1][j][k]+(MOD-f[j][k]))%MOD;
				}
			}
		}
	}
	long long ans=0;
	for(int i=MAX-1;~i;--i){
		for(int j=MAX-1;~j;--j){
			if(i&j){
				continue;
			}
			ans+=f[i][j];
			ans%=MOD;
		}
	}
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}
发布于

lp2831 NOIP2016 愤怒的小鸟

看到\(n<=18\)，很容易可以想到状压\(DP\)。
最大力的做法就是，枚举原集合和转移的目的集合，然后考虑一条抛物线能否穿过其中的所有点。
但是这样的复杂度显然是不可接受的，考虑优化。
易知，三点确定一条抛物线，故而在给定\(c=0\)的时候，确定两点即可确定第三点。具体的方程组是：
$$a=\frac{x_{j}*y_{i}-x_{i}*y{j}}{x_{i}*x_{j}*(x_{i}-x_{j})}$$
$$b=\frac{y_{i}}{x_{i}}-a*x_{i}$$
从而我们可以预处理出，通过某两个点的抛物线通过的点的集合，然后对于每一个状态，选择哪两个点拓展即可。
但这个时候的时间复杂度是\(O(T*n^2*2^n)\)，对于较大的数据还是很难通过的。
这时候我们可以发现，第一个选择的点是可以固定的，也就是第一个可选择的点。因为如果选择其他点开始拓展的话，到最后依然要拓展那个点。
那么就成功地将复杂度压缩到了\(O(T*n*2^n)\)，这时候就可以通过了。
PS:凡是Double的题都应该注意精度。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define eps 1E-6
int n,m;
int f[1<<18],A[20][20];
double x[20],y[20];
inline int lwbt(const int &_X){
    return _X&-_X;
}
inline int Min(const int &_X,const int &_Y){
    return _X<_Y?_X:_Y;
}
inline int cnt(int _X){
    int rt=0;
    while(_X&1){
        ++rt;
        _X>>=1;
    }
    return rt;
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i){
        scanf("%lf%lf",&x[i],&y[i]);
    }
    double a,b;
    for(int i=0;i<n;++i){
        for(int j=i;j<n;++j){
            if(x[i]-x[j]<=eps&&x[i]-x[j]>=-eps){
                if(!(y[i]-y[j]<=eps&&y[i]-y[j]>=-eps)){
                    A[i][j]=0;
                    continue;
                }else{
                    A[i][j]=(1<<i)|(1<<j);
                    continue;
                }
            }
            a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
            b=y[i]/x[i]-a*x[i];
            A[i][j]=0;
            if(a>=-eps){
                continue;
            }
            for(int k=0;k<n;++k){
                if(a*x[k]*x[k]+b*x[k]-y[k]<=eps&&a*x[k]*x[k]+b*x[k]-y[k]>=-eps){
                    A[i][j]|=(1<<k);
                }
            }
        }
    }
    /*
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            printf("%d ",A[i][j]);
        }
        puts("");
    }
    */
    const int MAX=1<<n;
    int loc;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    
    for(int i=0;i<MAX;++i){
        loc=cnt(i);
        for(int j=loc;j<n;++j){
            f[i|A[loc][j]]=Min(f[i|A[loc][j]],f[i]+1);
        }
    }
    printf("%d\n",f[MAX-1]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

发布于

lp3959 NOIP2017 宝藏

我们首先，如果两个点之间有连多条边，肯定只有最短的那条最优。
那么我们进行状压，对于某一个状态\(S_{0}\)，我们维护它的所有拓展的集合\(T_{S_{1}}\)
然后，记\(f_{i,k}\)表示，当前状态为\(i\)，当前的深度为\(k\)时的最小花费。
这样拓展，每一次拓展都相当于把深度加深了一层，因此就可以不要花费太多的精力去考虑\(k\)对贡献的影响。
而，从某一个根开始拓展，即相当于\(f_{(1<<i),0}\)
于是我们便可以开始DP。每一次拓展都会将可行集合纳入范围。这样拓展的花费也是可以被轻松计算出来的。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int n,m,f[1<<12][12],usf[1<<12];
int mp[15][15];
void init(){
    scanf("%d%d",&n,&m);
    int u,v,w;
    memset(mp,0x3f,sizeof(mp));
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        --u,--v; 
        mp[u][v]=Min(mp[u][v],w);
        mp[v][u]=Min(mp[v][u],w);
    }
    const int MAX=1<<n;
    for(int i=1;i<MAX;++i){
        for(int j=0;j<n;++j){
            if((i|(1<<j))!=i){
                continue;
            }
            for(int k=0;k<n;++k){
                if(mp[j][k]!=0x3f3f3f3f){
                    usf[i]|=(1<<k);
                }
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<n;++i){
        mp[i][i]=0;
        f[1<<i][0]=0;
    }
    long long sm,nw,x;
    for(int i=2;i<MAX;++i){
        for(int j=i-1;j;j=(j-1)&i){
            if(((usf[i]|j)!=usf[i])){
                continue;
            }
            sm=0,nw=i^j;
            for(int k=0;k<n;++k){
                if((nw>>k)&1){
                    x=0x3f3f3f3f;
                    for(int l=0;l<n;++l){
                        if((j>>l)&1){
                            x=Min(x,mp[l][k]);
                        }
                    }
                    sm+=x;
                }
            }
            for(int k=1;k<n;++k){
                f[i][k]=Min(f[i][k],f[j][k-1]+sm*k);
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<n;++i){
        ans=Min(ans,f[MAX-1][i]);
    }
    printf("%d\n",ans);
}
int main(){
    init();
    return 0;
}