题目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;
}
}
}
