社区讨论
请求加强数据
P4391[BalticOI 2009] Radio Transmission 无线传输参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m07iy9nv
- 此快照首次捕获于
- 2024/08/24 10:31 2 年前
- 此快照最后确认于
- 2025/11/04 22:35 4 个月前
rt
下述算法的复杂度是 的,但是借助O2可以卡过去
hack的大概思路是让拉长字符串长度和结果串长度,同时在前几位出现尽可能多样的字符.
附代码:
CPP#include <iostream>
#include <string>
using namespace std;
int pi[1000005], len, cnt;
bool use[30];
string s, sub;
int main()
{
ios::sync_with_stdio(false);
cin >> len >> s;
for (int i = 0; i < len; i++)
if (!use[s[i] - 'a'])
{
use[s[i] - 'a'] = true;
cnt++;
}
// 保证sub串中出现所有s中出现的字符
for (int i = 0; i < len && cnt; i++)
{
sub += s[i];
if (use[s[i] - 'a'])
{
use[s[i] - 'a'] = false;
cnt--;
}
}
cnt = sub.length();
sub.erase(cnt - 1);
// 穷举匹配
for (int sub_len = cnt; sub_len <= len; sub_len++)
{
sub += s[sub_len - 1];
bool find = true;
// 能够整串匹配的部分
for (int k = 2; find && k <= len / sub_len; k++)
for (int j = 0; j < sub_len; j++)
if (s[(k - 1) * sub_len + j] != sub[j])
{
find = false;
break;
}
// 剩余部分
for (int i = len / sub_len * sub_len; i < len; i++)
if (s[i] != sub[i - len / sub_len * sub_len])
{
find = false;
break;
}
if (find)
{
cout << sub_len << endl;
break;
}
}
return 0;
}
···
回复
共 0 条回复,欢迎继续交流。
正在加载回复...