AtCoder Beginner Contest 115

Author Avatar
ZC 12月 08, 2018
  • 在其它设备中阅读本文章

比赛链接

Tasks

# Title Time limit Memory limit
A Christmas Eve Eve Eve 2 sec 1024 MB Submit
B Christmas Eve Eve 2 sec 1024 MB Submit
C Christmas Eve 2 sec 1024 MB Submit
D Christmas 2 sec 1024 MB Submit

A:

#include<bits/stdc++.h>
using namespace std;
int main(){
    cin>>n;n=25-n;
    printf("Christmas");
    while(n--)printf(" Eve");
}

B:

题意:

一个人买n件东西,其中最贵的一件半价,求要付多少钱。

#include<bits/stdc++.h>
#define Fur(i,x,y) for(ri i=x;i<=y;i++)
using namespace std;
int main(){
    int n,s=0,ma=0;
    cin>>n;
    Fur(i,1,n){
        int x=gi();
        s+=x;ma=MAX(ma,x);
    }
    s-=ma/2;
    printf("%d\n",s);
}

C:

题意:

从n个数里选k个数,求所有被选的数中的最大数和最小数的差最小为多少?

方法:

排序后O(n)查找

#include<bits/stdc++.h>
#define Fur(i,x,y) for(ri i=x;i<=y;i++)
using namespace std;
#define N 100010
int n,a[N],k,ans=1000000000;
int main(){
    cin>>n>>k;
    Fur(i,1,n)scanf("%d\n",&a[i]);
    sort(a+1,a+n+1);
    Fur(i,1,n-k+1)
        ans=MIN(ans,a[i+k-1]-a[i]);
    printf("%d\n",ans);
}

D:

题意:

Takaha先生决定制作一个多维汉堡。 L级汉堡($L>=0$)是以下内容:

一个0级汉堡是一个小馅饼。
​ L级汉堡($L≥1$)是一个面包 + (L-1)级汉堡 + 一个小馅饼+另一个(L-1)汉堡+另一个面包

例如:

说明:(旋转90度)其中B和P代表面包和馅饼

1级汉堡:BPPPB

2级汉堡:BBPPPBPBPPPBB

Takaha先生将制作的汉堡是一个N级汉堡。 Lachlun the Dachshund将从这个汉堡的底部吃掉X层(每一层是馅饼或面包)。 她会吃多少馅饼?

题解:

很像这道题:Moo

不能直接模拟,要推出一点小规律

我们用$s[d]$代表d级汉堡有多少层馅饼,$l[d]$表示面包和馅饼总共有多少层

按照馅饼够成的规则进行模拟:

#include<bits/stdc++.h>
#define ll unsigned long long
#define il inline
#define Fur(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
ll l[55],n,k,s[55],ans=0;
il void cl(){//预处理s,l
    l[0]=s[0]=1;
    Fur(i,1,50)l[i]=(l[i-1]<<1)+3,s[i]=(s[i-1]<<1)+1;
}
#define chk if(!k){cout<<ans<<endl;exit(0);}
/*
_:空的
.:面包
bk:低一级级汉堡
$:馅饼
*/
il void dfs(ll d){
    if(d==0){
        chk;
        cout<<ans+1<<endl;exit(0);
    }
    chk;//  _
    k--;chk;// .
    if(k>=l[d-1]){ans+=s[d-1],k-=l[d-1];chk;}// .bk
    else dfs(d-1);
    ans++;k--;chk;// .bk$
    if(k>=l[d-1]){ans+=s[d-1],k-=l[d-1];chk;}// .bk&bk
    else dfs(d-1);
    k--;chk;// .bk&bk.
}
int main(){
    cl();
    cin>>n>>k;
    dfs(n);
}