2019 hdu多校1

悠悠 2023-10-11 09:14 13阅读 0赞

A:一类线性dp，时间卡的有点紧

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

/*
    定义 dp[t][i][j][k]代表填完前 t 个位置后，{0, 1, 2, 3} 这 4 个数字最后一次出现的位置，
    排序后为 t, i, j, k(t > i > j > k) 的方案数目，则按照第 t 位的数字的四种选择，可以得
    到四种转移。
    t选t-1这个位置的数：dp[t][i][j][k]
    t选i这个位置的数：dp[t][t-1][j][k]
    t选j这个位置的数：dp[t][t-1][i][k]
    t选k这个位置的数：dp[t][t-1][i][j]
    枚举r[l]==t+1的所有条件，当且仅当满足所有条件时才进行转移 
    
    最后的方案数=sum{dp[n]} 
    总时间复杂度 O(n4)。滚动一维，空间复杂度 O(n3)
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 110
    #define ll long long 
    #define mod 998244353
    ll dp[2][maxn][maxn][maxn];
    int n,m;
    struct Node{
        int l,x;
        Node(){}
        Node(int l,int x):l(l),x(x){}
    };
    vector<Node>v[maxn];
    
    inline void update(ll &a,ll b){
        a=(a+b);
        while(a>=mod)a-=mod; 
    }
    int c;
    void solve(){
        c=0;
        dp[c][0][0][0]=1;
        for(int t=1;t<=n;t++){
            c^=1;
            for(int i=0;i<=t;i++)
                for(int j=0;j<=i;j++)
                    for(int k=0;k<=j;k++)
                        dp[c][i][j][k]=0;
            
            for(int i=0;i<t;i++)
                for(int j=0;j<=i;j++)
                    for(int k=0;k<=j;k++){
                        update(dp[c][i][j][k],dp[c^1][i][j][k]);
                        update(dp[c][t-1][j][k],dp[c^1][i][j][k]); 
                        update(dp[c][t-1][i][k],dp[c^1][i][j][k]);
                        update(dp[c][t-1][i][j],dp[c^1][i][j][k]);
                    }
            for(int p=0;p<v[t].size();p++){
         //枚举每个条件 
                int l=v[t][p].l,x=v[t][p].x;
                for(int i=0;i<t;i++)
                    for(int j=0;j<=i;j++)
                        for(int k=0;k<=j;k++){
                            int cnt=1;
                            if(i>=l)cnt++;
                            if(j>=l)cnt++;
                            if(k>=l)cnt++;
                            if(cnt!=x)dp[c][i][j][k]=0;
                        }
            }
        }
    }
    
    int main(){
        //ios::sync_with_stdio(false);
        int t;cin>>t;
        while(t--){
            for(int i=0;i<maxn;i++)v[i].clear();
            
            scanf("%d%d",&n,&m);
            for(int i=1;i<=m;i++){
                int l,r,x;
                scanf("%d%d%d",&l,&r,&x);
                v[r].push_back(Node(l,x));
            }
            solve();
            ll ans=0;
            for(int i=0;i<n;i++)
                for(int j=0;j<=i;j++)
                    for(int k=0;k<=j;k++)
                        ans+=dp[c][i][j][k],ans%=mod;
            cout<<ans<<'\n';
        }
    }

B:线性基前缀和，cf原题

C:待补

D:模拟，二分也可以做

E:队友过得，最短路最小割

F,G,H待补

I:字符串dp，调了半天才做出来

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

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 300005
    int cnt[maxn][26],nxt[maxn][26],pos[26];
    int n,k,l[26],r[26],used[26],up,down;
    char ans[maxn],s[maxn];
    int judge(int i,int pos){
        int res1=0,res2;
        for(int j=0;j<26;j++){
            if(used[j]+cnt[pos][j] < l[j])return 0;
            res1+=max(0,l[j]-used[j]);//后面最少要的字符个数 
            res2+=min(cnt[pos][j],r[j]-used[j]);//后面最多能的字符个数 
        }
        if(res1>k-i || res2<k-i)return 0;
        return 1;
    }
    void init(){
        memset(used,0,sizeof used);
        up=down=0;
        memset(cnt,0,sizeof cnt);
        memset(ans,0,sizeof ans);
    }
    
    int main(){
        while(scanf("%s%d",s+1,&k)==2){
            init();
            n=strlen(s+1);
            for(int i=0;i<26;i++)scanf("%d%d",&l[i],&r[i]),up+=r[i],down+=l[i];
            
            for(int i=n;i>=1;i--){
                for(int j=0;j<26;j++)
                    if(s[i]-'a'==j)cnt[i][j]=cnt[i+1][j]+1;
                    else cnt[i][j]=cnt[i+1][j];
            }
            int flag=0;
            if(down>k || up<k){puts("-1");continue;}
            for(int i=0;i<26;i++)if(cnt[1][i]<l[i]){puts("-1");flag=1;break;}
            if(flag)continue;
            
            for(int i=0;i<26;i++)pos[i]=n+1;
            for(int i=n;i>=1;i--){
                for(int j=0;j<26;j++)
                    nxt[i][j]=pos[j];
                pos[s[i]-'a']=i;
            }
            for(int j=0;j<26;j++)nxt[0][j]=pos[j];
            
            int now=0; 
            for(int i=1;i<=k;i++){
                for(int j=0;j<26;j++){
         //第i位选择j 
                    if(used[j]>=r[j])continue;
                    
                    int tmp=nxt[now][j];
                    used[j]++;
                    if(judge(i,tmp+1)){
                        ans[i]=j;
                        now=tmp;
                        break;
                    }
                    else 
                        used[j]--;
                }
            }
            
            for(int i=1;i<=k;i++)cout<<(char)(ans[i]+'a');
            puts("");
        }
    }

JKLM：待补

转载于:https://www.cnblogs.com/zsben991126/p/11348002.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif