社区讨论

请求加强数据

P4391[BalticOI 2009] Radio Transmission 无线传输参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m07iy9nv
此快照首次捕获于
2024/08/24 10:31
2 年前
此快照最后确认于
2025/11/04 22:35
4 个月前
查看原帖
rt
下述算法的复杂度是 O(L2)\Omicron(L^2) 的,但是借助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 条回复,欢迎继续交流。

正在加载回复...