C. Prefixes and Suffixes ( Codeforces Round #527 (Div. 3) )
and div round Codeforces 527
2023-06-13 09:17:22 时间
题解:
- 找到 n - 1 长的子串一个是(假设第一个是)最长前缀,另一个是最长后缀。
- 判断假设是否正确,遍历所有子串,如果符合前缀 tot 加 1,如果 tot 不够 n - 1 或者我们假设的那个前缀从第二个开始不等于那个后缀的前 n - 2 个,也就是我们假设的前后缀倒了,比如 cdeae 和 fcdea,我们原来的假设中前缀 pre = " cdeae " 和后缀 sur = " fcdea ",这样子显然不可以,所以以上两种情况都需要交换前后缀。
- 判断就可以了,比赛时有提示,同样长度的一个是前缀一个是后缀,如果已经又一个是前缀了,那么另一个就是后缀了。
- 这里科普一个小知识:string 类不能用 scanf 读入,因为 c 不支持。
代码(参考):
#include <bits/stdc++.h>
using namespace std;
string s[500];
bool vis[500];
int main()
{
int n;
bool flag = true;
string pre, sur;
string ans;
scanf("%d", &n);
for(int i = 1; i <= 2 * n - 2; i ++)
{
cin >> s[i];
if(flag && (s[i].size() == (n - 1)))
{
pre = s[i];
flag = false;
}
else if(s[i].size() == (n - 1)){
sur = s[i];
}
}
int tot = 0;
for(int i = 1; i <= 2 * n - 2; i ++)
{
if(s[i][0] == pre[0]) tot ++;
}
if(tot < n - 1 || pre.substr(1) != sur.substr(0, n - 2))
{
swap(pre,sur);
}
memset(vis,false,sizeof(vis));
for(int i = 1; i <= 2 * n - 2; i ++)
{
if(pre.substr(0,s[i].size())== s[i] && !vis[s[i].size()])
{
vis[s[i].size()] = true;
ans += "P";
}
else ans += "S";
}
cout << ans << endl;
return 0;
}
相关文章
- Linux pip错误分析 (Running pip as the ‘root‘ user can result in broken permissions and conflict)
- Neuro Causal and Symbolic AI. 36th NIPS
- ORA-30358: summary and materialized view are not in same schema ORACLE 报错 故障修复 远程处理
- ORA-19164: XQST0085 – It is a static error if the namespace URI in a namespace declaration attribute is a zero-length string, and the implementation does not support [XML Names 1.1]. ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-013863; Symbol: ER_IB_MSG_LOG_FILES_CREATED_BY_CLONE_AND_READ_ONLY_MODE; SQLSTATE: HY000 报错 故障修复 远程处理
- mybatis配置文件xxxx.xml中缺失返回类型的后果A query was run and no Result Maps were found详解编程语言
- 多条件查询MySQL中使用And多条件查询的步骤(mysql中and)
- and 扩展Oracle命令的功能:Expanding Oracle Commandability(oracle命令exp)
- Utilizing Redis Intersections for Advanced Data Analysis and Optimization(redis交集)
- Power Up Your Projects with Linux PP: Exploring the Best Tools and Techniques(linuxpp)
- Exploring the Benefits and Uses of PPPD in the Linux Environment(pppdlinux)
- Oracle数据库中的AND查询(oracle and查询)
- 深入探究Mysql中IN与AND逻辑运算的应用(mysql中in与and)
- Mysql中强大的AND运算符的使用方法探究(mysql中and的使用)
- MySQL中的AND逻辑操作符是什么(mysql中and是什么)
- Oracle中使用AND运算符的示例分析(oracle中and用法)