程序员进阶之算法练习（四十四）
正文
题目1
题目链接 题目大意： 给出整数x，求两个整数a和b，满足： ???(?,?)+???(?,?)=? . GCD是最大公约数； LCM是最小公约数；
题目保证a和b存在；
输入： 第一行整数t，表示样例个数； (1≤?≤100) 接下来t个样例，每个样例一行，整数x；(2≤?≤10^9)
输出： 整数a和b； (要求范围，1≤?,?≤10^9)
Examples input 2 2 14 output 1 1 6 4
题目解析： 构造题，这里提供一种方法：1+(x-1)。
构造题，想到就简单；想不到就很难。 如果不能马上想到规律，可以尝试将数字设置小一些，比如说x=10； 再多考虑x=11、x=12这些，探索规律，然后将x=100进行验证。
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << 1 << " " << n - 1 << endl;
}题目2 CopyCopyCopyCopyCopy
题目链接 题目大意： 给出n个整数的数组，现在将数组复制，放在数组末尾，重复n次； 求新的数组中，最长严格递增子序列的长度是多少？
输入： 第一行整数t，表示样例个数； (1≤?≤100) 接下来t个样例，每个样例2行； 第一行，整数? (1≤?≤10^5) 第二行，n个整数?1, ?2, …, ?? (1≤??≤10^9) 每个样例一行，表示最长递增子序列的长度；
Examples input 2 3 3 2 1 6 3 1 4 1 5 9 output 3 5 样例解释，3,2,1重复3次，得到[3,2,1,3,2,1,3,2,1] 最长递增子序列是[1,2,3]，长度是3；
题目解析： 如果n个数字不相同，重复n次之后，必然可以选出n个数字，最长递增子序列的长度是n；（因为重复n次，每次选1个数字就好） 如果n个数字中存在相同，则相同的数字只能取一个； 所以答案就是数组中，数字不同的个数。
转换思路，题目变成求数组中不同数字的数量。
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = 0;
map<int, int> mp;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
if (!mp[k]) {
mp[k] = 1;
++ans;
}
}
cout << ans << endl;
}题目3 Numbers Exchange
题目链接 题目大意： 小明喜欢一种字符串Zebras，Zebras的定义是以0开头，以0结束，中间0/1交替出现，比如说：0, 010, 01010； 类似1, 0110, 0101这种就不是Zebras； 现在给出一串长度为n的字符串（全部是01组成）； 小明希望把字符串分成若干个子序列，并且每个子序列都是Zebras；（每个字符存在子序列中，且只在一个） 如果不能，则输出-1；
输入数据： 一串字符串，长度不超过20w；
输出数据： 第一行，数字k，表示分为k个子序列；
Examples input 0010100
output 3 3 1 3 4 3 2 5 6 1 7 样例解释： 分3个子序列010，010，0；
题目解析： 由贪心知道，01010..的序列越长越好；（0的利用率提升） 题目的要求是每个字符都要放到子序列里去，那么有一种简单的做法： 每次从左到右扫描，在未选择的字符中，寻找最长的Zebras，比如说对样例0010100处理： 第一次扫描，扫出01010；（1，3，4，5，6） 第二次扫描，扫出0；（2） 第三次扫描，扫出0；（7）
但是这样的代价比较高，是N^2级别复杂度；（对于00001111000这样的数据） 考虑这样一种优化方案： 有两个队列x、y，队列x是0结束的子序列，队列y是1结束的子序列；
当遇到0时，从队列y取一个子序列，末尾拼0然后放入队列x；如果队列y没有数据，则新建一个子序列（因为0可以是单独的序列），然后将子序列放入队列x； 当遇到1时，从队列x取一个子序列，末尾拼1然后放入队列y；如果队列x没有数据，则无解；
这样每次都是O(1)的操作，总体的复杂度是O(N)；
cin >> str;
size_t n = strlen(str);
queue<int> q[2];
int id = 0;
int ok = 1;
for (int i = 0; i < n && (ok>0); ++i) {
if (str[i] == '0') {
if (q[1].empty()) {
ans[id].push_back(i);
q[0].push(id++);
}
else {
int x = q[1].front();
q[1].pop();
ans[x].push_back(i);
q[0].push(x);
}
}
else {
if (q[0].empty()) {
ok = -1;
}
else {
int x = q[0].front();
q[0].pop();
ans[x].push_back(i);
q[1].push(x);
}
}
}
if (ok > 0 && q[1].size() == 0) {
cout << id << endl;
for (int i = 0; i < id; ++i) {
cout << ans[i].size() << " ";
for (int j = 0; j < ans[i].size(); ++j) {
cout << ans[i][j] + 1 << " ";
}
cout << endl;
}
}
else {
cout << -1 << endl;
}题目4 A Leapfrog in the Array
题目链接 题目大意： 有若干个格子排成一行序号是1、2、3、4、5、、、，有1~n的n个整数分别放在格子里，第i个数字放在第2i-1格子； 现在对数字进行操作： 每次把最右边的数字x，放在x左边最接近的空格里； 不断重复，直到x左边没有空的格子；
现在有q个询问，每个询问是数字x[i]，求第x[i]个格子上面的数字；
输入数据： n and q (1 ≤ n ≤ 1e18, 1 ≤ q ≤ 200 000) 接下来q行，每行一个数字x[i];
输出数据： 对于每个询问，输出第x[i]个格子上面的数字；
Examples input 4 3 2 3 4 output 3 2 4
样例解释，见上图。
题目解析： 从题目的操作结果来看，最后操作停止的结果必然是n个数字分布在第1到n个格子里； 容易知道，小于等于n/2的数字是不会动的。（因为数字的左边没有格子） 相当于后面(x - n/2)数字排列紧密（没有空格），然后数字的最后一个跳到前面； 于是可以用递归的思想解决问题，不断重复，直到数字剩下1个。
思考?： 另一种解法： 我们用0表示空格，当n=8的时候，原序列为1，0，2，0，3，0，4，0，5，0，6，0，7，0，8 把每次移动的数字写出来： 8，8，7，8，6，7，5，8，4，6，3，7，2，5，1。 或许看不出来问题？ 试试这么看： 8， 8，7 8，6，7，5， 8，4，6，3，7，2，5，1 每次都是从n-2^(i-1)开始，按顺序插入上一行的数字。 从题意知道，每次都会填补数字最左边的一个空格。 又根据移动的性质，我们知道填补第n个格子数字不会再移动。（因为当第n个格子成为最右边的数字时，左边已经没有格子） 所以只需要算出n个数中间的格子是倒数第k个空格，从上面的序列选择第k个数字，就是n个数字移动后最右边一个数字。
/**
1 2 3 4 5 6 按照原来的规则进行选择，最右边的一个
@param n 前n个
@return 最右边的一个
*/
lld solve(lld n) {
if (n % 2) {
return (n + 1) / 2;
}
return n / 2 + solve(n - n / 2);
}
int main(int argc, const char * argv[]) {
// insert code here...
lld n, q;
cin >> n >> q;
while (q--) {
lld x;
cin >> x;
if (x % 2 == 1) {
cout << (x + 1) / 2 << endl;
}
else {
cout << solve(n - x / 2) + x / 2 << endl;
}
}
return 0;
}总结
题目1 是简单构造题，构造题也有一些思考门路，从小样例开始分析规律； 题目2 是考察思路，代码很简单，核心在于有没有想到题目其实就是求数组的不同数字； 题目3 是考察实现能力，可能方法会有很多，但是需要找一个简单快捷方案，并且能输出答案； 题目4 看似很复杂，其实考虑下n=3、n=4、n=5，模拟下操作可以发现规律。