Educational Codeforces Round 161 (Rated for Div. 2) E. Increasing Subsequences 动态规划逼近，二进制拆分补充，注意严格递增

id="article_content" class="article_content clearfix"> id="content_views" class="htmledit_views">

Problem - E - Codeforces

目录

推荐视频：

题意：

细节（我踩得没什么价值的坑）：

思路：

对样例3 （X = 13）做解释：

——————

总思路：

——————

动态规划逼近：

——————

二进制拆分补充剩余：

核心代码： 

推荐视频：

E_哔哩哔哩_bilibili

其实有一些细节说的不是特别清楚好理解，可以结合我的题解来看。但是对题目的解析说的还是特别好的 

题意：

你需要制作一个数组，使其严格递增子序列的数目为X

细节（我踩得没什么价值的坑）：

1.严格递增strictly increasing，我直到看了别人的题解才发现，，才能看懂样例，，

2.好好读题，我靠X是1e18了，得long long

3.快速逼近的时候while循环记得写<=

4.空也算一个序列（这个坑我没踩）

思路：

对样例3 （X = 13）做解释：

组合数解释：

  1.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1">
class="hljs-ln-code"> class="hljs-ln-line">2 2 3 4 2
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2">
    • class="hljs-ln-code"> class="hljs-ln-line">单独一个数一组：
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line">5   2,2,3,4,2
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line">两个数一组：
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line">5   23 23 24 24 34
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line">三个数一组：
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line">2   234,234
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line">总共12，然后加上题目说的空也算一组，一共13组啦
    •  class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

    ——————

    总思路：

    此题我们用动态规划快速逼近答案，然后二进制拆分补充剩余的

    （本题解没有去探讨题目中的长度最长为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

    正好是二进制  （注意我们倒着补，后面不再组成递增序列）

    ——————————

    核心代码： 

    1.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1"> class="hljs-ln-code"> class="hljs-ln-line">ll ksm(int a,int b)//a的b次幂
    2.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2"> class="hljs-ln-code"> class="hljs-ln-line">{
    3.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line">	if (b == 1)return (ll)a;
    4.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line">	ll tmp = ksm(a, b / 2);
    5.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line">	if (b % 2) return tmp * tmp * a;
    6.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line">	else return tmp * tmp;
    7.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line">}
    8.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line"> 
    9.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line">void solve()
    10.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line">{
    11.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="11"> class="hljs-ln-code"> class="hljs-ln-line">	ll x;
    12.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="12"> class="hljs-ln-code"> class="hljs-ln-line">	cin >> x;
    13.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="13"> class="hljs-ln-code"> class="hljs-ln-line">	x--;
    14.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="14"> class="hljs-ln-code"> class="hljs-ln-line">	ll cursum = 1;
    15.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="15"> class="hljs-ln-code"> class="hljs-ln-line">	int curn = 1;
    16.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="16"> class="hljs-ln-code"> class="hljs-ln-line">	vector<int>ans;
    17.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="17"> class="hljs-ln-code"> class="hljs-ln-line">	ans.push_back(curn++);
    18.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="18"> class="hljs-ln-code"> class="hljs-ln-line">	while (cursum <= x)//快速逼近
    19.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="19"> class="hljs-ln-code"> class="hljs-ln-line">	{
    20.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="20"> class="hljs-ln-code"> class="hljs-ln-line">		cursum = cursum * 2 + 1;
    21.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="21"> class="hljs-ln-code"> class="hljs-ln-line">		if(cursum<=x)
    22.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="22"> class="hljs-ln-code"> class="hljs-ln-line">		ans.push_back(curn++);
    23.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="23"> class="hljs-ln-code"> class="hljs-ln-line">	}
    24.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="24"> class="hljs-ln-code"> class="hljs-ln-line">	if (cursum > x)//二进制拆分补充
    25.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="25"> class="hljs-ln-code"> class="hljs-ln-line">	{
    26.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="26"> class="hljs-ln-code"> class="hljs-ln-line">		curn--;
    27.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="27"> class="hljs-ln-code"> class="hljs-ln-line"> 
    28.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="28"> class="hljs-ln-code"> class="hljs-ln-line">		cursum = (cursum - 1) / 2;
    29.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="29"> class="hljs-ln-code"> class="hljs-ln-line">		cursum = x - cursum;
    30.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="30"> class="hljs-ln-code"> class="hljs-ln-line">		//补
    31.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="31"> class="hljs-ln-code"> class="hljs-ln-line">		//求个最大值快速幂吧，顺便当复习了
    32.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="32"> class="hljs-ln-code"> class="hljs-ln-line">		ll val = ksm(2, curn);
    33.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="33"> class="hljs-ln-code"> class="hljs-ln-line">		int curvaln = curn+1;
    34.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="34"> class="hljs-ln-code"> class="hljs-ln-line">		while (cursum > 0)
    35.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="35"> class="hljs-ln-code"> class="hljs-ln-line">		{
    36.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="36"> class="hljs-ln-code"> class="hljs-ln-line">			if (val <= 0)
    37.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="37"> class="hljs-ln-code"> class="hljs-ln-line">			{
    38.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="38"> class="hljs-ln-code"> class="hljs-ln-line">				cout << "impossible!!!";
    39.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="39"> class="hljs-ln-code"> class="hljs-ln-line">				exit(-1);
    40.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="40"> class="hljs-ln-code"> class="hljs-ln-line">			}
    41.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="41"> class="hljs-ln-code"> class="hljs-ln-line"> 
    42.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="42"> class="hljs-ln-code"> class="hljs-ln-line">			if (val <= cursum)
    43.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="43"> class="hljs-ln-code"> class="hljs-ln-line">			{
    44.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="44"> class="hljs-ln-code"> class="hljs-ln-line">				ans.push_back(curvaln);
    45.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="45"> class="hljs-ln-code"> class="hljs-ln-line">				cursum -= val;
    46.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="46"> class="hljs-ln-code"> class="hljs-ln-line">			}
    47.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="47"> class="hljs-ln-code"> class="hljs-ln-line">			val /= 2;
    48.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="48"> class="hljs-ln-code"> class="hljs-ln-line">			curvaln--;
    49.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="49"> class="hljs-ln-code"> class="hljs-ln-line">		}
    50.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="50"> class="hljs-ln-code"> class="hljs-ln-line">	}
    51.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="51"> class="hljs-ln-code"> class="hljs-ln-line">	cout << ans.size() << endl;
    52.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="52"> class="hljs-ln-code"> class="hljs-ln-line">	for (auto num : ans)
    53.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="53"> class="hljs-ln-code"> class="hljs-ln-line">	{
    54.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="54"> class="hljs-ln-code"> class="hljs-ln-line">		cout << num << " ";
    55.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="55"> class="hljs-ln-code"> class="hljs-ln-line">	}
    56.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="56"> class="hljs-ln-code"> class="hljs-ln-line">	cout << endl;
    57.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="57"> class="hljs-ln-code"> class="hljs-ln-line">}
     class="hide-preCode-box"> class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

    >>
    注：本文转载自blog.csdn.net的DBWG的文章"https://blog.csdn.net/JK01WYX/article/details/135715281"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
    复制链接
    复制链接
    相关推荐
    发表评论

    评论记录：

    未查询到任何数据！