Starry

NENU新生题解第一场

发布于 字数统计 8.4k 字 阅读时长 28 分钟

NENU新生题解第一场

发布于 字数统计 8,362 阅读时长 42 分钟

写题模版(学前必看)

一般写题时,我们会自然而然的打出头文件和主函数等等,但是每道题目都要重复写一遍会很浪费时间,因此我在写题的时候会提前准备一个模板,从而避免反复的浪费时间。接下来我将展示一个比较实用的模板,解决了一些目前可能面对的问题。

引用万能头

我们在初学打代码的时候,会学习到很多封装好的函数,但是这些函数往往不在同一个库下面,所以需要记录非常繁多的函数,导致我们经常忘记每个库都存了什么函数,都是什么用法,因此有了万能头。
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用
“bits/stdc++.h”就是万能头,他包含了我们正常使用c++和c的所有库,但是记住别忘记规定他的命名空间,具体逻辑大家可以自行详细了解,实战中会使用即可。
但是请注意,大家在学习c语言课时,不要因为会用万能头就不记忆一些基础的函数库名,这只是打比赛时的简要写法,不要去拿他偷懒专业课。

习惯使用长整型(longlong)

long long是我们在竞赛中最为常使用的一种数据类型,为了答案的精确度,我们往往会避免数据转化为浮点数,这是因为浮点数在计算机的存储中,一般是不精确的。所以我们会将数据尽可能的放在整数空间中进行计算和转化,而往往题目的数据给出的范围会相当大,所以我们一般用long long长整型来对我们的数据进行存储,而不是int类型接下来我们来看看各类型之间的差别。
当存储超过我们数据类型的数据,会导致我们数据的错误存储,使得我们代码返回“答案错误”(Wrong Answer)。
整数类型占用字节数可以存储的数据范围
int4-2147483648~+2147483647及(-2^31~2^31-1)及1e9左右
long long8-9223372036854775808~+9223372036854775807及(-2^63~2^63-1)及1e18左右
这个表格表明了longlong可存储的数据范围是int的平方倍以上,因此我们往往会使用longlong作为我们的常使用的整形类型,但是这还是得按照具体的题目进行考虑,我们代码有时会碰到“代码超限”(MLE)的情况,这是由于我们在运行代码时,开辟了过多的空间导致的,一般我们在运行代码是不要开辟太大数组基本就可以搞定,并且longlong和int的占用空间也仅仅差了一倍的大小,没有必要为此而舍弃longlong。
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */
 typedef long long ll;
我们在模板中直接使用typedef将longlong定义为了ll,因此我们在之后进行声明时直接使用ll即可,这是一个方便的写法,可以具体了解学习一下,之后c语言课中应该也会涉及到。

模板整体

#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    /**  
     * 后期代码书写区域  
     */}
模板往往能够让节省我们大量的时间,避免在做题时考虑到什么再去添加什么的麻烦操作,每个人都应该有自己比较熟悉的模板。

B2002

这题要求输入对应的字符串,因此我们使用printf对字符串进行输出。
需要注意的是,当我们在对字符串进行存储时候要使用""(双引号),而不是字符的''(单引号)。
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    printf("Hello,World!");  
}

P1001

虽然这题整形计算用int类型并不会导致数据溢出,但是为了培养大家的良好习惯,我们这次用longlong为大家展现一些需要注意的重点。大家在使用longlong存储整型时需要注意,我们输入输出时,我们对应的格式应当是%lld而不是int类型所对应的%d,错误的匹配会导致不可预料的结果,可能导致你的输入异常,a和b存储为0的情况。
还有在使用scanf和printf时需要注意的是,scanf中不要忘记&,&是取址符,具体作用可以在c语言课上具体关注,这里不做过多的解释,需要记住的是在字符串输入时没有&。新手常常会因为没有&导致报错半天无法解决。
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    ll a,b;  
    scanf("%lld %lld",&a,&b);  
    printf("%lld",a+b);  
}

P5715

这题其实是一个比较简单的判断就可以实现相应的功能,三个数的排序,我们可以确定一个的位置之后固定其他两个人都位置即可。
因为要排序,我们必然会涉及到两个数交换的操作,但是计算机上的交换操作并没有我们想象的那么简单。假设我要将a和b进行交换,并不是我把a赋值给b,b赋值给a即可。当我们将a赋值给b时,b已经是a的值了,当我们将b赋值给a的时候,b是a的值而不是原先b的值,所以a的值不会有变化。所以当我们进行交换操作的时候,应当有一个辅助变量来帮助我们完成这个任务,他往往是对即将被赋值的数进行存储,避免他被覆盖后数据消失,其代码为:
tmp=a;  
a=b;  
b=tmp;
现在我们要对abc进行从小到大的排序,我们只需要保证a的位置上是最小的,我们再对b和c进行调整即可。
讨论如何将最小数放在a上时,我们只需要判断b和c是否为三个最小的即可:
if(b<a&&b<c)  
{  
    tmp=a;  
    a=b;  
    b=tmp;  
}  
else if(c<a&&c<b)  
{  
    tmp=a;  
    a=c;  
    c=tmp;  
}
随后我们对后两个数进行讨论:
if(b>c)  
{  
    tmp=b;  
    b=c;  
    c=tmp;  
}
因此整合后的代码为:
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    ll a,b,c,tmp;  
    scanf("%lld%lld%lld",&a,&b,&c);  
    if(b<a&&b<c)  
    {  
        tmp=a;  
        a=b;  
        b=tmp;  
    }  
    else if(c<a&&c<b)  
    {  
        tmp=a;  
        a=c;  
        c=tmp;  
    }  
    if(b>c)  
    {  
        tmp=b;  
        b=c;  
        c=tmp;  
    }  
    printf("%lld %lld %lld",a,b,c);  
}

P5703

此题就是一个比较简单的两个数乘法,不需要过多的讲述,需要关注的是乘法后数据是否仍在我们的数据范围之内,当两个存着1e9大小int类型的数进行乘法运算,其结果是1e18,这明显的超出了前面所说的int类型的数的范围,因此会造成溢出,这种题目应当使用longlong进行存储,但是题干中已经表明数据结果和输入都在int范围之内,所以不需要考虑以上问题。
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    ll a,b;  
    scanf("%lld %lld",&a,&b);  
    printf("%lld",a*b);  
}

P5708

此题涉及到一个浮点数计算,但是由于题干中已经给出了公式所以难度大幅降低,需要注意的是,虽然题目样例中给的是3个整数,但是实际上输入的是三个实数,因此我们不能用int或者longlong来接受输入的数据,所以要用浮点数进行存储和输入。
其次这道题目的难点在于格式化的输出,题干要求精确到小数点后1位,因此我们只能保留小数位后的一个数。
但是printf实际为我们提供了相应的方式。我们正常输出浮点数时,只用写%.lf即可,但是我们想要保留固定位数的小数时,我们只需要在%后加上个.x(x为想要精确到的小数位后的个数),就像我想精确一位小数就是%.1lf即可,float型也是同理,但是为了精度我们一般使用double。然而在数字前面保留0或者是空格,在acm的比赛中较少见到,因此大家自行回去了解。
代码是:
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    double a,b,c,p;  
    scanf("%lf%lf%lf",&a,&b,&c);  
    p=(a+b+c)/2;  
    printf("%.1lf",sqrt(p*(p-a)*(p-b)*(p-c)));  
}

P5705

初看这题目非常的复杂,得将浮点数进行倒转,但是仔细观察会发现,数据都是由小数点前的三位数和小数点后的一位数组成的。因此,我们只需要对其进行按位输出即可。
按位输出有个小方法就是,想要哪一位的数字,就将哪一位整除到个位的位置上,再对他进行求余即可,就想12345我想要百位上的3,我只需要对其整除100后,这个数就变成了123,3就到了个位,我只需要求余10分离他个位上的数即可,然后按照格式输出即可。
代码为:
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    double a;  
    scanf("%lf",&a);  
    ll b=a*10;  
    printf("%lld.%lld%lld%lld",b%10,b/10%10,b/100%10,b/1000);  
}

P5709

这题其实就是对题目的理解,最后问我们的是剩余有几个完整的苹果,所以当前我们没有吃完,但是正在吃的苹果也算是不完整的苹果,所以我们在算剩余苹果时还要减去当前在吃的,所以s/t计算吃了几个苹果的时候我们要对其结果进行向上取整。

如何进行向上取整

之前我提及了在计算的时候尽可能的将数据按照整数进行计算,否则浮点型的不精确性可能会导致你的结果有细小的误差,最后无法挽回的答案错误。
但是向上取整不用浮点型又如何做到呢?
我们可以想一下,什么情况下我们要向上取整加一,其实就是在s不能被t整除到时候,那么我们只需要排除整除到情况加一即可,所以我们在整除的时候对s加上一个t-1,因为t-1被t整除为0,这就能保证如果s本来是被t整除的时候,加上t-1也不会使其结果加上1,而任意不能被整除的都能使结果加一。
这个方法非常重要,经常被运用到题目当中去,请大家牢记。
(s+t-1)/t;//向上取整

快速让负数变成0

这道题是计算苹果完整的有几个,实际上除了整除问题以外还有一个问题就是,当时间充裕的情况下,我们计算出来我们吃掉的苹果个数是超过拥有的苹果个数的,所以判断苹果是否被吃完。
这里有个小技巧,就是当苹果吃完的时候我们的结果是负数,所以只需要将负数变为0即可,那我们只需要对结果和0进行一个去最大的操作即可。
	max(0ll,m-((s+t-1)/t));
这里有人可能就要问0ll是什么东西,难道不是0吗?
因为我们普遍运用longlong整形,然而常数默认的数据类型其实是用int,然而max这个方法他只能对于两个相同的数据类型进行比较,所以我们要将两边的数变成相同数据类型,0ll就是0的longlong数据类型的表示。

判断除数为0的情况

在现实生活中我们明确的说明了除数为0的情况是不存在意义的,所以当我们进行除法的时候一定要讨论除数有没有可能为0,当除数为0的时候评测机系统会返回运行错误(Runtime Error)的标识。
这道题确实拥有除数为0的情况,但是我其实除数为0在这道题目里面非常扯淡,但是无话可说,还是跟着题目走吧。
除数为0实际就是,我们吃苹果的速度为0,就相当于我有超光速,我在0秒内就能将苹果全部吃完,所以直接输出0即可。

代码

#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    ll m,t,s;  
    scanf("%lld%lld%lld",&m,&t,&s);  
    if(t==0)  
    {  
        printf("%lld",0ll);  
    }  
    else  
    {  
        printf("%lld",max(0ll,m-((s+t-1)/t)));  
    }  
}

P1425

这题如果对时和分进行分开讨论的话会非常麻烦,但是有方法可以对其进行巧妙的转换,我们可以将所有的时间转换为分钟表示,因为一个小时就是60分钟,这样可以在算差值的时候大大减少讨论的复杂程度。最后我们只需要将分钟转化为时和分即可,转化为时就是t/60,转化为分就是t%60.
代码为:
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    ll a,b,c,d,t1,t2,t;  
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);  
    t1=a*60+b;  
    t2=c*60+d;  
    t=t2-t1;  
    printf("%lld %lld",t/60,t%60);  
}

P5711

这道题主要就是多个条件判断容易晕,其实就是一个嵌套的情况,我们从覆盖面最小的进行讨论,就是每400必定闰年,然而每100年不闰年,但是每400年闰,所以我们只要判断400的话就能把100的情况排除在外了,4年一闰,不是4就不闰。其实就是按照覆盖范围最小的情况开始讨论即可。
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    ll t;  
    scanf("%lld",&t);  
    if(t%400==0)  
    {  
        printf("1");  
    }  
    else if(t%100==0)  
    {  
        printf("0");  
    }  
    else if(t%4==0)  
    {  
        printf("1");  
    }  
    else  
    {  
        printf("0");  
    }  
}

P5714

这道题只需要按照公式对bmi进行计算,然后对其进行判断,按需求输出即可。
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    double m,h,bmi;  
    scanf("%lf%lf",&m,&h);  
    bmi=m/h/h;  
    if(bmi<18.5)  
    {  
        printf("Underweight");  
    }  
    else if(bmi<24)  
    {  
        printf("Normal");  
    }  
    else  
    {  
        printf("%lf\nOverweight",bmi);  
    }  
}

P5713

该题我们按照公式计算,如果在本地所需的时间就是n*5,而在洛谷上面所需的时间是3*n+11,我们只需要对两者进行对比,我就可以得到答案。
#include "bits/stdc++.h"  
using namespace std;  
//引用万能头,省去一些繁杂库的引用,c++和c语言都库都可以自由使用  
  
/**  
 * typedef 是将一些我们常用的写法进行,简写的工具。  
 * 这里是将长整型longlong简写为了ll,方便我们的声明,  
 * 也同样警醒我们不要忘记日常声明整形时最好使用longlong,  
 * 避免整形存储时溢出导致的答案错误(WA)。  
 */typedef long long ll;  
  
int main()  
{  
    ll n;  
    scanf("%lld",&n);  
    if(n*5>n*3+11)  
    {  
        printf("Luogu");  
    }  
    else  
    {  
        printf("Local");  
    }  
}