Codeforces GYM 100503B: Kakuro 题解

81 阅读 0 评论 54 点赞

我是靠谱客的博主专一蜻蜓，最近开发中收集的这篇文章主要介绍Codeforces GYM 100503B: Kakuro 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这题很显然的是搜索+剪枝

有两个较好的剪枝：

1.不要按kakuro棋盘的顺序搜索，这样可能会被特殊数据卡掉，可以random_shuffle一下搜索顺序

2.我们用布尔数组can[i][j][k]表示该行(列)还有i个空格可以填，当前已经用过的数为j(j是一个Mask)，最终该行(列)要求和为k能否达到

用Mask数组canMask[i][j][k]表示该行(列)还有i个空格可以填，当前已经用过的数为j(j是一个Mask)，最终该行(列)要求和为k如果能达到，当前可以填哪几个数

can数组可以dp写出来：if ! j&1<<(u-1) && can[i-1][j | 1<<(u-1)][k] can[i][j][k]=true 同时更新canMask

这样搜索的时候在横竖的canMask的交集里面搜就可以了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <utility>
#include <map>
#include <stack>
#include <set>
#include <vector>
#include <queue>
#include <deque>
#include <sstream>
#include <bitset>
#include <ctime>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define LL long long
#define ld long double
#define Pair pair<int,int>
#define LOWBIT(x) x & (-x)
using namespace std;
const int INF=0x7ffffff;
const int MOD=1e9+7;
const int magic=348;
struct node
{
int type;
int down,right;
}a[10][10];
bool f=false;
int n,m;
inline int getInd(int x,int y)
{
return (x-1)*m+y;
}
inline Pair getnum(int id)
{
int x=id%m==0?id/m:id/m+1;
int y=id-x*m;
return mp(x,y);
}
int cc=0;
Pair seq[4800];
int psum_l[2000],psum_s[2000];
Pair rc[1000];
int sum[1000],cnt[1000];
Pair bel[1000];
int ans[10][10];
bool can[10][1100][60];
int canMask[10][1100][60];
map<pair<int,bool>,int> ID;int top=0;
inline int getID(pair<int,bool> x)
{
if (ID[x]) return ID[x];
ID[x]=++top;
return top;
}
int used[2000];
void dfs(int nn)
{
if (nn==cc+1)
{
f=true;
return;
}
int x=seq[nn].x,y=seq[nn].y;
int i,j,dd;
vector<int> can_use;
int xx=bel[getInd(x,y)].x,yy=bel[getInd(x,y)].y;
int can=canMask[cnt[xx]][used[xx]][sum[xx]]&canMask[cnt[yy]][used[yy]][sum[yy]];
for (i=1;i<=9;i++)
{
if (!(can&(1<<(i-1)))) continue;
dd=i;
ans[x][y]=dd;
cnt[xx]--;cnt[yy]--;
used[xx]^=(1<<(dd-1));used[yy]^=(1<<(dd-1));
dfs(nn+1);
if (f) return;
cnt[xx]++;cnt[yy]++;
used[xx]^=(1<<(dd-1));used[yy]^=(1<<(dd-1));
}
}
void init()
{
int i,j,k,u;
int s;
for (j=0;j<=(1<<9)-1;j++)
for (k=0;k<=60;k++)
{
s=0;
for (u=1;u<=9;u++)
if (j&(1<<(u-1))) s+=u;
if (s==k) can[0][j][k]=true; else can[0][j][k]=false;
}
for (i=1;i<=6;i++)
for (j=0;j<=(1<<9)-1;j++)
for (k=0;k<=60;k++)
for (u=1;u<=9;u++)
if ((j&(1<<(u-1)))==0 && can[i-1][j|(1<<(u-1))][k])
{
can[i][j][k]=true;
canMask[i][j][k]=(canMask[i][j][k]|(1<<(u-1)));
}
}
int main ()
{
freopen ("input.txt","r",stdin);
freopen ("output.txt","w",stdout);
int i,j,k,num;string s;
cin>>n>>m;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
cin>>s;
if (s=="XXXXX") a[i][j].type=1;
if (s==".....") a[i][j].type=2;
if (s[2]=='\' )
{
a[i][j].type=3;
if (s[0]=='X')
a[i][j].down=-1;
else
{
stringstream ss(s.substr(0,2));
ss>>a[i][j].down;
}
if (s[3]=='X')
a[i][j].right=-1;
else
{
stringstream ss(s.substr(3,2));
ss>>a[i][j].right;
}
}
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
if (a[i][j].type!=3) continue;
if (a[i][j].down!=-1)
{
num=getID(mp(getInd(i,j),false));
rc[num]=mp(getInd(i,j),false);
sum[num]=a[i][j].down;cnt[num]=0;
for (k=i+1;k<=n && a[k][j].type==2;k++)
{
bel[getInd(k,j)].x=num;
cnt[num]++;
}
}
if (a[i][j].right!=-1)
{
num=getID(mp(getInd(i,j),true));
rc[num]=mp(getInd(i,j),true);
sum[num]=a[i][j].right;
for (k=j+1;k<=m && a[i][k].type==2;k++)
{
bel[getInd(i,k)].y=num;
cnt[num]++;
}
}
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (a[i][j].type==2)
seq[++cc]=mp(i,j);
init();
dfs(1);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
if (a[i][j].type==2) cout<<ans[i][j]; else cout<<"_";
if (j==m) cout<<'n'; else cout<<' ';
}
return 0;
}