本文主要是介绍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(补题补写法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!