社区讨论

【求助诸位神牛】请问是什么原因导致超时。

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 条回复,欢迎继续交流。

正在加载回复...