E. Left Shifting 3

statements

方法一

两个nanjing 子串不可能相交，因此只要左移之后，字符串的开头不会“截断”一个nanjing子串，就能得到最大的答案。nanjing 子串的长度是 7，所以左移 7 次之内肯定有个位置不会截断nanjing 子串。因此模拟min(k,7) 次左移并计算答案即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int fnd(string s){
    int n=s.length();
    int res=0;
    for(int i=0;i+7-1<n;i++){
        if(s.substr(i,7)=="nanjing") res++;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int ans=0;
        if(k<=6){
            string tmp=s;
            for(int i=0;i<=min(n,k);i++){
                tmp=s.substr(i,n)+s.substr(0,i);
                ans=max(ans,fnd(tmp));
            }
        }
        else{
            string tmp=s;
            for(int i=0;i<min((long long)7,n);i++){
                tmp=s.substr(i,n)+s.substr(0,i);
                ans=max(ans,fnd(tmp));
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int f[N];
void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<=2*n+10;i++) f[i]=0;
    string s;
    cin>>s;
    s+=s;
    k=min(k,n);
    for(int i=6;i<2*n;i++){
        if(s.substr(i-6,7)=="nanjing") f[i]++;
        f[i]+=f[i-1];
    }
    int ans=0;
    for(int i=0;i<=k;i++)
        ans=max(ans,f[max(0,i+n-1)]-f[i]);
    cout<<ans<<'\n';
}
signed main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

J. Social Media

statements

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int cnt[N],t[N];
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=max(2,k);i++) cnt[i]=t[i]=0;
    unordered_set<int> st;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        st.insert(x);
    }
    map<pair<int,int>,int> s;
    int ans=0;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        if(a>b) swap(a,b);
        s[{a,b}]++;
        if(st.count(a)&&st.count(b)) ans++;
        else if(st.count(a)) cnt[b]++;
        else if(st.count(b)) cnt[a]++;
        else if(a==b) cnt[a]++; 
    }
    for(int i=1;i<=k;i++) t[i]=cnt[i];
    int res=0;
    sort(t+1,t+k+1,greater<int>());
    res=t[1]+t[2];
    for(auto t:s){
        int a=t.first.first;
        int b=t.first.second;
        if(a==b) continue ;
        int tmp=0;
        if(st.count(a)==0&&st.count(b)==0){
            tmp=cnt[a]+cnt[b];
            res=max(res,tmp+t.second);
        }
    }
    cout<<ans+res<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

B. Birthday Gift

statements