ACM-ICPC 2020 线下新生选拔赛第一场

前言

此篇是我自己对SAU ACM-ICPC 2020 线下新生选拔赛第一场的题的理解，不代表是正确的题解，本文中不按题目顺序，按难易程度来

ACM, make it possible!

题目描述
废话，不用看

输入格式
无

输出格式
ACM, make it possible!

思路
求求了，这种打印东西的题，一定要复制qaq

code

int main(){
    printf("ACM, make it possible!");
}

成为想要成为的猫

题目描述
有一只猫猫在看一个数字，当然猫猫看不懂人类的数字，这串数字要你来解答。
如果一个非零的个位数（不包括未出现的数字）在一个数字中出现的次数是它本身的倍数，那么这个个位数就是猫猫的幸运数字。
现在给出一个数字，请按 至 的顺序输出这个数字中出现的所有幸运数字。

输入格式
一个数字n(1<=n<=10^100)。

输出格式
所有的幸运数字。

思路
数字这么大肯定就字符串读入，然后对每个字符-'0'，变成数字，到对应的数组里面值+1，最后取个余看看是不是等于0就行。

code

int t[15];
int main()
{
   char s[105];
   
   cin>>s;
   int len=strlen(s);
   for(int i=0;i<len;i++){
       t[s[i]-'0']++;
   }
   for(int i=1;i<10;i++){
       if(t[i]%i==0&&t[i]){
           printf("%d ",i);
       }
   }
   return 0;
}

在等待一杯香甜的牛奶

题目描述
身高只有1米5的a喜欢喝牛奶，因为想长高。
但是这次的故事和a没有关系。
b小姐会从一些农场中定期采购牛奶，并且每个农场的奶价是不一样的，每天每个农场也只能提供一定数量的牛奶。
b小姐每天都有一个对牛奶的需求量，她想知道这一天她最少需要花多少钱才能满足自己（保证总产量大于需求量）。

输入格式
第一行两个整数n,m(1<=n<=2*10^6,1<=m<=5000)，表示需要牛奶的数量和农场的数量。
接下来m行，每行两个整数w,q(1<=w<=10^3,1<=q<=10^6)，表示第i间农场奶的单价和提供奶的数量。

输出格式
一行一个整数，表示最小费用。

思路
一定要读好题再写- -，我没读明白题直接敲代码，导致以为单价是总价，没啥好说的，就一个结构体排序，然后判断当前q是不是已经超过n了，如果没超过，相乘求和，n-当前q；如果超过了，n*w，输出。

我们伟大的人形和炮姐又给了一个新的思想：桶排

code

struct st
{
    double w,q;
}s[5005];
bool cmp(st a,st b){
    return a.w<b.w;
}

int main(){
    int n,m;
    int ans=0;
    cin>>n>>m;
    for(int i=0;i<m;i++) cin>>s[i].w>>s[i].q;
    sort(s,s+m,cmp);
    //for(int i=0;i<m;i++) cout<<s[i].w<<" "<<s[i].q<<endl;
    for(int j=0;;j++){
        if(s[j].q>n){
            ans+=n*s[j].w;
            break;
        }
        n-=s[j].q;
        ans+=s[j].q*s[j].w;
        //cout<<ans<<endl;
        if(n==0) break;
    }
    cout<<ans<<endl;
}


//桶排思想
int t[5005]={0};
int main(){
    int n,m;
    int w,q;
    int ans=0;
    cin>>n>>m;
    while(m--){
        cin>>w>>q;
        t[w]+=q;
    }
    for(int i=1;;i++){
        if(t[i]>n){
            ans+=n*i;
            break;
        }
        n-=t[i];
        ans+=t[i]*i;
    }
    cout<<ans<<endl;
}

那一定是灾难对吧

题目描述
我们的蒟蒻魔术师小姐 h 做了个美梦，梦到自己有了一大笔钱，醒来之后却发现只是个梦，还要继续面对现实。
她又要帮助极东魔术协会统计今年得奖的人并帮忙发放奖励了。

• G：奖励 8000G，要求：普通魔术师魔术水平全国统一测试（下称魔考）成绩高于 80 分，且击杀一名及以上魔术杀手。
• B：奖励 4000G，要求：魔考 85 分以上，且协会评测成绩 80 分以上。
• P：奖励 2000G，要求：魔考 90 分以上，且协会评测成绩 70 分以上。
• F：奖励 1000G，要求：魔考 85 分以上。
• C：奖励 850G，要求：协会评测 85 分以上且在协会内任职。

只要符合条件就可以获得对应的奖励，每位魔术师可获得多个不同的奖励。题目保证一定会有人获得奖励。
现给出多名魔术师的数据，请帮助忙碌的 h 小姐完成工作。

输入格式
第一行一个整数n(1<=n<=1000) ，表示魔术师总数。
接下来n行，每行从左到右依次为姓名，魔考成绩，协会评测成绩，是否在协会内任职，及击杀魔术杀手数量。其中，姓名为仅由大小写英文字母组成的长度不超过 20 的字符串；魔考成绩与协会评测成绩为 0 至 100 之间的任意整数；是否在协会内任职由单个字符表示，Y为是，N为不是；击杀数量为 0 至 10 之间的任意整数。

输出格式
第一行是获得奖金最多的魔术师姓名，若获奖者为 Hibiki 则在本行姓名后额外输出Hibiki txdy!（以空格分隔）。
第二行是该魔术师所获得的奖金数量。
第三行是所有魔术师获得的总奖金数量。
（注：若奖金最多者出现多位，则输出第一次出现的魔术师。）

思路
结构体的加减法，直接码！

code

struct st
{
    char s[25];
    int mk,xh;
    char rz[5];
    int js;
    int all;
}s[1005];


int main(){
    int n;
    int ans=0,ansi=0;
    long long all=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i].s>>s[i].mk>>s[i].xh>>s[i].rz>>s[i].js;
        s[i].all=0;
        if(s[i].mk>80&&s[i].js!=0) s[i].all+=8000;
        if(s[i].mk>85&&s[i].xh>80) s[i].all+=4000;
        if(s[i].mk>90&&s[i].xh>70) s[i].all+=2000;
        if(s[i].mk>85) s[i].all+=1000;
        if(s[i].xh>85&&s[i].rz[0]=='Y') s[i].all+=850;
        if(s[i].all>ans){
            ans=s[i].all;
            ansi=i;
        }
        all+=s[i].all;
    }
    cout<<s[ansi].s;
    if(strcmp(s[ansi].s,"Hibiki")==0) cout<<" "<<"Hibiki"<<" "<<"txdy!";
    cout<<endl;
    cout<<s[ansi].all<<endl;
    cout<<all<<endl;
}

在无限延伸的梦想后面

题目描述
h 最近在玩一个经营模拟游戏，现在她有 n 件物品需要排队等待制造。
这 n 件物品按照制造顺序从 1 到 n 编号，每件物品都有一个制造消耗的时间 。
一共有 m 座制造站，单个制造站每次只能制造一件物品。
开始制造时，1 到 m 号物品分别占据一个制造站，同时开始制造，当某件物品完成制造时，会立即有下一件物品顶替该物品的位置开始制造（某件物品 t 秒制造完时，下一件物品会从 t+1 秒开始制造）。
h 特别菜，所以她想问问你这些物品按顺序制造需要多久才能制造完。

输入格式
第一行两个整数 n,m(1<=m<=100,1<=n<=10000 且 m<=n)，分别表示物品数与制造站数。
接下来一行有 n 个整数，第 i 个数字 t(1<=t<=100) 表示第 i 件物品需要花费的制造时间。

输出格式
一行一个整数，表示制造所有物品需要花费的时间。

思路
这题不应该在这个位置的，只是我想多了，我刚开始想的是：

然后我想先用sort试一下，写的是下边这个，今天问完人形，人形跟我说的是这个：

然后我：

草！（一种植物）

code

int main()
{
    int m,n,x,j=0;
    int ans=0;
    int t[10005];
    int tm[105];
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>x;
        if(j!=m) tm[j++]=x;
        else {
            sort(tm,tm+j);
            tm[0]+=x;
        }
    }
    sort(tm,tm+j);
    cout<<tm[j-1]<<endl;
}

把奇迹聚集起来

题目描述
众所周知，h 喜欢打游戏。最近 h 玩了一堆奇奇怪怪的小 RPG。
这天晚上她做了梦，梦到她在挑战一个魔王，但是魔王实在是太强大啦，菜如 h 根本打不过。
也不知道为什么，h 发现自己有一个特殊的机制叫做奇迹。
想要引发奇迹，就要填满奇迹槽，奇迹槽可以被划分成连续的 n 段，每段奇迹槽初始值都为0。每段所需要的奇迹值都不同，第 i 段奇迹槽所需要的奇迹值为 ki。拥有的奇迹值必须恰好等于 ki 才可以引发奇迹。
h 每次可以选择一个连续区间[L,R] ，使这段区间内的奇迹值增加1 。
h 胆小又菜，她想知道消灭魔王最少需要多少次操作。

输入格式
第一行，一个整数 n(1<=n<=10^5)，表示奇迹槽的划分。
第二行，n 个数，第 i 个数字表示 ki(1<=ki<=10^4)。

输出格式
一行，一个整数，表示最少需要操作多少次。

思路
这题不难，主要看能不能想通，我当时就没想通，太菜了呜呜呜，我们只需要比较当前值与下一个值，如果下一个值小于当前值，那么我在完成当前值的时候，下一个值必能满足，也就是说不用更新ans，如果当前值小于下一个值，ans要加上差值，遍历一遍数组就是答案~

code

int main(){
    int n,x;
    int ans=0,now=0;
    cin>>n;
    while(n--){
        cin>>x;
        if(x>now) ans+=x-now;
        now=x;
    }
    cout<<ans<<endl;
}

许个愿望也许希望就会降临

题目描述
止雨许了个愿望，想要吃比利时黑巧云朵蛋挞，人形决定满足她的愿望。
因为异世界没有KFC ，所以人形找到了魔法师h ，但是众所周知，h 很蒻，需要别人的帮助才能使用魔法。
h 有 n 个魔法球，编号 1 到 n，每个魔法球都有一个魔法值w 。
现在 h 需要执行 m 次操作来完成魔法，每次操作有如下两种：

• f x y表示查询编号 x 到 y 的魔球中的最大魔法值。
• m x k表示把编号为 x 的魔球的魔法值变为 。

现在人形要帮助 h 来完成这次魔法的过程，但是人形睡着了，所以希望你来帮助她实现这个过程。

输入格式
第一行两个整数 ，分别表示魔法球数目和魔法需要操作的次数。
第二行 n 个数，第 i 个数表示第 i 个魔球的魔法值 wi(1<=wi<=10^4)。
接下来 m 行，每行一条指令，格式如题目描述所示(1<=x<=y<=n,1<=k<=10^4)。

输出格式
对于每条查询操作，输出一行一个数字，表示查询结果。

思路
刚才有个朋友问我wls发生什么事了，我说怎么回事，给我发了一道题。我一看!嗷!原来是昨天，校队选拔赛，我想玩玩，啪就点进去许个愿望也许希望就会降临，很快啊!一看，线段树裸题，不码，直接放弃。
结果今天人形：

砸键盘.gif

既然暴力可以过，他怎么要求的就怎么写就行，但是在这里还是建议大家学一下树状数组和线段树~

code

int t[200005];
int main(){
    int n,m;
    int x,y;
    int ans;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&t[i]);
    while(m--){
    	char qs[3];
        scanf("%s %d %d",qs,&x,&y);
        if(qs[0]=='f'){
            ans=0;
            for(int i=x-1;i<y;i++){
                if(t[i]>ans) ans=t[i];
            }
            printf("%d\n",ans);
        }
        else if(qs[0]=='m'){
            t[x-1]=y;
        }
    }
    return 0; 
}