欢迎访问 生活随笔!

生活随笔

当前位置: 首页 > 运维知识 > windows >内容正文

windows

AtCoder Beginner Contest 327 (ABC327)

发布时间:2023/11/16 windows 31 coder
生活随笔 收集整理的这篇文章主要介绍了 AtCoder Beginner Contest 327 (ABC327) 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

A. ab

直接根据题意模拟即可。
Code

B. A^A

直接枚举 \(i= 1, 2,\dots, 15\),每次看看 \(i ^ i\) 是否等于 \(A\) 即可。
Code

C. Number Place

Description

给你一个 \(9 \times 9\) 的矩阵 \(A\),判断是否合法,满足以下三个条件,即为合法。

  • 对于每一行,包含数字 \(1 \sim 9\)
  • 对于每一列,包含数字 \(1 \sim 9\)
  • 将矩阵 \(A\) 从上到下分成三组,每组三行三列。这样会分成 \(9\)\(3 \times 3\) 的矩阵,每个矩阵也必须包含 \(1 \sim 9\) 的每个数字。

Solution

直接根据题意模拟即可。

每一行每一列不能出现同样的数字,很好判断。用 \(cntx\) 数组记录每一样每一个数字出现的次数;用 \(cnty\) 数组记录每一列每个数字出现的次数。

最后判断 \(cntx_i\)\(cnty_i\) 是否都 \(= 1\) 即可。

再处理第三种情况,将矩阵分成 \(9\)\(3 \times 3\) 的矩阵。这种情况我们可以分别枚举行的起点和列的起点,每次再从起点循环,就能取出每个小矩阵。

然后再用 \(cnt\) 数组记录出每个数字出现的次数,最后判断。

Code

D. Good Tuple Problem

Description

给你两个长度为 \(M\) 的序列 \(A\)\(B\),满足以下条件时成为他们是“好的序列”。

  • 存在一个长度为 \(N\) 的序列 \(X\),只由 \(0\)\(1\) 组成,满足以下条件:
    • 对于每个 \(i = 1,2,\dots M\)\(X_{A_i} \neq X_{B_i}\)

现在,请你判断序列 \((A,B)\) 是否是“好的序列”。

Solution

这道题非常经典,是一个二分图板子。

使用 DFS 判断是否是二分图。

维护数组 \(f\) 来记录当前的状态:

  • \(f_v = -1\) 表示当前结点 \(v\) 还未被访问。
  • \(f_v = 0/1\) 表示该顶点上写的是 \(0/1\)

对于每个 \(v = 1,2, \dots ,M\),执行以下操作:

  • 如果 \(f_v \neq -1\),表示已经访问了节点 \(v\),直接 continue
  • 如果 \(f_v = -1\),说明当前的联通块还没有被访问过。执行 DFS,从这个节点开始 DFS,执行二分图黑白染色。

最后判断这张图是否是二分图,输出答案即可。

Code

其他的不会。

总结

以上是生活随笔为你收集整理的AtCoder Beginner Contest 327 (ABC327)的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错,欢迎将生活随笔推荐给好友。