小游戏 题解
KesdiaelKen
2018-11-04 10:07:21
# T1 小游戏 题解
这个游戏是真实存在的，原名叫做**聪明方格**，大家可以自己上网搜一搜。
作为比赛T1，肯定很简单。正解即是爆搜。
### 方法1
简单爆搜。但是会超时，大约只有$30$分。
### 方法2
考虑方法1的一个可能使时间复杂度上升的地方。因为在每一次填完一个连同块后，都得重新扫一遍之前的格子，所以每一次的判断时间复杂度都是n^2。我们可以改进一下，开一个数组记录每一个连同块目前的结果。这样，如果是判断某一个符号为加或乘的连同块填完后的结果是否符合要求，则可以直接调用记录进行比较。加上了实时记录的连同块计算结果，还可以剪枝，即如果还没有填完某个连同块，其中的数就已经超过了要求的结果，或者运算符是乘法的连同块目前的结果不是要求结果的因数，则可以直接return。加上了这样的优化，大约可以得到$60$。
### 方法3
方法2的基础上进行玄学优化。如果将可能情况越少的限制条件看做其优先级更高，则连同块的条件肯定比每行每列不重复的条件优先级高。因此，我们可以优先考虑连同块的填数，即以每一个连同块为单位进行填数枚举，在此基础上进行行列不重复判断。并且，枚举连同块的顺序也要有讲究，一定是要在填完一个连同块后继续填相邻的连同块，否则可能比没有加优化的程序还慢。原因是：枚举不相邻的连同块，行列不重复条件没有充分利用，还可能绕过了行列不重复的判断，因此时间复杂度会增加；而枚举相邻的连同块，恰好同时利用了两个限制条件，可能情况更少，就可以跑得更快了。
本题就是个爆搜，但是标称的代码量巨大，大家可以打来练练手。当然，不排除有大佬用$10$行代码秒杀本题，也可能会有人用一些玄学算AC本题。
总之，第一题就是给大家玩玩的，希望大家打代码开心！
```cpp
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
using namespace std;
map<int,int>dy;
int sdk[20][20],usa[200][2],sol[20][20],ans[200]={0},jl[200][2]={0};
inline int cha(char a)//返回运算符的编号
{
if(a=='+')return 1;
if(a=='-')return 2;
if(a=='*')return 3;
return 4;
}
int gs[200]={0};
int n;
bool used[2][20][10]={0};
bool tf=true;
struct POS//下为链表结构
{
int x,y,nexty;
}pos[200];
int head[200]={0};
int first[200]={0};
int cnt=0;
inline void forward(int a,int b)//将某一个格子填入的数计入它所属的连同块的记录当中
{
if(usa[sdk[a][b]][0]&1)
{
if(usa[sdk[a][b]][0]==1)ans[sdk[a][b]]+=sol[a][b];
else
{
if(!ans[sdk[a][b]])ans[sdk[a][b]]=sol[a][b];
else ans[sdk[a][b]]*=sol[a][b];
}
return;
}
if(!jl[sdk[a][b]][0])jl[sdk[a][b]][0]=sol[a][b];
else jl[sdk[a][b]][1]=sol[a][b];
}
inline void backward(int a,int b)//与上一个函数的功能相反，将此格在记录删除
{
if(usa[sdk[a][b]][0]&1)
{
if(usa[sdk[a][b]][0]==1)ans[sdk[a][b]]-=sol[a][b];
else ans[sdk[a][b]]/=sol[a][b];
return;
}
if(jl[sdk[a][b]][1])jl[sdk[a][b]][1]=0;
else jl[sdk[a][b]][0]=0;
}
int sa,sb;
inline bool check(int a,int b)//检查是否符合连同块条件（见50分做法与70分的优化）
{
if(b)
{
if(usa[a][0]==3)
{
if(ans[a]>usa[a][1]||usa[a][1]%ans[a])return false;
return true;
}
if(ans[a]<usa[a][1])return true;
return false;
}
if(usa[a][0]&1)
{
if(ans[a]==usa[a][1])return true;
return false;
}
sa=jl[a][0],sb=jl[a][1];
if(sa<sb)swap(sa,sb);
if(usa[a][0]==2)
{
if(sa-sb==usa[a][1])return true;
return false;
}
if((sa%sb)||(sa/sb!=usa[a][1]))return false;
return true;
}
void dfs(int node)//搜索函数
{
if(!node)//如果链表遍历完毕
{
for(register int i=1;i<=n;i++)
{
for(register int j=1;j<=n;j++)printf("%d ",sol[i][j]);
printf("\n");
}
tf=false;//已经解完
return;
}
register int a=pos[node].x,b=pos[node].y;
for(register int i=1;i<=n&&tf;i++)
if(!used[0][a][i]&&!used[1][b][i])//没用过此数
{
sol[a][b]=i;
used[0][a][i]=used[1][b][i]=true;
gs[sdk[a][b]]--;
forward(a,b);
if(check(sdk[a][b],gs[sdk[a][b]]))
{
dfs(pos[node].nexty);
}
backward(a,b);
gs[sdk[a][b]]++;
used[0][a][i]=used[1][b][i]=false;
}
}
int shu,ch;
inline int dr()//读入优化
{
shu=ch=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')shu=shu*10+ch-'0',ch=getchar();
return shu;
}
int main()
{
int no=0;
n=dr();
char ope;
int ty,num;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)//处理连同块情况
{
ty=dr();
if(!dy.count(ty))dy[ty]=no++;
sdk[i][j]=dy[ty];
gs[sdk[i][j]]++;
cnt++;
pos[cnt].x=i,pos[cnt].y=j;
pos[cnt].nexty=head[sdk[i][j]];
head[sdk[i][j]]=cnt;
if(!first[sdk[i][j]])first[sdk[i][j]]=cnt;
}
while(scanf("%d%d %c",&ty,&num,&ope)!=EOF)//读入条件
{
ty=dy[ty];
usa[ty][0]=cha(ope);
usa[ty][1]=num;
}
for(register int i=0;i<no-1;i++)pos[first[i]].nexty=head[i+1];
dfs(head[0]);//从头开始遍历
}
```
PS：这是出题人好久之前打的代码了，码风……看不懂也没什么办法，毕竟出题人现在也不怎么看得懂……