Problem - E - Codeforces
目录
推荐视频：
题意：
细节（我踩得没什么价值的坑）：
思路：
对样例3 （X = 13）做解释：
——————
总思路：
——————
动态规划逼近：
——————
二进制拆分补充剩余：
核心代码：
推荐视频：
E_哔哩哔哩_bilibili
其实有一些细节说的不是特别清楚好理解，可以结合我的题解来看。但是对题目的解析说的还是特别好的
题意：
你需要制作一个数组，使其严格递增子序列的数目为X
细节（我踩得没什么价值的坑）：
1.严格递增strictly increasing，我直到看了别人的题解才发现，，才能看懂样例，，
2.好好读题，我靠X是1e18了，得long long
3.快速逼近的时候while循环记得写<=
4.空也算一个序列（这个坑我没踩）
思路：
对样例3 （X = 13）做解释：
组合数解释：
2 2 3 4 2
单独一个数一组：
5 2,2,3,4,2
两个数一组：
5 23 23 24 24 34
三个数一组：
2 234,234
总共12，然后加上题目说的空也算一组，一共13组啦——————
总思路：
此题我们用动态规划快速逼近答案，然后二进制拆分补充剩余的
（本题解没有去探讨题目中的长度最长为200
不过单调递增就是最快的了）
——————
动态规划逼近：
然而他给这个数组不太适合弄规律（当然方法不止一种哦）
我们动态规划的思想来规则地做这道题：
我们用arr[ i ]记录 i 及此前的所有严格递增子序列总数目
比如 1 2 3 4
arr[ 1 ] = 1 （1自己，只有1个）
arr[ 2 ] = 3 为 arr[ 1 ]*2 +1 ，
解释：这里arr[ 1 ]*2理解为两个arr[ 1 ]，
第一个arr[1]是不算2的此前所有的严格递增子序列总数目；
第二个arr[1]代表此前的子序列尾都加个2的序列，这样形成的序列的数目是等于arr[ i-1 ]的；
第三个1就是我们2单独自己啦。
（所以状态转移方程就是 arr[ i ] = arr[ i-1 ]*2 +1 ）
此后同理，所以
arr[ 3 ] = 7 (arr[2]*2+1)
arr[ 4 ] = 15 （7*2+1）
——————
二进制拆分补充剩余：
（剩余的数是个数，肯定能用二进制来表示）
先看例子直接理解：
1 2 3 4 2
顺序后面补个2，我们可以发现2只会和前面的2之前的数形成严格递增序列，此时能形成两个：
2 和 1 2
其中：
1 2其实就是我们上面动态规划部分提到的 “ 第二个1代表此前的子序列尾都加个2的序列 ”
2就是单独自己啦
所以补的这个值即是arr[ i ] + 1啦
————
（再举个例子，比如1 2 3 4 3，补的是3，补的序列是： 3和 1 3，1 2 3，2 3 共4种）
又因为：
1 （补1）
arr[ 1 ] + 1 = 2 （补2）
arr[ 2 ] + 1 = 4 （补3）
arr[ 3 ] + 1 = 8
arr[ 4 ] + 1 = 16
正好是二进制 （注意我们倒着补，后面不再组成递增序列）文章来源：https://www.toymoban.com/news/detail-836745.html
——————————文章来源地址https://www.toymoban.com/news/detail-836745.html
核心代码：
ll ksm(int a,int b)//a的b次幂
{
if (b == 1)return (ll)a;
ll tmp = ksm(a, b / 2);
if (b % 2) return tmp * tmp * a;
else return tmp * tmp;
}
void solve()
{
ll x;
cin >> x;
x--;
ll cursum = 1;
int curn = 1;
vector<int>ans;
ans.push_back(curn++);
while (cursum <= x)//快速逼近
{
cursum = cursum * 2 + 1;
if(cursum<=x)
ans.push_back(curn++);
}
if (cursum > x)//二进制拆分补充
{
curn--;
cursum = (cursum - 1) / 2;
cursum = x - cursum;
//补
//求个最大值快速幂吧，顺便当复习了
ll val = ksm(2, curn);
int curvaln = curn+1;
while (cursum > 0)
{
if (val <= 0)
{
cout << "impossible!!!";
exit(-1);
}
if (val <= cursum)
{
ans.push_back(curvaln);
cursum -= val;
}
val /= 2;
curvaln--;
}
}
cout << ans.size() << endl;
for (auto num : ans)
{
cout << num << " ";
}
cout << endl;
}到了这里，关于Educational Codeforces Round 161 (Rated for Div. 2) E. Increasing Subsequences 动态规划逼近，二进制拆分补充，注意严格递增的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
