这道题,又是一位玄学搜索......

我是用的蜗牛序搜的(顾名思义,@,这么搜),我正着搜80然后一反转比原来快了几十倍........一下AC.......

我的思路是这样的话我们可以从内到外或者从外到内搜索,这样的话我们就可以在一定程度上运用贪心,因为中间的价值大外面的价值小,我是作为一个从来没有玩过数独的人的思路...然而任何一个玩过数独的人都会先选可能状态少的优先搜索.......

对于这题里的数据,可行方案很少因此摆在我们面前的不是减去不优的解而是减去不成立的解,然而对于不成立的解在我们真正意识到他不成立之前他也许是很优的,然而我们要提前预知是否是可行解基本不可行,那么我们就还真得爆搜了,然而怎样让我们的爆搜AC而不是TLE呢:我们搜索到的深度是一定的所以我们就要让他更晚“蓬松”,对于这样一个玄学的搜搜,我们这样的策略似乎是最可行且科学的了

#include <cstdio>
namespace Pre{
inline void read(int &sum){
register char ch=getchar();
for(sum=;ch<''||ch>'';ch=getchar());
for(;ch>=''&&ch<='';sum=(sum<<)+(sum<<)+ch-'',ch=getchar());
}
inline int Max(int x,int y){
return x>y?x:y;
}
inline int Abs(int x){
return x<?-x:x;
}
int bin[],have[][],pos[][],val[][];
inline void Init(){
bin[]=;
for(int i=;i<=;i++)
bin[i]=bin[i-]<<;
int full=(<<)-;
for(int i=;i<=full;i++)
for(int j=;j>;j--)
if((bin[j]&i)==){
have[i][++have[i][]]=j;
}
}
int ans;
}
namespace Handle{
int line[],column[],big_lattice[],key[][];
}
namespace point{
struct Point{
int x,y;
inline friend Point operator + (Point a,Point b);
inline void operator += (Point a){
*this=(*this)+a;
}
}S,X,Z,Y,N,Queue[];
int len;
inline Point operator + (Point a,Point b){
return (Point){a.x+b.x,a.y+b.y};
}
inline void Init(){
N.x=,N.y=;
S.x=-,S.y=;
X.x=,X.y=;
Z.x=,Z.y=-;
Y.x=,Y.y=;
}
inline Point To(){
int Dis=Pre::Max(Pre::Abs(N.x-),Pre::Abs(N.y-));
if(N.y==Dis+&&N.x!=Dis+)return X;
if(N.x==Dis+&&N.y!=-Dis)return Z;
if(N.x==-Dis&&N.y!=-Dis&&N.y!=+Dis)return Y;
if(N.y==-Dis)return S;
}
inline int get_val(Point p){
int Dis=Pre::Max(Pre::Abs(p.x-),Pre::Abs(p.y-));
return -Dis;
}
inline int get_pos(Point p){
return (p.x-)/*+(p.y-)/+;
}
inline void get_queue(){
if(N.x==)return;
if(Handle::key[N.x][N.y]){
N+=To();
get_queue();
return;
}
Queue[++len]=N;
N+=To();
get_queue();
}
}
namespace Handle{
inline void Insert(point::Point p,int Key){
using Pre::bin;
using Pre::pos;
key[p.x][p.y]=Key;
line[p.x]|=bin[Key];
column[p.y]|=bin[Key];
big_lattice[pos[p.x][p.y]]|=bin[Key];
}
inline void Delete(point::Point p){
using Pre::bin;
using Pre::pos;
line[p.x]^=bin[key[p.x][p.y]];
column[p.y]^=bin[key[p.x][p.y]];
big_lattice[pos[p.x][p.y]]^=bin[key[p.x][p.y]];
key[p.x][p.y]=;
}
}
namespace Main{
void Init(){
using namespace point;
Pre::Init();
point::Init();
for(int i=;i<=;i++)
for(int j=;j<=;j++)
Pre::pos[i][j]=get_pos((Point){i,j}),
Pre::val[i][j]=get_val((Point){i,j});
for(int i=,x;i<=;i++)
for(int j=;j<=;j++)
Pre::read(x),Handle::Insert((Point){i,j},x),Pre::ans+=Pre::val[i][j]*x;
get_queue();
using namespace Handle;
using Pre::pos;
using Pre::val;
using Pre::have;
}
void dfs(int Now,int Had){
if(Now==){
Pre::ans=Pre::Max(Pre::ans,Had);
return;
}
using namespace point;
using namespace Handle;
using Pre::pos;
using Pre::val;
using Pre::have;
int Can=line[Queue[Now].x]|column[Queue[Now].y]|big_lattice[pos[Queue[Now].x][Queue[Now].y]];
for(int i=;i<=have[Can][];i++){
Handle::Insert(Queue[Now],have[Can][i]);
dfs(Now-,Had+have[Can][i]*val[Queue[Now].x][Queue[Now].y]);
Handle::Delete(Queue[Now]);
}
}
inline void Work(){
int HAD=Pre::ans;
dfs(point::len,HAD);
if(point::len!=&&HAD==Pre::ans)Pre::ans=-;
}
}
int main(){
freopen("sudoku.in", "r", stdin);
freopen("sudoku.out", "w", stdout);
Main::Init();
Main::Work();
printf("%d",Pre::ans);
return ;
}

最新文章

  1. excel链接sharepoint 用于 Excel 的 Microsoft Power Query
  2. TD Rigging Demo Reel 性感美女绑定展示
  3. 关于字符串查找 charindex ,Patindex 还有一个like
  4. Spark大数据的学习历程
  5. RC-50221 问题解决 - netstat 查看端口占用情况
  6. MySQL 仅保留7天、一个月数据
  7. 【Add binary】cpp
  8. ocp 1Z0-051 1-22题解析
  9. PHP之open_ssl
  10. Crashing Robots
  11. 表单提交---前端页面模拟表单提交(form)
  12. windows下eclipse跑junit报错:CreateProcess error=206
  13. orientationchange
  14. 在 .NET中,一种更方便操作配置项的方法
  15. r.js合并实践
  16. Python线性表——单链表
  17. vue生产环境清除console.log
  18. zookeeper 启动显示started,jps查看进程却没有,解决方法
  19. 2018-11-26 BIG DATA ANALYSIS
  20. 何登成大神对Innodb加锁的分析

热门文章

  1. Win7下如何安装python pygame的whl包
  2. .net Core错误记录
  3. delphi 数据库中Connection与Query连接数量问题思考
  4. 扩展报表-JavaSet
  5. Plsql developer 怎么在打开时登陆配置oracel client?
  6. 各种网站,app的手机号绑定真坑爹
  7. Accept 惊群现象测试perl脚本
  8. 04-Mysql----初识sql语句
  9. spring+apache dbcp +oracle 连接池配置以及优化
  10. devstack环境搭建