Codeforces Round #621 C

发布于 2020-02-23  95 次阅读


一开始看这道题被吓到了,想了好久QAQ

题意是给你一个字符串t,求出其出现次数最多子串的出现个数。

同时给出限制,要求对于每个子串,其中的每个元素在t中的下标必须呈等差数列。

刚开始我想的是暴力求出所有子串,然后用Map进行统计,可是字符串长度是10^5级的(TLE预定)

之后经过分析得出,任何长度大于2的子串的长度都不可能是出现次数最多的

因为任何长度大于3的字符串都可以被分解成长度为2和1的子串

比如说 abb 其中含有的子串就是 a(1次) b(2次) ab(2次) bb(1次)

因此问题就转化为了一个字符串中长度为1,2的子串出现次数的最大值。

用dp可以在O(n)时间内解决

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x7FFFFFFF;
#define bug puts("here\n")
typedef long long ll;
ll dp[26][26];//dp数组代表开头是i结尾是j的字符串出现次数
ll letter[26];//单个字母出现次数
void work()
{
    ll ans = 0;
    string tmp;
    cin >> tmp;
    for (int i = 0; i < tmp.size(); i++)
    {
        for (int j = 0; j < 26; j++)
        {
            dp[j][tmp[i] - 'a'] += letter[j];
            ans = max(dp[j][tmp[i] - 'a'], ans);
        }
        letter[tmp[i] - 'a']++;
        ans = max(letter[tmp[i] - 'a'], ans);
    }
    cout << ans << endl;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    while (t--)
    {
        work();
    }
    return 0;
}


💭💭💭💭💭💭