每日一题 | 老板出的下棋问题

发布于

昨日问题

传送门

同样出自codeforces，是codeforces套题中的C题，难度大约LeetCode Medium-Hard。链接：https://codeforces.com/contest/1395/problem/C

PS再次推荐一下这个网站，免费的刷题网站，所有的题解以及其他人的代码都可以免费查看。而且其中的题目质量很高，虽然是竞赛网站，但是难度不会过度大。以思维题尤为出众，属于即使算法你都会，但是就是不知道怎么用的题。

昨天的这道题可以算是其中之一，它是一道典型的反套路问题。我们一般思考问题都是先想到思路再去寻找答案，但是这道题反其道而行之，而是直接寻找答案。

因为题目当中的n, m的范围只有200，每个数字的最大范围是512。虽然看起来一通花里胡哨的and和or操作，但是我们仔细分析一下就会发现，不管多少个512以内的数进行怎样的and和or操作，最后的结果一定不会超过512。也就是说答案就在512之间。

所以我们可以抛弃思路直接去寻找答案，因为题目要求得到的结果最小，所以我们从最小的0开始寻找。如果说我们可以找到一个数k，使得对于每一个数都可以找到一个，使得，那么k就是最终的答案。

据说这道题还有动态规划的思路，但是我太菜了暂时还没想出来，欢迎有想法的同学找我讨论。

代码语言：javascript
复制
import sys

n, m = map(int, input().split(' '))


arrn = list(map(int, input().split(' ')))

arrm = list(map(int, input().split(' ')))


for k in range(512):

found = True

for i in range(n):

flag = False

for j in range(m):

if arrn[i] & arrm[j] | k == k:

flag = True

break

if not flag:

found = False

break


如果每一个a[i]都找到了一个b[j]


if found:
    print(k)
    break</code></pre></div></div><h3 id="5cn8n" name="%E4%BB%8A%E6%97%A5%E9%97%AE%E9%A2%98"><strong>今日问题</strong></h3><h4 id="6ojih" name="%E8%80%81%E6%9D%BF%E4%B8%8B%E6%A3%8B%E9%97%AE%E9%A2%98"><strong>老板下棋问题</strong></h4><p>老板很喜欢下棋，听说你也很喜欢下棋，于是给你出了一道下棋的问题。</p><p>给了你一个n * m的棋盘，并在棋盘的(x, y)位置放置了一颗棋子。保证这颗棋子不在棋盘边缘。这颗棋子每次可以移动到同行或者是同列的任何一个位置，要求你在不重复访问的前提下，把这个棋盘上的每一个位置都访问一次。</p><p>- END -</p>
#medium#ode#ps