Skip to content

牛客网 NC14132 贝伦卡斯泰露#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description#

贝伦卡斯泰露，某种程度上也可以称为古手梨花，能够创造几率近乎为0的奇迹，通过无限轮回成功打破了世界线收束理论。和某科学者不同，贝伦并不在意世界线收束的那套理论，作为奇迹之魔女，贝伦的爱好只在于品茶。作为品茶的消遣，贝伦正在解一道简单的谜题。

给出一个长度为n的数列 ，问是否能将这个数列分解为两个长度为 的子序列，满足

  • 两个子序列不互相重叠。
  • 两个子序列中的数要完全一样， ，。

1.3. Input#

第一行，一个正整数 ，表示数据组数。

接下来 组数据，每组数据的第一行，一个正整数 ，第二行 个正整数 。

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

维护两个数组 和 ， 在每遇到一个匹配的元素 时，会进入分岔点，如果该元素 进入队列 后能够搜索完全部元素，则搜索完成。

如果 中的元素数列超过所有元素数列 的一半，即 ，则回退到上一步，让元素进入。

重复上述步骤即能遍历所有情况。

比如如下测试用例。

1
6
1 1 2 1 1 2

| 序号 | | | 入队元素 | 备注 | | :---: | :-----: | :-----: | :------: | :----------: | | 1 | 1 | | 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 | | | 回退 | | 7 | 1 1 | | 1 | 入队 A | | 8 | 1 1 2 | | 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 <iostream>
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

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。

Back to top