ACM-11月12日周日周末训练心得

116 阅读 0 评论 77 点赞

我是靠谱客的博主壮观小鸭子，这篇文章主要介绍ACM-11月12日周日周末训练心得，现在分享给大家，希望可以做个参考。

这周是数位DP专题结束前的最后一周，老师把周六的比赛取消了，目的是让我们有时间抓紧写各自的专题，老师每次在群里发的东西都是对我们的警醒，我们与其他学校的差距，甚至曾经同一水平线上的学校如今的成绩都比我们好，每次做题的时候都在反思自己，到底学了什么，只有不停地往前走，深深的踩下每一步脚印。

还是照常反思一下这周的训练，做题目我一开始一直都是跟着别人的脚步走，看哪些题目做的人多成功率高，才去做，专题里有一道S一直没人去触碰，以为很难，直到有大佬在群里问我们为什么不做S题，其实很简单的，我才仔细重新看了看题，原来不是那么难这道题大致的意思是有k位数，输入一个n，求是这k位数加起来等于n并且a[i]&a[i+1]=a[i+1]，这里就让我重新复习了一遍&的用法，就样例3 2来说，一共有六种情况，0 1 1、1 1 0、1 0 1、2 0 0、0 2 0、0 0 2，符合条件的就只有1 1 0和2 0 0，用一个dp[i][j]来表示，表示到第i位的和为j

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i=0;i<17;i++)
        {
            for(int j=0;j<=n;j++)
            {
                if(dp[i][j]==0)
                    continue;
                for(int geshu=0;geshu<=k;geshu++)
                {
                    ll sum=j+(geshu<<i); 
                    if(sum>n)
                        break;
                    dp[i+1][sum]=(dp[i+1][sum]+dp[i][j])%1000000009; 
                }
            }
        }