Codeforces Global Round 16 2021.9.13Codeforces Global Round 16

93 阅读 0 评论 62 点赞

我是靠谱客的博主激情月光，这篇文章主要介绍Codeforces Global Round 16 2021.9.13Codeforces Global Round 16，现在分享给大家，希望可以做个参考。

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;
}
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/*
* @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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/*
* @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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/*
* @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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
* @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;
}