算法刷题笔记|牛客网 NC14132 贝伦卡斯泰露 DFS DFS|#

文章目录

1. 题目描述

1.1. Limit
1.2. Problem Description
1.3. Input
1.4. Output
1.5. Sample Input
1.6. Sample Output
1.7. Source

2. 解读
3. 代码

1. 题目描述 1.1. Limit

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description
贝伦卡斯泰露，某种程度上也可以称为古手梨花，能够创造几率近乎为0的奇迹，通过无限轮回成功打破了世界线收束理论。和某科学者不同，贝伦并不在意世界线收束的那套理论，作为奇迹之魔女，贝伦的爱好只在于品茶。作为品茶的消遣，贝伦正在解一道简单的谜题。
给出一个长度为n的数列A i A_i Ai?，问是否能将这个数列分解为两个长度为n / 2 n/2 n/2 的子序列，满足

两个子序列不互相重叠。
两个子序列中的数要完全一样， { 1 , 2 } = { 1 , 2 } \{1, 2\} = \{1, 2\} {1,2}={1,2} ， { 1 , 2 } ≠ { 2 , 1 } \{1, 2\} \ne \{2, 1\} {1,2}?={2,1}。

1.3. Input
第一行，一个正整数T T T ，表示数据组数。
接下来T T T 组数据，每组数据的第一行，一个正整数n n n，第二行n n n 个正整数A i A_i Ai?。
1.4. Output
每组数据输出一行，如果可以完成，输出Frederica Bernkastel，否则输出Furude Rika。
1.5. Sample Input

3 4 1 1 2 2 6 1 2 3 4 5 6 4 1 2 2 1

1.6. Sample Output

Frederica Bernkastel Furude Rika Furude Rika

1.7. Source
牛客网 NC14132 贝伦卡斯泰露
2. 解读 DFS
维护两个数组l i s t A listA listA 和l i s t B listB listB，在每遇到一个匹配的元素A i A_i Ai? 时，会进入分岔点，如果该元素A i A_i Ai? 进入队列l i s t B listB listB 后能够搜索完全部元素，则搜索完成。
如果l i s t A listA listA 中的元素数列超过所有元素数列n n n 的一半，即l i s t A . s i z e ( ) > n / 2 listA.size() > n / 2 listA.size()>n/2，则回退到上一步，让元素进入 l i s t B listB listB。
重复上述步骤即能遍历所有情况。
比如如下测试用例。

1 6 1 1 2 1 1 2

T a b l e 1. 计算过程表 Table 1. \text{计算过程表} Table1.计算过程表

序号	l i s t A listA listA	l i s t B listB listB	入队元素	备注
1	1	n u l l null null	1	初始化
2	1	1	1	入队 B
3	1 2	1	2	入队 A
4	1 2 1	1	1	入队 A
5	1 2 1 1	1	1	队A元素4 > 3
6	1	n u l l null null		回退
7	1 1	n u l l null null	1	入队 A
8	1 1 2	n u l l null null	2	入队 A
9	1 1 2	1	1	入队B
10	1 1 2	1 1	1	入队B
11	1 1 2	1 1 2	2	入队B
12	1 1 2	1 1 2		搜索完成

3. 代码

#include using namespace std; int list[41], listA[41], listB[41], t, n; //i,j分别表示listA[],listB[]中元素个数,id表示当前匹配元素下标 bool dfs(int i, int j, int id) { if (i > n / 2 || j > n / 2) { // 若子序列中元素个数大于总元素个数的一半，停止搜索 return 0; } if (id > n) { // 若已搜索完全部元素，搜索完成 return 1; } //当前元素匹配,加入到listB[] if (list[id] == listA[j + 1]) { listB[j + 1] = list[id]; // listB长度加一，继续递归 if (dfs(i, j + 1, id + 1)) { // 若搜索完成，结束搜索 return 1; } } //即使相等也加入listA[]或者不相等加入到listA[] listA[i + 1] = list[id]; // listA长度加一，递归 return dfs(i + 1, j, id + 1); } int main() { cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) cin >> list[i]; listA[1] = list[1]; puts(dfs(1, 0, 2) ? "Frederica Bernkastel" : "Furude Rika"); } return 0; }

注：代码参考自v5zsq 的CSDN博客
联系邮箱：curren_wong@163.com
Github：https://github.com/CurrenWong
【算法刷题笔记|牛客网 NC14132 贝伦卡斯泰露 DFS】欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。