本文主要是介绍Codeforces Round #740 -64，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
不摆烂了，开始板刷cf。
耻辱之中绝无慰藉，除非脱离耻辱
A 题意
按轮次奇偶性交换元素，问最小排序成功次数
A 思路
模拟题，stl真好用
A 代码
#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<chrono>
#include<bitset>
#include<complex>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=400505;const int inf=0x3f3f3f3f;int n,m,k;void YES(){cout<<"YES"<<endl;}void NO(){cout<<"NO"<<endl;}void solve(){vector<int>v;cin>>n;for(int i=0;i<n;i++){int t;cin>>t;v.push_back(t);}int ans=0;while(!is_sorted(v.begin(),v.end())){if(ans&1){for(int i=1;i<n-1;i+=2){if(v[i]>v[i+1]) swap(v[i],v[i+1]);}}else{for(int i=0;i<n-1;i+=2){if(v[i]>v[i+1]) swap(v[i],v[i+1]);}}ans++;}cout<<ans<<endl;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;cin>>tn;for(int __=1;__<=tn;__++){solve();}} B 题意
ab轮流抛硬币，若正面自己得分，否则对方得分。只知道二人得分，不知道先后手以及每局具体情况，问可能出现的反面次数。
B 思路
读题读一年，读完也卡。
直到总局数，知道自己掷硬币次数（若总局数为奇数就跑两次），枚举自己反面次数为cnt，可以根据得分，抛掷次数等把自己正面，对方反面，对方正面表示出来，假设这四个全部合法，则记录答案。
B 代码
#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<chrono>
#include<bitset>
#include<complex>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=400505;const int inf=0x3f3f3f3f;int n,m;void YES(){cout<<"YES"<<endl;}void NO(){cout<<"NO"<<endl;}void solve(){vector<int>v;int a,b;cin>>a>>b;if(a>b) swap(a,b);n=a+b;int p=n/2;int now=a+b,cnt=0;while(cnt<=b){int zuocheng=p-cnt;int zuoshi=cnt;int youcheng=b-cnt;int youshi=a-p+cnt;if(zuocheng>=0&&zuoshi>=0&&youcheng>=0&&youshi>=0){if(2*cnt+a-p>=0&&2*cnt+a-p<=a+b)v.push_back(2*cnt+a-p);}cnt++;}cnt=0;if(n%2){p++;while(cnt<=b){int zuocheng=p-cnt;int zuoshi=cnt;int youcheng=b-cnt;int youshi=a-p+cnt;if(zuocheng>=0&&zuoshi>=0&&youcheng>=0&&youshi>=0){if(2*cnt+a-p>=0&&2*cnt+a-p<=a+b)v.push_back(2*cnt+a-p);}cnt++;}}sort(v.begin(),v.end());cout<<v.size()<<endl;for(auto i:v)cout<<i<<' ';cout<<endl;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;cin>>tn;for(int __=1;__<=tn;__++){solve();}} C 题意
n个洞穴，每个洞穴有ki个怪物，每个怪物有防御力，你的攻击力严格大于防御才能杀死他。杀死怪物会让攻击力+1，进入一个洞穴就必须全部打完怪物。你可以选择进入不同洞穴的顺序，每个洞穴只能进入一次，问最小能通关的攻击力。
C 思路
首先处理出每个洞穴二元组<a,b>。代表至少a点攻击力可以通过，且一共有b个怪物(增加b点攻击力)。容易想清楚我们应该按a从小往大遍历洞穴。我们将洞穴按a排序，假如我们的初始攻击力是x，那我们需要满足以下不等式：
- x>=a1
- x+b1>=a2
- x+b2>=a3
- …
将它们移项，求不等式右边最大值即可。
既然发现了贪心策略，也可以二分搜索。
C 代码
#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<chrono>
#include<bitset>
#include<complex>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=400505;const int inf=0x3f3f3f3f;int n,m;void solve(){cin>>n;vector<pair<int,int>>v;for(int i=1;i<=n;i++){int a=-1,b,now=-1;int t,num;cin>>t;for(int i=0;i<t;i++){cin>>num;if(num>=now){now=num+1;a=now-i;}now++;}b=now;v.push_back({a,t});}sort(v.begin(),v.end());int ans=-inf;int cnt=0;for(auto i:v){ans=max(ans,i.first-cnt);cnt+=i.second;} cout<<ans<<endl;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;cin>>tn;for(int __=1;__<=tn;__++){solve();}} D 题意
这里只放代码，单独写新题解
D 思路
D 代码
void solve(){cin>>n>>mod;bit[n]=1;sum[n]=1;for(int i=n-1;i;i--){bit[i]=sum[i+1]%mod;for(int j=2;j*i<=n;j++){int l=i*j,r=min(n,i*j+j-1);bit[i]=(bit[i]+sum[l]-sum[r+1]+mod)%mod;}sum[i]=(bit[i]+sum[i+1])%mod;}cout<<bit[1]<<endl;}
E 题意
给你一个排列，长度为奇数，每次可以选择一个奇数长度前缀，把这个前缀reverse。要你选择一个方案操作排列，让他排好序。次数需要不超过5n/2。不可能输出-1。
E 思路
首先关于-1的判断，容易发现每次交换不改变奇偶性。那么一个必要条件是每个ai和i的奇偶性相同，这其实也是充分条件。
这里需要发现一个性质，假如第n个元素和第n-1个元素归位了，那么我们就不再需要动n和n-1了。因此我们可以写一个类似递归的方案，每一层将后两个元素排好序，之后将长度减2继续操作，直到长度为1。当然我们不需要递归实现，一个while就可以了。现在考虑如何将n和n-1归位。
下面是一个5步的操作流程，我们约定x为当前排列最大数（也就是长度），y为次大数，reverse长为len的前缀称为操作len：
- 找到x，操作pos_x，现在x在1号位置。
- 找到y，操作pos_y-1，现在x在pos_y-1,y在pos_y
- 操作pos_y+1，现在x在3，y在2.
- 操作2，现在x在1，y在2
- 操作x，现在x在x，y在y
上述操作一共五步，可以发现需要操作(n-1)/2轮，满足要求。
E 代码
void fun(vector<int>&v,int p){for(int i=1;i<=p/2;i++){swap(v[i],v[p+1-i]);}/* for(auto i:v)cout<<i<<' ';cout<<endl; */}void locate(int &p1,int &p2,vector<int>&a){for(int i=1;i<=m;i++){if(a[i]==m) p1=i;if(a[i]==m-1) p2=i;}}void solve(){vector<int>sol;vector<int>a;cin>>n;a.resize(n+10);for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){if((a[i]^i)&1){cout<<-1<<endl;return ;}}m=n;while(m!=1){int p1,p2;/* cout<<m<<':'<<endl; */locate(p1,p2,a);sol.push_back(p1);fun(a,p1);locate(p1,p2,a);sol.push_back(p2-1);fun(a,p2-1);locate(p1,p2,a);sol.push_back(p2+1);fun(a,p2+1);locate(p1,p2,a);sol.push_back(3);fun(a,3);locate(p1,p2,a); sol.push_back(m);fun(a,m);m-=2;}cout<<sol.size()<<endl;for(auto i:sol) cout<<i<<' ';cout<<endl;}
这篇关于Codeforces Round #740 -64的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
