[Week 21] 每日一题（C++，数学，二分，字符串，STL）-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Week 21] 每日一题（C++，数学，二分，字符串，STL）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

T1 [Daimayuan] 一半相等（C++，数学）
- - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据规模
  - 解题思路
T2 [Daimayuan] 兔纸（C++，二分）
- - 题目背景
  - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 附加说明
  - 解题思路
T3 [Daimayuan] 添加括号（C++，数学）
- - 输入格式
  - 输出格式
  - 数据范围
  - 输入样例
  - 输出样例
  - 解题思路
T4 [Daimayuan] 贪就是了（C++，BFS）
- - 题目描述
  - 输入描述
  - 输出描述
  - 样例输入1
  - 样例输出1
  - 样例输入2
  - 样例输出2
  - 数据范围
  - 解题思路
T5 [Daimayuan] 算的我头都大啦（C++，数学）
- - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 解题思路
T6 [Daimayuan] 全部相等（C++，数学）
- - 数据规模
  - 输入格式
  - 输出格式
  - 样例 1 输入
  - 样例 1 输出
  - 样例 2 输入
  - 样例 2 输出
  - 样例 3 输入
  - 样例 3 输出
  - 解题思路
T7 [Daimayuan] 分段求和（C++，二分）
- - 输入格式
  - 数据范围
  - 输出格式
  - 输入样例
  - 输出样例
  - 解题思路
T8 [Daimayuan] nice party（C++，二分，贪心）
- - 输入描述
  - 输出描述
  - 样例输入
  - 样例输出
  - 解题思路
T9 [Daimayuan] Gene（C++，字符串）
- - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 样例说明
  - 数据范围
  - 解题思路
T10 [Daimayuan] 赢救瓜瓜（C++，字符串哈希）
- - 题目描述
  - 输入描述
  - 输出描述
  - 样例输入
  - 样例输出
  - 说明
  - 解题思路

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

样例输出

数据规模

$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≤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$

输入样例

输出样例

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,m)= \begin{cases} f(g(x,m-1)),\quad m>1 \\[1ex] f(x), \quad m=1 \end{cases} \]

比如$g(x,2)=f(f(x))$ 现在，要你求出 $∑^m_{i=1}{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代码如下：文章来源地址https://www.toymoban.com/news/detail-486074.html

#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 输出

解释：

[1,3,2,1,4,2] 满足条件且最长。

样例 2 输入

4
100 100 4 100

样例 2 输出

样例 3 输入

8
1 2 3 3 3 2 6 6

样例 3 输出

解题思路

根据题意，我们有这样一种直觉：

所选择的公共词频过低的时候，会有很多元素，但是每个元素出现的次数很少；

所选择的公共词频过高的时候，会有很少的元素，但是每个元素出现的次数很多。

类似于下面这个简单的函数：

\[y=-x^2 \]

所以我们知道答案在区间的中间位置，但是应该如何搜索？

因为答案不具有单调性，所以不能二分搜索。

所以我们直接~~放弃思考~~开始爆搜。

在统计词频过程中，由于取值范围过大，使用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

输出样例

解题思路

没有一套标准的算法用于此题，只能进行搜索。

暴力搜索直接$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所能邀请的最多的人的人数

样例输入

样例输出

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∗10^3$的字符串，字符串仅包含大小写字母与数字。数据保证$∑|string|≤5∗10^3$

输出描述

每一组输出一个整数，代表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;
}

到了这里，关于[Week 21] 每日一题（C++，数学，二分，字符串，STL）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！