首页 > 代码库 > 垂死挣扎-4

垂死挣扎-4

现在有一个字符串,你要对这个字符串进行 n 次操作,每次操作给出两个数字:(p, l) 表示当前字符串中从下标为 p 的字符开始的长度为 l 的一个子串。你要将这个子串左右翻转后插在这个子串原来位置的正后方,求最后得到的字符串是什么。字符串的下标是从 0 开始的,你可以从样例中得到更多信息。

 

输入描述:

每组测试用例仅包含一组数据,每组数据第一行为原字符串,长度不超过 10 ,仅包含大小写字符与数字。接下来会有一个数字 n 表示有 n 个操作,再接下来有 n 行,每行两个整数,表示每次操作的(p , l)。

保证输入的操作一定合法,最后得到的字符串长度不超过 1000。



输出描述:

输出一个字符串代表最后得到的字符串。

 

输入例子:
ab20 21 3

 

输出例子:
abbaabb



#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {

string str;
while (cin>>str) {
int n;
cin >> n;
while (n --) {
int beg,len,index;
cin>>beg>>len;
string temp = str.substr(beg,len);
index = beg + len;
reverse(temp.begin(), temp.end());
str.insert(index, temp);
}
cout<<str<<endl;
}

return 0;
}

 

 

给定 x, k ,求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算,例如 3 | 5 = 7。

比如当 x=5,k=1时返回 2,因为5+1=6 不等于 5|1=5,而 5+2=7 等于 5 | 2 = 7。

 

输入描述:

每组测试用例仅包含一组数据,每组数据为两个正整数 x , k。 满足 0 < x , k ≤ 2,000,000,000。



输出描述:

输出一个数y。

 

输入例子:
5 1

 

输出例子:
2


先上代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <bitset>
using namespace std;
 
int main() {
    unsigned long long x, y = 1, k;
    cin >> x >> k;
     
    std::bitset<64> xbs(x), kbs(k);
 
    for (size_t i = 0, kpos = 0; i < xbs.size(); ++i) {
        if (! xbs.test(i)) { // xbs[i] == 0
            xbs.set(i, kbs[kpos++]);
        }
    }
 
    y = xbs.to_ullong();
    y ^= x;
 
    cout << y << endl;   
     
    return 0;
}
 
再来分析:
 
此题很容易用代码描述,
bool is_eq(x, y) {
return x + y == x | y;
}
 
然后整个循环从 1 到 y,y 是 第 k 个 满足 is_eq() 的数。这样做没错,但是 测试用例给整个:
x = 1073741802, k = 1073741823 这么大的数,显然暴力穷举就不合适了。
 
但是可以举几个数字组合来找其中的规律:
例如:
k = 1 时,5 + 2 == 5 | 2
k = 2 时,5 + 8 == 5 | 8
k = 3 时,5 + 10  == 5 | 10
k = 4 时,5 + 16  == 5 | 16
k = 5 时,5 + 18  == 5 | 18
 
技术分享 
 
转二进制
技术分享 
 
满足这个运算规律 x + y == x | y 的二进制有:
0 + 0 == 0 | 0
1 + 0 == 1 | 0
1 + 1 !=  1 | 1 (只有这个不满足)
 
所以 x y 各自相对应的二进制位不能同时为 1,换言之, x 中 当前位 为 1 时, 与之对应的 y 那一位 肯定是 0
所以 x 位为 1 的就确定了,可以去除1
 
X
技术分享 
Y
技术分享 
 
将 Y 中红色 的 0 去掉看看,得到一组新数据
技术分享 
 
这正是 从 1 2 3 4 5 6 7,由于 y 表是按照 k 从1递增的顺序得到的值。所以你有理由猜想 这组新数据正是 k !
 
X  Y K 之间 有了这个关系,就大胆的编写代码去验证吧。
 
算法大概是,将 x 和 y 都转成 二进制串, 然后将 y 的二进制串依次塞进 x 串中为 0 的部位,得到的一个新值,
把这个值中原先 x 为 1 的 位 都给改成 0,就能得到 y 值。
 
比如 k = 3 = b(1 1), x = 5 = b(0101)
第一步将 k 塞入 x, 得到 b(1111), 第二步将原先 x 中为 1 的变成 0, 得到 b(1010) , 即 y = 10

垂死挣扎-4