hdu多校-蒲公英云

hdu多校

1006

#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define read(a) scanf("%d",&a)
const int maxn=1e6+10;
typedef long long LL;
char str[maxn];
int nxt[maxn];
void pre_EKMP(char ptr[],int len,int nxt[]){
    nxt[0]=len;
    int j=0;
    while(j+1<len&&ptr[j]==ptr[j+1]) j++;
    nxt[1]=j;
    int k=1;
    fo(i,2,len-1){
        int p=nxt[k]+k-1;
        int L=nxt[i-k];
        if(i+L<p+1) nxt[i]=L;
        else{
            j=max(0,p-i+1);
            while(i+j<len&&ptr[i+j]==ptr[j]) j++;
            nxt[i]=j;
            k=i;
        }
    }
}
int main(){
    int t;
    read(t);
    while(t--){
        scanf("%s",str);
        int len=strlen(str);
        pre_EKMP(str,len,nxt);
        LL ans=0;
        fo(i,1,len-1){
            if(nxt[i]==(len-1-i+1)) ans+=nxt[i];
            else ans+=nxt[i]+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

1007

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define op freopen("in.txt","r",stdin)
 4 #define fo(i,a,b) for(int i=a;i<=b;i++)
 5 #define fod(i,a,b) for(int i=a;i>=b;i--)
 6 #define me0(a) memset(a,0,sizeof(a))
 7 #define read(a) scanf("%d",&a)
 8 const int maxn=1e6+10;
 9 typedef long long LL;
10 const LL mod=998244353;
11 
12 LL dp[maxn];
13 
14 int main(){
15     //op;
16     int t;
17     read(t);
18     while(t--){
19         int n,x,y;
20         read(n);read(x);read(y);
21         if(y!=n) y--;
22         if(x!=1) x++;
23         
24         int l=0,r=y;
25         l=min(l,x-4);
26         fo(i,l,r) dp[i]=0; 
27         dp[x]=1;
28         fo(i,x+1,y){
29             if(i-3>0) dp[i]+=dp[i-3];
30             dp[i]+=dp[i-1];
31             dp[i]%=mod;
32         }
33         
34         printf("%lld\n",dp[y]);
35     }
36     return 0;
37 }