链接: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;
}
标签:泰露,return,int,题解,s1,ans,lst,贝伦,s2
From: https://www.cnblogs.com/CasseShimada/p/16731816.html