参考代码放在最后面。
思路
A.小红的双层夹心
按照题意直接比较即可。
B.小红的马卡龙定位
中点公式
可以逐一枚举，也可以移项偷懒，减少代码量
C.小红的奶油蛋糕工坊
通过定义，我们容易得到：修改值连续的 个数字并改成中位数一定不劣。
证明：
由于给出序列是排列，所以每种数只有一个，那么需要修改 个数字。
设相等的数字为 ，则其余数字
改成
所需代价为
，由函数性质可知，最小的值一定在
的两侧，即连续的数字。
一种便于实现的做法就是将 的数字改成其中位数（如果存在两个任取一个即可。）
时间复杂度为 。
D.小红的奇数奶油球
我们倾定 为根，那么我们可以 DFS 求出对应节点的子树大小
。
按照题目定义，一个节点是好的，满足删除 节点后一定满足其子节点
大小都是奇数，此时还剩下父亲节点与节点
形成的子树，其大小为
，判断一下即可。
时间复杂度为 。
E.小红的提拉米苏配方（easy）
由于所有的 1 都要操作到无法操作为止，所以最后只会剩余 个
1，于是可以进行分类讨论。
1的个数是偶数：由于2的字典序最大，所以可以贪心将所有的2全部放到最后面，即变成2的1一定是后者，结果一定不劣。1的个数是奇数：由于存在其中一个1不需要被删除，于是我们选择尽可能靠前的12结构中的1进行保留，若不存在则保留尽可能后的1（但是要在所有变成2的1之前。）
感性理解一下：（下划线为被删除的 1，加粗为变成 2 的 1）
这个过程跑左右端双指针即可完成。
时间复杂度为 。
F.小红的提拉米苏配方 （hard）
和 E 题类似，当存在 12 结构时，不删除一定最优，此时，拓展一下即可得到另一种情况下删除一定更优，即 10 的情况。
因此，我们可以将 1...10 尽可能删除成 0，若后续的 1 数量足够，如果不够就尽可能删。
于是我们可以预处理出每个位置后缀 1 的数量，然后同样跑双指针处理当前 1 组成的连通块 11...11x，然后分类讨论 10 和 12 的情况，尽可能地删 10 的前导 1。
时间复杂度为 。
代码（C++）
A.小红的双层夹心
void solve(){
string s;
cin >> s;
cout << (s[1] == s[2] ? "Yes" : "No") << "\n";
}
B.小红的马卡龙定位
using p32 = std::array<int,2>;
void solve(){
vector<p32> p(4);
i64 sx=0,sy=0;
for (int i = 1;i <= 3;i++){
cin >> p[i][0] >> p[i][1];
sx += p[i][0];
sy += p[i][1];
}
for (int i = 1;i <= 3;i++){
if (sx == p[i][0]*3 && sy == p[i][1]*3){
cout << i << "\n";
return;
}
}
}
C.小红的奶油蛋糕工坊
void solve(){
int n;
cin >> n;
vector<int> a(n+1);
for (int i = 1;i <= n;i++) cin >> a[i];
int tp = (n+1) / 2,goal = (tp+1) / 2;
for (int i = 1;i <= n;i++) {
if (a[i] <= tp) a[i] = goal;
}
for (int i = 1;i <= n;i++) cout << a[i] << " \n"[i==n];
}
D.小红的奇数奶油球
void solve(){
int n;
cin >> n;
vector<vector<int>> G(n+1);
vector<int> size(n+1,1),fa(n+1);
for (int i = 1;i < n;i++){
int u,v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
auto dfs = [&](this auto&& self,int u,int pa)->void {
fa[u] = pa;
for (int v : G[u]){
if (v == pa) continue;
self(v,u);
size[u] += size[v];
}
};
dfs(1,1);
int ans = 0;
for (int u = 1;u <= n;u++){
int add = 1;
for (int v : G[u]){
if (v == fa[u]){
if ((n - size[u]) % 2 == 0) add = 0;
} else {
if (size[v] % 2 == 0) add = 0;
}
}
ans += add;
}
cout << ans << "\n";
}
E.小红的提拉米苏配方（easy）
void solve(){
string s;
cin >> s;
int n = s.size();
vector<int> typ(n),vis(n,1);
int cnt = 0;
for (int i = n-1;i >= 0;i--){
if (s[i] == '1') {
cnt++;
}
}
bool tag = cnt & 1;
for (int l = 0,r = n-1;l < r;l++,r--){
while (l < r && s[l] != '1') l++;
if (tag && l < r && s[l] < s[l+1]){
tag = 0,l++;
while (l < r && s[l] != '1') l++;
}
while (l < r && s[r] != '1') r--;
if (l == r) break;
vis[l] = 0,vis[r] = 2;
}
for (int i = 0;i < n;i++){
if (vis[i] == 1) cout << s[i];
else if (vis[i] == 2) cout << '2';
}
cout << "\n";
}
F.小红的提拉米苏配方 （hard）
void solve(){
string s;
cin >> s;
int n = s.size();
vector<int> vis(n,1),suf(n);
for (int i = n-1;i >= 0;i--){
if (i != n-1) suf[i] = suf[i+1];
if (s[i] == '1') {
suf[i]++;
}
}
int mid = 0,cnt = 0;
for (int l = 0,r = 0;r < n;r++){
if (s[r] != '1') continue;
while (r < n && s[r] == '1'){
r++;
}
if (r >= n || s[r] == '2') continue;
l = r-1;
while (l >= 0 && r < n && s[l] == '1' && cnt + 1 <= suf[r]){
cnt++;
vis[l] = 0;
l--;
}
}
for (int i = n-1;i >= 0;i--){
if (s[i] == '1' && cnt > 0){
cnt--;
vis[i] = 2;
}
}
for (int i = 0;i < n;i++){
if (vis[i] == 1) cout << s[i];
else if (vis[i] == 2) cout << '2';
}
cout << "\n";
}
头文件（模板）
#include<bits/stdc++.h>
#if __has_include("tool/local.hpp")
#include "tool/local.hpp"
#include "grader.hpp"
#else
#define Testcases(T) while(T--) solve();
#ifndef ONLINE_JUDGE
#define listen(...) freopen("data.in","r",stdin),freopen("data.out","w",stdout);
#else
#define listen(...)
#endif
#endif
using namespace std;
// Base type
using ll = long long;
using ld = long double;
using i64 = long long;
using f128 = long double;
using u64 = unsigned long long;
using p32 = std::array<int,2>;
using p64 = std::array<i64,2>;
// mt19937_64 rnd(time(0));
void solve(){
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr),std::cout.tie(nullptr);
listen(_TIMER,_FILE,_CHECKER);
int T = 1;
// std::cin >> T;
Testcases(T);
return 0;
}
End
复建了一下，唐完了。
京公网安备 11010502036488号