# 牛客周赛87题解（出题人）
A. 小苯的V图
直接按题意判断即可。
void solve() {
int a, b, c;
cin >> a >> b >> c;
if(a > b && b < c) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
B. 小苯的数字切割
做法1：枚举切割的位置，统计所有情况取max。
做法2：实际上我们会发现，最优解一定仅存在于切 或者
，因此我们两种情况取max即可
void solve() {
string s;
cin >> s;
assert(s.size() > 1);
for(auto & c : s) {
assert(c != '0');
}
int n = stoll(s);
n /= 10;
n += (s.back() - '0');
int m = 0;
for(int i = 1; i < s.size(); i++) {
m = (m * 10) + (s[i] - '0');
}
m += (s[0] - '0');
cout << max(n, m) << endl;
}
C. 小苯的Z串匹配
我们会发现，<和> 固定的位置是不能改变的，这启发我们贪心地先模拟将所有 '<' 和 '>' 对应的 都改成对应正负性的数字（可以直接取
和
）。
最后我们再从前往后枚举匹配 'Z'。如果枚举到的地方不匹配，不难发现由于我们不好改变已经确定的 的部分，因此我们直接改
，把它的正负性改为和
一样即可。（这一步直接赋值就最方便。）
void solve() {
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) {
a[i] = -1;
ans++;
}
} else if(s[i] == '>') {
if(a[i] <= 0) {
a[i] = 1;
ans++;
}
}
}
assert(s[1] != 'Z');
for(int i = 2; i <= n; i++) {
if(s[i] == 'Z') {
if(a[i] * a[i - 1] <= 0) {
ans++;
assert(a[i - 1] != 0);
a[i] = a[i - 1]; // 直接继承正负性
}
}
}
cout << ans << endl;
}
D. 小苯的最大和
本题实际上带一些诈骗色彩，想启发同学们去写贪心，因为根据 ”麦乐鸡定理“，所有长度大于 的连续负数段都可以全部删干净，因此最后所有负数段长度都为
，这时可能会有同学去思考一些比较困难的贪心。
然而以上想法是不正确的，本题正解为 。
我们考虑，其实题目中删除一段区间再拼接起来剩下的，再在拼接后的数组上删除，其实等价于在原数组中选择若干个不交的区间 (每个区间的长度都是
或
)并删除。
比如 12345678 先删除 34 变成 125678，再删除 256 变成 178。
实际上等价于选择了 [2,3] 和 [4,5,6] 这两段长度分别为 和
的区间。
因此转化后，我们的问题变成了非常经典的 ，我们考虑如下
：
表示前
个数字中，用以上方法删除区间得到的最大和，则决策有三种：
不删除数字，则
；
删长度为
的区间，则：
；
删长度为
的区间，则：
。
注意后两种转移有 的限制。
void solve() {
int n;
cin >> n;
vector<int> dp(n + 1, -1e18);
dp[0] = 0;
for(int i = 1, x; i <= n; i++) {
cin >> x;
dp[i] = dp[i - 1] + x;;
if(i >= 2) {
dp[i] = max(dp[i], dp[i - 2]);
}
if(i >= 3) {
dp[i] = max(dp[i], dp[i - 3]);
}
}
cout << dp[n] << endl;
}
E. 小苯的数组构造
位运算题我们直接考虑拆位，由于题目限制了需要全正，因此贪心地，我们尽量能给所有数字填就给所有数字填。
考虑一个位上 对应的四种情况：
为
，
为
，这种显然不能填东西，直接跳过。
为
，
为
，碰到这种显然直接无解，因为
当前是
意味着必须所有
都是
，则
就不可能产生
。
为
，
为
，这种我们分
的奇偶性看，如果
是偶数，则我们可以给所有
当前位填
，否则需要跳过一个。
为
，
为
，和
的情况完全对称，只不过反过来变成
是偶数需要跳过。
按上述最贪心的构造方法如果还构造不出答案，则一定无解。
void solve() {
int n, x, y;
cin >> n >> x >> y;
if((x & y) != y) {
cout << "NO" << endl;
return ;
}
int skip = 1;
vector<int> ans(n + 1);
for(int j = 31; j >= 0; j--) {
int a = (x >> j & 1), b = (y >> j & 1);
if(a == 0) continue; // 0 0 不用考虑
int now = (a ^ b) ^ (n & 1);
if(now == 0) {
for(int i = 1; i <= n; i++) {
if(i == skip) continue;
ans[i] |= (1LL << j);
}
skip = min(skip + 1, n);
}
else {
for(int i = 1; i <= n; i++) { // 无脑全塞 1
ans[i] |= (1LL << j);
}
}
}
for(int i = 1; i <= n; i++) {
if(ans[i] <= 0) {
cout << "NO" << endl;
return ;
}
}
int v1 = 0, v2 = 0;
for(int i = 1; i <= n; i++) {
v1 |= ans[i];
v2 ^= ans[i];
}
if(v1 != x || v2 != y) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
for(int i = 1; i <= n; i++) {
cout << ans[i] << " \n"[i == n];
}
}
}
F. 小苯的ovo2.0
一句话题解：
最优解一定是，所有被改成 的问号处于一个连续区间内，区间中不存在改为
的问号。
因此我们直接 枚举所有可能的区间，将区间内的问号改成
，区间外的全改
，再跑一个
的
计数即可求出答案，对所有枚举的答案取
即可。
严格证明比较复杂，大家可以感性地理解成：所有的 都会产生：其左侧
个数
其右侧
个数。的贡献，而
个数固定的情况下，这个贡献可以写成一个凸的二次函数。而对于所有的
产生的贡献之和（也就是答案）实际上就是多个二次函数的加和，其结果依然是凸的二次函数，因此最优的改变方案里不会出现：
子序列这种结构。因此只能是所有
都聚在一堆。
void solve() {
string s;
cin >> s;
int n = s.size();
auto calc = [&](int l, int r) -> int {
string S = s;
for(int i = 0; i < n; i++) {
if(S[i] != '?') continue;
if(i < l || i > r) {
S[i] = 'o';
} else {
S[i] = 'v';
}
}
int o = 0, ov = 0, ovo = 0;
for(auto & c : S) {
if(c == 'o') {
o++;
ovo += ov;
} else {
ov += o;
}
}
return ovo;
};
int ans = 0;
for(int l = 0; l < n; l++) {
for(int r = l - 1; r < n; r++) {
int now = calc(l, r);
ans = max(ans, now);
}
}
cout << ans << endl;
}
查看14道真题和解析
