题解

A.直接二分长度ck一下区间是否有这些字母即可.

#include <bits/stdc++.h>
using namespace std;
const int N=2e5,M=20;
char s[N];
int pos[M][N];
int C(char c)
{
    if(c=='p')    return 1;
    if(c=='u')    return 2;
    if(c=='l')    return 3;
    if(c=='e')    return 4;
    if(c=='y')    return 5;
    if(c=='a')    return 6;
    if(c=='k')    return 7;
    if(c=='n')    return 8;
    if(c=='o')    return 9;
    if(c=='i')    return 10;
    return 0;
}
bool ck(int p,int len)
{
    int flag=1;
    for(int i=1;i<=10;i++)
    {
        if(pos[i][p+len-1]-pos[i][p-1]==0)    flag=0;
    }
    if(flag)    return true;
    else        return false;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%s",s+1);int len=strlen(s+1);
        for(int i=1;i<=len;i++)
        {
            int x=C(s[i]);
            for(int j=1;j<=10;j++)
            {
                pos[j][i]=pos[j][i-1]+(x==j);
            }
        }
        int ans=2e9;
        for(int i=1;i<=len;i++)
        {
            int l=10,r=len-i+1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(ck(i,mid))
                {
                    r=mid-1;
                    ans=min(ans,mid);
                }
                else l=mid+1;
            }
        }
        for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=10;j++)
            {
                 pos[j][i]=0;
            }
        }
        ans==2e9?puts("-1"):printf("%d\n",ans);
    }
    return 0;
}

B.套用第一个题,不过这次要二分十次,每次贪心找到最小的即可.边界设置inf.

#include <bits/stdc++.h>
using namespace std;
const int N=2e5,M=20;
char s[N];
vector<int>v[M];
int C(char c)
{
    if(c=='p')    return 1;
    if(c=='u')    return 2;
    if(c=='l')    return 3;
    if(c=='e')    return 4;
    if(c=='y')    return 5;
    if(c=='a')    return 6;
    if(c=='k')    return 7;
    if(c=='n')    return 8;
    if(c=='o')    return 9;
    if(c=='i')    return 10;
    return 0;
}
bool ck(int p,int len)
{
    int pos1=p,pos2=p+len-1;
    for(int i=2;i<=10;i++)
    {
        pos1=*lower_bound(v[i].begin(),v[i].end(),pos1);

    }
    if(pos1<=pos2)    return true;
    else              return false;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%s",s+1);int len=strlen(s+1);
        for(int i=1;i<=10;i++)    v[i].clear();
        for(int i=1;i<=len;i++)
        {
            int x=C(s[i]);
            v[x].push_back(i);
        }
        for(int i=1;i<=10;i++)    v[i].push_back(2e9);
        int ans=2e9;
        for(int i=1;i<=len;i++)
        {
            if(s[i]=='p')
            {
                int l=10,r=len-i+1;
                while(l<=r)
                {
                    int mid=(l+r)>>1;
                    if(ck(i,mid))
                    {
                        r=mid-1;
                        ans=min(ans,mid);
                    }
                    else l=mid+1;
                }
            }
        }
        ans==2e9?puts("-1"):printf("%d\n",ans);
    }
    return 0;
}

C.循环节内可过,先预处理出来莫比乌斯函数,然后找循环节,最后输出答案即可.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =2e7+10;
int prime[maxn],mu[maxn],pcnt;
bool vis[maxn];
void init() 
{
    mu[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i])
      {
            prime[++pcnt]=i;
            mu[i]=-1;
       }
        for(int j=1;i*prime[j]<maxn;j++)
      {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
          {
                mu[i*prime[j]]=0;
                break;
            }
          else mu[i*prime[j]]=-mu[i];
        }
    }
}
int main()
{
    int T;
    cin >>T;
    init();
    while(T--) 
    {
        ll n,k;
        scanf("%lld%lld",&n,&k);
        vector<int>v;
        map<int,int> vis;
        int now=n;
        while(!vis[now]) 
        {
            v.push_back(now);
            vis[now]=1;
            now=now+mu[now];
        }
        int j;
        for (int i=0;i<v.size();i++)
            if(v[i]==now) {j=i;break;}
        vector<int>v1;
        for (int i=j;i<v.size();i++)
        v1.push_back(v[i]);
        if(k<v.size()) cout<<v[k]<<endl;
        else cout<<v1[(k-v.size())%v1.size()]<<'\n';
    }
    return 0;
}

D.拿set模拟删边,加边操作,然后最后输出ans即可.

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int u[maxn],v[maxn],a[maxn],op[maxn];
set<int>g[maxn];
int main()
{
    int n,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        cin>>op[i];
        if(op[i]==3) continue;
        cin>>u[i]>>v[i];
        a[++cnt]=u[i];
        a[++cnt]=v[i];
    } 
    sort(a+1,a+1+cnt);
    cnt=unique(a+1,a+1+cnt)-a-1;
    for(int i=1;i<=n;i++) 
    {
        if(op[i]==3) continue;
        u[i]=lower_bound(a+1,a+1+cnt,u[i])-a;
        v[i]=lower_bound(a+1,a+1+cnt,v[i])-a;
    }
    int ans=0;
    for(int i=1;i<=n;i++) 
    {
        if(op[i]==1) 
        {
            if(g[u[i]].count(v[i])) continue;
            if(g[u[i]].size()&&g[v[i]].size()) ans--;
            else if(!g[u[i]].size()&&!g[v[i]].size()) ans++;
            g[u[i]].insert(v[i]);
            g[v[i]].insert(u[i]);
        }
        else if(op[i]==2) 
        {
            if(!g[u[i]].count(v[i])) continue;
            g[u[i]].erase(g[u[i]].find(v[i]));
            g[v[i]].erase(g[v[i]].find(u[i]));
            if(g[u[i]].size()&&g[v[i]].size()) ans++;
            else if(!g[u[i]].size()&&!g[v[i]].size()) ans--;
        }
        else cout<<ans<<endl;
    }
    return 0;
}