本文主要是介绍Codeforces Round 915 (Div. 2) A-F（补题补写法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A. Constructive Problems（签到）
题解
输出max(x,y)
t = int(input())
for _ in range(t):u, v = map(int,input().split())print(max(u,v))B. Begginer's Zelda（统计树的叶子）
题解
输出叶子个数除以2上取整
// Problem: B. Begginer's Zelda
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10;
int t,n,u,v;
vector<int>e[N];
void sol(){sci(n);rep(i,1,n)e[i].clear();int lf=0;rep(i,2,n){sci(u),sci(v);e[u].pb(v);e[v].pb(u);}rep(i,1,n)lf+=(SZ(e[i])==1);pte((lf+1)/2);
}
int main(){sci(t); // t=1while(t--){sol();}return 0;
}C. Largest Subsequence（模拟）
题解
注意到初始序列里的字典序最大的子序列是非严格递减的，记为x
并且循环移位一个字母之后，后面变成的子序列也只是x去掉最后一个字母的子序列
所以最终操作完就是相当于将x排序（将x反转）
特别地，当x只剩全由一种字母组成时，无需再操作了，所以判一下和第一个字母相同的个数
// Problem: C. Largest Subsequence
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int t,n,suf[N];
void sol(){string s,ss;vector<int>pos;sci(n);cin>>s;ss=s;sort(ss.begin(),ss.end());if(s==ss){puts("0");return;}suf[n]=0;int cnt=0;per(i,n-1,0){int v=s[i]-'a';suf[i]=max(v,suf[i+1]);}rep(i,0,n-1){int v=s[i]-'a';if(v==suf[i]){pos.pb(i);if(suf[pos[0]]==v)cnt++;}}int sz=SZ(pos);rep(i,0,sz/2-1)swap(s[pos[i]],s[pos[sz-1-i]]);//cout<<"s:"<<s<<" ss:"<<ss<<endl;if(s==ss)pte(sz-cnt);else puts("-1");
}
int main(){sci(t); // t=1while(t--){sol();}return 0;
}D. Cyclic MEX（线段树/单调栈）
题意
给定长为n(n<=1e6)的一个排列p，
对前缀依次求mex得到数组a，再对a内所有值求和，得到代价cost
求p的所有循环排列中，cost最大时对应的值
t(t<=1e5)组样例，sumn不超过1e6
题解
先循环移位，使得0在最后，
然后每把一个数字v拽到最后，就会新增一个mex值n
并且会使得之前大于v的mex值变为v，所以可以线段树区间覆盖和单点修改区间加
倘若注意到mex是非严格单调递增的，可能存在每个值对应一段的情形，
那么可以向左不断弹栈弹出大于v的所有位置，
具体来说维护一个单调栈，放入（值，值对应的一段区间的最右位置）
赛后补的（单调栈）
注意到一定是小的值把大的值踢出来，
所以维护一个单调栈，弹出和置入的时候算贡献改变量
// Problem: D. Cyclic MEX
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e6+10;
P stk[N];
int t,n,a[N],c;
void sol(){sci(n);int st;rep(i,0,n-1){sci(a[i]);if(a[i]==0)st=(i+1)%n;}stk[c=0]=P(0,0);//stk[++c]=P(n,1);ll ans=n,now=0;rep(i,0,n-1){int r=i+1;while(c && a[st]<=stk[c].fi){now-=1ll*stk[c].fi*(stk[c].se-stk[c-1].se);c--;}now+=1ll*a[st]*(r-stk[c].se);stk[++c]=P(a[st],r);ans=max(ans,now+n);st=(st+1)%n;}ptlle(ans);
}
int main(){sci(t); // t=1while(t--){sol();}return 0;
}赛中写的（线段树）
线段树对应单点修改，区间覆盖，区间询问求和
// Problem: D. Cyclic MEX
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e6+10;
struct segtree2{int n;struct node{int l,r,c,w;ll v;}e[N<<2];#define l(p) e[p].l#define r(p) e[p].r#define v(p) e[p].v#define w(p) e[p].w#define c(p) e[p].cvoid up(int p){v(p)=v(p<<1)+v(p<<1|1);w(p)=max(w(p<<1),w(p<<1|1));}void bld(int p,int l,int r){l(p)=l;r(p)=r;if(l==r){v(p)=c(p)=w(p)=0;return;}int mid=l+r>>1;bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);up(p);}void psd(int p){if(c(p)){v(p<<1)=1ll*(r(p<<1)-l(p<<1)+1)*c(p);c(p<<1)=c(p);w(p<<1)=c(p);v(p<<1|1)=1ll*(r(p<<1|1)-l(p<<1|1)+1)*c(p); c(p<<1|1)=c(p);w(p<<1|1)=c(p);c(p)=0; }}void init(int _n){n=_n;bld(1,1,n);}void chg(int p,int x,int v){if(l(p)==r(p)){v(p)=w(p)=v;return;}int mid=l(p)+r(p)>>1;psd(p);chg(p<<1|(x>mid),x,v);up(p);}void cov(int p,int ql,int qr,int v){if(ql<=l(p)&&r(p)<=qr){v(p)=1ll*(r(p)-l(p)+1)*v;c(p)=v;w(p)=v;return;}psd(p);int mid=l(p)+r(p)>>1;if(ql<=mid)cov(p<<1,ql,qr,v);if(qr>mid)cov(p<<1|1,ql,qr,v);up(p);}ll cnt(int p,int ql,int qr){if(ql<=l(p)&&r(p)<=qr)return v(p);int mid=l(p)+r(p)>>1;ll res=0;psd(p);if(ql<=mid)res+=cnt(p<<1,ql,qr);if(qr>mid)res+=cnt(p<<1|1,ql,qr);return res;}int f(int p,int v){if(w(p)<=v)return -1;if(l(p)==r(p))return l(p);if(w(p<<1)>v)return f(p<<1,v);return f(p<<1|1,v);}
}seg;
int t,n,a[N];
void sol(){sci(n);int st;rep(i,0,n-1){sci(a[i]);if(a[i]==0)st=(i+1)%n;}seg.init(n);seg.chg(1,1,n);ll ans=n;rep(i,0,n-1){int r=i+1;int p=seg.f(1,a[st]);seg.cov(1,p,r,a[st]);seg.chg(1,r+1,n);ans=max(ans,seg.cnt(1,1,r+1));st=(st+1)%n;}ptlle(ans);
}
int main(){sci(t); // t=1while(t--){sol();}return 0;
}E. One-X（递推/记忆化搜索/bfs）
题意
给一棵[1,n](n<=1e18)完整建好的线段树，
对于点i，左儿子2*i，右儿子2*i+1，根是1，
n个叶子节点，取若干个叶子结点得到一个集合，对这个集合求lca得到一个点号，
求所有非空情况（即2^n-1种情况）下lca点号的和，答案对998244353取模
题解
尝试递推，即尝试缩小规模，
第i层的子树大小只有三种值，x和x-1都需要除以2，
即x/2上取整，x/2下取整，(x-1)/2上取整，(x-1)/2下取整，
所以记忆化搜索子树大小对应的答案即可，
此外，还有根id的变化，
即一棵大小为n的根id=1的树，变为大小为n的根id=2的树（或变为根id=3的树）时，
对应的贡献增加了多少
手玩不难发现，根id每增加1，总贡献增加：
系数=lca在第一层方案数*1+lca在第二层方案数*2+lca在第三层方案数*4+...
暴力维护这个方案数是一个长为log的vector，每次算的时候现乘，复杂度O(nlogn^2)
但是注意到可以直接把这个系数加一起，每次乘以2，再把第一层的方案数加上即可，
复杂度O(nlogn)
赛后补的（1log）
// Problem: E. One-X
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/E
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int mod=998244353;
int t;
ll n;
map<ll,array<int,3> >mp;
int modpow(int x,ll n,int mod){int res=1;for(;n;n>>=1,x=1ll*x*x%mod){if(n&1)res=1ll*res*x%mod;}return res;
}
//(答案,系数,叶子数)
//系数=lca在第一层路径数*1+lca在第二层路径数*2+lca在第三层路径数*4+...
array<int,3> dfs(ll x){if(x==1)return {1,1,1};if(mp.count(x))return mp[x];auto [ansL,wL,lfL]=dfs((x+1)/2);auto [ansR,wR,lfR]=dfs(x/2);array<int,3>res;auto &[ans,w,lf]=res;int cnt=1ll*(modpow(2,lfL,mod)+mod-1)%mod*(modpow(2,lfR,mod)+mod-1)%mod;ans=(ansL+ansR)%mod;ans=(ans+1ll*wL%mod)%mod;//1->2 lson add 1ans=(ans+2ll*wR%mod)%mod;//1->3 rson add 2ans=(ans+cnt)%mod;w=(2ll*wL%mod+2ll*wR%mod)%mod;w=(w+cnt)%mod;lf=(lfL+lfR)%(mod-1);return mp[x]=res;
}
void sol(){scll(n);mp.clear();pte(dfs(n)[0]);
}
int main(){sci(t); // t=1while(t--){sol();}return 0;
}赛中写的（2log）
// Problem: E. One-X
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/E
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int mod=998244353;
int t;
ll n;
map<ll,vector<int> >mp;
map<ll,int>mp2;
int modpow(int x,ll n,int mod){int res=1;for(;n;n>>=1,x=1ll*x*x%mod){if(n&1)res=1ll*res*x%mod;}return res;
}
vector<int> dfs(ll x){if(mp.count(x))return mp[x];if(x==1){vector<int>ans;ans.pb(1);return ans;}//printf("x:%lld\n",x);ll ls=(1+x)/2,rs=x-ls;vector<int>l=dfs(ls),r=dfs(rs);int sz=max(SZ(l),SZ(r));vector<int>now(sz+1,0);rep(i,1,sz){now[i]=0;if(i-1<SZ(l))now[i]=(now[i]+l[i-1])%mod;if(i-1<SZ(r))now[i]=(now[i]+r[i-1])%mod;}now[0]=1ll*(modpow(2,ls,mod)+mod-1)%mod*(modpow(2,rs,mod)+mod-1)%mod;return mp[x]=now;
}
int dfs2(ll x,ll y){if(x==1)return y%mod;if(y==1){ if(mp2.count(x))return mp2[x];vector<int>z=dfs(x);ll ls=(1+x)/2,rs=x-ls;int v1=dfs2(ls,y*2),v2=dfs2(rs,y*2+1);v1=(v1+v2)%mod;v1=(v1+z[0])%mod;return mp2[x]=v1; }else{int w=dfs2(x,1);vector<int>z=dfs(x);int add=(y-1)%mod,sz=SZ(z);rep(i,0,sz-1){w=(w+1ll*z[i]*add%mod)%mod;add=2ll*add%mod;}return w; }
}
void sol(){scll(n);mp.clear();mp2.clear();pte(dfs2(n,1));
}
int main(){sci(t); // t=1while(t--){sol();}return 0;
}F. （暴力 map+前后缀最大值次大值/线段树/set）
给定长为n(2<=n<=2e5)的一个排列p，
称一个位置x是good的，当且仅当所有y<x都有py<px，且所有y>x都有py>px，
其实就是，将(x,px)看成是二维平面点的时候，左侧的点都在左下方，右侧的点都在右上方
必须交换（全部有序了也得换小）一组值px和py(px!=py)，求交换后good位置的最大个数
t(t<=2e4)组样例，但保证sumn不超过2e5
题解写的又是树状数组又是线段树，非常麻烦，补一下jiangly的代码
只需用到前后缀的最大值和次大值，从而判断是否有good位置+1，非常优雅
当然也看了一个set
题解
有贡献的位置，ai=i是其必要条件，
首先，因为只能操作一次，
那么注意到可能新增good位置的手段只有两种（第一步就没注意到）
1. 将ai和i的值交换，令ai归位，这样可能能增加1
2. 看成是二维平面点的时候，(x,px)左上方恰有一个点，右下方恰有一个点，可以交换
就是交换px左侧的最大值，和px右侧的最小值，交换这两个位置
所以，可能产生贡献的位置对，只有2*n个，暴力检查这2*n个，能快速算贡献改变量即可
统计一下序列中已经good的位置，
是ai=i且左侧最大值小于i，右侧最小值大于i的位置
计这个个数是cnt
1. 如果所有位置都归位，那么交换会损失两个，也就是cnt-2
2. 至少有一个没归位的
①换一个归位的和一个没归位的，相邻就可以只损失一个位置，答案至少为cnt-1
但是注意到，没归位的是成对出现的
并且一定存在没归位的两个位置是逆序的（假设都是正序的，那么就都归位了，矛盾）
交换这两个逆序位置，cnt不变，所以答案可以取到cnt
3. 当交换(x,y)(x<y)两个位置时，
[1,x-1]的位置不受影响，[y+1,n]的位置不受影响，
由于想让答案增大，所以px>py一定成立(px<py越换越乱只能减小)
考虑[x+1,y-1]这个区间里的位置i，在(x,y)交换前，是没有good位置的，
因为，将(i,pi)看成是二维平面点的时候，左侧的点都在左下方，右侧的点都在右上方，
也就意味着，当i左侧的值和i右侧的值没有形成逆序对时，才会出现good位置，
而px和py是一对逆序对，所以没有good位置
所以，枚举所有可能增加的位置对，直接将对应贡献加上即可，2*n种情况取max
心得
此外学习到jiangly的最大值次大值的写法，只需要每次和x交换即可
for (int i = 1; i < n; i++) {
pre[i] = pre[i - 1];
int x = p[i - 1];
for (int j = 0; j < 2; j++) {
if (x > pre[i][j]) {
std::swap(x, pre[i][j]);
}
}
}
最大值次大值写法
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> p(n), invp(n);for (int i = 0; i < n; i++) {std::cin >> p[i];p[i]--;invp[p[i]] = i;}std::vector<std::array<int, 2>> pre(n, {-1, -1}), suf(n, {n, n});for (int i = 1; i < n; i++) {pre[i] = pre[i - 1];int x = p[i - 1];for (int j = 0; j < 2; j++) {if (x > pre[i][j]) {std::swap(x, pre[i][j]);}}}for (int i = n - 2; i >= 0; i--) {suf[i] = suf[i + 1];int x = p[i + 1];for (int j = 0; j < 2; j++) {if (x < suf[i][j]) {std::swap(x, suf[i][j]);}}}std::vector<int> bad(n);int cnt = 0;int ans = 0;std::map<std::pair<int, int>, int> mp;for (int i = 0; i < n; i++) {if (p[i] == i) {if (pre[i][0] < i && suf[i][0] > i) {//符合条件,不换bad[i] = 1;cnt += 1;} else if (pre[i][1] < i && suf[i][1] > i) {//换i左侧最大的和i右侧最小的，可使i符合条件mp[{invp[pre[i][0]], invp[suf[i][0]]}] += 1;}} else if (invp[i] < i) {if (suf[i][0] > i && pre[i][0] == i) {//令i值向后换归位mp[{invp[i], i}] += 1;}} else {if (suf[i][0] == i && pre[i][0] < i) {//令i值向前换归位mp[{i, invp[i]}] += 1;}}}//4 1 3 2ans = cnt - 2;//默认会损失两个位置if (cnt < n) {//至少有一个没归位的，换相邻就可以只损失一个位置ans = cnt;// 一定有至少一对逆序没归位的，换这对不会减少答案}for (auto [s, c] : mp) {//换(s_x,s_y]能增加c个归位的，换一对(x,y),x以左y以右不会受到影响,但是会减少[bad[x],bad[y]]个归位的auto [x, y] = s;ans = std::max(ans, cnt + c);}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}set写法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
const int INF = 0x3f3f3f3f;int n,a[N],pos[N],pre[N];void solve(){int ans = 0;cin >> n;set <int> ps,vs;map <pair <int,int>,int> mp;for(int i = 1;i <= n;i ++){cin >> a[i];pos[a[i]] = i;ps.insert(i);vs.insert(i);pre[i] = 0;}for(int mxpos = 0,i = 1;i <= n;i ++){if(pos[i] != i){if(mxpos <= i){mp[make_pair(min(i,pos[i]),max(i,pos[i]))] ++;} // swap i to position(i) makes ans ++}else{if(mxpos <= i){ans ++; pre[i] = 1;} // i already satisfyelse{if(ps.size() >= 2 && (*(++ ps.begin())) == i){int val = *vs.begin();int p = *ps.begin();if(val < i && p < i) mp[make_pair(min(pos[val],p),max(pos[val],p))] ++;}}}mxpos = max(mxpos,pos[i]);ps.erase(pos[i]);vs.erase(a[i]);}for(int i = 1;i <= n;i ++) pre[i] += pre[i - 1];if(ans == n){cout << n - 2 << '\n';return;}int mx = 0;for(auto it = mp.begin();it != mp.end();it ++){int now = it->second;//auto [l,r] = it->first;//now -= (pre[r] - pre[l - 1]); // um// cout << l << ' ' << r << ' ' << now << endl;mx = max(mx,now);}cout << ans + mx << '\n';// cout << ans << ' ' << mx << " -> " << ans + mx << '\n';
}int main(){ios::sync_with_stdio(false);int TC;cin >> TC;while(TC --){solve();}return 0;
}这篇关于Codeforces Round 915 (Div. 2) A-F（补题补写法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
