正文
题目1
题目链接
题目大意：
有n个糖果，分给两个人A和B，要求：
两个人都有分配到糖果；
糖果不能拆分，必须全部分分完；
A的糖果数量比B的要多；
问，最终有多少种分配方案。
输入：
第一行，整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
接下来每个样例一行，整数𝑛 (1≤𝑛≤2⋅1e9)
输出：
每个样例一行，输出存在分配方案，不存在则输出0；
Examples
input
6
7
1
2
3
2000000000
763243547
output
3
0
0
1
999999999
381621773
样例解释：
样例1：
7个糖果，有下面3个方案：
𝑎=6, 𝑏=1;
𝑎=5, 𝑏=2;
𝑎=4, 𝑏=3.
题目解析：
分糖条件写的很清楚，两个整数a和b，要求a<b；
对于数字n来说，如果n是偶数，那么有n/2-1种可能；
如果n是奇数，那么有n/2种可能；
利用计算机整除的特性，可以表述为(n-1)/2；
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << (n - 1) / 2 << endl;
}
return 0;
}
题目2
题目链接
题目大意：
有三个正整数n，a，b，现在需要构造一个字符串s，长度为n，只包含小写字母，并且满足要求：
字符串s中，任何长度为a的子串要包含b个不同的字符。
输入：
第一行，整数𝑡表示有t个样例数量 (1≤𝑡≤2000)
接下来每个样例一行，四个整数 𝑛, 𝑎 and 𝑏 (1≤𝑎≤𝑛≤2000,1≤𝑏≤min(26,𝑎))
输出：
每个样例一行，输出满足要求的字符串；（题目保证答案一定存在）
Examples
input
4
7 5 3
6 1 1
6 6 1
5 2 2
output
tleelte
qwerty
vvvvvv
abcde
题目解析：
题目的要求是，长度为a的子串中，有b个不同的字符；
那么将b个字符构成的字符串不断重复，即可满足题目要求；
比如说题目样例 7 5 3
b=3，则用abc不断循环，得到abcabca
样例 5 2 2
b=2，则用ab不断循环，得到ababa
实现较为简单。
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n, a, b;
cin >> n >> a >> b;
int k = 0;
for (int i = 0; i < n; ++i) {
putchar('a' + k);
k = (k + 1) % b;
}
puts("");
}
return 0;
}
题目3
题目链接
题目大意：
有n个整数a[i]，现在需要从中选择两组数字，要求：
1、两组数字的数量一样，每个整数只能划分到一个组内；
2、第一组的数字各不相同，第二组的数字完全相同；
现在希望两组数字尽可能的多，问最多一组能有几个整数。
输入：
第一行，整数𝑡表示有t个样例数量 (1≤𝑡≤10000)
接下来每个样例两行，第一行整数𝑛 (1≤𝑛≤2⋅1e5)
第二行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛),
输出：
每个样例一行，整数x，表示一组最多能够有x个整数。
Examples
input
4
7
4 2 4 1 4 3 4
5
2 1 5 4 3
1
1
4
1 1 1 3
output
3
1
0
2
题目解析：
假如没有要求2，那么直接平分，x最大值就是n/2；
单独考虑不同数字的情况，直接算出数组中有k个不同的整数q，再算出数组中最多重复的整数w;
大多数情况下，min(q, w)就是答案了。
但是存在q和w会公用一个整数，比如说1.2.3,3,3这种情况，或者1.2.3.4.5.2.2情况。
当w<=q-1的时候，重复的数字比较少，所以答案就是w；
如果w>q-1的时候，重复的数字比较多，那么优先把重复的数字分配到第一组，答案就是min(w-1,q)；
int a[N];
map<int, int> hmap;
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
hmap.clear();
int maxCount = 0;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
++hmap[k];
maxCount = max(maxCount, hmap[k]);
}
if (hmap.size() <= maxCount - 1) {
cout << hmap.size() << endl;
}
else {
cout << min((int)hmap.size() - 1, maxCount) << endl;
}
}
return 0;
}
题目4
题目链接
题目大意：
长度为n的字符串，一共有三种字符，'B', 'R', '?'；
'?'的字符需要填充为'B'或者'R'；
现在小明不喜欢相连两个字符是一样的， 现在需要知道怎么填充使得最终相连两个字符相同的情况尽可能少？
比如说"BRRRBBR"就有3个相连的字符相同，"BB"出现一次，"RR"出现两次；
输入：
第一行，整数𝑡表示有t个样例数量 (1≤𝑡≤100)
接下来每个样例两行，第一行整数𝑛 (1≤𝑛≤100)
第二行长度为n的字符串s
输出：
每个样例一行，输出由'B'和'R'字符串构成的字符串。
Examples
input
5
7
?R???BR
7
???R???
1
?
1
B
10
?R??RB??B?
output
BRRBRBR
BRBRBRB
B
B
BRRBRBBRBR
题目解析：
方案1，动态规划，dp[i][2]表示前i个字符，第i个字符为B、R的最小重复次数；
初始化的时候，如果第1个字符是？则dp[1][0]=dp[1][1]=0；
第1个字符是B，则dp[1][0]=0，dp[1][1]=n;（n是极大值，表示dp[1][1]不可取）
第1个字符是R，则dp[1][1]=0，dp[1][0]=n;（n是极大值，表示dp[1][0]不可取）
状态转移的时候，dp[i]可以由dp[i-1]来进行计算；
如果a[i]==B，则dp[i][0] = min(dp[i-1][0]+1, dp[i-1][1])； dp[i][1]=n;
如果a[i]==R，则dp[i][1] = min(dp[i-1][1]+1, dp[i-1][0])； dp[i][1]=n;
这样看最终dp[n]的最小值即可。
方案2，找到第一个不为?的字符，从这个位置分别向左右开始填充，每次优先选择相邻字符不相同的方案；
??R??
RBRBR
方案3，通过数学直接计算；
从左到右，如果第i个字符串前面??没有确定字符，则这段?不会产生特殊字符；若？？前面有确定字符k，则根据a[i]和a[k]以及(i-k)可以直接计算出来有多少个相同字符；（0或者1）
考虑到题目要输出结果，还是方案2比较简单。
思考🤔：
如果是要连续3个字符串不一样呢？
class Solution {
static const int N = 200010;
string str;
char ans[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cin >> str;
int pos = n;
for (int i = 0; i < n; ++i) {
if (str[i] != '?') {
pos = i;
break;
}
}
ans[n] = '\0';
if (pos == n) {
for (int i = 0; i < n; ++i) {
ans[i] = i % 2 ? 'B' : 'R';
}
}
else {
ans[pos] = str[pos];
for (int i = pos - 1; i >= 0; --i) {
if (str[i] == '?') {
ans[i] = 'B' + 'R' - ans[i + 1];
}
else {
ans[i] = str[i];
}
}
for (int i = pos + 1; i < n; ++i) {
if (str[i] == '?') {
ans[i] = 'B' + 'R' - ans[i - 1];
}
else {
ans[i] = str[i];
}
}
}
printf("%s\n", ans);
}
}
}
ac;
题目5
题目链接
题目大意：
从n个整数的数组中，找到(i, j) 要求 l ≤ a[i]+a[j] ≤ r，问有多少(i, j)符合要求；
输入：
第一行是整数t，表示有t个样例 (1≤𝑡≤10000 ).
每个样例第一行是整数𝑛,𝑙,𝑟 (1≤𝑛≤2⋅1e5, 1≤𝑙≤𝑟≤1e9)
第二行是n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤109).
输出：
(𝑖,𝑗)的数量，要求是 (𝑖<𝑗) 并且 𝑙≤𝑎𝑖+𝑎𝑗≤𝑟.
Examples
input
4
3 4 7
5 1 2
5 5 8
5 1 2 4 3
4 100 1000
1 1 1 1
5 9 13
2 5 5 1 1
output
yes
2
7
0
1
题目解析：
题目要求的是任意a[i]和a[j]，那么数组的顺序没有意义，可以直接将数组进行排序；
如果不考虑复杂度，我们可以枚举pair(i, j)是否满足要求，这样复杂度是N*N；
由于排序完之后，数组是有序的，我们在枚举pair(i, j)的时候，可以采用下面的策略：
从小到大枚举i，假设已经先取了数字a[i]并且i<j，要求是找到l<=a[i]+a[j]<=r，那么就是在区间[i+1, n]里面找到l-a[i]作为起点，r-a[i]作为终点的区间；
我们可以采用二分查找来，也可以使用快捷方法lower_bound。
class Solution {
static const int N = 200010;
public:
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, l, r;
cin >> n >> l >> r;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
lld sum = 0;
for (int i = 0; i + 1 < n; ++i) {
int left = l - a[i];
int right = r - a[i] + 1;
// 从i+1开始，找到第一个大于等于left的数字作为起点x
int x = lower_bound(a + i + 1, a + n, left) - a;
if (x >= n) {
continue;;
}
// 新x开始，找到第一个大于right的数字作为终点y
int y = lower_bound(a + x, a + n, right) - a;
sum += y - x;
}
cout << sum << endl;
}
}
}
ac;
