CSU-ACM Home Page

2019暑假集训选拔赛第一场题解

Update Time: 2019-05-29 22:08:06     Recent Editor: Scanf     Create Time: 2019-05-29 22:06:08     Creator: Scanf    


终局

贪心,每时每刻都尽可能攻击玄霄,然后把这回合受的伤害丢进一个大根堆。当云天河这回合攻击玄霄就要死的时候,我们反悔一次,从大根堆里拿出最大的某次收到的伤害,表示那回合不攻击玄霄,而是使用治疗或者格挡,如果治疗血量大于那次伤害就用治疗,否则用格挡,相当于总攻击减一次,血量从当前的要死状态增加,依此策略贪心。

板烧鸡腿堡

从后往前扫,严格递减,如果递减到<=0,就结束了。

最长不下降子序列

dp[0][i]表示还没有隔开L的LIS和dp[1][i]表示已经隔开过一段L的的LIS 然后算dp[1]由dp[1]更新,还可以由dp[0]的i-L之前的跟新 权值树状数组维护

水题

选择一对数,那么肯定是选择最小的数字乘以x,选择某个数字除以x 那么枚举这个某个数字再枚举这个数字的因数x

千言万语

题目大意

​ 定义27中字符的信息量,定义信息量为V的集合的每个元素是一个含有W个单词的句子,每个单词之间由一个空格分割,将这些句子按字序排序,求第K大的句子是多少,如果不存在则输出not exist! ​ 1 ≤ V ≤ 75,1 ≤ W ≤ 20,1 ≤ K ≤ 10^18。

问题分析

​ 比较显然的是,这是一个计数题,dp状态不唯一 我们定义f[i][j]表示含有i个单词,信息量为j的句子有多少句。 那么有以下递推式成立: 新添加一个单词的一部分 f[i+1][j+k]+=f[i][j],k=3..28,且(j+k<=75) 在原单词末尾加上一个字符 f[i][j+k]+=f[i][j],k=2..27且(j+k<=75) 因为添加的第一个单词前不需要空格,因此初始状态为f[1][0]=1 对于字典序而言我们发现如果已经处理了前1~i-1个字符,且组成的单词个数不到W个,那么放空格比放字符的字典序要小,因此我们在放字符和放空格之间优先选择第一个递推式,在选择第二个递推式,将字符从小到大枚举即可

具体实现

        for(i=2;i<=27;++i)
            {
                if(m>1)
                {
                    if(K<=f[m-1][n-i-1])
                    {
                        ans[++ansl]='a'+i-2;
                        ans[++ansl]=' ';
                        --m;
                        n-=i+1;
                        break;
                    }
                    K-=f[m-1][n-i-1];
                }
                if(K<=f[m][n-i])
                {
                    ans[++ansl]='a'+i-2;
                    n-=i;
                    break;
                }
                K-=f[m][n-i];
            }

题目评价

考查内容:dp计数,字典序

时间复杂度:O(TNV*28)