Problem - E - Codeforces
目錄
推薦視頻：
題意：
細節(jié)（我踩得沒什么價值的坑）：
思路：
對樣例3 （X = 13）做解釋：
——————
總思路：
——————
動態(tài)規(guī)劃逼近：
——————
二進制拆分補充剩余：
核心代碼：?
推薦視頻：
E_嗶哩嗶哩_bilibili
其實有一些細節(jié)說的不是特別清楚好理解，可以結(jié)合我的題解來看。但是對題目的解析說的還是特別好的?
題意：
你需要制作一個數(shù)組，使其嚴格遞增子序列的數(shù)目為X
細節(jié)（我踩得沒什么價值的坑）：
1.嚴格遞增strictly increasing，我直到看了別人的題解才發(fā)現(xiàn)，，才能看懂樣例，，
2.好好讀題，我靠X是1e18了，得long long
3.快速逼近的時候while循環(huán)記得寫<=
4.空也算一個序列（這個坑我沒踩）
思路：
對樣例3 （X = 13）做解釋：
組合數(shù)解釋：
2 2 3 4 2
單獨一個數(shù)一組：
5?? 2,2,3,4,2
兩個數(shù)一組：
5 ? 23 23 24 24 34
三個數(shù)一組：
2 ? 234,234
總共12，然后加上題目說的空也算一組，一共13組啦——————
總思路：
此題我們用動態(tài)規(guī)劃快速逼近答案，然后二進制拆分補充剩余的
（本題解沒有去探討題目中的長度最長為200
不過單調(diào)遞增就是最快的了）
——————
動態(tài)規(guī)劃逼近：
然而他給這個數(shù)組不太適合弄規(guī)律（當然方法不止一種哦）?
我們動態(tài)規(guī)劃的思想來規(guī)則地做這道題：
我們用arr[ i ]記錄 i 及此前的所有嚴格遞增子序列總數(shù)目
比如 1 2 3 4
arr[ 1?] = 1? ? ?（1自己，只有1個）
arr[ 2 ] = 3? ? ? ?為 arr[ 1 ]*2 +1? ，
解釋：這里arr[ 1 ]*2理解為兩個arr[ 1 ]，
第一個arr[1]是不算2的此前所有的嚴格遞增子序列總數(shù)目；
第二個arr[1]代表此前的子序列尾都加個2的序列，這樣形成的序列的數(shù)目是等于arr[ i-1 ]的；
第三個1就是我們2單獨自己啦。
（所以狀態(tài)轉(zhuǎn)移方程就是 arr[ i ]?= arr[ i-1 ]*2 +1?）
此后同理，所以
arr[ 3 ] = 7? ? ? ? (arr[2]*2+1)?
arr[ 4 ] = 15? ? （7*2+1）
——————
二進制拆分補充剩余：
（剩余的數(shù)是個數(shù)，肯定能用二進制來表示）
先看例子直接理解：
1 2 3 4 2
順序后面補個2，我們可以發(fā)現(xiàn)2只會和前面的2之前的數(shù)形成嚴格遞增序列，此時能形成兩個：
2 和?1 2
其中：
1 2其實就是我們上面動態(tài)規(guī)劃部分提到的?“?第二個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
正好是二進制? （注意我們倒著補，后面不再組成遞增序列）文章來源：http://www.zghlxwxcb.cn/news/detail-836745.html
——————————文章來源地址http://www.zghlxwxcb.cn/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;
//補
//求個最大值快速冪吧，順便當復(fù)習了
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;
}到了這里，關(guān)于Educational Codeforces Round 161 (Rated for Div. 2) E. Increasing Subsequences 動態(tài)規(guī)劃逼近，二進制拆分補充，注意嚴格遞增的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
