1009

考虑贪心，暴力枚举一位。

$o(676n)$

#include
      
       using namespace std;const int N=1e5+333;int n,m,zl;int pos[26],cnt[N],t[26],az[N];char s[N],st[N];int l[N],r[N],nx[N],zzq[26];int main(){    ios::sync_with_stdio(0);    //freopen("p.in","r",stdin);    //freopen("p.out","w",stdout);    while(cin>>s){    n=strlen(s);    cin>>m;    for(int i=0;i<26;i++)cin>>l[i]>>r[i];    //if(m>10)continue;    int ans=0;    for(int i=0;i<=25;i++){ans+=l[i];pos[i]=n+3;t[i]=0;cnt[n+3]=0;}     for(int i=0;i<=n+20;i++)az[i]=cnt[i]=0;    for(int i=n;i>=1;i--){        int dot=s[i-1]-'a';        nx[i]=pos[dot];        pos[dot]=i;        t[dot]++;            cnt[i]=t[dot];    }    zl=0;    /*while(pos[0]<=n){        cout<
       
        <
        
         m-i&&k!=j)ax=1;            }            int q=0;            for(int pp=0;pp<=25;pp++)if(l[pp]>0)q+=l[pp];                        //cout<
         <
          
           m-i)ax=1;            if(ax){                for(int k=0;k<=25;k++)                pos[k]=zzq[k];                l[j]++;            continue;}            //AFAEFAEEFD            az[j]++;            st[i-1]='a'+j;            //cout<
           
            <
           
          
        
       
      

 

1001

考虑dp

https://www.cnblogs.com/DeaphetS/p/11229389.html

#include
      
       using namespace std;#define ll long longconst int mo=998244353;ll dp[102][102][102][2],n,m,ans;vector
       
        r[102],x[102]; int main(){    int t;    //freopen("p.in","r",stdin);    //freopen("p.out","w",stdout);    cin>>t;    while(t){        t--;        cin>>n>>m;        memset(dp,0,sizeof(dp));        for(int i=1;i<=n;i++){            r[i].clear();            x[i].clear();        }        for(int i=1;i<=m;i++){            int a,b,c;            cin>>a>>b>>c;            r[b].push_back(a);            x[b].push_back(c);        }        dp[0][0][0][0]=1;    for(int cur=1;cur<=n;cur++){        int o=cur%2;        for(int i=0;i<=cur;i++)            for(int j=i;j<=cur;j++)                for(int k=j;k<=cur;k++)                dp[i][j][k][o]=0;        for(int i=0;i<=cur;i++)            for(int j=i;j<=cur;j++)                for(int k=j;k<=cur;k++)        {        dp[i][j][cur-1][o]=(dp[i][j][cur-1][o]+dp[i][j][k][o^1])%mo;        dp[i][k][cur-1][o]=(dp[i][k][cur-1][o]+dp[i][j][k][o^1])%mo;        dp[j][k][cur-1][o]=(dp[j][k][cur-1][o]+dp[i][j][k][o^1])%mo;        dp[i][j][k][o]=(dp[i][j][k][o]+dp[i][j][k][o^1])%mo;}        for(int i=0;i<=cur;i++)            for(int j=i;j<=cur;j++)                for(int k=j;k<=cur;k++)                for(int az=0;az
        
         =ql)+(j>=ql)+(k>=ql)+(cur>=ql)!=qx)                    dp[i][j][k][o]=0;                }    }        ans=0;        for(int i=0;i<=n;i++)            for(int j=i;j<=n;j++)                for(int k=j;k<=n;k++)            ans=(ans+dp[i][j][k][n%2])%mo;            cout<
         
          <