[Codeforces Round 963 (Div. 2)](https://codeforces.com/contest/1993)
A. Question Marks
题意
有一场考试一共 道题目，其中答案为A,B,C,D 的题目各 道， 现在你有一份考试的结果，由字母A,B,C,D 组成，请问最多得到多少分。
思路
每种选项最多答对n道题目，我们统计每个选项的出现次数 ，和n取较小值 ，将结果加起来即可。
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
int n;
cin>>n;
string str;
cin>>str;
int cnt[150] = {0};
for(auto & p : str){
cnt[p] ++;
}
int ans = 0;
for(int i = 'A';i<='D';i++){
ans += min(cnt[i],n);
}
cout<<ans<<'\n';
}
signed main(){
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
|
B. Parity and Sum
题意
给你一个由n个正整数组成数组a ， 你每次操作可以选择两个下标 undefinedi,j)a_ia_ja_ia_ja_i+a_j$ 。
问最少需要操作几次才能够使得数组a中的所有的数奇偶性相同。
思路
我们将奇数和偶数分开来， 奇数在数组odd中，偶数在数组even中 ， 那么我们每次操作即为从odd和even中各选择一个数， 最后目标为使odd数组为空或者even数组为空。
首先，如果odd数组初始为空，或者even初始数组为空，那么答案即为0 。
因为我们每次操作一定选择的是一个奇数和一个偶数，那么我们最终加和后的结果一定是奇数 ，于是每次操作只会使得奇数越来越多，偶数越来越少。
下面给出结论： 假设起初有个偶数 ，那么需要的操作次数最少为， 最多为 。
我们假设选择的奇数为 ，偶数为。 如果 那么会让奇数 变为另一个奇数 ； 如果 那么会让偶数变为奇数 。即只有第二种操作才能令偶数的数量减少一个。 因此最少需要cnt次才能将所有的偶数变为奇数。
因此我们应该尽可能地保证每次选择的奇数比偶数要大，于是我们每次一定会选择目前最大的奇数 , 如果在这种选择下仍然会出现奇数更小的情况，那么我们就一定无法在cnt次操作下完成目标了。 此时我们可以选择将mx和最大的偶数进行操作，得到的新的奇数一定比所有的偶数大，之后每次都选择这个奇数，便可以保证每次都满足奇数大于偶数了。 最终需要cnt+1次操作。
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
int n;
cin>>n;
vector<int> odd,even;
for(int i =1;i<=n;i++){
int x;cin>>x;
if(x%2) odd.push_back(x);
else even.push_back(x);
}
if((!odd.size()&&even.size())) {cout<<"0"<<endl;return ;}
if((odd.size()&&!even.size())) {cout<<"0"<<endl;return ;}
sort(odd.begin(),odd.end());
sort(even.begin(),even.end());
int sz = even.size();
int mx = odd.back();
queue<int> q;
for(auto p:even) q.push(p);
int ans = 0;
while(q.size()){
if(mx > q.front()) {
ans++;
mx = mx + q.front();
q.pop();
}else{
ans ++;
mx = mx + q.front();
}
}
cout<<min(ans,sz+1)<<'\n';
}
signed main(){
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
|
C. Light Switches
题意
有n个房间，每个房间都有一盏灯，起初所有的灯都是灭的，第个房间会在 的时间刻转换灯的状态，即在 区间内亮灯。
问最早在哪个时刻，能保证所有n盏灯都是亮着的。如果不存在某个时刻所有的灯都是亮着的，那么输出-1 .
思路
题意即为将所有房间的亮灯区间取交集，然后取最小值。
我们可以对所有的房间按照 从小到大进行排序 ，然后依次取交集， 因为每个区间都为重复区间，所以每次取交集后一定也为 重复区间，于是我们只需要使用undefinedl,r)[l+j*2k,r+j*2k]$ 即可。
起初 ,之后我们遍历每个区间 , 如果当前遍历的区间与交集的初始区间 相差距离超过 便可以通过令 都加上个（其中 ），来使得两个区间的左端点的距离不超过 ， 此时如果 那么取交集一定为空，我们尝试让 再向后移动一个 ，试图令 与取交集。 （取交集即为 ）
如果某次遍历时使得 那么此时交集已经为空，直接输出-1即可。
如果遍历结束，那么最终的答案即为 。
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
int n,k;
cin>>n>>k;
vector<int>a(n+5);
rep(i,1,n) cin>>a[i];
sort(a.begin()+1,a.begin()+1+n);
int l = a[1];
int r = a[1] + k - 1;
for(int i=2;i<=n;i++){
if(a[i] <= r && a[i] >= l){
l = a[i];
}
int t = (a[i] - l) / (2*k);
l += t * 2 * k;
r += t * 2 * k;
if(a[i] > r){
l+=2*k;
r+=2*k;
}
l = max(l,a[i]);
r = min(r,a[i]+k-1);
if(l > r) {
cout<<"-1\n";
return ;
}
}
cout<<l<<'\n';
}
signed main(){
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
|
D. Med-imize
题意
有一个长度为n的数组 (注意本题的数组下标从0开始) ， 以及一个整数 , 我们每次选择一个长度为k的子数组，将其从数组a中删除，直到数组的中的数组元素数量不大于k。
问最终数组a的中位数最大是多少。本题的中位数为对数组的元素排序后，第undefinedfrac{sz+1}{2}sz$为数组的长度。
思路
我们可以二分答案来求最终的中位数 。于是问题变成了： 给定一个数mid ，能否存在一个最终数组 ，使得 中的大于等于mid的数的数量，比小于mid的数的数量更多。
我们将满足 的元素设置为 , 否则就设置为 。 我们尽可能让最终选出的 数组的和尽可能大，最后判断是否大于0即可。
但是我们不能任意选择剩下的元素，最终一定会剩下m个元素( ) ，并且最终剩下的数组 即选出的最终的下标为的数的原始下标一定在的同余集中。
很好证明这点： 假设我们选出了第3个数（即下标为2），那么之前一定进行过选择了2个数，然后又删除了几组数（每组一定为k个数），所以这个数的原始下标一定为 。
我们用 表示考虑前个数，数组最大为多少，由于我们每次只能成组地删除元素，那么就代表了如果我们选择不要 这个元素，那么 , 而如果我们选择要这个元素，那么 ， 最终比较 是否成立即可。
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int a[500005];
int b[500005];
int dp[500005];
int n,k;
bool check(int mid){
for(int i = 0;i < n;i++){
if(a[i] >= mid) b[i] = 1;
else b[i] = -1;
}
dp[0] = b[0];
for(int i = 1;i<n;i++){
if(i%k == 0){
dp[i] = max(dp[i-k],b[i]);
}else{
dp[i] = dp[i-1] + b[i];
if(i > k)
dp[i] = max(dp[i],dp[i-k]);
}
}
return dp[n-1] > 0;
}
void solve(){
cin>>n>>k;
rep(i,0,n-1) cin>>a[i];
int l,r;
l = 1;r = 1e9;
while(l<r){
int mid = (l+r+1)>>1;
if(check(mid)){
l = mid;
}else{
r = mid-1;
}
}
cout<<l<<'\n';
}
signed main(){
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
|
