hdu多校

比眉伴天荒 2023-08-17 16:26 127阅读 0赞

1006

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/Aiahtwo/p/11302761.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/83c732c5fdb14791b9a2313a6f9d1664.png