[破碎的状态] [-16] 100503 B
一道爆搜题
被我爆搜掉了..
各种奇怪的优化
感谢@JCarlson 翻译
数和是一个结合了Crosswords（填字游戏）和Sudoku（数独）的游戏。有一些格子是黑的，一些格子是白的。黑的里面有一些被分为了左下三角和右上三角，其中有一些数。
你需要在白色格子里填写一些1-9之间的数字，使得一横行所有数之和等于这一行左侧黑格子右上三角的数，每一竖列所有数之和等于这一列上方黑格子左下三角的数，且每一横行、每一数列使用的数字不得重复。
所以这题我用尽了各种姿势写暴力优化
My Submissions
然后..
一些WA on test 1是优化写错了..
不管这些..
杀手数据-test 72
6 6 XXXXX 26\XX 31\XX 32\XX 33\XX 32\XX XX\31 ..... ..... ..... ..... ..... XX\35 ..... ..... ..... ..... ..... XX\21 ..... ..... ..... ..... ..... XX\32 ..... ..... ..... ..... ..... XX\35 ..... ..... ..... ..... .....
杀手数据-test 218(注意本数据比test 72要强很多)
6 6 XXXXX 34\XX 21\XX 30\XX 19\XX 21\XX XX\29 ..... ..... ..... ..... ..... XX\28 ..... ..... ..... ..... ..... XX\24 ..... ..... ..... ..... ..... XX\29 ..... ..... ..... ..... ..... XX\15 ..... ..... ..... ..... .....
做法:
暴力搜索每个格子填了些啥,是否合法,然后暴力横竖对应的行列进行修改
优化1:
如果一个行/列的结果不靠谱,一行一共x个数,如果和不在[x,9x]这个范围内即判定不合法
结局:Time Limit Exceeded on Test 72 (17500ms,为Test #218的数据,下同;该数据结果根据计算得到)
*该结果通过计算得到:本机运行时间/1250(本地运行最优程序时间)*750(cf上运行最优程序时间)
void dfs(int x,int y)
{
if (x==n)
{
int i;
for (i=0;i<n;i++)
{
int j;
for (j=0;j<m;j++)
{
if (type[i][j]==-1)
{
printf("_");
}
else
{
printf("%d",type[i][j]);
}
if (j!=m-1) printf(" ");
}
printf("\n");
}
exit(0);
}
if (y==m)
{
dfs(x+1,0);
return;
}
if (type[x][y]==-1)
{
dfs(x,y+1);
return;
}
int i;
for (i=1;i<=9;i++)
{
int t1=lef[x][y];
int t2=up[x][y];
if ((1<<i)&used_hang[t1]) continue;
if ((1<<i)&used_lie[t2]) continue;
hang[t1]-=i;
hang_num[t1]--;
used_hang[t1]^=(1<<i);
lie[t2]-=i;
lie_num[t2]--;
used_lie[t2]^=(1<<i);
if ((hang_num[t1]<=hang[t1])&&(hang[t1]<=hang_num[t1]*9))
{
if ((lie_num[t2]<=lie[t2])&&(lie[t2]<=lie_num[t2]*9))
{
type[x][y]=i;
dfs(x,y+1);
}
}
used_lie[t2]^=(1<<i);
lie_num[t2]++;
lie[t2]+=i;
used_hang[t1]^=(1<<i);
hang_num[t1]++;
hang[t1]+=i;
}
}
优化2:
对优化1进行加强
如果和不在[1+2+..+x,9+8+..+(10-x)]内即判定不合法
结局:Time Limit Exceeded on Test 72 (15000ms;该数据结果根据计算得到)
优化3:
进行第一次局部常数调整
将一部分代码的位置调整,包括t1,t2,hang_num,lie_num等操作丢出循环,hang,lie的操作进行微调,具体如下:
int t1=lef[x][y];
int t2=up[x][y];
hang_num[t1]--;
lie_num[t2]--;
for (i=1;i<=9;i++)
{
hang[t1]--;
lie[t2]--;
if ((1<<i)&used_hang[t1]) continue;
if ((1<<i)&used_lie[t2]) continue;
used_hang[t1]^=(1<<i);
used_lie[t2]^=(1<<i);
if ((sum1[hang_num[t1]]<=hang[t1])&&(hang[t1]<=sum2[hang_num[t1]]))
{
if ((sum1[lie_num[t2]]<=lie[t2])&&(lie[t2]<=sum2[lie_num[t2]]))
{
type[x][y]=i;
dfs(x,y+1);
}
}
used_lie[t2]^=(1<<i);
used_hang[t1]^=(1<<i);
}
hang[t1]+=9;
lie[t2]+=9;
lie_num[t2]++;
hang_num[t1]++;
结局:Time Limit Exceeded on Test 72 (12800ms;该数据结果根据计算得到)
优化4:
将used_hang,used_lie丢进if里面,继续常数调整
结局:Time Limit Exceeded on Test 72 (12100ms;该数据结果根据计算得到)
"优化"5:
对递归进行优化,直接用next_x和next_y数组记录下一个x和y的位置
结局:Time Limit Exceeded on Test 72 (13400ms;该数据结果根据计算得到;我很意外的发现这个操作使程序变慢了;去掉后的AC记录是686ms)
优化6:
代码重构,利用好continue,这一步为后面的优化提供了方便
void dfs(int x,int y)
{
if (x==n)
{
int i;
for (i=0;i<n;i++)
{
int j;
for (j=0;j<m;j++)
{
if (type[i][j]==-1)
{
printf("_");
}
else
{
printf("%d",type[i][j]);
}
if (j!=m-1) printf(" ");
}
printf("\n");
}
exit(0);
}
int i;
int t1=lef[x][y];
int t2=up[x][y];
hang_num[t1]--;
lie_num[t2]--;
for (i=1;i<=9;i++)
{
hang[t1]--;
lie[t2]--;
if ((1<<i)&used_hang[t1]) continue;
if ((1<<i)&used_lie[t2]) continue;
if (hang[t1]>sum2[hang_num[t1]]) continue;
if (lie[t2]>sum2[lie_num[t2]]) continue;
if (sum1[hang_num[t1]]>hang[t1])
{
i++;
break;
}
if (sum1[lie_num[t2]]>lie[t2])
{
i++;
break;
}
used_hang[t1]^=(1<<i);
used_lie[t2]^=(1<<i);
type[x][y]=i;
dfs(next_x[x][y],next_y[x][y]);
used_lie[t2]^=(1<<i);
used_hang[t1]^=(1<<i);
}
hang[t1]+=i-1;
lie[t2]+=i-1;
lie_num[t2]++;
hang_num[t1]++;
}
结局:Time Limit Exceeded on Test 72 (11100ms;该数据结果根据计算得到)
优化7:
对于某个数字如果填完以后剩下这行的最后一个或者这列的最后一个,我们就可以直接知道最后一个填上去会不会导致位数冲突
例如填充和为16的,长度为3的一行,我们已经填了5和6,那么我们可以计算出下一个一定是5一定有冲突
事实证明这个优化很有效
结局:Time Limit Exceeded on Test 74 (2500ms)
优化8:
我们把这两个continue直接带到外面
if (hang[t1]>sum2[hang_num[t1]]) continue;
if (lie[t2]>sum2[lie_num[t2]]) continue;
在这次优化后,我们的循环不再从1开始,而是l开始
int t1=lef[x][y];
int t2=up[x][y];
hang_num[t1]--;
lie_num[t2]--;
int l=1;
l=max(l,hang[t1]-sum2[hang_num[t1]]);
l=max(l,lie[t2]-sum2[lie_num[t2]]);
hang[t1]-=l-1;
lie[t2]-=l-1;
for (i=l;i<=9;i++)
{
hang[t1]--;
lie[t2]--;
if ((1<<i)&used_hang[t1]) continue;
if ((1<<i)&used_lie[t2]) continue;
if (sum1[hang_num[t1]]>hang[t1])
{
i++;
break;
}
if (sum1[lie_num[t2]]>lie[t2])
{
i++;
break;
}
used_hang[t1]^=(1<<i);
used_lie[t2]^=(1<<i);
if (hang_num[t1]==1)
{
if ((1<<hang[t1])&(used_hang[t1]))
{
used_lie[t2]^=(1<<i);
used_hang[t1]^=(1<<i);
continue;
}
}
if (lie_num[t2]==1)
{
if ((1<<lie[t2])&(used_lie[t2]))
{
used_lie[t2]^=(1<<i);
used_hang[t1]^=(1<<i);
continue;
}
}
type[x][y]=i;
dfs(next_x[x][y],next_y[x][y]);
used_lie[t2]^=(1<<i);
used_hang[t1]^=(1<<i);
}
hang[t1]+=i-1;
lie[t2]+=i-1;
lie_num[t2]++;
hang_num[t1]++;
这一次的优化效果巨大,我差点以为这题过了
后来其实发现还有点远..
结局:Time Limit Exceeded on Test 218 (约2000ms)
优化9:
将r和另外两个if拖出去
因为这对循环次数的减少为1,所以这次优化的效果相对并不够好,实际上,这次优化后代码优化了约22.5%,
结局:Time Limit Exceeded on Test 218 (约1550ms)
优化10:
进行第三次常数调整
int i;
int t1=lef[x][y];
int t2=up[x][y];
hang_num[t1]--;
lie_num[t2]--;
int l=1;
l=max(l,hang[t1]-sum2[hang_num[t1]]);
l=max(l,lie[t2]-sum2[lie_num[t2]]);
int r=9;
r=min(r,hang[t1]-sum1[hang_num[t1]]);
r=min(r,lie[t2]-sum1[lie_num[t2]]);
if (hang_num[t1]==0)
{
l=max(l,hang[t1]);
r=min(r,hang[t1]);
}
if (lie_num[t2]==0)
{
l=max(l,lie[t2]);
r=min(r,lie[t2]);
}
if (l>r)
{
hang_num[t1]++;
lie_num[t2]++;
return;
}
int oh=hang[t1];
int ol=lie[t2];
int uh=used_hang[t1];
int ul=used_lie[t2];
for (i=l;i<=r;i++)
{
if ((1<<i)&used_hang[t1]) continue;
if ((1<<i)&used_lie[t2]) continue;
hang[t1]=oh-i;
lie[t2]=ol-i;
used_hang[t1]=uh^(1<<i);
used_lie[t2]=ul^(1<<i);
if (hang_num[t1]==1)
{
if ((1<<hang[t1])&(used_hang[t1]))
{
continue;
}
}
if (lie_num[t2]==1)
{
if ((1<<lie[t2])&(used_lie[t2]))
{
continue;
}
}
type[x][y]=i;
dfs(next_x[x][y],next_y[x][y]);
}
hang[t1]=oh;
lie[t2]=ol;
used_hang[t1]=uh;
used_lie[t2]=ul;
lie_num[t2]++;
hang_num[t1]++;
结局:Time Limit Exceeded on Test 218 (约1400ms)
优化11:
这时候常数卡不下去了
剩下的优化只能通过减少状态
我们回头看优化1和优化2
我们发现,对于不同的当前状态的sum值可以进一步减小
我们预处理出来,可以进一步优化
for (i=0;i<10;i++)
{
int j;
for (j=0;j<1024;j++)
{
int k;
int cnt=0;
sum1[i][j]=0;
for (k=1;;k++)
{
if (cnt==i) break;
if ((1<<k)&j) continue;
sum1[i][j]+=k;
cnt++;
}
cnt=0;
sum2[i][j]=0;
for (k=9;;k--)
{
if (cnt==i) break;
if ((1<<k)&j) continue;
sum2[i][j]+=k;
cnt++;
}
}
}
结局:Time Limit Exceeded on Test 218 (约1040ms)
这时候换成GNU C++可能能过了
优化12:
我们回头看决定性的优化,优化7
实际上我们也有些长度为2的计算不出来
我们可以通过预处理把这个值给算出来
虽然代码整体很不好看,但是这个优化真的起了作用
结局:Accepted (约750ms)
*去掉优化5这种东西后,跑了约680ms
GNU C++提交后跑了577ms
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int hang[32];
int hang_num[32];
int used_hang[32];
int lie[32];
int lie_num[32];
int used_lie[32];
int type[16][16];
int lin=0;
int col=0;
int up[16][16];
int lef[16][16];
int sum1[8][1024];
int sum2[8][1024];
int next_x[16][16];
int next_y[16][16];
bool cannot[48][1024][8];
int n,m;
void dfs(int x,int y)
{
if (x==n)
{
int i;
for (i=0;i<n;i++)
{
int j;
for (j=0;j<m;j++)
{
if (type[i][j]==-1)
{
printf("_");
}
else
{
printf("%d",type[i][j]);
}
if (j!=m-1) printf(" ");
}
printf("\n");
}
exit(0);
}
int i;
int t1=lef[x][y];
int t2=up[x][y];
hang_num[t1]--;
lie_num[t2]--;
int l=1;
l=max(l,hang[t1]-sum2[hang_num[t1]][used_hang[t1]]);
l=max(l,lie[t2]-sum2[lie_num[t2]][used_lie[t2]]);
int r=9;
r=min(r,hang[t1]-sum1[hang_num[t1]][used_hang[t1]]);
r=min(r,lie[t2]-sum1[lie_num[t2]][used_lie[t2]]);
if (hang_num[t1]==0)
{
l=max(l,hang[t1]);
r=min(r,hang[t1]);
}
if (lie_num[t2]==0)
{
l=max(l,lie[t2]);
r=min(r,lie[t2]);
}
if (l>r)
{
hang_num[t1]++;
lie_num[t2]++;
return;
}
int oh=hang[t1];
int ol=lie[t2];
int uh=used_hang[t1];
int ul=used_lie[t2];
for (i=l;i<=r;i++)
{
if ((1<<i)&used_hang[t1]) continue;
if ((1<<i)&used_lie[t2]) continue;
hang[t1]=oh-i;
lie[t2]=ol-i;
used_hang[t1]=uh^(1<<i);
used_lie[t2]=ul^(1<<i);
if (cannot[hang[t1]][used_hang[t1]][hang_num[t1]])
{
continue;
}
if (cannot[lie[t2]][used_lie[t2]][lie_num[t2]])
{
continue;
}
type[x][y]=i;
dfs(next_x[x][y],next_y[x][y]);
}
hang[t1]=oh;
lie[t2]=ol;
used_hang[t1]=uh;
used_lie[t2]=ul;
lie_num[t2]++;
hang_num[t1]++;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d%d",&n,&m);
int i;
for (i=0;i<n;i++)
{
int j;
for (j=0;j<m;j++)
{
static char c[15];
scanf("%s",c);
if (c[0]=='.')
{
type[i][j]=0;
}
else
{
type[i][j]=-1;
if (c[2]=='X') continue;
if (c[0]!='X')
{
up[i][j]=col;
lie[col]=(c[0]-'0')*10+c[1]-'0';
col++;
}
if (c[3]!='X')
{
lef[i][j]=lin;
hang[lin]=(c[3]-'0')*10+c[4]-'0';
lin++;
}
}
}
}
for (i=0;i<n;i++)
{
int j;
for (j=0;j<m;j++)
{
if (type[i][j]==0)
{
int k;
for (k=j-1;k>=0;k--)
{
if (type[i][k]==-1) break;
}
lef[i][j]=lef[i][k];
hang_num[lef[i][j]]++;
for (k=i-1;k>=0;k--)
{
if (type[k][j]==-1) break;
}
up[i][j]=up[k][j];
lie_num[up[i][j]]++;
}
}
}
int lastx=n;
int lasty=0;
for (i=n-1;i>=0;i--)
{
int j;
for (j=m-1;j>=0;j--)
{
if (type[i][j]==0)
{
next_x[i][j]=lastx;
next_y[i][j]=lasty;
lastx=i;
lasty=j;
}
}
}
for (i=0;i<8;i++)
{
int j;
for (j=0;j<1024;j++)
{
int k;
int cnt=0;
sum1[i][j]=0;
for (k=1;;k++)
{
if (cnt==i) break;
if ((1<<k)&j) continue;
sum1[i][j]+=k;
cnt++;
}
cnt=0;
sum2[i][j]=0;
for (k=9;;k--)
{
if (cnt==i) break;
if ((1<<k)&j) continue;
sum2[i][j]+=k;
cnt++;
}
}
}
memset(cannot,true,sizeof(cannot));
for (i=0;i<1024;i+=2)
{
int x1,x2,x3,x4,x5;
cannot[0][i][0]=false;
for (x1=1;x1<=9;x1++)
{
if ((1<<x1)&i) continue;
cannot[x1][i][1]=false;
for (x2=x1+1;x2<=9;x2++)
{
if ((1<<x2)&i) continue;
cannot[x1+x2][i][2]=false;
for (x3=x2+1;x3<=9;x3++)
{
if ((1<<x3)&i) continue;
cannot[x1+x2+x3][i][3]=false;
for (x4=x3+1;x4<=9;x4++)
{
if ((1<<x4)&i) continue;
cannot[x1+x2+x3+x4][i][4]=false;
for (x5=x4+1;x5<=9;x5++)
{
if ((1<<x5)&i) continue;
cannot[x1+x2+x3+x4+x5][i][5]=false;
}
}
}
}
}
}
dfs(lastx,lasty);
return 0;
}
评论 (0)