T1

Description

给定一个\(N*N(N≤8)\)的矩阵，每一格有一个0~5的颜色。每次可将左上角的格子所在连通块变为一种颜色，求最少操作数。

Solution

IDA*=启发式迭代加深（我似乎是第一次打这东西）
首先我们要想到迭代加深（这我都没想到）
设一个数组\(v[][]\)。记左上角所在连通块为1，它扩展一周的位置为2。每次选取2中一种颜色i进行操作，操作时则从2中颜色为\(i\)的格子处\(dfs\)，更新\(v[][]\)的值。当然回溯时要将所有值变回去。
然后设一个估价函数。如果当前矩阵中除了左上角的连通块之外，共有\(M\)种颜色，那么还需要的步数不小于\(M\)。因此如果当前搜索深度+估价函数的值>深度限制，可以回溯。

时间复杂度什么的就不分析了吧

Code

#include <bits/stdc++.h>

#define S(a) memset(a,0,sizeof a);

#define C(a,b) memcpy(a,b,sizeof a);

#define fo(i,a,b) for(i=a;i<=b;i++)

#define go int k,xx,yy; fo(k,0,3)if((xx=x+v[k][0])&&xx<=n&&(yy=y+v[k][1])&&yy<=n&&!vis[xx][yy])

using namespace std;

const int N=9,v[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

int i,j,n,a[N][N],V[N][N],c[6],V2[6],deep;

bool vis[N][N];

void getV(int x,int y)

{

	vis[x][y]=V[x][y]=1;

	c[a[x][y]]--;

	go

	if(a[xx][yy]==a[x][y]) getV(xx,yy); else

	if(!V[xx][yy]) V[xx][yy]=2,V2[a[xx][yy]]++;

}

bool dfs(int t)

{

	int i,x,y,cs=0,pV[N][N],pc[6],pV2[6];

	fo(i,0,5) cs+=(bool)c[i];

	if(t+cs>deep) return 0;

	if(!cs) return 1;

	fo(i,0,5)

		if(V2[i])

		{

			C(pV,V) C(pc,c) C(pV2,V2)

			fo(x,1,n) fo(y,1,n) if(V[x][y]==2&&a[x][y]==i)

			{

				V2[a[x][y]]--;

				S(vis) getV(x,y);

			}

			if(dfs(t+1)) return 1;

			C(V,pV) C(c,pc) C(V2,pV2)

		}

	return 0;

}

int main()

{

	for(scanf("%d",&n); n; scanf("%d",&n))

	{

		S(c)

		fo(i,1,n) fo(j,1,n) scanf("%d",&a[i][j]), c[a[i][j]]++;

		S(V) S(V2) S(vis) getV(1,1);

		fo(deep,0,n*n)

		if(dfs(0)) break;

		printf("%d\n",deep);

	}

}

T2

今天最有意思的一题。

Description

给定一个\(N(≤200)\)个点、\(M(≤30000)\)条边的\(DAG\)，求最长反链长度。
\(DAG\)中的反链：一个点集，其中的点两两不能互达

Solution

可以先用\(Floyd\)做一遍传递闭包（就是求\(f[x][y]\)表示点\(x\)能否到达点\(y\)）。
如果我们把\(f\)数组取反，形成一个新的邻接矩阵，那么问题就转化为求最大团（团：极大完全子图）。
但这样很难用多项式算法解决。

\(Dilworth\)定理：最长反链长度=最小链（可重复点）覆盖数。
这本来是应用在偏序集上的定理；但由于偏序集可与哈塞图映射，而哈塞图是一个\(DAG\)，故该定理也可应用在图论的\(DAG\)上面。
先定义两个东西：源为入度为0的点，汇为出度为0的点。
定理的证明就是用数学归纳法：1.对于某些特殊图（最长反链全部是源或汇）成立；2.对于一个图\(G\)，其有一个最长反链\(A\)，记\(G\)中能走到\(A\)的点集为\(B\)，\(A\)能走到的点集为\(C\)，则\(B\cup C=G\)且\(B\cap C=A\)，且\(A\)肯定是\(B\)、\(C\)中的一个最长反链，然后因为\(B\)、\(C\)是满足结论的（我们在用犯贱的数学归纳法），所以\(A\)又对应\(B\)、\(C\)的最小链（具体地说，\(A\)中每一个点是\(B\)的最小链的汇和\(C\)的最小链的源），故我们可将那些链两两拼接，则\(G\)也成立。

那么上面是要求可重复最小链覆盖数；我们可以对原图做一遍传递闭包，那么就转化为求不可重复最小链覆盖数。
不可重复最小链覆盖数=\(n\)（点数）-最大匹配数。具体地说，我们在二分图的左部和右部各开辟\(n\)个点；对于一条边\(x\to y\)，我们用左部的\(x\)向右部的\(y\)连一条边。这样的话，我们每次匹配实际上就是将两条链合并，故答案\(--\)。
于是直接跑匈牙利即可。

时间复杂度：\(O(M+N^3)\)。

Code

#include <bits/stdc++.h>

#define fo(i,a,b) for(i=a;i<=b;i++)

using namespace std;

const int N=210;

int i,j,k,n,m,x,y,link[N],ans;

bool f[N][N],vis[N];

bool find(int x)

{

	if(vis[x]) return 0;

	vis[x]=1;

	int y;

	fo(y,1,n)

		if(f[x][y]&&(!link[y]||find(link[y])))

		{

			link[y]=x;

			return 1;

		}

	return 0;

}

int main()

{

	scanf("%d%d",&n,&m);

	fo(i,1,m) scanf("%d%d",&x,&y), f[x][y]=1;

	fo(k,1,n) fo(i,1,n) fo(j,1,n) f[i][j]|=f[i][k]&f[k][j];

	fo(i,1,n)

	{

		fo(j,1,n) vis[j]=0;

		ans+=find(i);

	}

	printf("%d",n-ans);

}

T3

Description

用\(K(≤15)\)种颜色为\(N\)个点染色，要求第\(i\)种颜色使用\(C_i(≤6)\)次，且相邻两个点颜色不能相同。求方案数。
\(T(≤2000)\)组询问。

Solution

这题应该是最水的，但腐太久降智了，完全没想到\(DP\)。
可以设个方程\(f[i][j]\)表示用到第\(i\)种颜色，有\(j\)对相邻的点颜色相同。边界\(f[0][0]=1\)，答案显然是\(f[K][0]\)。
转移详见\(Code\)。

Code

#include <cstdio>

#include <cstring>

#define min(x,y) (x<y?x:y)

#define fo(i,a,b) for(i=a;i<=b;i++)

using namespace std;

typedef long long ll;

const int mK=16,N=99,M=1e9+7;

int i,j,T,K,c,s,x,y;

ll C[N+1][N+1],f[mK][N];

int main()

{

	fo(i,0,N)

	{

		C[i][0]=1;

		fo(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%M;

	}

	for(scanf("%d",&T); T--;)

	{

		scanf("%d",&K);

		s=0, f[0][0]=1;

		fo(i,1,K)

		{

			memset(f[i],0,sizeof f[i]);

			scanf("%d",&c);

			fo(j,0,s)

				if(f[i-1][j])

					fo(x,1,c)

						fo(y,0,min(x,j))

							(f[i][j-y+c-x]+=f[i-1][j]*C[s+1-j][x-y]%M*C[j][y]%M*C[c-1][x-1])%=M;

			s+=c;

		}

		printf("%lld\n",f[K][0]);

	}

}

巴特西

【纪中集训】2019.08.01【NOIP提高组】模拟 A 组TJ

T1

Description

Solution

Code

T2

Description

Solution

Code

T3

Description

Solution

Code

最新文章

热门文章