程序员进阶之算法练习（七十九）
题目1
题目链接 题目大意： 有n个人参加投票，小明是第一个； 投票一共k轮，每轮每个人会做出一个选择，分别用+和-表示，那么一共有三个结果： +的人数大于-的人数，那么-的人出局； -的人数大于+的人数，那么+的人出局； 如果+和-的人数一样多，那么所有人出局； 出局的人，不再参与后续投票。
小明有特权，可以在第一轮投票之前淘汰掉若干个人，现在想知道，最终能有多少个人留到了最后；（小明一定保证自己会留到最后）
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例n+1行 第一行，整数𝑛 和 𝑘 (1≤𝑛,𝑘≤100) 接下来n行，每行有k个字符，表示每个人都投票结果。
输出： 输出留到最后的人数。
Examples input 5 2 2 ++ +- 1 3 +-+ 4 1
5 4 ++++ +--+ ++-+ +-++ ++++ 4 2 ++ -- -- -+
output 1 1 2 2 1
题目解析： 由于题目不需要选择淘汰的顺序，并且小明一定会留在最后，那么和小明相同的投票结果的人会保留；
class Solution {
static const int N = 201010;
char s[N], r[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int ans = 1;
cin >> s;
for (int i = 1; i < n; ++i) {
cin >> r;
int tmp = 0;
for (int j = 0; j < k; ++j) tmp += s[j] == r[j];
ans += tmp == k;
}
cout << ans << endl;
}
}
}题目2
题目链接 题目大意： 给出一个由整数和?组成的字符串，其中符号?可以匹配任何单个数字； For example: 42 matches 4?; 1337 matches ????; 1337 matches 1?3?; 1337 matches 1337; 3 does not match ??; 8 does not match ???8; 1337 does not match 1?7.
现在问给出的字符串，最多存在多少个合法的匹配数字；（不包括前导零，整数大于零）
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤20000) 每个样例1行，字符串𝑠 (1≤|𝑠|≤5)
输出： 每个样例一行，输出最多存在多少个合法的匹配数字；
Examples input 8 ?? ? 0 9 03 1??7 ?5? 9??99
output 90 9 0 1 0 100 90 100
题目解析： 分情况讨论： 1、给出的字符串就存在前导零，那么结果为0； 2、给出的字符串合法，并且存在x个?号，那么有两种情况： 2.1，?号之前已经有整数，此时?号可以取任意数字，那么x个?号可以得到10^x个整数； 2.2，?号前面没有整数，此时第一个?号只能取1-9数字，所以会减少10^(x-1)个答案；
class Solution {
static const int N = 201010;
char s[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> s;
int n = strlen(s);
int x = 0;
for (int i = 0; i < n; ++i) x += (s[i] == '?');
if (s[0] == '0') cout << 0 << endl;
else if (s[0] == '?') {
if (!x) cout << 1 << endl;
else cout << (int)pow(10, x) - (int)pow(10, x - 1) << endl;
}
else {
cout << (int)pow(10, x) << endl;
}
}
}
}
ac;题目3
题目链接 题目大意： 给出一个由n个整数组成的数组a，在数组中选择区间[l, r]，将区间内的整数按照非降序进行处理得到整数数组b，比如说： 整数数组a为[6,7,3,4,4,6,5]，选择区间[2, 5]得到整数数组b为[6,3,4,4,7,6,5]；（区间外的整数位置不变）
现在已知整数数组a和变化后的整数数组b，求区间最长可能为多少？
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例3行： 第一行整数n(2≤𝑛≤2⋅1e5) 第二行整数数组a 第二行整数数组b 注意：数组a和数组b至少有一个位置的元素不相同。
输出： 每个样例一行，输出区间[l, r]，表示可以选择进行操作的最长区间，如果由多个答案，输出任意一个；（题目保证有解）
Examples input 3 7 6 7 3 4 4 6 5 6 3 4 4 7 6 5 3 1 2 1 1 1 2 3 2 2 1 2 1 2
output 2 5 1 3 2 3
题目解析： 假如不考虑复杂度，那么应该枚举区间[x, y]，然后计算每个区间的可行性，这样复杂度为枚举复杂度 * 验证复杂度，枚举就已经超过题目限制； 注意题目给出的条件，数组a和b有元素不相同，那么至少存在2个位置不相同，否则题目无解； 假定第一个不相同元素的位置是x，最后一个不相同元素的位置是y，那么区间[x, y]必然是一个解，但不是最长解： 假设区间[x, y]右边的元素比区间[x, y]内的元素更大，那么可以纳入到这个区间内，因为排序完无影响； 同理对于区间[x, y]左边的元素，只要小于的等于区间内最小值，那么同意可以纳入到区间中；
注意： 区间外的整数，不一定有序的，比如说： 2 2 4 3 5 4 2 2 3 4 5 4
class Solution {
static const int N = 201010;
int a[N];
int b[N];
public:
void solve() {
int t;
cin >> t;
int cnt = 0;
while (t--) {
int n, x, y = 0;
cnt++;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cin >> b[i];
x = -1;
for (int i = 0; i < n; ++i) {
if (a[i] != b[i]) {
if (x == -1) x = i;
else y = i;
}
}
int valMin = b[x], valMax = b[y];
while (x > 0) {
if (b[x - 1] <= valMin) --x;
else break;
valMin = min(valMin, b[x]);
}
while (y < n - 1) {
if (b[y + 1] >= valMax) ++y;
else break;
valMax = max(valMax, b[y]);
}
cout << (x + 1) << " " << (y + 1) << endl;
}
}
}题目4
题目链接 题目大意： 给出一个小写字母组成的字符串s，现在可以对字符串进行多次操作： 选择若干个不相邻的位置，移除这些位置上的字符，剩下的字符保持相对顺序组成新的字符串s；
假如操作若干次后，剩下的字符串都由相同字符组成，最少需要多少次；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行，字符串s；（长度不超过200,000）
输出： 每个样例一行，输出最少的次数。
Examples input 5 abacaba codeforces oooooooo abcdef mewheniseearulhiiarul
output 1 3 0 2 4
12345678
题目解析： 先简化题目，按照题目去掉若干个字符： 去掉字符长度为2，需要2个操作； 去掉字符长度为3，需要2个操作； 去掉字符长度为4，需要3个操作； 去掉字符长度为7，需要3个操作； 去掉字符长度为8，需要4个操作； ... 去除的规则比较简单，每次去除所有奇数位置，就可以最快去除；
题目的要求，最后只剩一种字符，那么结果一共有26种组合。 以字符a为例，遍历一遍字符串，那么就可以得到若干个由a分隔的区间，其中最长的区间假设是x，那么这个区间的移除代价就是最终的移除代价； 同理得到26个字母的结果，取其最小得到结果。
class Solution {
static const int N = 201010;
char s[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> s;
int n = strlen(s);
int ans = n;
for (int i = 0; i < 26; ++i) {
char c = 'a' + i;
int len = 0, last = -1;
for (int j = 0; j < n; ++j) {
if (s[j] == c) {
last = j;
}
else {
len = max(len, j - last);
}
}
if (len == 0) {
ans = 0;
break;
}
int tmp = 1;
while ((1 << tmp) <= len) ++tmp;
ans = min(ans, tmp);
}
cout << ans << endl;
}
}
}题目5
题目链接 题目大意： 有一排格子排成一行，编号从左到右分别为0、1、2、3； 小明站在第0个格子，每次小明有三个选择可以进行操作： 1、移动到下一个格子：从格子x移动到格子x+1； 2、按下shift按钮； 3、松开shift按钮，小明在按下shift按钮期间经过的格子会被染色；
现在只有若干个区间[x, y]允许染色，区间外的格子不允许染色； 现在想要染色k个格子，问最少需要操作多少次；
1e18
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例3行： 第一行，整数 𝑛 和 𝑘 (1≤𝑛≤2⋅1e5; 1≤𝑘≤1e9) 第二行，整数 𝑙1,𝑙2,…,𝑙𝑛，表示n个区间的起点 (1≤𝑙1<𝑙2<⋯<𝑙𝑛≤1e9) 第三行，整数 𝑟1,𝑟2,…,𝑟𝑛 ，表示n个区间的终点 (1≤𝑟𝑖≤109; 𝑙𝑖≤𝑟𝑖<𝑙𝑖+1−1) n个区间没有重合；
输出： 每个样例一行，输出最少的操作次数，如果无解则输出-1；
Examples input 4 2 3 1 3 1 4 4 20 10 13 16 19 11 14 17 20 2 3 1 3 1 10 2 4 99 999999999 100 1000000000
output 8 -1 7 1000000004
题目解析： 简单策略，小明从左到右，只要经过允许的区间就染色，直到k个格子； 考虑到要最小操作次数，那么同一个区间的染色操作要合并，那么策略可以进行优化： 对于每一个区间，先考虑区间是否小于需要染色数量，是的话则直接染色整个区间； 如果当前区间足够剩余染色数量，则选择需要染色的x个格子即可。 但是这种策略少考虑了一种情况： 以题目样例3为例，假设一种情况是1011111111，其实先选择前面的1，则会花费3的代价（两次shift+1次移动），总的花费是8；如果不选择前面1，而是选择后面位置3开始的1，则只需要花费的代价是7； 为什么会出现这种情况？ 因为前面会有2次选中操作，但是后面则只需要1次选中操作，减少了1次选中操作（即是2次shift），虽然多花费了1次move操作，但是总的花费还是减少了1； 所以在这种情况下，简单的策略在以下这种情况： 101010....011111....0110..101010....1111111... 都会难以处理，因为在决策是否要染色时，还可能受到后续方块的影响。
为了简化思考过程，可以我们把移动和选择拆分来看，先假设小明从0开始移动到第i个可以染色区间，小明经过的区间可以分为三类： 1、长度为1区间； 2、第1个到第i-1个区间中，长度大于1的区间； 3、第i个区间；（为什么第i个单独列出来，是因为第i个允许仅染色部分）
移动的代价分为两部分，首先是移动到第i个区间起始位置，另外一个是在第i个区间移动的距离； 选择的代价，首先是长度大于>1的区间，然后是第i个区间，接着是长度为1的区间；
Example： k=10 10101010101010101010111011111111111111 19+2*10=39 20+4+7+4=35
class Solution {
static const int N = 201010;
int a[N], b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cin >> b[i];
lld sum = 0, oneCnt = 0;
lld ans = 0xffffffffffff;
for (int i = 0; i < n; ++i) {
lld len = b[i] - a[i] + 1;
if ((sum + len) >= k && k >= (sum - oneCnt)) {
if (sum - oneCnt + len >= k) {
ans = min(ans, a[i] - 1 + (i - oneCnt + 1) * 2 + (k - (sum - oneCnt)));
}
else {
ans = min(ans, a[i] - 1 + (i - oneCnt + 1) * 2 + len + 2 * (k - (sum - oneCnt + len)));
}
}
if (len == 1) ++oneCnt;
sum += len;
}
if (ans == 0xffffffffffff) cout << "-1" << endl;
else cout << ans << endl;
}
}
}腾讯云开发者
