A-Median Maximization
题意
给出n和s，求n个数字和为s的情况下，求中位数的最大值。
思路
签到题，贪心，中位数前面全为0，后面都平均下来，如果不是整数，那么就在给后面让它最大
代码
当时是用的隐藏掉的部分，因为时间不等人，分情况百分百对就没有考虑那么多了...好吧是我菜了
1
2
3
4
5
6
7
8inline void Case_Test() { cin>>n>>s; //if (n%2==1) n-=n/2; //else n-=(n-1)/2; n-=(n-1)/2; cout<<s/n<<endl; }
B-MIN-MEX Cut
题意
MEX就是没出现的最小数字，给一个01串，可以将这个字符串求最小的MEX和是多少。
思路
我们可以看出，如果有"01"的话，那么就是2，这样划不来，实际上我们可以将一个"01"直接分成"0"和"1"，这样的话答案只贡献了1(1+0)，因为MEX("1")=0，那么我们就将1分割开来，看有多少个"01"，但是最后要取min(2,ans)，因为答案最多才是2，不可能比2还多，因为我们什么也不选，选择原串才到2，只出现了01，MEX(s)=2
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19inline void Case_Test() { cin>>s; l=s.length(); ans=0; if (s[0]=='1') ans+=0,pre=1; else ans+=1,pre=0; //cout<<ans<<" "<<pre<<endl; for (int i=1;i<l;i++) { tmp=s[i]-'0'; if (tmp==pre) continue; if (tmp==1) // tmp=0 ans+=0,pre=1; else //tmp = 1 ans+=1,pre=0; } cout<<min(ans,2)<<endl; }
C-MAX-MEX Cut
题意
给出一个两行的字符串，跟B很像，可以将原串分为若干个两行子串，求最大的MEX和，好吧，大致是这个意思。
思路
这个两行好难打，还得用latex，我还是简单写吧，还是按照B题一样看，一行一行相邻的比较，大致就是遇到一列是"01"的话就直接ans+=2，因为贪心嘛，要求最大的MEX和，那么遇到能凑2的就凑2...然后我当时做题，就是前一列是{00,01,11}和后一列是{00,01,11}一共三三得九种情况，然后判断，大致就能贪心出来了，比如如果前一列是"00"后一列是"11"，那么这个时候能凑出2了，然后清零（具体清零操作就是pre=-1）
但是注意一点，如果是"00"遇到"01"，我这里wa了一发，就是这时候得分开算，ans+=3，因为可以分成两个，前面"00"贡献是1后面的"01"贡献是2。
代码
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
44inline void Case_Test() { int ans=0; cin>>n>>s1>>s2; for (int i=0;i<n;i++) a[i]=s1[i]+s2[i]-'0'-'0'; pre=a[0]; if (a[0]==1) ans+=2,pre=-1; //for (int i=0;i<n;i++) cout<<a[i]<<" "; //cout<<endl; for (int i=1;i<n;i++) { int t=a[i]; //cout<<i<<" "<<a[i]<<" "<<pre<<endl; if (pre==-1) { pre=t; if (t==1) pre=-1,ans+=2; continue; } if (pre==0) { if (a[i]==0) ans+=1; if (a[i]==1) ans+=3,pre=-1; if (a[i]==2) ans+=2,pre=-1; } else if (pre==1) { ans+=2; pre=-1; } else if (pre==2) { if (a[i]==0||a[i]==1) ans+=2,pre=-1; else pre=2; } //cout<<i<<" "<<ans<<endl; } if (pre==0) ans++; if (pre==1) ans+=2; //cout<<pre<<endl; cout<<ans<<endl; }
D1-Seating Arrangements (easy version)
题意
给出一个n和m，在这个题目n=1，是简单版本。然后一共有n*m个座位，每个人都有一个视力值，视力小的坐前面，然后问不方便值是多少，不方便值就是越过有人坐的位置，每个人进入座位的顺序都是按照读入的顺序。
思路
当n=1,m最大也才300，那么我们可以按照一边读入一边来算前面有多少，直接暴力两层循环搞定，重点是在第二题D2
代码
1
2
3
4
5
6
7
8
9
10
11
12inline void Case_Test() { cin>>n>>m; ans=0; for (int i=1;i<=n*m;i++) { cin>>a[i]; for (int j=1;j<i;j++) if (a[i]>a[j]) ans++; } cout<<ans<<endl; }
D2-Seating Arrangements (hard version)
题意
题意就是如D2，具体就是看原题吧
思路
按照第一题的思路，我们来想第二题的暴力思路，然后想办法优化降时间复杂度，这里直接讲吧。
因为要求最小，所以按照模拟，每个进入顺序都会进入到一个固定的位置，假如有相同的，那么先进入的会进入到后面的座位，因为如果相反，那么下一个相同的数会跨过ta，ans++。所以我们用结构体，然后sort一遍（手写cmp）得到每个人应该到的位置，最后循环来进一步判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16struct node { int v,pos; }b[N]; int n,m,t,x,y; struct carry { int v,x,y; }a[N]; int ans,tmp; vector<int> v[301]; inline bool cmp(node x,node y) { if (x.v==y.v) return x.pos<y.pos; return x.v<y.v; }
暴力：一个二维数组a[i][j]来表示位置，每进入一个人就填入它，然后循环模拟前面有多少个，这样的时间复杂度是O(n^3)，不太现实，所以我们来降一个时间复杂度。因为每一行都是升序的，所以我们就用二分来看，但是如果是数组的话没进入就是0的话就不太行，所以换一种容器，我第一个想到的是set，set可以插入，插入后是有序的，但是我不知道可以这样...
1set<int> s[n];
我后面想的是vector容器，但是插入的话又不能有序插入，所以...我上网搜了，可以这样：
1v[x].insert(lower_bound(v[x].begin() , v[x].end() , a[i].v) , a[i].v);
这样我们就能模拟每一个v[x]（x代表x排/行）中的几个人，视力是多少，当每次进入一个人的时候，就先提取出它应该在哪个x行，然后用二分(O(logn))判断在哪一个位置（前面有多少个） ，所以一共时间复杂度是O(Tn^2logn)
1
2
3
4
5
6
7
8for (int i=1;i<=n*m;i++) { x=a[i].x; tmp=lower_bound(v[x].begin() , v[x].end() , a[i].v)-v[x].begin(); ans+=tmp; v[x].insert(lower_bound(v[x].begin() , v[x].end() , a[i].v) , a[i].v); //cout<<i<<" "<<tmp<<endl; }
代码
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#include<stack> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<cstring> #include<deque> #include<vector> #include<iostream> #include<map> #include<unordered_map> #include<set> #include<iomanip> #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ll long long #define endl "n" #define debug(a) cout<<#a<<"="<<a<<endl; #define eps 1e-8 using namespace std; ll GCD(ll a,ll b){while(b^=a^=b^=a%=b);return a;} const int inf=0x3f3f3f3f; const int N = 90007; struct node { int v,pos; }b[N]; int n,m,t,x,y; struct carry { int v,x,y; }a[N]; int ans,tmp; vector<int> v[301]; inline bool cmp(node x,node y) { if (x.v==y.v) return x.pos<y.pos; return x.v<y.v; } inline void Case_Test() { cin>>n>>m; for (int i=1;i<=n*m;i++) { cin>>a[i].v; b[i].v=a[i].v; b[i].pos=i; } sort(b+1,b+1+n*m,cmp); x=n;y=m; for (int i=n*m;i>=1;i--) { t=b[i].pos; a[t].x=x; a[t].y=y; y--; if (y==0) y=m,x--; } //for (int i=1;i<=n*m;i++) cout<<a[i].v<<" "<<a[i].x<<" "<<a[i].y<<endl; ans=0; for (int i=1;i<=300;i++) v[i].clear(); for (int i=1;i<=n*m;i++) { x=a[i].x; tmp=lower_bound(v[x].begin() , v[x].end() , a[i].v)-v[x].begin(); ans+=tmp; v[x].insert(lower_bound(v[x].begin() , v[x].end() , a[i].v) , a[i].v); //cout<<i<<" "<<tmp<<endl; } cout<<ans<<endl; } signed main() { #ifndef ONLINE_JUDGE freopen("IO\in.txt","r",stdin); freopen("IO\out.txt","w",stdout); clock_t start, end; start = clock(); #endif IOS int _=1; cin>>_; while (_--) { Case_Test(); } #ifndef ONLINE_JUDGE end = clock(); cout << endl << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "sn"; #endif }
E-Buds Re-hanging
题意
给出一个树，你可以将芽连上别的顶点（这个顶点不能是自己这一支，实际上就是保证还是一棵树），求问经过若干个操作后最少的叶子树是多少。
思路
曹佬：dfs找芽，叶，其他。找到芽之后直接把芽断开。答案是芽上的叶子+其他叶子-芽数。注意特判根
代码
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#include<stack> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<cstring> #include<deque> #include<vector> #include<iostream> #include<map> #include<unordered_map> #include<set> #include<iomanip> #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ll long long #define endl "n" #define debug(a) cout<<#a<<"="<<a<<endl; #define eps 1e-8 using namespace std; ll GCD(ll a,ll b){while(b^=a^=b^=a%=b);return a;} const int inf=0x3f3f3f3f; const int N = 2e5+1; struct node { int to,next; }edge[N<<1|1]; int head[N],cnt; inline void add(int x,int to) { edge[++cnt].to=to; edge[cnt].next=head[x]; head[x]=cnt; } int u,v,n,num_ya,num_ye,ans; inline int dfs(int x,int pre) { bool ya=true; int cnt=0; for (int i=head[x];i;i=edge[i].next) { int y=edge[i].to; if (y==pre) continue; int t=dfs(y,x); //t=0 wu t=1 ye t=2 ya if (t==0) ya=false; if (t!=2) cnt++; //cout<<cnt<<" "<<num_ya<<" "<<num_ye<<" "<<ans<<endl; } //cout<<cnt<<" "<<num_ya<<" "<<num_ye<<" "<<ans<<endl; if (cnt&&ya&&x!=1) { num_ya++; ans+=cnt; return 2; } //ya if (cnt==0&&x!=1) return 1; //ye if (x==1&&cnt==0) cnt++; //cout<<cnt<<" "<<num_ya<<" "<<num_ye<<" "<<ans<<endl; num_ye+=cnt; return 0; //wu } inline void Case_Test() { cin>>n; memset(head,0,sizeof(head)); for (int i=1;i<n;i++) { cin>>u>>v; add(u,v);add(v,u); } ans=0;num_ya=0;num_ye=0;cnt=0; dfs(1,-1); cout<<max(1,ans-num_ya+num_ye)<<endl; } signed main() { #ifndef ONLINE_JUDGE freopen("IO\in.txt","r",stdin); freopen("IO\out.txt","w",stdout); clock_t start, end; start = clock(); #endif IOS int _=1; cin>>_; while (_--) { Case_Test(); } #ifndef ONLINE_JUDGE end = clock(); cout << endl << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "sn"; #endif }
F-Points Movement
待补
总结
这一场上了大分+178，马上1500了，小号也1404，冲冲冲！
最后
以上就是谦让人生最近收集整理的关于Codeforces Global Round 16 A-E 部分题解的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。
发表评论 取消回复