我校和同层次学校算法集训队 2024 OneWan Camp 系列文章

2024 OneWan Camp-chapter 3 A - Maximum Substring

题面

来自：CODEFORCES B. Maximum Substring

image-20240128030540143

Example

Input

6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0

Output

9
12
16
12
9
1

image-20240128030555507

初版代码

#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned int u_int;
u_int n,sub_n,max_n,tmp,len;
char cache[200001];

u_int calcSub(u_int l,u_int r){
	int x = 0,y = 0; // x,y
	for(;l<=r;l++){
		if(cache[l] == '0') x++;
		else y++;
	}
	
	if(x > 0){
		if(y > 0) return x*y;
		if(y == 0) return x*x;
	}else if(y > 0) return y*y;
}

int main(){
	scanf("%d",&n);
	for(u_int i=0;i<n;i++){
		scanf("%d",&sub_n);
		scanf("%s",cache);
		len = strlen(cache);
		
		for(u_int j=0;j<len;j++){
			for(u_int k=j;k<len;k++){
				tmp = calcSub(j,k);
				if(max_n < tmp) max_n = tmp;
			}
		}
		
		printf("%d\n",max_n);
		max_n = 0;
	}
	return 0;
}

但是评测结果是：Time limit exceeded on test 5

# Author Problem Lang Verdict Time Memory Sent Judged
243667292 Practice: HenryZeng 1750B- 29 GNU C++17 Time limit exceeded on test 5 1000 ms 204 KB 2024-01-27 21:56:32 2024-01-27 21:56:38 Add to favourites

真的扎心了......

问题分析

我的初代解法是纯模拟解题，可能造成效率低下的点有：

  • cost 计算用了大量的 if ... else ... 而且不在循环中使用，计算机无法有效进行分支预测。
  • 基于枚举的思路本质是暴力做法， n^2 级别的时间复杂度太高。

救赎之道

要解决时间复杂度的问题，就要摈弃暴力解法。

题目中计算cost的方法是基于一个规则表，分类讨论后进行计算。

不妨先分类讨论，研究是否存在易于推出的二级结论，从而把尝试行为转变成求最优解的行为。

回看题目：

image-20240128032941339

已知，x 是 0 的数量，y 是 1 的数量。不难看出：

  • x 或 y 等于 0 的时候，子串越长，cost 越大。
  • x 或 y 不等于 0 时，子串等于输入字符串时，存在 cost 最大的情况。

存在 cost 最大的情况下，要比较最长连续字串得到的 cost 和 输入串 x*y 的大小。

这样，分别求出对应情况的max值即可。

另外，重新看题目数据范围的限制，会发现 int 不足以存储 cost 的最大值（不难理解， (2 x 10^5)^2 ）

修改代码

从样板代码里面学到了不少东西。

#include <iostream>
using namespace std;

void solve(){
	// 变量前置声明
	// 避免中途创建，影响自己理解代码
	int n;
	int count;              // 连续字符计数
	int x = 0;              // 字符 0 计数
	int y = 0;              // 字符 0 计数
	int max_n = 0;          // 最长连续串的长度
	string str;
	char last_c = 0;        // 前一个字符 记录
	
	cin >> n >> str;
	
	for(auto c : str){
		// 统计 0,1
		if(c == '0') x++;
		else y++;
		
		if(last_c == 0) {
			last_c = c;
			count = 1; // 已经探测到一个字符
			continue;
		}
		
		if(c == last_c){
			count++; // 增加连续字符计数
			if(max_n < count) max_n = count;
		}else count = 1; // 第一个相异字符出现也是一种探测：已经探测到一个连续字符
		
		last_c = c;
	}
	
	if(x == 0 || y == 0) cout << 1LL * n * n;
	else cout << max(1LL * max_n * max_n,1LL * x * y);
	cout << endl;
}

int main(){
	// Fast IO
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	
	cin >> n;
	
	while(n--){
		// 利用函数调用解决变量后效性的问题
		// 使用后销毁，不用手动维护状态
		solve(); 
	}
	
	return 0;
}

经验复盘

Fast IO

// Fast IO
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

快速读写 (Fast IO) 1

std::ios::sync_with_stdio(0);

详细资料:2

作用：设置在每次输入/输出操作之后，标准C++流是否与标准C流同步。

在实践中，这意味着同步的C++流是无缓冲的，并且对C++流的每个I/O操作都立即应用于相应的C流的缓冲区。这使得可以自由地混合C++和C I/O。

此外，同步的C++流保证是线程安全的（从多个线程输出的单个字符可以交错，但不会发生数据争用）。

如果关闭同步，则允许C++标准流独立地缓冲它们的I/O，在某些情况下这可能会快得多。

默认情况下，所有八个标准C++流都与它们各自的C流同步。

标准 C++ 流有这些： std::cin, std::cout, std::cerr, std::clog, std::wcin, std::wcout, std::wcerr, std::wclog

标准 C 流有这些：stdin, stdout , stderr

如果关闭同步，混用 C++ 流和 C 流的函数会变得不安全，同时使用 scanf 和 std::cout 或同时使用 printf 和std::cin 会出现不可预知的错误。不过，同时使用 scanf 和 std::cin 或同时使用 printf 和 std::cout 不会有问题。

std::tie()

tie 是将两个 stream 绑定的函数，空参数的话返回当前的输出流指针。

在默认的情况下 std::cin 绑定的是 std::cout，每次执行 << 操作符的时候都要调用 flush() 来清理 stream buffer，这样会增加 IO 负担。可以通过 std::cin.tie(0)（0 表示 NULL）来解除 std::cin 与 std::cout 的绑定，进一步加快执行效率。

副作用：

因为解除了绑定，程序中必须手动 flush 才能确保每次 std::cout 展现的内容可以在 std::cin 前出现。

摘自1 (怎么处理副作用的代码在参考资料里面放出了)

不依赖 for 循环的读入器

cin >> n;

while(n--){
	// 利用函数调用解决变量后效性的问题
	// 使用后销毁，不用手动维护状态
	solve(); 
}

在后续不需要变量 n 的情况下，利用表达式特性，结合 while 循环就可以完成多次读入操作。

如果每个读入部分互不干扰（例如本题），可以使用一个 solve() 函数来处理每个部分的输入。

函数里面创建的临时变量即用即弃，不用手动设置后续状态。

提前声明变量 和 赋值

// 变量前置声明
// 避免中途创建，影响自己理解代码
int n;
int count;              // 连续字符计数
int x = 0;              // 字符 0 计数
int y = 0;              // 字符 0 计数
int max_n = 0;          // 最长连续串的长度
string str;
char last_c = 0;        // 前一个字符 记录

变量前置声明可以避免中途创建，影响自己理解代码。

因为函数中的变量不是在外侧定义变量时的默认静态变量，不会默认拥有初始值，所以不赋值会导致计算结果异常。

（上面的 x,y 因为第一次改的时候没有赋值，调试了很久才发现结果异常的原因）

模板：优秀的感知扫描器

for(auto c : str){
	// 统计 0,1
	if(c == '0') x++;
	else y++;
	
	if(last_c == 0) {
		last_c = c;
		count = 1; // 已经探测到一个字符
		continue;
	}
	
	if(c == last_c){
		count++; // 增加连续字符计数
		if(max_n < count) max_n = count;
	}else count = 1; // 第一个相异字符出现也是一种探测：已经探测到一个连续字符
	
	last_c = c;
}

存储上一个字符，拥有感知能力。但是写的时候有好几个容易出错的地方，需要搞清楚各种变量更新的时机。

用这个题目举例子，分析模式如下：

扫描一遍输入串，统计 0 和 1

  • 用到的变量：x，y
  • 更新时机：每次获取新字符时

所以放在扫描器的最前面

扫描过程更新存储的上一次字符的状态

  • 用到的变量：last_c
  • 更新时机：
    • 读入第一个字符的时候：存储第一个值，同时跳过后续过程（因为一个字符无法实现感知，要开展感知需要再读入一个字符）。
    • 一遍扫描结束时

所以代码结构如下：

string str;
char last_c = 0; // 标记为未初始化状态

cin >> str;

for(auto c : str){
	... // 预处理代码
        
	if(last_c == 0) {
		last_c = c;
		... // 其他需要初始化的代码
		continue;
	}
	
	... // 工作代码
	
	last_c = c;
}

特别需要注意，最后面的更新代码 last_c = c; 特别容易被忘记。

样板代码

#include <bits/stdc++.h>
using namespace std;

// 2023 OneWan

void solve() {
    int n;
    cin >> n;
    string str;
    cin >> str;
    int ans = 0;
    // 目前连续 0/1 的数量
    int now_cnt0 = 0, now_cnt1 = 0;
    // 总共 0/1 的数量
    int all_cnt0 = 0, all_cnt1 = 0;
    for (auto &i : str) {
        if (i == '0') {
            // 如果当前字符为 0，那么目前连续 1 的数量一定为 0， 连续 0 的数量一定自增1。
            now_cnt0++;
            now_cnt1 = 0;
            all_cnt0++;
        } else {
            // 如果当前字符为 1，那么目前连续 0 的数量一定为 0， 连续 1 的数量一定自增1。
            now_cnt0 = 0;
            now_cnt1++;
            all_cnt1++;
        }
        // 目前的 ans 是最长连续 0/1 的长度
        // max({}) 是 c++11 语法
        ans = max({ans, now_cnt0, now_cnt1});
    }
    cout << max(1LL * ans * ans, 1LL * all_cnt0 * all_cnt1) << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

参考文献

  1. 读入、输出优化 ↩ ↩

  2. std::ios_base::sync_with_stdio ↩