锐评

C题卡了半小时就去打牛客小白月赛了，所以加起来只做了半小时，C题并不难，只不过自己想的太复杂了。

交题点：星码StarryCoding 入门教育赛 5

A. a+b（easy）

题目描述

给定一个形式为 𝑎 + 𝑏 的表达式，其中 𝑎 和 𝑏 是 0 到 9 的一个整数，您需要对其进行求值并打印结果。

输入格式

第一行包含一个整数 𝑇 ( 1 ≤ 𝑇 ≤ 1000)，表示测试样例组数。
接下来 𝑇 行每行一个表达式。

输出格式

为每个表达式求值并打印结果。

输入样例

4
4+2
0+0
3+7
8+9

输出样例

思路：

输入的是字符串格式的公式，a 和 b 都是一位数，因次可以直接提取下标 0 和 2 的值就是 a 和 b。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n;

void solve() {
	string s;
	cin >> s;
	int a = s[0] - '0', b = s[2] - '0';
	cout << a + b << "\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

B. a+b（hard）

题目描述

本题为𝐴的ℎ𝑎𝑟𝑑版本，与𝑒𝑎𝑠𝑦版本的唯一区别在于𝑎和𝑏的范围不同。
给定一个形式为𝑎 + 𝑏 (0 ≤ 𝑎, 𝑏 ≤ 10¹⁴)的表达式，您需要对其进行求值并打印结果。

输入格式

第一行包含一个整数𝑇(1 ≤ 𝑇 ≤ 1000)，表示测试样例组数。
接下来𝑇T行每行一个表达式。

输出格式

为每个表达式求值并打印结果。

输入样例

test 复制代码

4
4+2
0+0
3+7
8+9

输出样例

test 复制代码

思路：

和A的区别是 a b 不再只是一位数，可能是很多位，因此遍历字符串到计算符号处停止为 a，计算符号后一位到最后为 b。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n;

void solve() {
	string s;
	cin >> s;
	int a = 0, b = 0;
	int index;
	for (int i = 0; i < s.size(); ++ i) {
		if (s[i] >= '0' && s[i] <= '9') {

			a *= 10;
			a += (s[i] - '0');
		}else {
			index = i;
			break;
		}
		
	}
	for (int i = index + 1; i < s.size(); ++ i) {
		b *= 10;
		b += (s[i] - '0');
	}
	cout << a + b << "\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

C. 最近不存在数字

题目描述

给定长度为 𝑛 的数组 𝑎 和一个整数 𝑏。

要求找出一个整数 𝑥 满足：

𝑥 ∉ 𝑎，即𝑥不存在于数组𝑎中。
∣𝑏−𝑥∣最小。

若有多个 𝑥 满足条件，取较小的 𝑥 作为答案。

输入格式

注意：本题有多组测试样例！

第一行一个整数 𝑇 表示测试用例个数。(1 ≤ 𝑇 ≤ 10)

对于每组测试用例：

一行两个整数 𝑛, 𝑏(1≤𝑛≤10⁵,1≤𝑏≤10⁹)。

第二行𝑛n个整数表示𝑎_𝑖( 1 ≤𝑎_𝑖≤ 10⁹ )。

数据保证：∑𝑛≤2×10⁵

输出格式

对于每组测试用例，输出一个整数表示答案。

输入样例1

输出样例1

5
5

思路：

卡了我半天的题，刚开始想的先二分找到里 b 最近的，然后再往前往后找看那一个数空缺了，中间的过程太麻烦，而且也有错误，这样不一定满足∣𝑏−𝑥∣最小。

其实只要讲数组放到一个能 find 的结构里面就可以了，然后从 b 开始一个一个的向两边去找

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n, b;

void solve() {
	cin >> n >> b;
	set<int> a;
	for (int i = 1; i <= n; ++ i) {
		int x; cin >> x;
		a.insert(x);
	}
	for (int i = 0; i <= 1e5; ++ i) {
		if (a.find(b - i) == a.end()) {
			cout << b - i << "\n";
			return;
		}
		if (a.find(b + i) == a.end()) {
			cout << b + i << "\n";
			return;
		}
	}

}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

D. 数字根

题目描述

非负整数的数字根是通过不断迭代对数字的每一位求和，直到得出一个一位数为止，这个一位数就是它的数字根。例如5的数字根是5，而38的数字根是2，求解过程如下：38→3+8=11→1+1=238→3+8=11→1+1=2。
现在阿慧得到了一个作业，要求找出第𝑘k个数字根为𝑥x的数字，但是她不会，所以请教了你来帮她解决这个麻烦。

输入描述

第一行一个整数𝑇(1 ≤ 𝑇 ≤ 1000)，表示测试样例组数。
接下来𝑇T行，每行两个整数𝑘, 𝑥( 1 ≤ 𝑘 ≤ 10¹², 1 ≤ 𝑥 ≤ 9)。

输出描述

为每个测试样例打印一个整数，表示第𝑘k个数字根为𝑥x的整数。

输入样例

输出样例

5
38
19

思路

挺唬人的一道题，实际上特别特别简单，就是数字跟的那个数加上 9 的倍数构成其他的数，所以我们找第 k 个数就是找相差 k - 1 个 9 的数。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int k, n;

void solve() {
	cin >> k >> n ;
	cout << n + 9 * (k - 1) << "\n";

}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

E. 再短一点

题目描述

当一个长度为 𝑚 的二进制字符串𝑇是幸运的，我们可以通过任意顺序执行以下两种操作𝑚−1来获得长度为1的字符串:

选择 𝑇 中任意等于 01 的子字符串，将其替换为 1。
选择 𝑇 中任何等于 10 的子字符串，然后将其替换为 0。

例如，如果 𝑇 = 001，我们可以选择子字符串 [𝑇2 𝑇3] 并执行第一个操作。得到 𝑇 = 01。

您将得到一个长度为 𝑛 的二进制字符串 𝑆，索引从 1 到 𝑛。找出 (𝑙, 𝑟) (1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛) 使得 𝑆[𝑙…𝑟] (𝑆 从 𝑙 到 𝑟 的子字符串)是一个幸运的字符串的整数对的个数。

输入描述

第一行包含一个整数 𝑡 (1 ≤ 𝑡 ≤ 1000)—测试用例的数量。下面是测试用例的描述。

每个测试用例的第一行包含一个整数 𝑛( 1 ≤ 𝑛 ≤ 2⋅10⁵)——大小为𝑆。

每个测试用例的第二行包含一个由 𝑛 字符 𝑆1 𝑆2 … 𝑆𝑛组成的二进制字符串𝑆。(每个1 ≤ 𝑖 ≤ 𝑛 对应 𝑆𝑖 = 0 或 𝑆𝑖 = 1)

保证所有测试用例的 𝑛 之和不超过 2⋅10⁵。

输出描述

对于每个测试用例，输出使 𝑆[𝑙 … 𝑟](𝑆从𝑙到𝑟的子字符串)为幸运字符串的整数对 (𝑙, 𝑟) 1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛 的个数。

输入样例1

输出样例1

样例解释

在第一个示例中，𝑆已经具有长度1，不需要任何操作。

在第二个示例中，𝑆的所有子字符串都是幸运的。对于整个字符串，执行第一个操作就足够了。

在第三个示例中，除了[𝑆2𝑆3]之外，𝑆的所有子字符串都是幸运的，因为我们不能对它和[𝑆1𝑆2𝑆3](整个字符串)执行任何操作。

思路

这道题需要思考一下，看看有多少个子区间是幸运的，实际上模拟一下就知道，其实取决于最后两个字符是否相同，因为两个不同的字符会变成右边的字符，因此如果最右边的两个字符相同，那么这个区间的整数对数就和去掉最右边的端点的区间的整数对数相同，否则加上前面所有左端点的数量。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int  n;

void solve() {
	cin >> n ;
	string s; cin >> s;
	int ans = n;
	for (int i = 1; i < n; ++ i) 
		if (s[i] != s[i - 1]) ans += i;
	cout << ans << "\n"; 

}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}