今晚 CF A-D1 题解
2026-01-18 01:49:10
发布于：广东
37阅读
0回复
0点赞
赛时写的，所以是今晚。
谁懂 18min 切 ABC 1h 切 D1 然后 1h 坐牢无果放弃的救赎感。
A
题意解析：给定一个 的排列 。你需要将它染色，使它满足：
- 对于所有 ， 颜色与 颜色不同。
- 将 从小到大排序，每个数颜色不变，然后依然满足对于所有 ， 颜色与 颜色不同。
你需要判断是否存在一种合理的染色方法是上面两个条件成立。
注意到染色方法只有一种。所以暴力判断即可。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <pii> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i].first;
a[i].second = i % 2;
}
std::sort(a.begin() + 1, a.begin() + n + 1);
for(int i = 2; i <= n; i++){
if(a[i].second == a[i - 1].second){
std::cout << "NO\n";
return;
}
}
std::cout << "YES\n";
}
}
时间复杂度：。
B
题意解析：给定一个长度为 的数组 。你需要重排 ，使它满足：
- 对于所有 ， 的 与 的 不同。
请你判断是否存在。
显然有个贪心做法：将所有的 都放在后面，其他放在前面。
分类讨论一下会发现满足 。
- 如果两个的 都为 的话，则 中没有 ，显然无论如何重排都不行。
- 如果两个的 都为 的话，则 至少有两个 且没有 ，此时将 任意重排：
定义数组 ，满足 。显然如果 ，则 ，否则 。
显然无论如何重排，都存在 。
所以这个贪心是正确的。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
std::sort(a.begin() + 1, a.begin() + n + 1, cmp);
std::vector <int> bucket(n + 5);
std::vector <int> pre(n + 5), suf(n + 5);
for(int i = 1; i <= n; i++){
bucket[a[i]]++;
pre[i] = pre[i - 1];
while(bucket[pre[i]]) pre[i]++;
}
for(int i = 1; i <= n; i++){
bucket[i] = 0;
}
for(int i = n; i; i--){
bucket[a[i]]++;
suf[i] = suf[i + 1];
while(bucket[suf[i]]) suf[i]++;
}
for(int i = 1; i < n; i++){
if(pre[i] == suf[i + 1]){
std::cout << "NO\n";
return;
}
}
std::cout << "YES\n";
}
}
时间复杂度：。
C
题意解析：Alice 和 Bob 在玩一个游戏。给定一个 串 。他们会轮流对 进行操作：
- 选定几个数 ，使得对于任意 ，。
- 通过对 交换使得对于任意 ，。
谁先让 升序谁就赢了。
问谁会获胜，若 Alice 获胜输出先手操作。
我们可以画图模拟。
会发现有若干个“峰”（两边为 中间为 的块）和若干个“谷”（两边为 中间为 的块）。我们只需要把这几个“峰”和“谷”消掉就行了。
模拟一下，发现把前面的“峰”和后面的“谷”选了就能一次性全消掉了。
双指针解决。
namespace cjdst{
void solve(){
int n;
std::string a;
std::cin >> n >> a;
a = " " + a + " ";
std::vector <int> ans;
int l = 1, r = n;
while(l <= r){
while(l <= r && a[l] == '0') l++;
while(l <= r && a[r] == '1') r--;
if(l > r) break;
ans.push_back(l), ans.push_back(r);
l++, r--;
}
if(!ans.size()){
std::cout << "Bob\n";
return;
}
std::sort(ans.begin(), ans.end());
std::cout << "Alice\n" << ans.size() << '\n';
for(int i:ans){
std::cout << i << ' ';
}
std::cout << '\n';
}
}
时间复杂度：。
D1
时间主要花在对拍上了。
题意解析：定义一个括号串 “优于”另一个括号串 如下：
- 是 的前缀且 ，或
- 存在一个整数 满足对于所有 满足 ，且 。
给定一个匹配的括号串 ，请你求出所有优于 且为 的子匹配括号串中，长度最大值。
考虑贪心。
显然第一个条件没用。
我们可以枚举 在哪里，使保证：
- 前面的全选。
- 为 ，然后答案选一个 。
- 后面的在能与前面的匹配的情况下，能选多少选多少。
显然后面的所有 尽量与前面多的 匹配；如果还有多的，那就可以和后面的 匹配。
所以我们只需要处理出：
- 后面的 和 个数。
- 后面第一个 的下标。
然后就解决了。
namespace cjdst{
void solve(){
int n;
std::string a;
std::cin >> n >> a;
a = " " + a + " ";
std::vector <int> suf(n + 5), suf2(n + 5), nxt(n + 5);
for(int i = n; i; i--){
suf[i] = suf[i + 1] + (a[i] == '(');
suf2[i] = suf2[i + 1] + (a[i] == ')');
}
for(int i = n; i; i--){
if(a[i + 1] == '(') nxt[i] = i + 1;
else nxt[i] = nxt[i + 1];
}
int cur = 0, ans = -1;
for(int i = 1; i < n; i++){
if(a[i] == '('){
cur++;
}else{
if(suf[i + 1] && suf2[nxt[i] + 1] >= cur + 1){
ans = std::max(ans, i + (cur + 1) + std::min(suf[nxt[i] + 1], suf2[nxt[i] + 1] - (cur + 1)) * 2);
}
cur--;
}
}
std::cout << ans << '\n';
}
}
时间复杂度：。
有帮助，赞一个