CF#739-D Make a Power of Two

CF#739-D Make a Power of Two

整局链接：Codeforces Round #739 (Div. 3)

题目大意：

给一个数字，你可以有以下两种操作：

1.删除任意数位上的数字；2.在最右边加上一个数位

问最少经过多少次操作这个数字可以变成2的次方。

思路：

一开始我以为是数位dp直接GG

//以下文字结合代码看比较好理解

实际上，只要把给定的数和所有2的次方比较求答案取最小值就行了。当然，2的次方不会是无限个，这题的数据范围只需要到60次就行。那怎么去比较呢，可以用子序列的思想。设2的次方是a，给定的是b，我们要找b里面形如a的子序列（可能不是完整的）。

在b中如果找到不一样的，就是说要删掉这个数位。上图中颜色一样的就是对应相等的，而b[2]就是应该删掉的数位。

设指向a的是i，指向b的是j。

当ij指针中有一个走完后，有四种情况：i没走完，j没走完，ij都没走完，ij都走完。

i < la ：i没走完，就是说要b变成a，就要加上a中i后面的那些数字

j < lb ：j没走完，就是说b要变成a，就要减去b中j后面的那些数字

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 2*1e8+10;
string s[70] = {"1","2","4","8","16","32","64","128","256","512","1024","2048","4096","8192","16384","32768","65536","131072","262144","524288","1048576","2097152","4194304","8388608","16777216","33554432","67108864","134217728","268435456","536870912","1073741824","2147483648","4294967296","8589934592","17179869184","34359738368","68719476736","137438953472","274877906944","549755813888","1099511627776","2199023255552","4398046511104","8796093022208","17592186044416","35184372088832","70368744177664","140737488355328","281474976710656","562949953421312","1125899906842624","2251799813685248","4503599627370496","9007199254740992","18014398509481984","36028797018963968","72057594037927936","144115188075855872","288230376151711744","576460752303423488","1152921504606846976"};//这个是1~2**60的打表拿另外一个程序写很快的。
string t;
int T;

inline ll read(){//快读
    ll ans = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c)){
        ans = ans * 10 + c - ‘0‘;
        c = getchar();
    }return ans;
}

int solve(string a,string b){
	int i = 0,j = 0,res = 0;
	int la = a.length(),lb = b.length();
	while(i < la && j < lb){
		if(a[i] == b[j])++i,++j;
		else{
			while(j < lb && a[i] != b[j])++j,++res;
		}
	}
	
	if(i < la)res += la - i;//a没走完，要在最后加数字
	if(j < lb)res += lb - j;//b没走完，要在最后删数字
	//cout<<a<<"======================>"<<res<<"\n";
	return res; 
}

int main(){
	T = read();
	while(T--){
		cin>>t;
		int ans = INF;
		for(int i = 0;i < 61; i++)//对和所有2的次方的比较中取最小值
			ans = min(ans,solve(s[i],t));
		cout<<ans<<"\n";
	}
}

CF#739-D Make a Power of Two

原文：https://www.cnblogs.com/tyriis/p/15172824.html