今晚 CF ABC1D 题解
2026-02-24 01:10:10
发布于：广东
13阅读
0回复
0点赞
这是啥子比赛？
A
Difficulty：3- / Easy
Tag：-
注意到每次移动会使 的值 ，所以只能跳到 是 的倍数的格子。然后特判一下边界即可。
namespace cjdst{
void solve(){
int x, y;
std::cin >> x >> y;
if(y * 2 > x || -y * 4 > x || (x + y) % 3) std::cout << "NO\n";
else std::cout << "YES\n";
}
}
时间复杂度：。
B
Difficulty：3.2 / Easy+
Tag：可行性 DP
除了某道神秘抓人以外让我最汗流浃背的 B。
注意到所有情况可以归类为这 种状态：
- 左右两边均为 。
- 左右两边一个为 一个为 。
- 左右两边均为 。
将这三个状态分别记作 ，则有：
相当于所有的 条边。
然后就可以 DP 了。
namespace cjdst{
void solve(){
int n;
std::string a;
std::cin >> n >> a;
a = " " + a + " ";
std::bitset <3> cur;// 0: aa 1: ab 2: bb
cur.set(~n & 1);
for(int i = 1; i <= n; i++){
std::bitset <3> tmp;
if(a[i] == 'a'){
tmp = cur << 1;
}else if(a[i] == 'b'){
tmp = cur >> 1;
}else{
tmp[0] = tmp[2] = cur[1];
tmp[1] = cur[0] | cur[2];
}
if(!tmp.count()){
std::cout << "NO\n";
return;
}
if(i == n){
if((a[i] == 'A' && !cur[0]) || (a[i] == 'B' && !cur[2])){
std::cout << "NO\n";
return;
}
}
cur = tmp;
}
std::cout << "YES\n";
}
}
时间复杂度：。
C1
Difficulty：3- / Easy
Tag：-
根据题意随便模拟即可。其实是不好讲
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];
}
int ans = n, l = -1, r = -1;
for(int i = 2; i <= n; i++){
if(a[i] == a[i - 1] + 1){
ans--;
if(l == -1) l = r = a[i];
else r = a[i];
}else{
if(l != -1 && l <= a[i] && a[i] <= r){
ans--, r = a[i];
}else l = r = -1;
}
}
std::cout << ans << '\n';
}
}
时间复杂度：。
C2
Difficulty：4.2 / (Easy+ / Medium)
Tag：？？？
不会。
D
Difficulty：3.2 / Easy
Tag：构造
世界上真的有这么简单的 D 吗？
首先求下界。显然是 吧，两两恰好配对就行。
然后求上界。
显然有一种方法，对于所有情况都不优于题目给的贪心：先两两翻，得到整副牌。然后两两配对。花费 次。
然后注意到如果得到了前 张牌，后 张牌一定可以知道并且直接配对，又可以省一次。所以最坏情况不超过 。
然后构造。
显然这种方法可以达到上界：
因为这会多 次无效翻牌。
然后我们使前 个数这么弄，后面的两两配对即可。
做完了。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
int val = m - n + 1;
if(val <= 0 || val > n){
std::cout << "NO\n";
return;
}
if(val == 1){
std::cout << "YES\n";
for(int i = 1; i <= n; i++){
std::cout << i << ' ' << i << ' ';
}
std::cout << '\n';
return;
}
std::cout << "YES\n";
std::cout << "1 2 ";
for(int i = 2; i < val; i++){
std::cout << i + 1 << ' ' << i - 1 << ' ';
}
std::cout << val - 1 << ' ' << val << ' ';
for(int i = val + 1; i <= n; i++){
std::cout << i << ' ' << i << ' ';
}
std::cout << '\n';
}
}
时间复杂度：。
有帮助，赞一个