Codeforces Global Round 16

Median Maximization

给出n和s，要构造一个非负整数数组，大小为n，和为s，要求满足情况下最大的中位数，注意这里的中位数下标应该是向下取的，也就是当n为偶数时应该取中间靠左的那个数。
解法是直接让中位数之前的置0，那么就是尽量把s分成n/2+1个数，多的部分只能给中位数之后的数，所以答案应该是s/(n/2+1)。

/*
* @Autor: violet apricity (zpx)
* @Date: 2021-07-22 22:06:15
* @LastEditors: violet apricity (zpx)
* @LastEditTime: 2021-09-12 22:39:37
* @FilePath: apricitycf.cpp
* @Description: Violet acm && Apricity:/ The warmth of the sun in the winter /
*/
// violet apricity
// Do all I can do.Do good to be good.
//g++
./violet/run.cpp -o ./violet/run.exe
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<sstream>
#include<numeric>
#include<queue>
#include<iomanip>
#include<fstream>
#include<unordered_map>
#include<stack>
#include<set>
#include<random>
//#include<bits/stdc++.h>
#define ll long long
#define db double
#define ldb long double
#define IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define MAX 88888888
#define INF 0x3f3f3f3f
#define r0 return 0;
#define SYP system("pause");
//#define endl 'n'
using namespace std;
ll gcd(ll a,ll b){ll d;while(b){d=b;b=a%b;a=d;}return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll _pow(ll a,ll b){ll d=1;while(b){if(b&1)d*=a;a*=a;b>>=1;}return d;}
ll mpow(ll a,ll b,ll m){ll d=1;while(b){if(b&1)d=(d*(a%m))%m;a=((a%m)*(a%m))%m;d%=m;b>>=1;}return d%m;}
void exgcd(ll a,ll b,ll &g,ll &x,ll &y){if(!b){g=a;x=1;y=0;}else {exgcd(a,b,g,y,x);y-=x*(a/b);}}
//#define int long long
//=====================================================================
const int N=1e6+5;
const ll mod=998244353;
/*
ll jie[N],tow[N];
void init()
{
jie[0]=1;
for(int i=1;i<N;i++)jie[i]=jie[i-1]*i%mod;
tow[N-1]=mpow(jie[N-1],mod-2,mod);
for(int i=N-2;i>=0;i--) tow[i]=tow[i+1]*(i+1)%mod;
}
ll cal(ll n,ll m){if(m>n) return 0; return jie[n]*tow[m]%mod*tow[n-m]%mod; }
*/
struct dsu {
//DSU
vector<int> f;
dsu(int n) :f(n) { iota(f.begin(), f.end(), 0); }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int x, int y) {
x = find(x); y = find(y);
if (x > y)swap(x, y);
f[y] = x;
}
};
/*
ll pri[N],privis[N],pritot;
//getprimes
void getpri(ll n) //(pri)-allprime (privis)-ispri (pritot)-cntpri
{privis[2]=0;for(ll i=2;i<=n;i++){if(!privis[i])pri[++pritot]=i; for(ll j=1;j<=pritot&&i*pri[j]<=n;j++){privis[pri[j]*i]=1; if(i%pri[j]==0)break; }}}
ll phi[N];
void getphi(ll n)
{
phi[1]=1;
for(ll i=2;i<=n;i++){
if(!privis[i]) {phi[i]=i-1; pri[pritot++]=i; }
for(ll j=1;j<=pritot&&i*pri[j]<=n;j++){
privis[i*pri[j]]=1;
if(i%pri[j]) { phi[i*pri[j]]=phi[i]*(pri[j]-1); }
else { phi[i*pri[j]]=phi[i]*pri[j]; break; }
}
}
}
*/
//=====================================================================
#define pcase(t,d) cout<<"Case #"<<(t)<<": "<<(d)<<'n'
#define pNO cout<<"NOn"
#define pYES cout<<"YESn"
#define pNo cout<<"Non"
#define pYes cout<<"Yesn"
#define pno cout<<"non"
#define pyes cout<<"yesn"
#define pdebug(ans) cout<<"ans:"<<(ans)<<'n'
#define pshow(x) cout<<" show:"<<(x)<<'n'
#define p(ans) cout<<(ans)<<'n'
#define pdec(t,ans) cout<<std::fixed<<std::setprecision(t)<<(ans)<<'n'
//=====================================================================
//=====================================================================
int main()
{
#ifdef LOCAL
//ifstream cin("E:\ACMdream\in.txt");
//ofstream cout("E:\ACMdream\out.txt");
freopen("E:\ACMdream\in.txt","r",stdin);
freopen("E:\ACMdream\out.txt","w",stdout);
#endif
IOS
//======================================================================
int T=1;
cin>>T;
while(T--){
ll n,s;cin>>n>>s;
ll p=n/2+1;
cout<<s/p<<'n';
}
//======================================================================
//SYP
return 0;
}
*/

MIN-MEX Cut

一个01串划分，使得mex的和最小，其中mex只有0/1/2三种。
因为是求最小和，所以直接考虑让mex取0和1即可。从头遍历01串，如果出现连续的0就分成一体贡献+1，如果出现1就单独拿出来贡献+0。

/*
* @Autor: violet apricity (zpx)
* @Date: 2021-07-22 22:06:15
* @LastEditors: violet apricity (zpx)
* @LastEditTime: 2021-09-12 22:53:59
* @FilePath: apricitycf.cpp
* @Description: Violet acm && Apricity:/ The warmth of the sun in the winter /
*/
// violet apricity
// Do all I can do.Do good to be good.
//g++
./violet/run.cpp -o ./violet/run.exe
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<sstream>
#include<numeric>
#include<queue>
#include<iomanip>
#include<fstream>
#include<unordered_map>
#include<stack>
#include<set>
#include<random>
//#include<bits/stdc++.h>
#define ll long long
#define db double
#define ldb long double
#define IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define MAX 88888888
#define INF 0x3f3f3f3f
#define r0 return 0;
#define SYP system("pause");
//#define endl 'n'
using namespace std;
ll gcd(ll a,ll b){ll d;while(b){d=b;b=a%b;a=d;}return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll _pow(ll a,ll b){ll d=1;while(b){if(b&1)d*=a;a*=a;b>>=1;}return d;}
ll mpow(ll a,ll b,ll m){ll d=1;while(b){if(b&1)d=(d*(a%m))%m;a=((a%m)*(a%m))%m;d%=m;b>>=1;}return d%m;}
void exgcd(ll a,ll b,ll &g,ll &x,ll &y){if(!b){g=a;x=1;y=0;}else {exgcd(a,b,g,y,x);y-=x*(a/b);}}
//#define int long long
//=====================================================================
const int N=1e6+5;
const ll mod=998244353;
/*
ll jie[N],tow[N];
void init()
{
jie[0]=1;
for(int i=1;i<N;i++)jie[i]=jie[i-1]*i%mod;
tow[N-1]=mpow(jie[N-1],mod-2,mod);
for(int i=N-2;i>=0;i--) tow[i]=tow[i+1]*(i+1)%mod;
}
ll cal(ll n,ll m){if(m>n) return 0; return jie[n]*tow[m]%mod*tow[n-m]%mod; }
*/
struct dsu {
//DSU
vector<int> f;
dsu(int n) :f(n) { iota(f.begin(), f.end(), 0); }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int x, int y) {
x = find(x); y = find(y);
if (x > y)swap(x, y);
f[y] = x;
}
};
/*
ll pri[N],privis[N],pritot;
//getprimes
void getpri(ll n) //(pri)-allprime (privis)-ispri (pritot)-cntpri
{privis[2]=0;for(ll i=2;i<=n;i++){if(!privis[i])pri[++pritot]=i; for(ll j=1;j<=pritot&&i*pri[j]<=n;j++){privis[pri[j]*i]=1; if(i%pri[j]==0)break; }}}
ll phi[N];
void getphi(ll n)
{
phi[1]=1;
for(ll i=2;i<=n;i++){
if(!privis[i]) {phi[i]=i-1; pri[pritot++]=i; }
for(ll j=1;j<=pritot&&i*pri[j]<=n;j++){
privis[i*pri[j]]=1;
if(i%pri[j]) { phi[i*pri[j]]=phi[i]*(pri[j]-1); }
else { phi[i*pri[j]]=phi[i]*pri[j]; break; }
}
}
}
*/
//=====================================================================
#define pcase(t,d) cout<<"Case #"<<(t)<<": "<<(d)<<'n'
#define pNO cout<<"NOn"
#define pYES cout<<"YESn"
#define pNo cout<<"Non"
#define pYes cout<<"Yesn"
#define pno cout<<"non"
#define pyes cout<<"yesn"
#define pdebug(ans) cout<<"ans:"<<(ans)<<'n'
#define pshow(x) cout<<" show:"<<(x)<<'n'
#define p(ans) cout<<(ans)<<'n'
#define pdec(t,ans) cout<<std::fixed<<std::setprecision(t)<<(ans)<<'n'
//=====================================================================
//=====================================================================
int main()
{
#ifdef LOCAL
//ifstream cin("E:\ACMdream\in.txt");
//ofstream cout("E:\ACMdream\out.txt");
freopen("E:\ACMdream\in.txt","r",stdin);
freopen("E:\ACMdream\out.txt","w",stdout);
#endif
IOS
//======================================================================
int T=1;
cin>>T;
while(T--){
string s;cin>>s;
int n=s.size();
int ans=0;
for(int i=0;i<n;i++){
if(i==0&&s[i]=='0'){
ans++;continue;
}
if(s[i]=='0'&&s[i-1]=='0')ans+=0;
else if(s[i]=='0')ans++;
else if(s[i]=='1')ans+=0;
}
if(ans<=2)cout<<ans<<'n';
else cout<<2<<'n';
}
//======================================================================
//SYP
return 0;
}

MAX-MEX Cut

和b题有点像。这次给出两个等长的01串（视为矩阵）将其划分，要求最大的mex和。
依旧是分类讨论。每次统计0和1的数量（设为x和y）。
如果（x==1&&y==1）也就是[1.0]，那么就分成一体，xy置0后贡献+2。
如果（x==2&&y==0）也就是[0.0]，此时不一定是最优的，那么继续往后找，如果后续（x==4&&y==0）也就是[0.0+0.0]那么之前的[0.0]单独划分贡献+1，留下当前的[0.0]，如果后续（x==3&&y==1）也就是[0.0+1.0]那么划分为两组[0.0]+[1.0]贡献+3。如果后续（x==2&&y==2）也就是[0.0+1.1]，那么它们划分成一体贡献+2。
如果（x==0&&y==2）也就是[1.1]依旧是不一定最优需要往后找。如果后续（x==0&&y==4）也就是[1.1+1.1]那么前面的[1.1]做不出贡献直接拿掉留下当前的[1.1]（保证讨论的范围最多只有两组）。如果后续（x==1&&y==3）也就是[1.1+1.0]同样是前面的没有贡献（当前已经到最大贡献）贡献+2。如果后续（x==2&&y==2）也就是[1.1+0.0]那么跟上述一样划分为一体贡献+2。
注意到最后可能会留下一组，需要对其进行单独划分，讨论一下贡献即可。

/*
* @Autor: violet apricity (zpx)
* @Date: 2021-07-22 22:06:15
* @LastEditors: violet apricity (zpx)
* @LastEditTime: 2021-09-12 23:18:20
* @FilePath: apricitycf.cpp
* @Description: Violet acm && Apricity:/ The warmth of the sun in the winter /
*/
// violet apricity
// Do all I can do.Do good to be good.
//g++
./violet/run.cpp -o ./violet/run.exe
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<sstream>
#include<numeric>
#include<queue>
#include<iomanip>
#include<fstream>
#include<unordered_map>
#include<stack>
#include<set>
#include<random>
//#include<bits/stdc++.h>
#define ll long long
#define db double
#define ldb long double
#define IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define MAX 88888888
#define INF 0x3f3f3f3f
#define r0 return 0;
#define SYP system("pause");
//#define endl 'n'
using namespace std;
ll gcd(ll a,ll b){ll d;while(b){d=b;b=a%b;a=d;}return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll _pow(ll a,ll b){ll d=1;while(b){if(b&1)d*=a;a*=a;b>>=1;}return d;}
ll mpow(ll a,ll b,ll m){ll d=1;while(b){if(b&1)d=(d*(a%m))%m;a=((a%m)*(a%m))%m;d%=m;b>>=1;}return d%m;}
void exgcd(ll a,ll b,ll &g,ll &x,ll &y){if(!b){g=a;x=1;y=0;}else {exgcd(a,b,g,y,x);y-=x*(a/b);}}
//#define int long long
//=====================================================================
const int N=1e6+5;
const ll mod=998244353;
/*
ll jie[N],tow[N];
void init()
{
jie[0]=1;
for(int i=1;i<N;i++)jie[i]=jie[i-1]*i%mod;
tow[N-1]=mpow(jie[N-1],mod-2,mod);
for(int i=N-2;i>=0;i--) tow[i]=tow[i+1]*(i+1)%mod;
}
ll cal(ll n,ll m){if(m>n) return 0; return jie[n]*tow[m]%mod*tow[n-m]%mod; }
*/
struct dsu {
//DSU
vector<int> f;
dsu(int n) :f(n) { iota(f.begin(), f.end(), 0); }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int x, int y) {
x = find(x); y = find(y);
if (x > y)swap(x, y);
f[y] = x;
}
};
/*
ll pri[N],privis[N],pritot;
//getprimes
void getpri(ll n) //(pri)-allprime (privis)-ispri (pritot)-cntpri
{privis[2]=0;for(ll i=2;i<=n;i++){if(!privis[i])pri[++pritot]=i; for(ll j=1;j<=pritot&&i*pri[j]<=n;j++){privis[pri[j]*i]=1; if(i%pri[j]==0)break; }}}
ll phi[N];
void getphi(ll n)
{
phi[1]=1;
for(ll i=2;i<=n;i++){
if(!privis[i]) {phi[i]=i-1; pri[pritot++]=i; }
for(ll j=1;j<=pritot&&i*pri[j]<=n;j++){
privis[i*pri[j]]=1;
if(i%pri[j]) { phi[i*pri[j]]=phi[i]*(pri[j]-1); }
else { phi[i*pri[j]]=phi[i]*pri[j]; break; }
}
}
}
*/
//=====================================================================
#define pcase(t,d) cout<<"Case #"<<(t)<<": "<<(d)<<'n'
#define pNO cout<<"NOn"
#define pYES cout<<"YESn"
#define pNo cout<<"Non"
#define pYes cout<<"Yesn"
#define pno cout<<"non"
#define pyes cout<<"yesn"
#define pdebug(ans) cout<<"ans:"<<(ans)<<'n'
#define pshow(x) cout<<" show:"<<(x)<<'n'
#define p(ans) cout<<(ans)<<'n'
#define pdec(t,ans) cout<<std::fixed<<std::setprecision(t)<<(ans)<<'n'
//=====================================================================
//=====================================================================
int main()
{
#ifdef LOCAL
//ifstream cin("E:\ACMdream\in.txt");
//ofstream cout("E:\ACMdream\out.txt");
freopen("E:\ACMdream\in.txt","r",stdin);
freopen("E:\ACMdream\out.txt","w",stdout);
#endif
IOS
//======================================================================
int T=1;
cin>>T;
while(T--){
int n;cin>>n;
string s1,s2;cin>>s1>>s2;
ll ans=0;
int x=0,y=0;
int nx=0,ny=0;
for(int i=0;i<n;i++){
if(s1[i]=='0')x++,nx++;else y++,ny++;
if(s2[i]=='0')x++,nx++;else y++,ny++;
if(x==1&&y==1){ans+=2;x=0;y=0;}//1.0
+2
else if(x==4&&y==0){ans+=1;x=2;y=0;}//0.0+0.0->0.0
+1
else if(x==3&&y==1){ans+=3;x=0;y=0;}//0.0+0.1
+3
else if(x==0&&y==4){ans+=0;x=0;y=2;}//1.1+1.1->1.1
+0
else if(x==1&&y==3){ans+=2;x=0;y=0;}//1.1+0.1
+2
else if(x==2&&y==2){ans+=2;x=0;y=0;}//1.1+0.0->2
+2
nx=ny=0;
}
if(x==2&&y==0)ans+=1;//0.0
+1
if(x==0&&y==2)ans+=0;//1.1
+0
cout<<ans<<'n';
}
//======================================================================
//SYP
return 0;
}

Seating Arrangements (easy version)+Seating Arrangements (hard version)

把d1和d2放在一起讲。
电影院有n*m个座位（n排m列），现有n*m个人，每个人有一个视力，要安排座位是的同一排内序号小的视力比序号大的视力要小，也就是视力小的在前，视力大的在后。d1和d2的区别在于前者n=1后者1<=n<=300。每个人就坐时从一排座位小到大移动，如果途中遇到有人就要贡献+1。要求安排座位使最小贡献。
容易发现，贡献的产生就是顺序对的存在。
首先明确一个问题，那就是同一排内按照视力小到大来安排座位，对于视力相等的人来说应该按照降序的方式就坐，也就是前面来的往后做后面来的往前坐。我们先要分出每一排分配的人再组排分配每个人的座位，这里很容易贪心地想到应该让总体小到大排序然后一次按m分排。（假设对于i排和j排，i<j，对于i排某个数x如果让它移动到j排只会让贡献增加而不会减少，因为总体而言i排比j排小，把x从小的那边放到大的那边只会让顺序对增加）。接下来讨论每排的分配，从小到大分配之后对于相等的人来说应该是逆着分（先来后坐）。那么问题就解决了

/*
* @Autor: violet apricity (zpx)
* @Date: 2021-07-22 22:06:15
* @LastEditors: violet apricity (zpx)
* @LastEditTime: 2021-09-13 00:18:53
* @FilePath: apricitycf.cpp
* @Description: Violet acm && Apricity:/ The warmth of the sun in the winter /
*/
// violet apricity
// Do all I can do.Do good to be good.
//g++
./violet/run.cpp -o ./violet/run.exe
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<sstream>
#include<numeric>
#include<queue>
#include<iomanip>
#include<fstream>
#include<unordered_map>
#include<stack>
#include<set>
#include<random>
//#include<bits/stdc++.h>
#define ll long long
#define db double
#define ldb long double
#define IOS std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define MAX 88888888
#define INF 0x3f3f3f3f
#define r0 return 0;
#define SYP system("pause");
//#define endl 'n'
using namespace std;
ll gcd(ll a,ll b){ll d;while(b){d=b;b=a%b;a=d;}return a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll _pow(ll a,ll b){ll d=1;while(b){if(b&1)d*=a;a*=a;b>>=1;}return d;}
ll mpow(ll a,ll b,ll m){ll d=1;while(b){if(b&1)d=(d*(a%m))%m;a=((a%m)*(a%m))%m;d%=m;b>>=1;}return d%m;}
void exgcd(ll a,ll b,ll &g,ll &x,ll &y){if(!b){g=a;x=1;y=0;}else {exgcd(a,b,g,y,x);y-=x*(a/b);}}
//#define int long long
//=====================================================================
//const int N=1e6+5;
const ll mod=998244353;
/*
ll jie[N],tow[N];
void init()
{
jie[0]=1;
for(int i=1;i<N;i++)jie[i]=jie[i-1]*i%mod;
tow[N-1]=mpow(jie[N-1],mod-2,mod);
for(int i=N-2;i>=0;i--) tow[i]=tow[i+1]*(i+1)%mod;
}
ll cal(ll n,ll m){if(m>n) return 0; return jie[n]*tow[m]%mod*tow[n-m]%mod; }
*/
struct dsu {
//DSU
vector<int> f;
dsu(int n) :f(n) { iota(f.begin(), f.end(), 0); }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int x, int y) {
x = find(x); y = find(y);
if (x > y)swap(x, y);
f[y] = x;
}
};
/*
ll pri[N],privis[N],pritot;
//getprimes
void getpri(ll n) //(pri)-allprime (privis)-ispri (pritot)-cntpri
{privis[2]=0;for(ll i=2;i<=n;i++){if(!privis[i])pri[++pritot]=i; for(ll j=1;j<=pritot&&i*pri[j]<=n;j++){privis[pri[j]*i]=1; if(i%pri[j]==0)break; }}}
ll phi[N];
void getphi(ll n)
{
phi[1]=1;
for(ll i=2;i<=n;i++){
if(!privis[i]) {phi[i]=i-1; pri[pritot++]=i; }
for(ll j=1;j<=pritot&&i*pri[j]<=n;j++){
privis[i*pri[j]]=1;
if(i%pri[j]) { phi[i*pri[j]]=phi[i]*(pri[j]-1); }
else { phi[i*pri[j]]=phi[i]*pri[j]; break; }
}
}
}
*/
//=====================================================================
#define pcase(t,d) cout<<"Case #"<<(t)<<": "<<(d)<<'n'
#define pNO cout<<"NOn"
#define pYES cout<<"YESn"
#define pNo cout<<"Non"
#define pYes cout<<"Yesn"
#define pno cout<<"non"
#define pyes cout<<"yesn"
#define pdebug(ans) cout<<"ans:"<<(ans)<<'n'
#define pshow(x) cout<<" show:"<<(x)<<'n'
#define p(ans) cout<<(ans)<<'n'
#define pdec(t,ans) cout<<std::fixed<<std::setprecision(t)<<(ans)<<'n'
//=====================================================================
//=====================================================================
int main()
{
#ifdef LOCAL
//ifstream cin("E:\ACMdream\in.txt");
//ofstream cout("E:\ACMdream\out.txt");
freopen("E:\ACMdream\in.txt","r",stdin);
freopen("E:\ACMdream\out.txt","w",stdout);
#endif
IOS
//======================================================================
int T=1;
cin>>T;
while(T--){
int n,m;cin>>n>>m;
vector<pair<int,int>>a(n*m);
for(int i=0;i<n*m;i++){
cin>>a[i].first;a[i].second=i;
}
sort(a.begin(),a.end());//此时相等视力的人序号小的在前
for(int i=0;i<n*m;i++)a[i].second*=-1;//取反为了后续排序
int ans=0;
for(int i=0;i<n;i++){
//重新排序
sort(a.begin()+m*i,a.begin()+m*(i+1));//序号取反后排序，相等视力的人序号大的在前
for(int j=0;j<m;j++){
for(int k=0;k<j;k++){
if(a[j+i*m].second<a[k+i*m].second)ans++;//对于每个人找到在他前面且序号比它小的让贡献+1
}
}
}
cout<<ans<<'n';
}
//======================================================================
//SYP
return 0;
}

最后

以上就是激情月光为你收集整理的Codeforces Global Round 16 2021.9.13Codeforces Global Round 16的全部内容，希望文章能够帮你解决Codeforces Global Round 16 2021.9.13Codeforces Global Round 16所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。