题意看似很难，要求出现次数最多的子序列，且这些子序列原下标成等差数列
不用考虑公差为负的，显然公差为负的和公差为正的对称
但细想长度大于2的子序列不如长度为2的子序列 因为长度为2的子序列不管下标是什么都能构成等差数列 长度大于2的子序列下标有了要构成等差数列的限制 且可以从长度大于2的子序列中任选2个构成长度为2的子序列 故长度为2的子序列不会比长度大于2的子序列差 只需取长度大于2的子序列的前两项就能使出现次数与其一样多 更何况像abab aaa等可以取出多个长度为2的相同子序列
综上贪心得证
只需统计出出现次数最多的长度为1或2的子序列
官方:
注意：1.1≤|s|≤105，长度为2的子序列数目最多可达到1e10 所以要开ll
2.刚开始写了个map统计，但显然可以将字母转化为数字，毕竟只有26个字母，可以像hash一样 转而用数组记录
map每次查询要logn 而数组可以o(1)访问 虽然时间快了但空间也大了 也就是用空间换时间
数组dp 31ms 300kb map 265ms100kb
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a1[26],a2[26][26]; int main(){ string s; ios::sync_with_stdio(false);cin.tie(0); cin>>s; int n=s.length(); for(int i=0;i<n;i++){ int k=s[i]-97; for(int j=0;j<26;j++) a2[j][k]+=a1[j]; a1[k]++; } ll ans=0; for(int i=0;i<26;i++)ans=max(ans,a1[i]); for(int i=0;i<26;i++) for(int j=0;j<26;j++)ans=max(ans,a2[i][j]); cout<<ans<<endl; }
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+5; char s[N]; map<char,int>mp; map<string,ll>coun;//int int main(){ int n; ios::sync_with_stdio(false);cin.tie(0); cin>>s; n=strlen(s); for(int i=0;i<n;i++){ mp[s[i]]++; string sub; sub.resize(2); sub[1]=s[i]; for(char j=‘a‘;j<=‘z‘;j++){ if(j==s[i])continue; sub[0]=j; coun[sub]+=mp[j];//mp[j]*mp[s[i]] } } int mx1=0; for(char i=‘a‘;i<=‘z‘;i++) if(mp[i]>mx1)mx1=mp[i]; ll ans=mx1; //if(mx2!=0)ans=1ll*mx2*mx1;//两个不同字符先后顺序不一样子串也不一样 ans=max(ans,1ll*mx1*(mx1-1)/2); for(char i=‘a‘;i<=‘z‘;i++) for(char j=‘a‘;j<=‘z‘;j++){ if(i==j)continue; string sub; sub.resize(2); sub[0]=i;sub[1]=j; ans=max(ans,coun[sub]); } cout<<ans<<endl; return 0; }
Codeforces Round #621 (Div. 1 + Div. 2)C - Cow and Message
原文：https://www.cnblogs.com/wyh447154317/p/12345601.html