P6416 题解

yxy666 · 2023-10-26 21:20:28 · 题解

凌驾于算法之上的思路：

对于第 x 行，在它之前的第 1 行有 1 个元素，第 2 行 有 2 个元素，第 x-1 行有 x-1 个元素。那么显然易见，第 x 行开头元素的下标即为 x\times (x-1)/2+1 \mod m ，但是这里仍然要注意最后取模等于零的情况。

细节：

直接求 x\times (x-1)/2+1 中途会爆 long long，所以我们要提前取模，但是后面还有一个除法运算，与模运算不相匹配，所以还需要判断数字的奇偶性情况提前除掉。

那么我们就可以刷暴力了。但是很明显，会超时。令 m 等于串长，手玩数据，于是我们发现对于较大的数据，除了开头一段和末尾一段，中间是有连续的一段 1-m，那就好处理了。

PS ：这题卡空间，所以需要分成一个一个字母处理。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
long long n,m,Ans[50005];
int q,Q,sum[maxn];
char a[maxn];
struct yxy{
    int id;long long x;char C;
    bool operator<(const yxy b)const{return C<b.C;}
}t[50005];
long long read(){
    long long ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch))ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void calc(int k){
    char ch=t[k].C;
    long long L,R,S;

    if(t[k].x&1)L=(long long)((t[k].x%m))*((t[k].x-1)/2%m);
    else L=(long long)((t[k].x/2%m))*((t[k].x-1)%m);
    L++;
    L%=m;if(L==0)L=m;
    if(L+t[k].x-1<=m){
        Ans[t[k].id]=sum[L+t[k].x-1]-sum[L-1];
//      if(L+t[k].x-1>m)Ans[t[k].id]+=sum[t[k].x-m+L-1];
    }//t[k].x -(m-L+1)==t[k].x-m+L-1
    else {
        Ans[t[k].id]=sum[m]-sum[L-1];
        t[k].x-=(m-L+1);L=1;
        long long size=t[k].x/m;
        Ans[t[k].id]+=(long long)size*sum[m];
        R=t[k].x%m;
        if(R!=0)Ans[t[k].id]+=sum[R];
    }
}
int main(){
    n=read();
    scanf("%s",a+1); m=strlen(a+1);
//  for(int i=1;i<=m;i++){
//      for(int j=0;j<26;j++)sum[i][j]=sum[i-1][j];
//      sum[i][a[i]-'A']++;
//  }
    q=read();
    while(q--){
        long long x=read();
        char C=getchar();
        while(C<'A'||C>'Z')C=getchar();
        t[++Q]=(yxy){Q,x,C};
    }
    sort(t+1,t+1+Q);
    for(int i=1;i<=Q;){
        int j=i;
        for(int K=1;K<=m;K++)sum[K]=sum[K-1]+(a[K]==t[i].C);
        while(t[i].C==t[j].C)calc(j),j++;
        i=j;
    }
    for(int i=1;i<=Q;i++)printf("%lld\n",Ans[i]);
    return 0;
}