当前位置: 代码迷 >> 综合 >> bzoj 5051: [Lydsy1709月赛]填字游戏
  详细解决方案

bzoj 5051: [Lydsy1709月赛]填字游戏

热度:73   发布时间:2023-10-29 05:03:18.0

链接:https://www.lydsy.com/JudgeOnline/problem.php?id=5051

本来挺简单的一个题,看漏了个条件,然后弄了半天不会做
然后和save_code讨论了一下,得出结论,都看漏条件了。。
在讨论里面可以看到,他是干脆没判就过了23333
然后下午就再GG中度过了
这种错误怎么一犯再犯呢。。
这可不行啊

来口胡一下做法吧,至于实现可能在晚点弄 (大概率咕了)

且上下边界的字符集与左右边界的字符集交集为空集。

这个条件非常重要,就是看漏了这个条件,然后就凉了
就因为这个条件,每一列/行的两个字母是没有用的,只需要看一下是不是一样的,不一样最后乘222就好了
然后不一样就可以变成覆盖某个格子是用行还是列,只要这个不一样就行了!
因为行和列永远不会冲突

有两个做法
可以直接爆搜,然后网络流剪枝,如果填到这个状态以后填不下去看就直接返回
也可以状压DP
fi,j,k,lf_{i,j,k,l}fi,j,k,l?表示处理到(i,j)(i,j)(i,j)这个格子
然后每一列的状态是kkk,这一行还有lll个格子没用
其中kkk是一个333进制的状态,表示这一列还有0/1/2个格子没有用
至于lll,也是0,1,20,1,20,1,2,同样的意思
按格子转移即可
时间复杂度算出来有点大。。但是时限也比较宽松

然后就没什么了。。

如果没有这个条件的话,状态数就没这么少了,并且容易DP出很多重复的情况,就会GG