声明
此文近为作者个人见解，原题链接：https://ac.nowcoder.com/acm/contest/105623
A.小苯的V图
题目描述
- 小苯有一个由 3 个整数组成的数组 {a₁, a₂, a₃}，他想知道这个数组是否是一个“V图”，请你帮他判断一下吧。
V图定义：
满足以下条件的由 3 个整数组成的数组：
1. a₁ > a₂
2. a₂ < a₃ - 输入描述：输入三个正整数 a1, a2, a3（1 ≤ a1,a2,a3 ≤ 100），用空格分隔。
- 输出描述：如果是V图，输出 "YES"；否则输出 "NO"。
示例
- 输入：3 1 4
输出：YES - 输入：2 2 2
输出：NO
思路
- 语法题，按照要求输入三个数，满足a > b 且 b < c 即可。时间复杂度：O(1)。
代码
void solve()
{
int a , b , c;
cin >> a >> b >> c;
if (a > b && b < c) cout << "YES" << endl;
else cout << "NO" << endl;
}
B.小苯的数字切割
题目描述
- 对于给定的正整数 n，小苯希望将 n 从某个位置切割成两个非空的子串，再将这两个子串表示的数字相加，使得这个和尽可能大。
特别保证：n 中的所有数位均大于 0。 - 输入描述：
每个测试文件均包含多组测试数据。
第一行输入一个整数 T (1 ≤ T ≤ 10^4) 代表数据组数。
接下来每组测试数据输入一个整数 n (11 ≤ n ≤ 10^9)，保证 n 的所有数位不为 0。 - 输出描述：
对于每组测试数据，输出一个整数，表示最大的和。
示例
- 输入：
2
114
23 - 输出：
15
5 - 说明：
对于 114，有两种分法：1+14=15 或 11+4=15，最大和为 15。
对于 23，唯一分法：2+3=5，结果为 5。
思路
- 暴力。列举所有情况，取max即可。时间复杂度：O(n)。
代码
void solve()
{
int t;
cin >> t;
while (t -- )
{
int n;
cin >> n;
int ans = 0;
string s = to_string(n);
for (int i = 1 ; i < s.size() ; i ++ )
{
int temp1 = stoll(s.substr(0 , i));
int temp2 = stoll(s.substr(i));
ans = max(ans , temp1 + temp2);
}
cout << ans << endl;
}
}
C.小苯的Z串匹配
题目描述
- 小苯有一个长度为 n 的数组 a，以及一个长度为 n 的字符串 S（仅由 '<', '>', 'Z' 组成）。
S 用于匹配数组 a，规则如下：- 若 S[i] = '<'，则要求 a[i] < 0；
- 若 S[i] = '>'，则要求 a[i] > 0；
- 若 S[i] = 'Z'（且 i > 1），则要求 a[i-1] × a[i] > 0（即相邻两数同号）。
数组 a 初始可能不满足匹配要求，小苯可以进行修改操作：
- 选择任意 a[i]，将其修改为任意整数 x（-1e9 ≤ x ≤ 1e9）。
求最少需要多少次修改才能使 a 满足 S 的匹配要求。
- 输入描述：
第一行输入 T (1 ≤ T ≤ 100) 表示测试数据组数。
每组数据格式如下：- 第一行：n (1 ≤ n ≤ 2e5)，表示数组和字符串长度；
- 第二行：n 个整数 a[i] (-1e9 ≤ a[i] ≤ 1e9)；
- 第三行：长度为 n 的字符串 S（保证 S[1] ≠ 'Z'）。
（所有测试数据的 n 总和不超过 2e5。）
- 输出描述：
对每组数据，输出一个整数表示最少修改次数。
示例
- 输入：
2
6
-1 4 -6 3 2 -11
Z<>>Z
4
1 1 1 1
ZZ< - 输出：
2
1 - 说明：
对于第一组测试数据：
修改 a1=3a_1=3 和 a6=1a_6=1 即可，因此两次操作即可。
对于第二组测试数据：
修改 a4=−9a_4=-9 即可，一次操作即可。
思路
- 思维题。'<' 和 '>' 处如果不匹配那么必须要修改 而'Z'处要根据前一个字符 保证是同号即可。直接从头到尾依次修改即可。要注意题目所描述不包括0，必须要取等。时间复杂度：O(n)。
代码
void solve()
{
int t;
cin >> t;
while (t -- )
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];
string s;
cin >> s;
s = " " + s;
int ans = 0;
for (int i = 1 ; i <= n ; i ++ )
{
if (s[i] == '<')
{
if (a[i] >= 0) ans ++ , a[i] = -1;
}
if (s[i] == '>')
{
if (a[i] <= 0) ans ++ , a[i] = 1;
}
if (s[i] == 'Z')
{
if (a[i - 1] * a[i] <= 0) ans ++ , a[i] = a[i - 1];
}
}
cout << ans << endl;
}
}
D.小苯的最大和
题目描述
- 小苯有一个长度为 n 的数组 a，但 a 中可能存在一些负数会使得 a 的总和不够大。
现在小苯希望 a 的总和（即：{a₁ + a₂ + ... + aₙ}）尽可能大，为此他可以做如下操作任意次（两种都任意次）：
∙ 选择两个相邻的数字 aᵢ 和 a_{i+1} (1 ≤ i < |a|)，将其删除，其余数字顺次拼接起来。（换句话说操作后 a 数组变为：{a₁, a₂, ..., a_{i-1}, a_{i+2}, ..., aₙ}。）
∙ 选择三个连续的数字 aᵢ, a_{i+1} 和 a_{i+2} (1 ≤ i < |a| - 1)，将其删除，其余数字拼接起来。（换句话说操作后 a 数组变为：{a₁, a₂, ..., a_{i-1}, a_{i+3}, ..., aₙ}。）
以上操作小苯均可执行任意次，他想知道数组 a 的最大总和可以达到多少，请你帮他算一算吧。 - 输入描述：
本题有多组测试数据。
输入的第一行包含一个正整数 T (1 ≤ T ≤ 100)，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行一个正整数 n (1 ≤ n ≤ 2 × 10⁵)，表示数组 a 的初始长度。
第二行 n 个整数 aᵢ (-10⁹ ≤ aᵢ ≤ 10⁹)，表示数组 a。
（保证所有测试数据中，n 的总和不超过 2 × 10⁵。） - 输出描述：
对于每组测试数据：
在单独的一行输出一个整数，表示数组 a 的最大总和。
示例
- 输入：
2
12
1 3 -2 -1 -4 -1 -2 5 -4 15 -10 9
5
1 2 3 4 5 - 输出：
20
15 - 说明：
对于第一组测试数据： 我们首先使用第一种删除 i=3,i=4，此时 a={1,3,-4,-1,-2,5,-4,15,-10,9}。 再使用第二种操作删除 i=2,i=3,i=4，此时 a={1,3,5,-4,15,-10,9}。 接着我们再使用第一种操作删除 i=6,i=7，此时 a={1,3,5,-4,15}。 此时数组 a 的总和等于 20 最大。 可以证明不存在更优的答案。
思路
- 简单的动态规划。分为三种情况：
1.不删，那么第i个位置的总和就是 f[i] = f[i - 1] + a[i];
2.删两个字符(需要满足i >= 2) 比较f[i] 与 f[i - 2] 取max
3.删三个字符(需要满足i >= 3) 比较f[i] 与 f[i - 3] 取max
时间复杂度O(n)。
代码
void solve()
{
int t;
cin >> t;
while (t -- )
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];
vector<int> f(n + 1 , 0);
for (int i = 1 ; i <= n ; i ++ )
{
f[i] = f[i - 1] + a[i];
if (i >= 2) f[i] = max(f[i], f[i-2]);
if (i >= 3) f[i] = max(f[i], f[i-3]);
}
cout << f[n] << endl;
}
}
F.小苯的ovo2.0
题目描述
- 小苯平时很喜欢使用"颜文字"："ovo"来表达惊讶。
这天他在键盘上输入了若干 'o', 'v' 和 '?' 字符，字符们组成了一个字符串 S。他想将 S 中所有的 '?' 都改成 'o' 或者 'v' 中的一种，以最大化 "ovo" 子序列（不一定连续）的个数。请你帮他算算，"ovo" 子序列的个数最多可以达到多少。 - 输入描述：
每个测试文件包含多组测试数据。
第一行输入一个正整数 T (1 ≤ T ≤ 100)，表示数据组数。
接下来包含 T 组数据，每组数据格式如下：
第一行一个字符串 S (1 ≤ |S| ≤ 500)，由 'o', 'v', '?' 三种字符构成。
（保证同一个测试文件中所有测试数据的 |S| 总和不超过 500。） - 输出描述：
对于每组测试数据：
输出一行一个整数，表示 "ovo" 子序列的最多个数。
示例
- 输入：
2
ov??ovoov
????? - 输出：
16
4 - 说明：
第一组：修改为 "ovovovoov" 可得16个"ovo"
第二组：修改为 "oovoo" 可得4个"ovo"
思路
- 暴力枚举。寻找"ovo" 子串，那么'v' 一定时在中间，'o'在两边。历遍所有中间的 '?' 为 'v' 而两边的'?' 为 'o'的情况，计算当前位置前、后缀数组存'o'的数量，那么每一个'v' 都会贡献一个 fronto * backo 。枚举所有的状态的所有的可能的值，找到其中最大值即答案。时间复杂度O(n³)
代码
void solve()
{
int t;
cin >> t;
while (t -- )
{
string s;
cin >> s;
int n = s.size();
s = " " + s;
int ans = 0;
for (int i = 1 ; i <= n ; i ++ )
{
for (int j = i ; j <= n ; j ++ )
{
string temp = s;
for (int k = 1 ; k <= n ; k ++ )
{
if (s[k] != '?') continue;
if (k < i || k > j) temp[k] = 'o';
else temp[k] = 'v';
}
vector<int> frontArr(n + 2 , 0) , backArr(n + 2 , 0);
for (int k = 1 ; k <= n ; k ++ )
{
if (temp[k] == 'o') frontArr[k] = frontArr[k -1] + 1;
else frontArr[k] = frontArr[k - 1];
}
for (int k = n ; k >= 1 ; k -- )
{
if (temp[k] == 'o') backArr[k] = backArr[k + 1] + 1;
else backArr[k] = backArr[k + 1];
}
int tempAns = 0;
for (int k = 2 ; k < n ; k ++ )
{
if (temp[k] == 'v')
tempAns += frontArr[k] * backArr[k];
}
ans = max(ans , tempAns);
}
}
cout << ans << endl;
}
}
Comments NOTHING