Codeforces Round #499 (Div. 2)

Codeforces Round #499 (Div. 2)](http://codeforces.com/contest/1011)

A. Stages

题意

给定一段序列,每个字母代表这一个权值,比如$a$代表$1$。之后问从中挑选出一个序列,要求$a[i]$和$a[i+1]$之间相隔一个字母,问从任意顺序选择$k$个字母,最少可以有多少权值。

题解

贪心,其实如果取最大值的话, 我就有点不会了。但是取最小值可以贪心的对所有位置都取能取的最小值。

AC代码

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;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,k;
const int maxn = 60;
char s[maxn];
int a[maxn];
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d%d",&n,&k);
scanf("%s",s);
int len = strlen(s);
rep(i,0,n) a[i] = s[i] -'a'+1;
sort(a,a+len);
int ans = 0;int t = 0;int si = -3;
rep(i,0,len){
if(si<a[i]-1 && t<k){
ans +=a[i];
t++;
si = a[i];
}
}
if(t==k){
printf("%d\n",ans);
}else{
puts("-1");
}
return 0;
}

B. Planning The Expedition

题意

每个人每天都要吃一个特定种类(由你分配)的食物,你现在有$k$种食物,每个食物都有对应的数量,问怎么分配可以在当前食物下过存活尽量多的天数。

题解

二分枚举答案(坑爹cf,$m<100$二分都不用)。因为答案是递减的。

AC代码

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<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int m,n;
const int maxn = 110;
int a[maxn],b[maxn];
bool cmp(int a,int b){
return a>b;
}
int cnt,ans;
void dfs(int day,int idx,int p){
if(p <= 0){
ans = max(ans,day);
return;
}
if(idx ==cnt) return;
for(int i=1;i<=a[idx];i++){
if(a[idx] / i < day) continue;
dfs(day,idx+1,p-i);
}
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
rep(i,1,m+1){
int x;scanf("%d",&x);
a[x]++;
}
ans = 0;
sort(a+1,a+m+1,cmp);
rep(i,1,101) if(a[i]==0) {cnt = i;break;}
for(ans = 1;ans<=100;ans++){
int peo = 0;
rep(i,1,10){
peo += a[i]/ans;
}
if(peo <n){
break;
}
}
printf("%d\n",ans-1);
return 0;
}

C.Fly

题意

每次降落和出发都需要消耗燃料,问最少带多少燃料可以来一次旅行。

题解

小学奥数题,反向做即可。

AC代码

1
2


D. Rocket

题意

猜数字,你问至多$60$次数字,他给出你问的数字是大了还是笑了,他有一个循环答题方案,比如第一次打错,第二次答对,循环少于$30$次。让你问出答案。

题解

循环至多$30$次暗示了你可以故意说一些已知的问题来试他。比如问-1是大了还是小了。之后就是简单的二分了。

心路历程:第一次做交互题,输入输出完全搞不懂。

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m;
bool vis[100];
int query(int x){
int y;
cout<<x<<endl;
fflush(stdout);
cin>>y;
return y;
}
int main(){
#ifdef LOCAL
//freopen("4.in","r",stdin);
#endif
scanf("%d%d",&m,&n);
rep(i,0,n){
int x = query(1);
if(x == 0){
cout<<1<<endl;
return 0;
}
if(x<0) vis[i] = 1;
}
int mid = 0;int cnt = 0;
int l,r;
l = 1,r = m;
while(l<=r){
mid = (l+r)>>1;
int y = query(mid);
if(vis[cnt]) y = -y;
if(y==1) l = mid+1;
else if(y==-1)r = mid-1;
else{
cout<<mid<<endl;
return 0;
}
cnt = (cnt+1)%n;
}
return 0;
}