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代码

#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代码

#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代码

D. Rocket

题意

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

题解

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

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

AC代码

#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;
}