Codeforces Round 1082 (Div. 2)-CF-1082 赛后总结（这个D呀，是真简单啊，后悔没看啊，在C2上花太多时间） · znzryb
## 基本情况
更新一下，虽然说其实我用小号打的其实也无所谓的，但是这个 D 还是不多评价，太简单了。当然了，也没有简单到说5分钟就能做出来了，但是我确实应该用了多久啊？我可以看一眼。应该是用了不到半个小时，还不是特别急吼拉轰的情况下，就做出来了这个赛事，估计半小时以内，肯定是能搞定的。这个实在是，不多评价了这个 D 哎呀。。
[https://codeforces.com/contest/2202](https://codeforces.com/contest/2202)
做出来4道题目啊，div2 做出来4道题目还是比较满意的。
应该是 C1 WA 了一发，其实也总结不出来什么，因为 C1 Wrong answer 的地方比较隐蔽。对拍也要拍100多组，得用数据生成器设置的比较好，输出比较长，也要拍100多组才能拍出错的地方，所以还是比较隐蔽的，总的来说也总结不出什么东西来。那么Wrong awnser on test three, 所以它并不是wrong answer on test two，而实测test two应该也是一个比较强的，不是很水，就是一个两个点，其实还是有一个，它是多策，还是比较强的。
下面来看一看，就是每道题目的解法，以及解题的过程和思路，我稍微总结一下。
A题的题目意思是有各种跑酷的移动方式，只有3种，不难发现这3种移动方式，如果你想要实现平动，**那么平动必须是3的倍数**，所以需要%3一下，看是不是3的倍数，然后注意排除一下负数情况。那么，至于你想问我怎么知道平动需要多少呢？实际上平动需要多少呢？就是向上动一定附带了平动吧，因为我们向上动都是加1+一或者是减1-1，他没有什么疑问啊，所以说这个把这个向上动的附带平动给减掉以后，它不能是一个负数然后剩下的这个值，我们去执行一下上面的一个这个检查
::: A 源代码
```cpp
/**
* Problem: A. Parkour Design
* Contest: Codeforces Round 1082 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2202/problem/A
* Created: 2026-02-23 22:35:28
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll X,Y;
cin>>X>>Y;
if (X<2) {
cout<<"NO\n";
return;
}
if (Y>0) {
X-=Y*2;
// if (X<2) {
// cout<<"NO\n";
// return;
// }
if (X<0) {
cout<<"NO\n";
return;
}
if (X%3==0) {
cout<<"YES\n";
return;
}
cout<<"NO\n";
return;
}else if (Y<0) {
X-=abs(Y)*4;
if (X<0) {
cout<<"NO\n";
return;
}
// if (X<2) {
// cout<<"NO\n";
// return;
// }
if (X%3==0) {
cout<<"YES\n";
return;
}
cout<<"NO\n";
return;
}else {
if (X%3==0) {
cout<<"YES\n";
return;
}
cout<<"NO\n";
return;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
1
2 10
*/
```
:::
那么这个B题我们采用的是贪心做法，首先我们会发现，如果双端队列的两端都和SI相同，那么无论操作哪一端无所谓的，因为它们都是对称的，然后剩下就是对于问号的处理。
问号的处理是这样的，我们维护一个问号。我们希望处理这个问号以后，不要对后面的处理，造成这个困难或各种问题，我们知道后面一个不是问号的字符是什么，后面一个我们一旦知道不是问号的字符，然后**我们就不要去动那个和后面一个不是问号的字符相同的端**就行了。
::: B 源代码
```cpp
/**
* Problem: B. ABAB Construction
* Contest: Codeforces Round 1082 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2202/problem/B
* Created: 2026-02-23 23:07:38
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N;
cin >> N;
string s;
cin>>s;
deque<char> deque_s;
// string t;
for (int i=0;i<N;++i) {
if (i%2==0) {
deque_s.push_back('a');
// t.push_back('a');
}else {
deque_s.push_back('b');
// t.push_back('b');
}
}
// ll cntb=count(all(s),'b');
// ll cnta=count(all(s),'a');
queue<char> sq;
for (int i=0;i<N;++i) {
if (s[i]=='?') {
continue;
}
sq.push(s[i]);
}
ll idx=0;
while (!deque_s.empty()) {
if (s[idx]=='?') {
if (deque_s.front()!=sq.front()) {
deque_s.pop_front();
}else if (deque_s.back()!=sq.front()) {
deque_s.pop_back();
}else {
deque_s.pop_front();
}
}else {
if (deque_s.front()==s[idx]) {
deque_s.pop_front();
}else if (deque_s.back()==s[idx]) {
deque_s.pop_back();
}else {
cout<<"NO\n";
return;
}
sq.pop();
}
++idx;
}
cout<<"YES\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
*/
```
:::
这个C1，其实是贪心啊，C1 的题目意思是问你能用最少的A中的元素生成整个A数组，用题目当中的这种向后插入其+1的方式。
那么我们的思路其实并不复杂，我们就是一开始想的就是维护类似于 123456 这样子的连续递增块吗。
```cpp
1
9
9 8 9 2 3 4 4 5 3
_______________[ Stress test, testcase 117 INPUT ]_______________
1
9
2 3 4 3 5 2 2 3 3
_______________[ Stress test, testcase 117 OUTPUT]_______________
3
[-] FAILURE: WRONG ANSWER
```
然后我们发现，题目中的最后一个样例比较强。你会发现234453，它也是一个联通的块，所以说这个，它并不是说一定要是单调不降或者是递增。于是，非常自然，我们可以维护一个该数组或该段落，**它可以接受的所有的接在其后面的值**。我们的这个代码当中使用了vector套，vector的这个 g vector去维护。
通过这个对拍，我们会发现能够跟在它后面的值会随它变化，比如234453，这个时候你想在3后面再加一个5是不可以的，但前面如果是是23445，然后再加一个5，没有问题，所以它会随着后面缩小以后，它这个我们所维护的，能够接受所有的接在其后面的值的这个序列，它也会发生变化。
这个具体的变化逻辑是使用lower bound实现的，具体就看代码吧。
::: C1 源代码
```cpp
/**
* Problem: C1. Lost Civilization (Easy Version)
* Contest: Codeforces Round 1082 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2202/problem/C1
* Created: 2026-02-23 23:14:51
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N;
cin >> N;
vector<ll> A(N+2);
for (int i=1;i<=N;++i) {
cin>>A[i];
}
vector<vector<ll>> g;
for (int i=1;i<=N;++i) {
if (g.empty()) {
g.push_back({A[i]+1});
continue;
}
if (binary_search(all(g.back()),A[i]) ) {
if (A[i]==g.back().back()) {
g.back().push_back(A[i]+1);
}else {
g.back().resize(lower_bound(all(g.back()),A[i]+1) -g.back().begin()+1);
}
}else {
g.push_back({A[i]+1});
}
}
cout<<SZ(g)<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
1
9
9 8 9 2 3 4 4 5 3
_______________[ Stress test, testcase 117 INPUT ]_______________
1
9
2 3 4 3 5 2 2 3 3
_______________[ Stress test, testcase 117 OUTPUT]_______________
3
[-] FAILURE: WRONG ANSWER
*/
```
:::
C2前面我感觉难度还是有一点，所以没花太大力气，时间也比较多，比较随意。主要是喝水，看看视频，再看C2，这个C2总体上来说还是比较顺利的，C2就是在这个C1的基础上，要求你求出全部的它的子段的的这个和。
具体来讲呢，如果说你把这个C1看作一个 solve 函数，那么C2所需要求的值就是这样子的。这个其实就是我们的C，R的暴力程序，虽然其实没有用上。
```cpp
void Solve() {
ll N;
cin >> N;
vector<ll> A(N+2);
for (int i=1;i<=N;++i) {
cin>>A[i];
}
ll ans=0;
for (int l=1;l<=N;++l) {
for (int r=l;r<=N;++r) {
vector<ll> sub(A.begin()+l,A.begin()+r+1);
sub.insert(sub.begin(),0);
ans+=solve(sub,r-l+1);
}
}
cout<<ans<<"\n";
}
```
实际上是这样子的，去求C2，你要**采用贡献**的方法，采用算贡献的方法。我们维护了一个A的值，首先，我们便利到癌的时候，我们就要计算包含这个I，以I为结尾的，所有的**以这个I为结尾的子串子数组会贡献多少答案**？
那么这个代码中的A，你可以理解为什么？所有以前的点在I之前的点，如果包含了I以后会增加多少？因为包含了I这个点以后，就是I能在多少个他前面的点当中进行贡献，就是如果说是和是包含了同段的一些值的话，那么实际上它是没法贡献的。所以说，一个正常的不是子负数开始值，实际上只会贡献一个答案。如果你是子数组的开始值，那么，就会贡献下标为I的答案。那么，如果说你是会去缩小这个区间长度的话，你缩小区间长度的话，你对A的，你对这个答案的贡献就是你的下标减去减去it的下标，减去那个it ID的下标。
```cpp
// 我想要在这里处理的时候，直接把这个块内部的答案给解决掉
for (int i=1;i<=N;++i) {
if (g.empty()) {
g.push_back({{A[i]+1,i}});
// g_id.push_back({i});
ans++;
add++;
continue;
}
if (is_find(A[i])/*binary_search(all(g.back()),A[i])*/ ) {
if (A[i]==g.back().back().val) {
g.back().push_back({A[i]+1,i});
// g_id.back().push_back(i);
add++;
ans+=add;
}else {
auto it=lower_bound(all(g.back()),(Val_id){A[i]+1,0});
add+=(i-it->id+1);
ll new_size=it-g.back().begin()+1;
g.back().resize(new_size);
// g_id.back().push_back(i);
ans+=add;
}
// g_id.back().push_back(i);
}else {
g.push_back({{A[i]+1,i}});
// g_id.push_back({i});
add+=i;
ans+=add;
}
}
```
::: C2 源代码
```cpp
/**
* Problem: C2. Lost Civilization (Hard Version)
* Contest: Codeforces Round 1082 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2202/problem/C2
* Created: 2026-02-24 00:05:49
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct Val_id {
ll val,id;
bool operator<(const Val_id &o) const {
if (val!=o.val) return val<o.val;
return id<o.id;
}
};
void Solve() {
ll N;
cin >> N;
vector<ll> A(N+2);
for (int i=1;i<=N;++i) {
cin>>A[i];
}
vector<vector<Val_id>> g/*,g_id*/;
ll ans=0;
ll add=0;
auto is_find=[&](ll val) -> bool {
auto it=lower_bound(all(g.back()),(Val_id){val,0});
if (it==g.back().end()) {
return false;
}
return it->val==val;
};
// 我想要在这里处理的时候，直接把这个块内部的答案给解决掉
for (int i=1;i<=N;++i) {
if (g.empty()) {
g.push_back({{A[i]+1,i}});
// g_id.push_back({i});
ans++;
add++;
continue;
}
if (is_find(A[i])/*binary_search(all(g.back()),A[i])*/ ) {
if (A[i]==g.back().back().val) {
g.back().push_back({A[i]+1,i});
// g_id.back().push_back(i);
add++;
ans+=add;
}else {
auto it=lower_bound(all(g.back()),(Val_id){A[i]+1,0});
add+=(i-it->id+1);
ll new_size=it-g.back().begin()+1;
g.back().resize(new_size);
// g_id.back().push_back(i);
ans+=add;
}
// g_id.back().push_back(i);
}else {
g.push_back({{A[i]+1,i}});
// g_id.push_back({i});
add+=i;
ans+=add;
}
}
cout<<ans<<"\n";
// #ifdef LOCAL
// debug(SZ(g));
// #endif
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
1
5
1 2 3 4 5
*/
```
:::
## 心得感悟