牛客题解 贝伦卡斯泰露

链接：https://ac.nowcoder.com/acm/problem/14132

来源：牛客网

题解

作者 岛田小雅

子序列的概念，需要区别于子串。

本来以为是道 DP 题，看了下范围发现爆搜好像问题也不是很大，于是我用了 DFS 爆搜。

我一开始看错题了，以为输入的是可以看作一个字符的数字，后来 WA 了两发才发现 \(A_i\) 是个数字而且范围是 \((1\leqslant{A_i}\leqslant{40})\)。但是问题不大，我们先把输入的东西当成一个字符来做，最后把输入改成整型，在判断时把 \(\texttt{int}\) 显式类型转换成 \(\texttt{char}\) 就可以啦。

具体实现见 AC 代码。

*AC 代码中使用了一个很方便的小玩意：\(\texttt{substr()}\)，它可以返回一个字符串在任意区间的子串。

AC 代码

作者 岛田小雅

#include <bits/stdc++.h>
using namespace std;

const int N = 42;
int t, n;
int lst[N];
bool ans;

void dfs(int p, string s1, string s2)
{
    if(ans) return; // 如果已经有一个答案，那剩下的就都不用考虑了
    if(s1.size() > n/2) return; // s1过长，该情况不合法
    if(s2.size() > s1.size()) return; // 规定s1的长度必须大于等于s2，避免重复搜索
    if(s2 != s1.substr(0,s2.size())) return; // 如果两个字符串前面不一样，后面就不用考虑了
    if(p > n) ans = true;
    else
    {
        dfs(p+1,s1+(char)lst[p],s2);
        dfs(p+1,s1,s2+(char)lst[p]);
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--)
    {
        ans = false;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> lst[i];
        dfs(1,"","");
        if(ans) cout << "Frederica Bernkastel\n";
        else cout << "Furude Rika\n";
    }
    return 0;
}