程序员进阶之算法练习（八十三）
题目1
题目链接
题目大意：
有长度为n的整数数组a，数组元素都由-1和1组成；
现在每次可以选择一个数组位置，翻转位置上元素（-1变成1，1变成-1）；
假如想要实现下面的要求，最少需要多少次操作：
𝑎1+𝑎2+…+𝑎𝑛≥0
𝑎1⋅𝑎2⋅…⋅𝑎𝑛=1
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤500) 每个样例2行， 第一行，整数n (1≤n≤ 100) 第二行，n个整数；
输出： 每个样例一行，输出最小操作次数。
Examples input 7 4 -1 -1 1 -1 5 -1 -1 -1 1 1 4 -1 1 -1 1 3 -1 -1 -1 5 1 1 1 1 1 1 -1 2 -1 -1
output 1 1 0 3 0 1 2
题目解析： 我们用x来表示1的数量，y表示-1的数量； 当x<y时，需要将一部分-1变成1，这个数量是ans=(y - x + 1) / 2；（因为每次变化，都会让x和y的值差2，所以最终要除以2） 当y=y-ans后，假如y%2为1，证明最终结果还是为负数，此时需要再去掉一个-1，故而++ans；
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a = 0, b = 0;
while (n--) {
int tmp;
cin >> tmp;
if (tmp == 1) ++a;
else ++b;
}
int ans = 0;
if (a < b) {
ans = (b - a + 1) / 2;
a += ans;
b -= ans;
}
if (b % 2) {
++ans;
}
cout << ans << endl;
}
}
}
ac;题目2
题目链接 题目大意： 有两个很大的整数，用字符串L和字符串R表示，其中L代表的数字小于R代表的数字； 现在想在区间[L, R]中找到2个数字，使得这两个数字的十进制表示上，每一位的绝对值差尽可能大。
十进制位数差，就是将两个整数每一位的数字进行想减，然后累加绝对值，如果位数不相同则补前导零； 比如说： 55和37，结果 |5−5|+|3−7|=4 190和209，结果 |1−2|+|9−0|+|0−9|=19 1909和90，结果 |1−0|+|9−0|+|0−9|+|9−0|=28
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤5000) 每个样例一行，字符串L和字符串R，长度不超过100；
输出： 每个样例一行，输出区间内最大的十进制位数差。
Examples input 6 53 57 179 239 13 37 132228 132228 54943329752812629795 55157581939688863366 88 1914
output 4 19 11 0 163 28
题目解析： 当只有1位时，十进制差就是个位数想减； 当有2位时，如果第一位相同，则结果为第二位相差； 如果第一位不相同，那么结果为第一位之差，加上第二位9和0的差距；因为L的第二位总是能上升到9，R的第二位总是能降低为0； 举例说明，区间[23, 46]，29肯定在区间内，因为十位数2<4，那么29肯定小于46；又由于9>=3，29在区间内； 同理，46可以选出40，满足在区间内；
那么当我们找到某一位不相同时，这一位后面的数字都可以填充9999..和0000...，然后再累加上当前位数差值，就是最大的结果。
class Solution {
static const int N = 201010;
char a[N], b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> a >> b;
int n = strlen(a);
int m = strlen(b);
int ans = 0;
if (n < m) {
ans = b[0] - '0' + (m - 1) * 9;
}
else if(n > m){
ans = a[0] - '0' + (n - 1) * 9;
}
else {
int k = -1;
for (int i = 0; i < n; ++i) if(a[i] != b[i]) {
k = i;
break;
}
if (k == -1) ans = 0;
else {
ans = abs(a[k] - b[k]) + (n - 1 - k) * 9;
}
}
cout << ans << endl;
}
}
}
ac;题目3
题目链接 题目大意： 有两个字符串S和T，长度均为n； 现在Alice和Bob两个人在玩有一个游戏，两个人轮流行动，Alice先手。 Alice的操作，是选择字符串S或者字符串T中的某一个元素，将其修改为任意字符； Bob的操作，是选择字符串S或者字符串T，翻转该字符串；
当字符串完全相同时，游戏结束。
Alice的目标是尽可能少行动次数，Bob的目标是尽可能多行动次数； 假设Alice和Bob的行动都是最优决策。 现在想要知道，当Alice和Bob总共需要行动多少步。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例3行， 第一行，整数𝑛(1≤𝑛≤1e5) 第二行，字符串S； 第三行，字符串T；
输出： 每个样例一行，输出最终行动步数。
Examples input 7 5 abcde abxde 5 hello olleo 2 ab cd 7 aaaaaaa abbbbba 1 q q 6 yoyoyo oyoyoy 8 abcdefgh hguedfbh
output 1 2 3 9 0 2 6
题目解析： 先分析Alice和Bob的策略。 先从Alice的视角来看，最终游戏必然会停止，因为Alice可以把字符串S、T修改为完全相同的字符组成，这样使得Bob的翻转操作无效； 为了尽可能减少步数，必须利用Bob的翻转操作，例如说当Bob遇到abc和cba时，由于Bob必须选择一个字符串翻转，最终游戏必然会停止。 我们以字符串S为参考下，最终结果要么是字符串S、要么是字符串revertS； 计算得到字符串T和字符串S、字符串T和字符串revertS的差异部分，最终的游戏过程就是Alice修改差异部分字符，然后Bob不断翻转，最终字符串以S或者revertS结束。 （注意，这里为了简化分析，利用了两个隐性条件，Alice修改S和修改T是等价的，Bob翻转字符串S和字符串T是等价的）
不同的是，当最终以字符串S结束时，翻转次数为偶数； 当最终以字符串revertS结束时，翻转次数为奇数。
class Solution {
static const int N = 201010;
char a[N], b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cin >> a >> b;
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; ++i) {
if (a[i] != b[i]) ++cnt1;
if (a[n - i - 1] != b[i]) ++cnt2;
}
if (cnt1 == 0) cout << 0 << endl;
else {
/*
1次，翻转成本0 0
2次，翻转成本2 0 21 0 12
3次，翻转成本2 0 21 0 12 0
4次，翻转成本4 0 21 0 12 0 21 0 12
5次，翻转成本4 0 21 0 12 0 21 0 12 0
*/
int ans1 = cnt1 + cnt1 / 2 * 2; //翻转成本为偶数
/*
1次，翻转成本1 0 21
2次，翻转成本1 0 21 0
3次，翻转成本3 0 21 0 12 0 21
4次，翻转成本3 0 21 0 12 0 21 0
5次，翻转成本5 0 21 0 12 0 21 0 12 0 21
*/
cnt2 = max(1, cnt2);
int ans2 = cnt2 + (cnt2 - 1) / 2 * 2 + 1;
cout << min(ans1, ans2) << endl;
}
}
}
}题目4
题目链接 题目大意： 课堂上有n个学生，一共有m门课程（序号为1、2、3、、、m）； 由于时间限制，每个学生只能预习序号为l[i]到r[i]的课程； 老师会询问若干个课程的预习情况，某个课程如果预习了可以得1分，没预习则扣1分； 现在想知道，分数最高者和分数最低者，两者的最大分差是多少？ 注意： 1、老师可以任意询问多个课程，但每个课程只能询问1次； 2、分数可以为负数；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例 第一行，整数𝑛 and 𝑚 (2≤𝑛≤1e5,1≤𝑚≤1e9 ) 接下来n行，每行两个整数𝑙𝑖 and 𝑟𝑖 (1≤𝑙𝑖≤𝑟𝑖≤𝑚 )
输出： 每个样例一行，输出分数最高者和分数最低者，两者的最大分差；
Examples input 6 4 8 2 6 4 8 2 7 1 5 3 3 1 3 2 3 2 2 3 5 1 5 1 5 1 5 3 5 1 1 3 3 5 5 4 7 1 7 1 3 3 3 4 5 2 4 1 3 2 4
output 6 4 0 2 12 2
题目解析： 抽象成两个线段，求某个线段去掉共同部分的最大值。 我们以线段A和B来思考，我们固定线段A，线段B有几种情况： 1、线段B与线段A相交，并且是线段B右边界超过了线段A，此时线段B的左区间越大越好； 2、线段B与线段A相交，并且是线段B左边界超过了线段A，此时线段B的右区间越小越好； 3、线段B在线段A内部，此时线段B越短越好； 4、线段B覆盖了线段A，此时可以认为是情况1或者情况2，所以当下情况可以忽略；
由上面分析可以知道，我们知道最终左区间最大、右区间最小、线段最短，这三种情况的线段必然会是最终两个线段中的一个； 那么可以选择这三条线段，再枚举其他所有线段，得到最优解。
trick1： 在处理线段相交、覆盖的时候，需要边界情况，可以枚举上面提到的多种样例情况进行测试； 比如说样例： 4 2 20 1 2 2 3
2 20 1 2 3 4
2 20 1 3 2 4
2 20 2 3 1 4
trick2： 由于数据范围较大，在枚举较大值时，用0xfffffff这种容易出错，直接用1e9+1保证结果正常；
class Solution {
static const lld N = 201010;
pair<lld, lld> a[N];
lld look(lld x1, lld y1, lld x2, lld y2) {
lld ret = 0;
pair<lld, lld> p[2] = {{x1, y1}, {x2, y2}};
sort(p, p + 2);
// p[0].first < p[1].first
if (p[0].second < p[1].first) {
ret = max(p[0].second - p[0].first + 1, p[1].second - p[1].first + 1);
}
else if (p[0].second < p[1].second) {
ret = max(p[1].first - p[0].first, p[1].second - p[0].second);
}
else {
ret = (p[1].first - p[0].first) + (p[0].second - p[1].second);
}
return ret;
}
lld check(lld x, lld y, lld n) {
lld ret = 0;
for (lld i = 0; i < n; ++i) {
ret = max(ret, look(x, y, a[i].first, a[i].second) * 2);
}
return ret;
}
public:
void solve() {
lld t;
cin >> t;
while (t--) {
lld n, m;
cin >> n >> m;
for (lld i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
lld ans = 0;
lld len = 1e9 + 1, x = 0, y = 0;
for (lld i = 0; i < n; ++i) {
if (a[i].second - a[i].first < len) {
x = a[i].first;
y = a[i].second;
len = y - x;
}
}
ans = max(ans, check(x, y, n));
x = 0, y = 0;
for (lld i = 0; i < n; ++i) {
if (a[i].first > x) {
x = a[i].first;
y = a[i].second;
}
}
ans = max(ans, check(x, y, n));
x = 0, y = 1e9 + 1;
for (lld i = 0; i < n; ++i) {
if (a[i].second < y) {
x = a[i].first;
y = a[i].second;
}
}
ans = max(ans, check(x, y, n));
cout << ans << endl;
}
}
}题目5
题目链接 题目大意： 有3个正整数a、b、c，并且满足a+b=c； 现在已知a、b、c三个整数的位数，用十进制表示分别为A、B、C； 想知道所有满足a+b=c的字符串中，按照字典序，第k个字符串是什么。 以 𝐴=1 , 𝐵=1 , 𝐶=2 为例 第1个字符串是，1+9=10 第2个字符串是，2+8=10 第3个字符串是，2+9=11 ...
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例一行，整数𝐴 , 𝐵 , 𝐶 , 𝑘 (1≤𝐴,𝐵,𝐶≤6 , 1≤𝑘≤1e12 ).
输出： 每个样例一行，如果存在，得输出第k个组合； 如果不存在，则输出-1；
Examples input 7 1 1 1 9 2 2 3 1 2 2 1 1 1 5 6 42 1 6 6 10000000 5 5 6 3031568815 6 6 6 1000000000000
output 2 + 1 = 3 10 + 90 = 100 -1 9 + 99996 = 100005 -1 78506 + 28543 = 107049 -1
题目解析： 首先，我们知道数字c长度不会比数字a和数字b短，因为两个正整数相加，位数不会变成少； 其次，两个正整数相加，位数最多变长1位，因为进位不可能连续变长2位，比如说99 + 99=199，2个两位数相加，数字和最多是三位；
剩下所有的数字，总能找出A+B=C的组合。 由于要按照字典序，那么枚举A优先级最高，其次是枚举B，最后C由A+B决定，不用枚举（但要满足位数限制）； 所以A首先从pow(10, A-1)开始枚举，也就是A=2则从10开始枚举，A=3则从100开始枚举； 数字B的枚举同样有个区间[minB, maxB]，minB=pow(10, B-1)，maxB=pow(10, B) - 1； 数字C的结果区间同样是[minC, maxC]； 如果想要满足A+B=C，那么A+maxB应该要大于等于minC，并且A+minB应该要小于等于maxC； 分析到这里，就可以很容易知道，当固定A之后，B的取值区间应该就是minC-A到maxC-A。
整个算法要枚举A的数值，每次枚举复杂度O(1)，整个算法复杂度O(A)；
class Solution {
typedef long long lld;
static const lld N = 201010;
public:
void solve() {
lld t;
cin >> t;
while (t--) {
lld a,b,c,k;
cin >> a >> b >> c >> k;
if (c < a || c < b || c > (max(a, b) + 1)) {
cout << -1 << endl;
continue;;
}
lld find = 0;
for (lld i = pow(10, a - 1); i < pow(10, a); ++i) {
// i + j = l
lld minJ = pow(10, b - 1);
lld maxJ = pow(10, b) - 1;
lld minL = pow(10, c - 1);
lld maxL = pow(10, c) - 1;
if (i + maxJ >= minL && i + minJ <= maxL) {
lld startJ = max(minJ, minL - i);
lld endJ = min(maxJ, maxL - i);
lld sum = endJ - startJ + 1;
if (sum < k) k -= sum;
else {
find = 1;
printf("%lld + %lld = %lld\n", i, startJ + k - 1, i + startJ + k - 1);
break;
}
}
}
if (!find) cout << -1 << endl;
}
}
}
ac;