打的是 div2，感觉这场有点难，加上思维固化的问题，导致了掉分。
CF2022A
考虑到向上走一次再向下走一次等价于向前走两次，于是如果 \(y>0\) 就需要向上走 \(y\) 步，否则向下走 \(-y\) 步。每一种走路方式被用到的次数是唯一的，直接判断就行了。
//to kill a living book
#include<bits/stdc++.h>
#define int long long
using namespace std;signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t; cin>>t;while(t--){int x,y; cin>>x>>y;if(y==0) cout<<(x%3==0?"Yes\n":"No\n");else if(y>0) cout<<(x-y*2>=0&&(x-y*2)%3==0?"Yes\n":"No\n");else cout<<(x+y*4>=0&&(x+y*4)%3==0?"Yes\n":"No\n");}return 0;
}
CF2022B
上次还在笑一同学卡 div2B，今天轮到我了。
其实这种题有一个比较显然的 DP 解法。设计状态 \(f_{i,j,k}\) 代表分配前 \(i\) 个字符，目前 \(t\) 左侧字母是 \(j\)，右侧字母是 \(k\) 的可行性。转移是朴素的。
一开始一直以为前 3/4 题是贪心，但是这次没想到正确的贪心就没必要再死磕了，这是思维固化带来的一种坏处的体现。
//to kill a living book
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7;
int n,a[N];string s;
int dp[N][2][2];
void solve(){cin>>n>>s;for(int i=0;i<=n;i++) memset(dp[i],0,sizeof dp[i]);if(n%2==1) dp[0][0][0]=1;else dp[0][0][1]=1;for(int i=0;i<n;i++){for(int hd=0;hd<2;hd++){for(int tl=0;tl<2;tl++){if(dp[i][hd][tl]==0) continue;if(s[i]=='?') dp[i+1][1-hd][tl]=dp[i+1][hd][1-tl]=1;else{int tar=s[i]-'a';if(hd==tar) dp[i+1][1-hd][tl]=1;else if(tl==tar) dp[i+1][hd][1-tl]=1;}}}}if(dp[n][0][1]||dp[n][1][0]) cout<<"YES\n";else cout<<"NO\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t; cin>>t;while(t--) solve();return 0;
}
CF2021A
\(f\) 值的定义见困难版。
简单版本
这个版本就让你直接找整个数组的 \(f\) 值。直接观察性质，由一个数 \(a\) 通过上述操作生成的数组 \(s\)，除了 \(a\) 本身，其它的数必须大于 \(a\)，且 \(s[i]-s[i-1] \le 1\)。直接从前到后扫一遍，遇到不满足条件的新开一个就好了，这个贪心过程不难发现是正确的。
//to kill a living book
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+7;
int n,a[N];
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int mn=-1,pre=-1,cnt=0;for(int i=1;i<=n;i++){if(mn==-1) cnt++,mn=a[i];else{if(a[i]<=mn) cnt++,mn=a[i];else if(a[i]>pre+1) cnt++,mn=a[i];}pre=a[i];}cout<<cnt<<"\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t; cin>>t;while(t--) solve();return 0;
}
困难版本
这个版本让你求所有子数组的 \(\sum f\)。除了朴素暴力之外，不难想到一种 \(n^2\) 算法，就是从每一个 \(i\) 开始往后扫，这样可以直接 \(n\) 时间内统计从 \(i\) 开始的所有子数组的权值。但是这还不够，我们考虑使用 DP 转移。注意在上述算法的一轮遍历中，当我们第一次遍历到一个不符合条件的值时，那么从这个值开始往后的情况其实都是计算过的，用一个 DP 数组记录过这个值就不需要再次计算了，而从 \(i\) 到这个点贡献的段数为 \(1\)。设计状态 \(dp_i\) 代表所有从 \(i\) 开始的子数组的 \(\sum f\)，\(dp_{n+1}=0\)。那么考虑如何维护转移点。我们上面说的新开一段的条件有两个：要么 \(a[i]-a[i-1]>1\)，要么这个数不大于数组的首个元素。对于第一个条件，我们可以直接使用一个变量存着，对于第二个条件，需要使用 BIT 来维护每一个数出现的最小坐标值。转移时直接取二者之间的最小值就行了。转移方程是朴素的。
//to kill a living book
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+7;
int n,a[N],f[N];
struct BIT{int val[N];#define lb(x) (x&(-x))void init(){for(int i=1;i<=n;i++) val[i]=n+1;}void upd(int x,int k){for(int i=x;i<=n;i+=lb(i)) val[i]=min(val[i],k);}int qur(int x){int res=n+1;for(int i=x;i;i-=lb(i)) res=min(res,val[i]);return res;}
};
BIT Misaka;
void solve(){cin>>n;set<int> s;for(int i=1;i<=n;i++){cin>>a[i];s.insert(a[i]);}map<int,int> mp;int idx=0;for(int x:s) mp[x]=++idx;int j=n+1,ans=0;f[n+1]=0,Misaka.init();for(int i=n;i>=1;i--){int idx=min(j,Misaka.qur(mp[a[i]]));f[i]=f[idx]+(n-idx+1)+idx-i,ans+=f[i];if(i>1&&a[i]-a[i-1]>=2) j=i;Misaka.upd(mp[a[i]],i);}cout<<ans<<"\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t; cin>>t;while(t--) solve();return 0;
}
CF2021B
考虑一对数最多会贡献两次操作，当且仅当第二个数在某一轮操作的第二次被翻出。那么最多也只可能有 \(2n\) 次操作。同时最少肯定有 \(n\) 次操作。顺着对每一对数构造的思路想下去似乎很麻烦，不妨换一个角度思考。因为数的排列顺序其实不重要，我们把一个数第一次出现的位置记为 \(1\)，否则记为 \(2\)。考虑每种组合的贡献：
- 单独的 \(2\)，贡献 \(1\) 次翻转。
- \(11\)，两个 \(1\) 各贡献 \(0.5\) 次。
- \(12\)（两个数字不同），\(1\) 贡献 \(0.5\) 次，\(2\) 贡献 \(1.5\) 次。
- \(12\)（两个数字相同），\(1\) 贡献 \(0.5\) 次，\(2\) 贡献 \(0.5\) 次。
这样的话，不难发现理想情况是 \(12121212\)。但是这样其实都属于两个数字相同的情况，不能取到。那退而求其次，安排 \(11121212..1222\) 可以达到 \(2n-1\) 次操作，那么确定了上下界。对于不同的操作次数具体构造方式只需要把两种方式组合起来就行了，请读者自行思考。
//to kill a living book
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+7;
int n,k,a[N<<1],vis[N];
void solve(){cin>>n>>k;if(k<n||k>2*n-1) return cout<<"NO\n",void();k-=n;if(!k){cout<<"YES\n";for(int i=1;i<=n;i++) cout<<i<<" "<<i<<" ";cout<<"\n"; return;}int idx=1;set<int> s;for(int i=1;i<=n;i++) vis[i]=0;cout<<"YES\n";for(int i=1;i<=k+1;i++){if(i==1) cout<<"1 2 ",vis[1]=vis[2]=1,s.insert(1),s.insert(2);else if(i<=k){while(vis[idx]) idx++;cout<<idx<<" "<<(*s.begin())<<" ";s.erase(s.begin()); vis[idx]=1,s.insert(idx);}else if(i==k+1) for(int x:s) cout<<x<<" ";}for(int i=k+2;i<=n;i++){cout<<i<<" "<<i<<" ";}cout<<"\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t; cin>>t;while(t--) solve();return 0;
}
CF2021C
没看，我想想，等会补上。