题解 | #贝伦卡斯泰露#

这是一道深度搜索的题目，具体解析在代码里

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

int arr[1001], arr_a[1001], arr_b[1001], n;//arr_a，arr_b分别是两个子序列

bool dfs(int i, int j, int k)//i, j, k分别是数组arr, arr_a, arr_b的下标
{
    if(j == k && j == n / 2) return true;
    if(i == n) return false;//两种情况分别是对和错
    if(i == 0)
    {
        arr_a[0] = arr[0];
        i++, j++;
    }
  	//当数组arr_a里面没有数时把第一个数加进去
    if(arr[i] != arr_a[k])//如果arr[i]! = arr_a[k]的话只能把这个数给arr_a
    {
        arr_a[j] = arr[i];
        return dfs(i + 1, j + 1, k);
    }
    else//不然可以给arr_a也可以给arr_b
    {
        arr_a[j] = arr[i];
        if(dfs(i + 1, j + 1, k))
            return true;
        arr_a[j] =  0;//这里需要回溯
        arr_b[k] = arr[i];
        if(dfs(i + 1, j, k + 1))
            return true;
        return false;
    }
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        memset(arr, 0, sizeof(arr));
        memset(arr_a, 0, sizeof(arr_a));
        memset(arr_b, 0, sizeof(arr_b));
      //每次循环之后重置数组
        cin >> n;
        for(int j = 0; j < n; j++)
            cin >> arr[j];
        if(n % 2 ==0 && dfs(0, 0, 0))
            cout << "Frederica Bernkastel" << endl;
        else
            cout << "Furude Rika" << endl;
    }
    return 0;
}