[Week 21] 每日一题(C++,数学,二分,字符串,STL)
[TOC]
T1 [Daimayuan] 一半相等(C++,数学)
给定 \(n\) (\(n\) 为偶数)个整数数组 \(a_1,a_2,…,a_n\)
考虑这样的一个 \(k\),每次操作选定一个 \(i\),将 \(a_i\) 减少 \(k\),执行多次(可能 \(0\) 次)后使得数组中至少有一半的元素相等,求最大的 \(k\),如果这样的 \(k\) 为无穷大,输出 \(−1\)
输入格式
输入包含两行,第一行为一个正整数 \(n\),表示数组大小。第二行为 \(n\) 个整数 \(a_1,a_2,…,a_n\)
输出格式
输出题意中的 \(k\)
样例输入
8
-1 0 1 -1 0 1 -1 0
样例输出
2
数据规模
\(4≤n≤100\),数据保证 \(n\) 为偶数
\(−10^6≤a_i≤10^6\)
解题思路
既然有一半的元素能够在相同的$k$的作用下达到相等即达到一个共同的值。
那么这一半的元素到这个共同值的距离可以被$k$整除,而要求$k$尽可能的大,故类似于最大公约数。
(当数组中已经有就有一半的元素相等,那么可以直接输出$-1$。)
但是我们要求哪一半元素?又是要求到谁的距离呢?
(注意是距离,也就是差值的绝对值,因为转化是双向的,如$1-2=-1,-1-(-2)=1$)
因为存在这样一种情形:一半的元素到$x$的距离的gcd
,大于到$y$的距离的gcd
。
例如:$2,5$到$0$的距离的最大公约数是$1$,而到$-1$的距离的最大公约数是$3$。
所以选择的目标位置会对最终的结果产生影响。
但是我们可以证明目标位置一定在给定的数组中:
直观起见,以下面这个数组为例,应该选择的一半元素是$2,5,8,8$。
2 5 3 3 8 8
对此,我们可以选择$-1$作为目标位置,拿到最大公约数$3$。
但是我们同样也可以选择$2$作为目标位置,拿到最大公约数$3$。
我们想不出一种比较好的算法来解决以上的两个问题,所以采用暴力搜索(毕竟$n\le100$):
1)尝试将每一个数作为目标位置;
2)计算其他所有数到目标位置的距离;
3)求出距离的所有的因子并统计其出现的频率;
4)保留最大的因子。
最后,AC代码如下:
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
const int max_n = 100;
int arr[max_n];
map<int, int>freqs;
void division(int x) {
int i;
for (i = 1; i * i < x; i++) {
if (x % i == 0) {
freqs[i]++;
freqs[x / i]++;
}
}
if (i * i == x) freqs[i]++;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
const int temp = arr[i];
int cnt = 0;
for (int j = 0; j < n; j++) {
if (temp == arr[j]) cnt++;
else division(abs(temp - arr[j]));
}
if (cnt >= n / 2) {
cout << -1 << endl;
return 0;
}
for (auto iter : freqs)
if (iter.second + cnt >= n / 2)
ans = max(ans, iter.first);
freqs.clear();
}
cout << ans << endl;
return 0;
}
T2 [Daimayuan] 兔纸(C++,二分)
题目背景
鶸尛鱻养了许多兔纸。
题目描述
众所周知,兔纸是一种神奇的生物,它有许多种毛色。
鶸尛鱻一共有 \(n\) 只兔纸,它们从左到右排成一排,第 \(i\) 只兔纸的毛色为 \(col_i\)。
兔纸们十分活跃,时常会与旁边的兔纸交换位置。
五颜六色的兔纸弄得鶸尛鱻眼花缭乱,他想统计区间 \([l,r]\) 内兔纸的颜色,但他的数学很差,你可以帮帮他吗?
输入格式
第 \(1\) 行两个正整数 \(n,m\) 分别表示兔纸数量和操作次数。
第 \(2\) 行 \(n\) 个正整数 \(col_1,col_2,…,col_n\),表示初始状态下从左到右每只兔纸的颜色。
此后 \(m\) 行,每行输入格式为 1 x
或 2 l r c
,其中 \(\{1/2\}\) 表示操作类型。
操作 \(1\) 为 交换 操作,表示第 \(x\) 只兔纸和第 \(x+1\) 只兔纸交换位置。
操作 \(2\) 为 查询 操作,询问当前区间 $[l,r] $内有多少只颜色为 \(c\) 的兔纸。
输出格式
对于每个操作 \(2\),你需要输出一行一个自然数作为答案。
样例输入
7 9
8 7 6 6 7 8 3
1 5
1 4
2 1 7 7
1 6
1 4
2 3 6 8
2 1 3 7
2 1 2 6
2 2 5 7
样例输出
2
1
1
0
1
数据范围
对于全部测试数据,满足 \(2≤n≤3×10^5\),\(1≤m,col_i,c≤3×10^5\),且保证 \(1≤x<n\),\(1≤l<r≤n\)。
附加说明
原题:P3939 数颜色
解题思路
最开始看到题目描述的时候,第一反应是用可持久化线段树来实现。
但是还有另外一种更简单快速的方法:二分(lower_bound()
和upper_bound()
)。
这里只介绍代码的逻辑(因为算法比较emm神奇,很难说怎么想出来的):
采用vector
容器,为每一种颜色维护一个容器。
每一个容器中维护着所有该种颜色兔纸的位置。
这样每一只兔纸都有两个标识:1)在队列中的位置;2)在容器中的索引。
交换操作就是将兔纸$x$位置++
,将兔纸$x+1$位置--
。
如果要交换的两个兔纸位置相同则不进行任何操作,这样可以保证vector
容器中的元素始终具有单调性。
查询操作是整个算法最巧妙的地方:
使用lower_bound()
和upper_bound()
获取指定范围$[l,r]$内最左边兔纸的索引和最右边兔纸的索引。
两个索引的差值$+1$即为答案。
最后,AC代码如下:
#include <iostream>
#include <vector>
using namespace std;
const int max_n = 3e5;
const int max_c = 3e5;
int rabbits[max_n + 1];
vector<int>pos[max_c + 1];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> rabbits[i];
pos[rabbits[i]].push_back(i);
}
int select, x, l, r, c;
while (m--) {
cin >> select;
if (select == 1) {
cin >> x;
if (rabbits[x] == rabbits[x + 1]) continue;
int col_1 = rabbits[x], col_2 = rabbits[x + 1];
swap(rabbits[x], rabbits[x + 1]);
int ret_1 = lower_bound(pos[col_1].begin(), pos[col_1].end(), x) - pos[col_1].begin();
pos[col_1][ret_1]++;
int ret_2 = lower_bound(pos[col_2].begin(), pos[col_2].end(), x + 1) - pos[col_2].begin();
pos[col_2][ret_2]--;
}
else {
cin >> l >> r >> c;
int ret_1 = lower_bound(pos[c].begin(), pos[c].end(), l) - pos[c].begin();
int ret_2 = upper_bound(pos[c].begin(), pos[c].end(), r) - pos[c].begin() - 1;
if (ret_1 > ret_2) cout << 0 << endl;
else cout << ret_2 - ret_1 + 1 << endl;
}
}
return 0;
}
T3 [Daimayuan] 添加括号(C++,数学)
现在给出一个表达式,形如 \(a_1/a_2/a_3/.../a_n\)。
如果直接计算,就是一个个除过去,比如 \(1/2/1/4=1/8\)。
然而小 \(A\) 看到一个分数感觉很不舒服,希望通过添加一些括号使其变成一个整数。一种可行的办法是 \((1/2)/(1/4)=2\)。
现在给出这个表达式,求问是否可以通过添加一些括号改变运算顺序使其成为一个整数。
输入格式
一个测试点中会有多个表达式。
第一行 \(t\) ,表示表达式数量。
对于每个表达式,第一行是 \(n\),第二行 \(n\) 个数,第 \(i\) 个数表示 \(a_i\)
输出格式
输出 \(t\) 行。
对于每个表达式,如果可以通过添加括号改变顺序使其变成整数,那么输出 \(Yes\),否则输出 \(No\)。
数据范围
\(2≤n≤10000\),\(1≤t≤100\),\(1≤a_i≤2^{31}−1\)
输入样例
2
4
1 2 1 4
5
6 5 7 9 12
输出样例
Yes
No
解题思路
通过不同的加括号方法,可以发现以下几个规律:
(1)第一个数必定是分子;
(2)第二个数必然是分母;
(3)从第三个数开始,任意数都可以成为分子,且互不影响。
同时,很容易知道:分子越多,分母越少,越容易形成整数。
那么我们的算法实现就很简单了:用其他所有数的乘积去尝试整除第二个数。
最后,AC代码如下:
#include <iostream>
using namespace std;
int main() {
int t, n;
long long a1, a2, sum;
bool flag;
cin >> t;
for (int i = 0; i < t; i++) {
cin >> n;
a1 = a2 = -1;
sum = 1;
flag = false;
for (int i = 0; i < n; i++) {
if (i == 1) {
cin >> a2;
}
else {
cin >> a1;
sum *= a1;
}
if (a2 != -1) {
sum %= a2;
if (sum == 0) {
flag = true;
}
}
}
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
T4 [Daimayuan] 贪就是了(C++,BFS)
题目描述
给你一个序列 \(a\),我们定义
\(S_{(l,r)}=∑_{i=l}^{i=r}{a_i}\)
显然易见我们会有$n∗(n+1)/2$个不同的$S_{(l,r)}$,请你输出其中前 $k$大的$S_{(l,r)}$
输入描述
第一行输入两个整数 \(n,k\) 第二行输入 $n$个整数代表序列 \(a\)
输出描述
输出一行包含 $k$个整数代表答案
样例输入1
6 8
1 1 4 5 1 4
样例输出1
16 15 14 12 11 11 10 10
样例输入2
7 8
1 9 1 9 8 1 0
样例输出2
29 29 28 28 28 27 20 19
数据范围
\(0≤a_i≤10^9,1≤n≤10^5,1≤k≤min(10^5,n∗(n+1)/2)\)
解题思路
根据题目,好像应该采用贪心算法,所以我们先来尝试一下。
对于序列1 2 100 3 100 4 5 6
,我们尝试找出最大的$k$个数:
第一大的是$sum=221$毫无疑问;
第二大的是$sum-1=220$;
第三大的是$sum-1-2=218$;
第四大的是$sum-6=215$,它并没有在第三大的基础上继续更新;
第五大的是$sum-1-2-6=212$,它并没有再次减去新的元素;
模拟到这里我们应该发现了,并没有贪心算法可以采用,我们只能搜索每一种可能的情况,然后找出top_k
。
这里采用bfs
的算法:
void bfs() {
//初始化
while () {//终止条件
//bfs主体
}
}
然后我们来实现具体的bfs
代码。
首先明确bfs
的功能是搜索并输出top_k
:
void bfs(int k) {
//初始化
while (k--) {//终止条件
//bfs主体
}
}
尝试每一种可能的情况,实际上就是尝试每一个区间$[l,r]$。
为了快速找出top_k
,我们采用优先队列维护已搜索到的结果。
我们将区间$[l,r]$加和用作比较的键值key
。
priority_queue<pair<pair<int, int>, int>>pq;//默认大根堆
void bfs(int k) {
//初始化
pq.push({{ arr[n],1 },n })
int sum, l, r;
while (k--) {//终止条件
//bfs主体
sum = pq.top().first.first;
l = pq.top().first.second;
r = pq.top().second;
pq.pop();
cout << sum << ' ';
...
}
}
最后是最重要的部分,每一步需要做什么:
1)尝试区间$[l+1,r]$;
2)尝试区间$[l,r-1]$。
priority_queue<pair<pair<int, int>, int>>pq;//默认大根堆
void bfs(int k) {
//初始化
pq.push({{ arr[n],1 },n })
int sum, l, r;
while (k--) {//终止条件
//bfs主体
sum = pq.top().first.first;
l = pq.top().first.second;
r = pq.top().second;
pq.pop();
cout << sum << ' ';
pq.push({{ arr[r]-arr[l],l+1 },r });
pq.push({{ arr[r-1]-arr[l-1],l },r-1 });
}
}
但是这样会产生对同一区间的重复搜索,所以我们加上一个去重判断。
priority_queue<pair<pair<int, int>, int>>pq;//默认大根堆
void bfs(int k) {
//初始化
pq.push({{ arr[n],1 },n })
int sum, l, r;
while (k--) {//终止条件
//bfs主体
sum = pq.top().first.first;
l = pq.top().first.second;
r = pq.top().second;
pq.pop();
cout << sum << ' ';
pq.push({{ arr[r]-arr[l],l+1 },r });
if (l == 1) pq.push({{ arr[r-1]-arr[l-1],l },r-1 });
}
}
最后,AC代码如下:
#include <iostream>
#include <queue>
using namespace std;
const int max_n = 1e5;
priority_queue<pair<pair<long long, int>, int>>pq;//默认大根堆
long long arr[max_n + 1], n;
void bfs(int k) {
//初始化
pq.push({ { arr[n],1 },n });
long long sum, l, r;
while (k--) {//终止条件
//bfs主体
sum = pq.top().first.first;
l = pq.top().first.second;
r = pq.top().second;
pq.pop();
cout << sum << ' ';
pq.push({ { arr[r] - arr[l],l + 1 },r });
if (l == 1) pq.push({ { arr[r - 1] - arr[l - 1],l },r - 1 });
}
}
int main() {
int k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
arr[i] += arr[i - 1];
}
bfs(k);
return 0;
}
可能会有人对为什么能直接输出pq.top().first.first
以及if (l == 1)
有疑问,所以在最后的最后做一下解释:
在每一轮bfs
,我们首先取出队首,然后在此基础上尝试两种不同的缩短区间方法。
区间缩短,所以新的结果一定小于队首,可以保证直接输出的结果是我们想要的结果。
但是新的结果仍然可能大于其他旧的结果,所以我们简单的采用if (l == 1)
的去重方式是否过于草率?
试着假设我们没有尝试的区间$[l,r-1]$之和大于其他旧的结果。
我们已知两个条件:1)这个区间会被重复搜索;2)新的结果一定小于队首。
很容易推出已知条件与假设矛盾,所以没有被尝试的区间不会对结果正确性产生影响。
T5 [Daimayuan] 算的我头都大啦(C++,数学)
爱数学的小明又回来辣!看了上次大家解决问题的方法后觉得自己实在是太笨了,同时引来了同是数学爱好者的小红的嘲笑,自尊心极强的小明气不过,便和小红打个赌,让小红出一道数学题给小明写,如果小明能在一周内写出来,小红就请他吃下个星期的疯狂星期四,如果做不出来就要小明请她疯狂星期四。
但是这道题实在是太难啦,小明把自己关在房间里想了一周也没能想出来,明天就是赌约的截止日期了,小明非常想吃KFC,于是他想到了再次向你求助,并承诺只要帮他写出这道题就把小红请的KFC分你一半。
小红设立了两个函数 $f(x)$和$g(x,m)$ ,$f(x)$的定义如下:
\(f(x)=∏_{i=1}^{x的位数}{(x\ mod\ 10^i)}\ mod\ (x+1)\)
比如:\(f(2013)=(2013∗13∗13∗3)\ mod\ 2014\)
$g(x,m)$的定义如下:
比如$g(x,2)=f(f(x))$ 现在,要你求出 $∑^m_{g(x,i)}$的值。
为了KFC,拼了!
输入格式
第一行有一个数$T$ (\(1≤T≤20\)),代表一共有$T$组数据。 接下来$T$行有两个数$x,m$(\(1≤x,m≤10^9\)),代表$g(x,m)$的两个参数
输出格式
对于每行测试例输出一个数字。
样例输入
2
3 4
4102 642
样例输出
12
21262
解题思路
把题中所述的函数实现出来,直接模拟过程即可。
AC代码如下:
#include <iostream>
using namespace std;
long long f(long long x) {
long long sum = 1, t = 1;
do {
t *= 10;
sum = (sum * (x % t)) % (x + 1);
} while (x % t != x);
return sum;
}
long long g(long long x, long long m) {
if (m > 1) return f(g(x, m - 1));
else return f(x);
}
int main() {
long long t, x, m, sum, last;
cin >> t;
while (t--) {
cin >> x >> m;
sum = 0; last = x;
for (int i = 1; i <= m; i++) {
last = f(last);//唯一一个需要优化的地方,缓存上次计算结果,防止重复计算
sum += last;
}
cout << sum << endl;
}
return 0;
}
T6 [Daimayuan] 全部相等(C++,数学)
* 注:题名的灵感来自 代码源 #914: 一半相等
给定长度为 \(n\) 的数组 \({A}\)。
派派非常喜欢 所有元素出现频率相同 的数组,但这样的数组却不常有。派派很伤心 (;´༎ຶД༎ຶ`)。不过聪明的你,发现总能从 \({A}\) 中挑选一个子序列满足上述条件。问此子序列最长为多长?
数据规模
- \(1≤n≤2×10^5\)
- \(A_i∈[1,10^9]\)
输入格式
输入包含两行,第一行有一个整数 \(n\),表示 \({A}\) 的大小。
接下来一行包含 \(n\) 个用空格分隔的整数,依次表示 \(A_1,A_2,⋯,A_n\)。
输出格式
输出答案。
样例 1 输入
6
1 3 2 1 4 2
样例 1 输出
4
解释:
[1,3,2,1,4,2] 满足条件且最长。
样例 2 输入
4
100 100 4 100
样例 2 输出
3
样例 3 输入
8
1 2 3 3 3 2 6 6
样例 3 输出
6
解题思路
根据题意,我们有这样一种直觉:
所选择的公共词频过低的时候,会有很多元素,但是每个元素出现的次数很少;
所选择的公共词频过高的时候,会有很少的元素,但是每个元素出现的次数很多。
类似于下面这个简单的函数:
所以我们知道答案在区间的中间位置,但是应该如何搜索?
因为答案不具有单调性,所以不能二分搜索。
所以我们直接放弃思考开始爆搜。
在统计词频过程中,由于取值范围过大,使用map
容器进行离散化。
然后将数据转移到vector
容器中进行排序,方便后续操作。
最后是本题的关键,搜索代码部分:
while (temp_freq) {
while (iter != arr.end() && temp_freq <= iter->first) {
cnt++;
iter++;
}
ans = max(ans, temp_freq * cnt);//每次统计结束后更新答案(ans=所选词频*元素数量)
temp_freq--;
}
对于每一个键值对,我们以词频作为键值,然后根据键值降序排序。
从高频开始尝试,这样可以不断拓展元素的数量,而不是每次都要重新计算。
AC代码如下:
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
const int max_n = 2e5;
const int max_a = 1e9;
int n;
map<int, int>freq;
vector<pair<int, int>>arr;
int main() {
cin >> n;
int temp;
for (int i = 0; i < n; i++) {
cin >> temp;
freq[temp]++;
}
for (auto iter : freq) arr.push_back({iter.second,iter.first});
sort(arr.begin(), arr.end(), [](pair<int, int>p1, pair<int, int>p2) {
return p1.first > p2.first;
});
int temp_freq = arr.begin()->first, cnt = 0;
int ans = 0;
vector<pair<int, int>>::iterator iter = arr.begin();
while (temp_freq) {
while (iter != arr.end() && temp_freq <= iter->first) {
cnt++;
iter++;
}
ans = max(ans, temp_freq * cnt);
temp_freq--;
}
cout << ans << endl;
return 0;
}
T7 [Daimayuan] 分段求和(C++,二分)
对于给定的一个长度为 \(N\) 的正整数数列 \(A_{1−N}\),现要将其分成 \(M(M≤N)\) 段,并要求每段连续,且每段和的最大值最小。
关于最大值最小:
例如一数列 \(4,2,4,5,1\) 要分成 \(3\) 段。
将其如下分段:\([4,2][4,5][1]\)。 第一段和为 \(6\),第 \(2\) 段和为 \(9\),第 \(3\) 段和为 \(1\),和最大值为 \(9\)。
将其如下分段:\([4][2,4][5,1]\)。第一段和为 \(4\),第 \(2\) 段和为 \(6\),第 \(3\) 段和为 \(6\),和最大值为 \(6\)。
并且无论如何分段,最大值不会小于 \(6\)。
所以可以得到要将数列 \(4,2,4,5,1\) 要分成 \(3\) 段,每段和的最大值最小为 \(6\)。
输入格式
第 \(1\) 行包含两个正整数 \(N,M\)。
第 \(2\) 行包含 \(N\) 个空格隔开的非负整数 \(A_i\),含义如题目所述。
数据范围
\(1≤N≤10^5,M≤N,A_i≤10^8\)
输出格式
一个正整数,即每段和最大值最小为多少。
输入样例
5 3
4 2 4 5 1
输出样例
6
解题思路
没有一套标准的算法用于此题,只能进行搜索。
暴力搜索直接$T$飞,考虑到题中要求是最小的最大值,所以采用二分搜索法。
二分答案:限制分段和的最大值越小,分段越多;反之,分段越少。
判断函数如下:
bool judge(long long x) {
int l = 0, cnt = 0;
for (int r = 1; r <= n; r++) {
if (arr[r] - arr[l] > x) {
l = r - 1;
cnt++;
}
}
return ++cnt <= m;//分段数越多,越容易符合题中要求的分段数
}
不断拓展区间,区间和小于上限则继续,大于上限则累计分段数,然后进行下个区间的计算。
二分主体如下:
long long bin_search() {
long long l = max_num - 1, r = arr[n] + 1, mid;
while (l + 1 != r) {
mid = l + r >> 1;
if (judge(mid)) r = mid;
else l = mid;
}
return r;//符合题意的最小限制值
}
通过l = nax_num - 1
来限制每段中至少含有一个元素,$[0,l]\(是不符合题意的限制值,\)[r,arr[n]]$是符合题意的限制值。
最后,AC代码如下:
#include <iostream>
using namespace std;
const int max_n = 1e5;
const int max_a = 1e8;
const int max_m = max_n;
long long arr[max_n + 1], max_num = 0;
int n, m;
bool judge(long long x) {
int l = 0, cnt = 0;
for (int r = 1; r <= n; r++) {
if (arr[r] - arr[l] > x) {
l = r - 1;
cnt++;
}
}
return ++cnt <= m;
}
long long bin_search() {
long long l = max_num - 1, r = arr[n] + 1, mid;
while (l + 1 != r) {
mid = l + r >> 1;
if (judge(mid)) r = mid;
else l = mid;
}
return r;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
max_num = max(max_num, arr[i]);
arr[i] += arr[i - 1];//数组前缀和
}
cout << bin_search() << endl;
return 0;
}
T8 [Daimayuan] nice party(C++,二分,贪心)
cc准备举办一场派对,他希望邀请他的朋友们过来参加,并且每个人都能玩得开心
cc有 \(n\) 位朋友,第 \(i\) 位的身价为 \(i\)
如果第 \(i\) 位朋友参加派对,并且玩得开心,当且仅当派对上至多有 \(X_i\) 个人比他身价严格大于他,至多有 \(Y_i\) 个人身价严格小于他
cc想知道,他最多能邀请来多少人,并且他们每个人都玩得开心
输入描述
第 \(1\) 行给出一个数 \(T\) ,表示有 \(T\),(\(1≤T≤10^4\)) 组数据
对于每一组数据
第 \(1\) 行给出一个数 \(n\),(\(1≤∑n≤2×10^5\)),表示有 \(n\) 个朋友
接下来 \(n\) 行,每一行给出两个数 \(X_i\),\(Y_i\),(\(0≤X_i,Y_i<n\))
输出描述
输出一个数,表示cc所能邀请的最多的人的人数
样例输入
3
3
1 2
2 1
1 1
2
0 0
0 1
2
1 0
0 1
样例输出
2
1
2
解题思路
根据题意,我们有这样一种直觉:
所想邀请的人数越多,越不容易成功;
所想邀请的人数越少,越容易成功。
所以我们采用二分搜索:
int bin_search() {
int l = 0, r = n + 1, mid;
while (l + 1 != r) {
mid = l + r >> 1;
if (judge(mid)) l = mid;
else r = mid;
}
return l;
}
但是如何judge(mid)
是否符合题意呢?
考虑一种通常的情况:
我们遍历每一个人,现在遍历到第i
个。
对于他,我们已知其前面已选择了cnt
个人。
1)如果这个人不能来参加聚会,那么就简单跳过即可;
2)如果这个人能够参加聚会,且mid
是符合题意的,那么在其之后至少还会再选择mid-cnt-1
个人。
bool judge(int x) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (cnt <= ys[i] && x - cnt - 1 <= xs[i]) cnt++;
}
return x <= cnt;
}
然后我们来解决两个可能存在的疑问:
1)按照如上的统计方式,我们最后得到的cnt
可能大于x
,这会导致之前判断条件mid-cnt-1
失去意义。
这个问题对结果没有影响,把多余的人删去就可以了。
2)按照如上的贪心算法,我们的统计结果不一定是最大的cnt
,因为可能前面选择的人数过多,导致更多的人不再符合条件cnt <= ys[i]
。
进行贪心证明:
假设存在组合,使得在不选前面cnt
个人的情况下,所选的人数能够变为cnt+k
。
那么根据已知条件,我们选择cnt+k
个人中靠前的cnt
个人,显然把他们替换为之前的cnt
个人后仍然能够符合题意。
所以假设不成立。
最后,AC代码如下:
#include <iostream>
using namespace std;
const int max_n = 2e5;
int xs[max_n + 1], ys[max_n + 1];
int n;
bool judge(int x) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (cnt <= ys[i] && x - cnt - 1 <= xs[i]) cnt++;
}
return x <= cnt;
}
int bin_search() {
int l = 0, r = n + 1, mid;
while (l + 1 != r) {
mid = l + r >> 1;
if (judge(mid)) l = mid;
else r = mid;
}
return l;
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> xs[i] >> ys[i];
cout << bin_search() << endl;
}
return 0;
}
T9 [Daimayuan] Gene(C++,字符串)
题目描述
高中生物中提到,酶切位点 是基因序列上一段特定的碱基序列,而 限制性核酸内切酶 能够识别出这个序列并在对应的切割位置将基因序列切成两段。
现有一种名为 \(EcoRI\) 的限制酶,其识别序列为 GAATTC
,切割位置在 G
和 A
之间。(本题只考虑 5'->3'
单链)
给出一段长度为 \(n\) 的基因序列(仅由 A/T/G/C
组成的字符串),请你判断使用 \(EcoRI\) 在理想条件下能将此序列切成几个部分,并输出每个切割位置 左侧 碱基的下标。
定义该基因序列的下标从左到右分别为 \(1,2,3,…,n\)。
输入格式
第 \(1\) 行一个正整数 \(n\) 表示基因序列长度。
第 \(2\) 行一个长度为 \(n\) 的字符串表示基因序列,保证只出现 A/T/G/C
四种字符。
输出格式
第 \(1\) 行输出一个正整数 \(x\),表示 \(EcoRI\) 在理想条件下能将给出序列切成 \(x\) 个部分。
第 \(2\) 行从小到大输出 \(x−1\) 个正整数,表示每个切割位置 左侧 碱基的下标。
样例输入
15
GATCGGAATTCTTCA
样例输出
2
6
样例说明
显然,对于此样例,容易找到 \(EcoRI\) 的识别序列和切割位点:\(GATCGG↓AATTCTTCA\)。
所以,可以将原基因序列切割成 \(2\) 部分,切割位置左侧碱基 G
的下标为 \(6\)。
数据范围
\(6≤n≤10^7\)
解题思路
利用string
提供的find
方法匹配GAATTC
字符串;
利用vector
存储答案并统计数量。
最后,AC代码如下:
#include <iostream>
#include <vector>
using namespace std;
vector<int>ans;
int main() {
int n;
string str;
cin >> n >> str;
string target = "GAATTC";
int ret = 0;
while (true) {
ret = str.find(target, ret);
if (ret != -1) ans.push_back(ret++);
else break;
}
cout << ans.size() + 1 << endl;
for (auto iter : ans) {
cout << iter + 1 << ' ';
}
return 0;
}
T10 [Daimayuan] 赢救瓜瓜(C++,字符串哈希)
题目描述
瓜瓜特工接到了一个新任务——保护CB直到毕业。 于是瓜瓜就装作实验室的集训队员潜伏在集训队,同时暗中保护CB的安全,并装弱让CB不要对ACM丧失信心。 某天早上,瓜瓜发现CB不在实验室,便打了个电话。 电话接通了,但是电话那头传来了陌生男人的声音。 “CB现在在我们手上,嘿嘿嘿♂ ……”。电话那头说完这句话就挂断了。 “CB!!!”瓜瓜大喊。 冷静下来的瓜瓜,发现了 CB 留下的纸条,上面的答案就是 CB 所在位置(聪明的 CB 自然不可能白白被抓走)。 rbq("wobeihuairenzhuazoulewwwkuailaijiuwoguagua")
这个rbq(string)
之前跟瓜瓜讲过 LSP 库里的一个函数。
这个函数的参数是一个字符串,返回的是 string
中子串的最大循环次数。
CB 为了不让坏人发现,把这个字符串用很多无用的字符填充了起来。但是字符串太长了,瓜瓜根本无法肉眼看出来。
于是瓜瓜找到了你,希望你能写个程序告诉他 CB 所在位置。
输入描述
第一行包含一个整数 \(T\),代表总共有 $T(1≤T≤10^3)$组字符串。
接下来 $T$行,每行包含一个长度小于 $5∗103$的字符串,字符串仅包含大小写字母与数字。数据保证$∑|string|≤5∗103$
输出描述
每一组输出一个整数,代表rbq(str)
样例输入
2
psdababab2345
avabcdad
样例输出
3
1
说明
rbq(psdababab2345)=3
因为子串 ababab
有循环节 ab
,并且循环了 3次,所以答案为 3。
rbq(avabcdad)=1
, 因为任何一个子串都没有循环次数超过 1的循环节,所以答案为 1。
解题思路
思路很容易想到:
三重循环:1)尝试每一种长度;2)尝试每一个起始位置;3)循环匹配。
for (int i = 1; i <= (len + 1 >> 1); i++) {
for (int j = 1; j <= len - i + 1; j++) {
/* 获取子串 */;
int temp = 1, k = j + i;
while (k <= len - i + 1 && /* 循环匹配 */) {
temp++;
k += i;
}
ans = max(ans, temp);
}
}
(没错就是这么简单粗暴,没有高级的算法)
很明显我们需要多次访问字符串,采用正常的方式会产生很大的开销,所以我们采用字符串哈希。
哈希算法就是将一个元素用一个索引来表示,字符串哈希也是如此,将每一个子串用一个索引表示。
这里推荐一篇博客,来自CSDN博主FoLiaGe丶:字符串哈希【算法】(绝对不是因为我懒得写一遍)
AC代码如下:
#include <iostream>
using namespace std;
const unsigned long long base = 13131;
const int max_len = 5e3;
unsigned long long arr[max_len + 1], power[max_len + 1];
unsigned long long get_hash(int l, int r) {
return arr[r] - arr[l - 1] * power[r - l + 1];
}
int main() {
power[0] = 1;
for (int i = 1; i <= max_len; i++) {
power[i] = power[i - 1] * base;
}
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
int len = str.size();
for (int i = 1; i <= len; i++) {
arr[i] = arr[i - 1] * base + (unsigned long long)(str[i - 1]);
}
int ans = 1;
for (int i = 1; i <= (len + 1 >> 1); i++) {
for (int j = 1; j <= len - i + 1; j++) {
unsigned long long hash = get_hash(j, j + i - 1);
int temp = 1, k = j + i;
while (k <= len - i + 1 && hash == get_hash(k, k + i - 1)) {
temp++;
k += i;
}
ans = max(ans, temp);
}
}
cout << ans << endl;
}
return 0;
}