牛客练习赛3|牛客练习赛3 B - 贝伦卡斯泰露牛客练习赛3B-贝伦卡斯泰露

链接：https://www.nowcoder.net/acm/contest/13/B
来源：牛客网

题目描述贝伦卡斯泰露，某种程度上也可以称为古手梨花，能够创造几率近乎
为0的奇迹，通过无限轮回成功打破了世界线收束理论。
和某民科学者不同，贝伦并不在意世界线收束的那套理论，作为奇迹
之魔女，贝伦的爱好只在于品茶。
作为品茶的消遣，贝伦正在解一道简单的谜题。
给出一个长度为n的数列A ?，问是否能将这个数列分解为两个长度为n/2的子序列，满足 ? 两个子序列不互相重叠。
? 两个子序列中的数要完全一样，{1, 2} = {1, 2}，{1, 2} ≠ {2, 1}。输入描述: 第一行，一个正整数T，表示数据组数。接下来T组数据，每组数据的第一行，一个正整数n，第二行?个正整数A ?。输出描述:

每组数据输出一行，如果可以完成，输出Frederica Bernkastel，否则输出Furude Rika。

示例1 输入

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

输出

Frederica Bernkastel Furude Rika Furude Rika

备注:

对于30%的数据，? ≤ 16。
对于另20%的数据，? = 1。
对于另20%的数据，? = 2。
对于100%的数据，? ≤ 5，1 ≤ ?i <= n <= 40, 保证n为偶数。

题解爆搜。
这题数据有点水，一开始用了一种$O(n^2)$的贪心水过去了。
自己造了很多数据发现跑不过去。下面这些数据都是可以分割出来的。

100
38 29 29 35 39 35 37 24 34 39 37 24 34 3 3 6 6 25 2 17 32 25 11 25 2 2 32 17 32 25 16 11 2 25 9 32 16 25 9 26 10 25 10 2 25 2 35 6 6 35 6 6 32 32 11 32 32 11 26 26 30 30 18 18 18 18 40 1 24 1 24 8 8 39 6 39 34 28 6 34 5 31 7 28 37 20 28 5 7 31 7 28 37 23 1 16 20 7 13 23 14 1 16 40 13 14 40 40 30 30 6 5 6 21 5 21 39 39 39 35 2 9 39 32 35 2 18 2 3 9 32 2 4 18 3 14 22 9 14 4 14 22 9 35 34 14 35 34 38 3 4 3 5 4 6 5 6 2 6 6 2 1 5 4 6 1 4 5 4 6 4 5 4 5 4 3 3 4 3 4 3 1 3 1 3 2 2 20 3 2 2 3 2 3 2 3 6 3 3 3 4 2 6 5 3 4 2 5 16 2 17 27 37 25 38 2 17 27 25 27 37 25 38 27 25 10 37 26 26 37 26 26 36 26 26 36 12 5 5 36 33 33 5 5 36 33 33 9 9 10 19 18 29 19 29 19 18 29 19 29 12 10 19 40 10 40 19 40 40 5 40 40 5 10 20 20 1 20 20 7 7 1 7 7 10 10 10 21 2 2 10 10 21 2 2 10 15 15 24 16 16 15 15 24 16 16 10 32 2 32 20 32 32 2 32 20 32

#include using namespace std; const int maxn = 110; int T, n; int a[maxn], f[maxn]; int ans; void dfs(int x, int y, int num) { if(num == n) { ans = 1; return; } int tx = -1; for(int i = x + 1; i <= n; i ++) { if(f[i]) continue; tx = i; break; } if(tx == -1) return; int ty = -1; for(int i = y + 1; i <= n; i ++) { if(f[i]) continue; if(a[tx] != a[i]) continue; if(tx == i) continue; ty = i; f[tx] = 1; f[ty] = 1; dfs(tx, ty, num + 2); if(ans == 1) return; f[tx] = 0; f[ty] = 0; } }int main() { scanf("%d", &T); while(T --) { scanf("%d", &n); for(int i = 1; i <= n; i ++) { scanf("%d", &a[i]); f[i] = 0; } ans = 0; for(int i = 2; i <= n; i ++) { for(int j = 1; j <= n; j ++) { f[j] = 0; } if(a[1] == a[i]) { f[1] = f[i] = 1; dfs(1, i, 2); if(ans) break; } } if(ans) printf("Frederica Bernkastel\n"); else printf("Furude Rika\n"); } return 0; }

【牛客练习赛3|牛客练习赛3 B - 贝伦卡斯泰露】转载于:https://www.cnblogs.com/zufezzt/p/8412896.html