前言

此篇是我自己对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; 
}