社区讨论
【求助诸位神牛】请问是什么原因导致超时。
P1074[NOIP 2009 提高组] 靶形数独参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi4hnxej
- 此快照首次捕获于
- 2025/11/18 19:27 4 个月前
- 此快照最后确认于
- 2025/11/18 19:27 4 个月前
自己已经加了搜索顺序优化和位运算优化,然而最后一个点还是tle了。加的剪枝效果也不是很明显······
没有学长和老师,只好求助于个位大神了,谢谢!
CPP#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<climits>
#include<ctime>
#define rep(i,s,n) for(int (i)=(s);(i)<=(n);(i)++)
using namespace std;
struct node
{
int x,y;
};
static node stk[100];
static int a[10][10],r[10],l[10],s[10],score,
CPP c[10][10][10],top,lim,re[3][10],sum;
int ans=-1;
int min(int a,int b)
{
return a<b? a : b;
}
int sdcnt(int x,int y,int k)
{
if(x==4&&y==4) return k*10;
else if(x>=3&&x<=5&&y>=3&&y<=5) return k*9;
else if(x>=2&&x<=6&&y>=2&&y<=6) return k*8;
else if(x>=1&&x<=7&&y>=1&&y<=7) return k*7;
else return k*6;
}
void fill(int x,int y,int k)
{
int t=1<<(k-1);
r[x]|=t;l[y]|=t;s[x/3*3+y/3]|=t;
--re[0][x];--re[1][y];--re[2][x/3*3+y/3];
score+=c[x][y][k];
}
bool pd(int x,int y,int k)
{
int t=1<<(k-1);
if(r[x]&t||l[y]&t||s[x/3*3+y/3]&t) return 0;
return 1;
}
inline void init()
{
rep(i,0,8) rep(j,0,8) rep(k,1,9)
c[i][j][k]=sdcnt(i,j,k);
rep(i,0,8) rep(j,0,8) //1
{
char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();
a[i][j]=ch-'0';
if(!pd(i,j,a[i][j])) {
printf("-1");exit(0);
}
if(a[i][j]) fill(i,j,a[i][j]);
else stk[++top]=(node){i,j},++lim,sum+=sdcnt(i,j,1);
}
}
void del(int x,int y,int k)
{
int t=1<<(k-1);
r[x]&=~t;l[y]&=~t;s[x/3*3+y/3]&=~t;
++re[0][x];++re[1][y];++re[2][x/3*3+y/3];
score-=c[x][y][k];
}
void update()
{
int a,b;
rep(i,1,top-1)
{
a=min(re[0][stk[i].x],min(re[1][stk[i].y],re[2][stk[i].x/3*3+stk[i].y/3]));
b=min(re[0][stk[i+1].x],min(re[1][stk[i+1].y],re[2][stk[i+1].x/3*3+stk[i+1].y/3]));
if(a<b)swap(stk[i+1],stk[i]);
}
}
/*inline int rest()
{
return sum;
}*/
void dfs(int dep)
{
//if(clock()>990) return;
if(dep==lim) // pd answer
{
if(ans<score) ans=score;
}
else
{
if(sum*9+score<ans) return;
update();
int x=stk[top].x,y=stk[top--].y;sum-=c[x][y][1];
for(int k=9;k>=1;k--) if(pd(x,y,k)) // new state && pd 2
{
fill(x,y,k); // record
dfs(dep+1);
del(x,y,k);
}
stk[++top]=(node){x,y},sum+=c[x][y][1];
}
}
int main()
{
freopen("e:/in.txt","r",stdin);
init();
dfs(0);
printf("%d",ans);
return 0;
}//by fjlyyz-ljy
回复
共 2 条回复,欢迎继续交流。
正在加载回复...