A. Median Maximization
题意：
一个长度为n的序列必须单增（不减），且数列的和，且序列的总和为s，求位置 ⌈ n 2 ⌉ lceil frac{n}{2} rceil ⌈2n⌉处的数字最大为多少
思路：
我们就保证 ⌈ n 2 ⌉ lceil frac{n}{2} rceil ⌈2n⌉前面的位置都为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#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5+5; ll n,m,k,s; void solve() { cin>>n>>s; cout<<s/(n-(n+1)/2+1)<<'n'; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int _; cin>>_; // _ = 1; while(_--) { solve(); } return 0; }
B. MIN-MEX Cut
题意：给一个字符串s，可以把s拆分成多个子串，定义mex运算为自然数从小到大第一个在s中没有出现的数，求把s分成的子串中，对每个子串的mex运算最小的和为多少
思路：
只有1肯定mex为0
有0的话mex为1
有1和0的话mex为2
首先如果整个s串不拆分的话，mex为2
mex小的情况：把1和0分开来，使每一个子串要么包含1，要么包含0，问题就变为统计连续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#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5+5; ll n,m,k; string s; void solve() { cin>>s; if(s.size()==1) { if(s[0]=='1') cout<<0<<'n'; else cout<<1<<'n'; return; } int cnt = 0; for(int i=1;i<s.size();i++) if(s[i]!=s[i-1] and s[i]=='0') cnt++; if(s[0]=='0') cnt++; if(cnt<=1) cout<<cnt<<'n'; else cout<<2<<'n'; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int _; cin>>_; // _ = 1; while(_--) { solve(); } return 0; }
C. MAX-MEX Cut
题意：
类似上一题，对同一位置的字符串a和b求mex，求拆分字串的mex 的最大值
0和1贡献为2，0 和0贡献为1，剩下1和1没贡献，我们把1和1 与 0 和 0结合在一起，就能多产生1的贡献，和0和1合在一起，贡献还是不变。
所以我们先统计10 ， 00的贡献，然后求11和00合在一起的贡献
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#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+5; ll n,m,k; bool vis[N]; string a,b; void solve() { for(int i=0;i<N;i++) vis[i] = false; cin>>n; cin>>a>>b; ll res = 0; for(int i=0;i<n;i++) { if((a[i]=='0' and b[i]=='1') or (a[i]=='1' and b[i]=='0')) res += 2; if(a[i]=='0' and b[i]=='0') res += 1,vis[i]=true; } // cout<<res<<'n'; for(int i=0;i<n;i++) { if(a[i]=='1' and b[i]=='1') { if(i and vis[i-1]) res += 1; else if(vis[i+1]) res += 1,vis[i+1] = false; } } cout<<res<<'n'; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int _; cin>>_; // _ = 1; while(_--) { solve(); } return 0; }
D1. Seating Arrangements (easy version)
题意：
一个数组代表视力，位置代表入场顺序，我们尽量安排视力小的在前面，一个人经过的人为不合适度，求不合适度为多少
思路：
以样例为例
2 1 5 3 3为视力大小
1 2 3 4 5为入场顺序
按视力从小到大排序之后入场顺序为：
2 1 5 4 3
结果就是统计逆序对个数，我们使用树状数组离散化求解按照视力大小从小到大排序，若视力相等，下标从大到小排 ，求下标的逆序对
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#include<bits/stdc++.h> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<ll,ll>pll; const int N = 1e5+5; ll n,m,k; pll p[305],a[305]; ll b[305],tr[305]; void add(int x,int y) { while(x<305) { tr[x] += y; x += x&-x; } } ll sum(int x) { ll res = 0; while(x) { res += tr[x]; x -= x&-x; } return res; } void solve() { memset(tr,0,sizeof tr); cin>>n>>m; for(int i=1;i<=m;i++) { cin>>p[i].fi; p[i].se = i; } sort(p+1,p+1+m,[&](pll a,pll b){ if(a.fi==b.fi) return a.se > b.se; return a.fi < b.fi; }); for(int i=1;i<=m;i++) { a[i].fi = p[i].se; a[i].se = i; } sort(a+1,a+1+m); for(int i=1;i<=m;i++) b[a[i].se] = i; ll res = 0; for(int i=1;i<=m;i++) { add(b[i],1); res += sum(b[i])-1; } cout<<res<<'n'; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int _; cin>>_; // _ = 1; while(_--) { solve(); } return 0; }
D.Seating Arrangements (hard version)
思路：
这一题就是处理相同数时的做法实现有难度。
我们先从小到大排序视力，然后对于每组再重新排序一下，就可以实现对于每组的视力，保证相同视力的人横跨两组时，保证大的入场顺序在后面的一组中
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#include<bits/stdc++.h> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<ll,ll>pll; const int N = 1e5+5; ll n,m; pll p[N],a[N]; ll b[N],tr[305]; void add(int x,int y) { while(x<305) { tr[x] += y; x += x&-x; } } ll sum(int x) { ll res = 0; while(x) { res += tr[x]; x -= x&-x; } return res; } void solve() { cin>>n>>m; for(int i=1;i<=n*m;i++) { cin>>p[i].fi; p[i].se = i; } sort(p+1,p+1+m*n); ll res = 0; int cnt = 1; for(int k=1;k<=n;k++) { sort(p+(k-1)*m+1,p+k*m+1,[](pll a,pll b){ if(a.fi == b.fi) return a.se > b.se; return a.fi < b.fi; }); for(int i=1;i<=m;i++) { a[i].fi = p[(k-1)*m+i].se; a[i].se = i; } sort(a+1,a+1+m); for(int i=1;i<=m;i++) b[a[i].se] = i; memset(tr,0,sizeof tr); for(int i=1;i<=m;i++) { add(b[i],1); res += sum(b[i])-1; } } cout<<res<<'n'; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int _; cin>>_; // _ = 1; while(_--) { solve(); } return 0; }
最后
以上就是愉快跳跳糖最近收集整理的关于Codeforces Global Round 16 A-D2A. Median MaximizationB. MIN-MEX CutC. MAX-MEX CutD1. Seating Arrangements (easy version)D.Seating Arrangements (hard version)的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。
发表评论 取消回复