2706: [SDOI2012]棋盘覆盖
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 255 Solved: 77
[Submit][Status]
Description
在一个N*M个方格组成的棋盘内，有K个方格被称为特殊方格。我们要使用一组俄罗斯方块来覆盖这个棋盘，保证特殊方格不能被覆盖，非特殊方格只能被一个俄罗斯方块覆盖，求最多能容纳的俄罗斯方块的数量。
已知有以下三组俄罗斯方块，一个棋盘可能用其中的某一组。
Input
第一行三个整数，N,M,K，和一个字符，type，为所用的俄罗斯方块组。
接下来K行每行两个整数，X,Y，表示第X行第Y列为特殊方格。
Output
一个整数，为所求的答案。
【样例输入1】
8 8 0 A
【样例输出1】
32
【样例输入2】
7 6 6 C
3 1
3 6
5 3
5 4
5 7
6 7
【样例输出2】
12
【数据范围】
|
测试点 |
N,M |
K |
type |
|
[1, 6] |
0 < N,M <= 100 |
0<=K<=N*M |
A |
|
[7, 12] |
N=M=2^L,0<L<=200000 |
K=1 |
B |
|
[13, 20] |
0<N,M<=11 |
0<=K<=N*M |
C |
第一组：二分图匹配
第二组：可以通过分治法证明ans=(n*n-1)/3
第三组：我用的是Dancing Link，但是不知道有没有网络流解法，如果用dancing link那么要注意如果当前答案等于(n*m-k)/3就强制退出。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; namespace sec1 { const int maxe=21000; const int maxv=11000; const int maxn=102; const int mov[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; struct Edge { int np,val; Edge *next; }E[maxe],*V[maxv]; int tope=-1; bool bad[maxn][maxn]; void addedge(int x,int y) { E[++tope].np=y; E[tope].next=V[x]; V[x]=&E[tope]; } bool vis[maxn*maxn]; int ptr[maxn*maxn]; bool find(int now) { Edge *ne; for (ne=V[now];ne;ne=ne->next) { if (vis[ne->np])continue; vis[ne->np]=true; if (!ptr[ne->np] || find(ptr[ne->np])) { ptr[ne->np]=now; return true; } } return false; } int main(int n,int m,int t) { int i,j,k,x,y; for (i=0;i<t;i++) { scanf("%d%d",&x,&y); bad[x][y]=true; } for (i=1;i<=n;i++) { for (j=1;j<=m;j++) { if (bad[i][j] || ((i+j)&1))continue; for (k=0;k<4;k++) { if (i+mov[k][0]>0 && i+mov[k][0]<=n && j+mov[k][1]>0 && j+mov[k][1]<=m && !bad[i+mov[k][0]][j+mov[k][1]]) { addedge(i*m+j,(i+mov[k][0])*m+j+mov[k][1]); } } } } int ans=0; for (i=1;i<=n;i++) { for (j=1;j<=m;j++) { if ((i+j)%2==0) { memset(vis,0,sizeof(vis)); ans+=find(i*m+j); } } } printf("%d ",ans); return 0; } } namespace sec2 { const int maxn=1100000; int a[maxn]; long long b[maxn]; void main(const char* str) { int m=strlen(str); for (int i=0;i<m;i++) a[(m-i-1)/8]=a[(m-i-1)/8]*10+str[i]-'0'; int n=(m-1)/8; for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) { b[i+j]+=(long long)a[i]*a[j]; b[i+j+1]+=b[i+j]/100000000; b[i+j]%=100000000; } for (int i=0;i<n*2+10;i++) { b[i+1]+=b[i]/100000000; b[i]%=100000000; } n=n*2+10; while (!b[n])n--; b[0]--; for (int i=n;i>=0;i--) { b[i-1]+=b[i]%3*100000000; b[i]/=3; } while (!b[n])n--; printf("%lld",b[n]); for (int i=n-1;i>=0;i--) printf("%08lld",b[i]); printf(" "); } } namespace sec3//DLX { //{{{ const int maxn=12; const int maxd=maxn*maxn*4*4; const int mov[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; const int inf=0x3f3f3f3f; int L[maxd],R[maxd],D[maxd],U[maxd]; bool bad[maxn][maxn]; int tt[maxd]; int top[maxd]; int head[maxn*maxn]; int vec[4]; int ans=0,cnt=0; int topd=0; int anslim; void Init_DLX(int l) { int now; L[0]=R[0]=D[0]=U[0]=0; for (int i=1;i<=l;i++) { now=++topd; R[now]=head[0]; L[now]=L[head[0]]; U[now]=D[now]=now; L[R[now]]=now; R[L[now]]=now; top[now]=i; head[i]=now; } } void Add_DLX(int *ss) { int now=++topd; D[now]=head[0]; U[now]=U[head[0]]; L[now]=R[now]=now; D[U[now]]=now; U[D[now]]=now; int h0=now; while (~(*ss)) { now=++topd; D[now]=head[*ss]; U[now]=U[head[*ss]]; L[now]=L[h0]; R[now]=h0; U[D[now]]=now; D[U[now]]=now; R[L[now]]=now; L[R[now]]=now; top[now]=*ss; tt[*ss]++; ss++; } } void Cover(int c) { R[L[c]]=R[c]; L[R[c]]=L[c]; for (int i=D[c];i!=c;i=D[i]) { for (int j=R[i];j!=i;j=R[j]) { tt[top[j]]--; U[D[j]]=U[j]; D[U[j]]=D[j]; } } } void Resume(int c) { R[L[c]]=c; L[R[c]]=c; for (int i=D[c];i!=c;i=D[i]) { for (int j=R[i];j!=i;j=R[j]) { tt[top[j]]++; U[D[j]]=D[U[j]]=j; } } } void Search_DLX(int tot) { ans=max(ans,tot); if (ans==anslim)return; int bst=inf,bstid; bstid=R[head[0]]; for (int i=R[head[0]];i!=head[0];i=R[i]) if (tt[top[i]] && tt[top[i]]<bst) bst=tt[top[i]],bstid=top[i]; for (int i=D[head[bstid]];i!=head[bstid];i=D[i]) { int k; for (k=R[i];top[k];k=R[k]); for (int j=R[k];j!=k;j=R[j])Cover(head[top[j]]); Search_DLX(tot+1); for (int j=R[k];j!=k;j=R[j])Resume(head[top[j]]); } } void main(int n,int m,int t) { int i,j,k1,k2; vec[3]=-1; int x,y; for (i=0;i<t;i++) { scanf("%d%d",&x,&y); bad[x][y]=true; } anslim=(n*m-t)/3; Init_DLX((n+1)*m); for (i=1;i<=n;i++) { for (j=1;j<=m;j++) { if (bad[i][j])continue; for (k1=0;k1<4;k1++) { if (i+mov[k1][0]==0 || i+mov[k1][0]==n+1 || j+mov[k1][1]==0 || j+mov[k1][1]==m+1 || bad[i+mov[k1][0]][j+mov[k1][1]]) continue; for (k2=k1+1;k2<4;k2++) { if (i+mov[k2][0]==0 || i+mov[k2][0]==n+1 || j+mov[k2][1]==0 || j+mov[k2][1]==m+1 || bad[i+mov[k2][0]][j+mov[k2][1]]) continue; vec[0]=i*m+j; vec[1]=(i+mov[k2][0])*m+j+mov[k2][1]; vec[2]=(i+mov[k1][0])*m+j+mov[k1][1]; Add_DLX(vec); } } } } Search_DLX(0); printf("%d ",ans); } //}}} } char str[110000]; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int n,m,t; char type; scanf("%s %d %d %c ",str,&m,&t,&type); if (type=='A') { sscanf(str,"%d",&n); sec1::main(n,m,t); }else if (type=='B') { sec2::main(str); }else if (type=='C') { sscanf(str,"%d",&n); sec3::main(n,m,t); } }