[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 x2 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,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_{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

解题思路

根据题意,我们有这样一种直觉:

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

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

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

\[ 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

输出样例

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,切割位置在 GA 之间。(本题只考虑 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;
}

热门相关:亿万盛宠只为你   豪门重生盛世闲女   高级娼女   朕是红颜祸水   横行霸道