ZC's blog

自分が選んだ道を、ひざまずいても歩き終わる

ZC's avatar ZC

ABC119

Tasks

Task Name Time Limit Memory Limit
A Still TBD 2 sec 1024 MB Submit
B Digital Gifts 2 sec 1024 MB Submit
C Synthetic Kadomatsu 2 sec 1024 MB Submit
D Lazy Faith 2 sec 1024 MB Submit

A:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int x,y,z;
    cin>>x>>y>>z;
    if(x>2019||(x==2019&&(y>4||(y==4&&z>30))))printf("TBD");
    else printf("Heisei");
}

B:

#include<cstdio>
#define db double
int main(){
    int n;
    db ans=0,x;
    char p[100];
    scanf("%d",&n);
    while(n--){
        scanf("%lf%s",&x,p);
        if(p[0]=='B')x=x*(db)380000.0;
        ans+=x;
    }
    printf("%lf\n",ans);
}

C:

题意:

你有$n(3 \leq n \leq 8)$根棒子,你要把这$n$根棒子中的一部分棒子(可能是全部)凑出长度为$A,B,C(\leq 1000)$的三根棒子。

有三种操作:

  1. 把一根棒子的长度$+1$,花费$1$点
  2. 把一根棒子的长度$-1$,花费$1$点
  3. 把两根棒子拼成$1$根,花费$10$点

求最少花费多少点?

题解:

$n$这么小dfs就可以了,细节比较多。

比如不能凭空多出一条棒子。

#include<bits/stdc++.h>
#define Fur(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
#define N 1000001
int n,a[4],l[10],ans=1000000000;
bool v[10];
void dfs(int d,int res,int t,int f){
    if(t>=ans)return;
    if(d==3){ans=t;return;}
    if(f)dfs(d+1,a[d+1],t+res,0);
    Fur(i,1,n)
    if(!v[i]){
        v[i]=1;
        if(res>=l[i])dfs(d,res-l[i],t+f*10,1);
        else dfs(d+1,a[d+1],t+l[i]-res+f*10,0);
        v[i]=0;
    }
}
bool cmp(int x,int y){return x>y;}
int main(){
    cin>>n>>a[0]>>a[1]>>a[2];
    Fur(i,1,n)cin>>l[i];
    sort(l+1,l+n+1,cmp);
    sort(a,a+3,cmp);
    dfs(0,a[0],0,0);
    cout<<ans<<endl;
}

D:

题意:

有$n(\leq 10^5)$个神社和$m$个庙会在一条线上,坐标分别为$a_i和b_i(\leq 10^{10})$

$q(\leq 10^5)$个询问$x_i$,问从坐标$x_i$开始,经过一个神社和一个庙会最少要走多远。

题解:

懒得二分upper_bound一下就可以了。细节较多。

无非就4种情况,设最近的两个神社的坐标为$L_a,R_a$,最近两个庙会的坐标为$L_b,R_b$

  1. $ x →L_a→L_b$
  2. $x→L_a→R_b$
  3. $x→L_b→L_a$
  4. $x→L_b→Ra​$

细节:

  1. long long
  2. inf要大于$10^{10}$
  3. 有可能这个点在最右或最左,所以要搞两个端点$-inf,inf$
#include<cstdio>
#include<algorithm>
namespace FastIO{const char* ln="\n";struct Reader{char buf[1<<20],*s,*t;bool EOF_FLG;Reader():s(buf),t(buf),EOF_FLG(false) {};char gt() {return s==t&&((t=(s=buf)+fread(buf,1,1<<20,stdin))==s)?EOF:(*s++);}Reader& operator>>(char* str) {if(EOF_FLG)return *str=0,*this;while((*str=gt())!=' '&&*str!='\n'&&*str!=EOF)++str;if(*str==EOF)EOF_FLG=true;*str=0;return *this;}template<typename T>Reader&operator>>(T&x) {if(EOF_FLG)return *this;char c=0,d;while(c!=EOF&&(c<'0'||c>'9'))d=c,c=gt();if(c==EOF){EOF_FLG=true;return *this;}else x=0;while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=gt();if(d=='-')x=-x;return *this;}}in;struct Writer{char buf[1<<20],*s,*t;Writer():s(buf),t(buf+(1<<20)){}~Writer(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,1<<20,stdout),*s++=c):(*s++=c);}template<typename T>Writer&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[40],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}Writer&operator<<(const char*s) {while(*s)pt(*s++);return *this;}}out;}using namespace FastIO;
#define Fur(i,x,y) for(int i=x;i<=y;i++)
int ABS(int x){return x>0?x:-x;}
int MIN(int x,int y){return x<=y?x:y;}
using namespace std;
#define N 100001
#define int long long
#define inf 40010000000
int n,m,q,a[N],b[N];
int qm(int x,int p,int q){return MIN(ABS(x-p)+ABS(p-q),ABS(x-q)+ABS(p-q));}
signed main(){
    in>>n>>m>>q;
    Fur(i,1,n)in>>a[i];a[0]=-inf;a[n+1]=inf;
    Fur(i,1,m)in>>b[i];b[0]=-inf;b[m+1]=inf;
    int x,la,lb,ra,rb,p;
    while(q--){
        in>>x;
        p=upper_bound(a,a+n+2,x)-a;
        la=a[p-1];ra=a[p];
        p=upper_bound(b,b+m+2,x)-b;
        lb=b[p-1];rb=b[p];
        int ans=MIN(MIN(qm(x,la,lb),qm(x,ra,rb)),MIN(qm(x,la,rb),qm(x,ra,lb)));
        out<<ans<<ln;
    }
}