洛谷十一月月赛解题报告

素颜马尾好姑娘i 2024-04-17 05:21 31阅读 0赞

比赛地址：[https://www.luogu.org/contestnew/show/12006][https_www.luogu.org_contestnew_show_12006]  
唉，T3考试的时候zz了，把式子写错了。。。。结果只有30分啊，然后T4连10分都没骗到。虽然身为蒟蒻但实在有点自闭了，只好来发篇解题报告。。。qwq

# T1 P4994 终于结束的起点 #

就是简单的模拟，不说了

# T2 P4995 跳跳 #

就是贪心。。。跳一次高的一次低的。。用个priority\_queue就可以了。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #define MAXN 30
    #define mod 998244353
    #define ll long long
    using namespace std;
    int n,m;
    int sum[MAXN],f[MAXN],cnt[MAXN],c[MAXN][MAXN],val[MAXN];
    ll ans;
    inline int read()
    {
        int cur_cnt=0;
        char ch=getchar();
        while(ch!=' ')
        {
            if(ch=='1') cur_cnt++;
            ch=getchar();
        }
        return cur_cnt;
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int cur_cnt=read();
            int cur_sum;
            scanf("%d",&cur_sum);
            val[cur_cnt]+=cur_sum;
        }
    
        for(int i=0;i<=20;i++) c[i][0]=1;
        for(int i=1;i<=20;i++)
            for(int j=1;j<=20;j++)
                c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        f[0]=1;
        for(int i=1;i<=n;i++)
            for(int j=0;j<i;j++)
                f[i]=(f[i]+(ll)c[i][j]*f[j]%mod)%mod;
        for(int i=0;i<=n;i++)
        {
            ans+=(ll)f[i]*f[n-i]%mod*val[i]%mod;
            ans%=mod;
        }
        printf("%lld\n",ans);
        return 0;
    }

# T3 P4996 咕咕咕 #

也就是组合数+DP

我们考虑因为只有那\\(m\\)种情况可以产生贡献，但是实际上01串中1的位置并没有影响，所以说一共的情况只有1的个数为0~n的这\\(n+1\\)种情况。

我们预处理出这\\(n+1\\)种情况的每种的歉意值总和。

因为最后的ans为所有步骤中选择的情况的总和，然后我们知道这\\(n+1\\)种情况中，每一种情况在整体过程中可能会出现多次。

所以处理一下组合数，最后我们的ans就是\\(\\sum\\)（从全0的情况到现在情况的种类数）\\(\\times\\)（从现在的情况到全1的情况的种类数）\\(\\times\\)（现在这种情况的歉意值总和）%mod；

# T4 P4997 不围棋 #

还不会。。晚上补

转载于:https://www.cnblogs.com/fengxunling/p/9903460.html

[https_www.luogu.org_contestnew_show_12006]: https://www.luogu.org/contestnew/show/12006