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

昨日问题

传送门

同样出自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

今日问题

老板下棋问题

老板很喜欢下棋，听说你也很喜欢下棋，于是给你出了一道下棋的问题。

给了你一个n * m的棋盘，并在棋盘的(x, y)位置放置了一颗棋子。保证这颗棋子不在棋盘边缘。这颗棋子每次可以移动到同行或者是同列的任何一个位置，要求你在不重复访问的前提下，把这个棋盘上的每一个位置都访问一次。

- END -

medium ode ps

0 人点赞