codeforces 211 div.2

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A.简单题略

B.简单题略

C.我的方法是“分块”,把字符串一块一块分出来然后处理,对于不用处理的块,直接输出

例如xyzaaijk这样的串,在我的代码里,aa是被分为一个块的,但是aa这个块不造成影响,后来还是直接输出

例如xyzaaaijk这样的串,aaa也被分为一个块,最后直接输出aa

wwwwaaaxxxyybbccdd这样串,看成一个块然后处理,每个连续的字母部分,只能留下1个或2个字母的

所以处理结果为wwaxxybbcdd,为什么不做成waaxyyaccd,因为这样会多一个字母,所以以2,1,2,1,2,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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 2000010

char text[N],str[N];
int lent,lens;

int find(int st,char ch){
for(int i = st; i < lens; i++){
if(str[i] != ch)
return i;
}
return lens;
}

int CUT(int st){
char pre = text[st];
lens = 0; str[lens] = '\0';
for(int i = st; i < lent; i++){
if(text[i] == pre){
str[lens++] = text[i];
pre = text[i];
}
else{
if(lens <= 1) break;
if(i+1 == lent) break;
if(text[i+1] != text[i]) break;
str[lens++] = text[i];
pre = text[i];
}
}
str[lens] = '\0';
if(lens <= 2){
printf("%s",str);
return st + lens;
}
int flag = 0;
pre = str[0];
for(int i = 0; i < lens;){
int id = find(i,pre);
if(flag == 0) printf("%c%c",pre,pre);
else printf("%c",pre);
pre = str[id];
flag = 1 - flag;
i = id;
}
return st + lens;
}

int main(){
while(scanf("%s",text)!=EOF){
lent = strlen(text);
for(int i = 0 ; i < lent; )
i = CUT(i);
puts("");
}
return 0;
}

D.一种贪心的策略,就是“用最富有的k个人(允许他们使用公共资产)去买k个最便宜的车”,因为这样才能

最大程度保证能买到车,如果最富有k个人买到最便宜k个车,那么就将k提升为k+1,k+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
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 100010

int b[N],p[N],n,m,a;

bool check(int num){
LL need = 0LL;
for(int i = 0; i < num; i++){
need += max(p[i] - b[n-num+i] , 0);
}
return (need <= a) ;
}

int main(){
while(scanf("%d%d%d",&n,&m,&a)!=EOF){
for(int i = 0 ; i < n; i++)
scanf("%d",&b[i]);
for(int i = 0 ; i < m; i++)
scanf("%d",&p[i]);
sort(b,b+n);
sort(p,p+m);
m = min(m,n);
int low = 0 , high = m-1 , ans = 0;
while(low <= high){
int mid = (low + high) >> 1;
if(check(mid+1)){
ans = mid+1; low = mid + 1;
}
else high = mid - 1;
}
LL sump = 0LL;
for(int i = 0 ; i < ans; i++)
sump += p[i];
printf("%d %I64d\n",ans,max(sump - a , 0LL));
}
return 0;
}

E.暂无