下面是我进大学以后第一次进队(ACM:一种全国性的计算机比赛)后,进行了第一次模拟比赛,一开始大一进队一共有50个人,到了现在(不到一年),仅剩23个人了(现在的大二还剩7个人)。
当时的我是真正意义上的小萌新,看看当时写的总结,还是挺有感慨的。。。
......
2019年ACM10月末总结
从开学到现在,来到队里也有蛮长时间的了,也迎来了队内的第一次正规的模拟比赛,心情说不紧张肯定是假的,但在真正开始比赛的期间,紧张感,压迫感,是加大还是减少,谁又能说的清楚,反正赛已经比完了,结局已定,往事不堪回首……
但回顾这些日子以来,自己从编程零基础到现在C语言的知识已经基本掌握(C++的知识点大部分也都会),看着一行一行代码从自己手中产生,再一个删除键从眼前消失,细细回想好像真的码下了不少代码。
废话不多说,这个比赛的主旨还是巩固自己不会的知识点,还是让代码来说话更能体现这篇总结最根本的价值吧。
下面是对这次比赛的一些解析,如果对这方面不敢兴趣的人,可以直接跳过这部分,看最后的总结。。。(如果不感兴趣:题目1001-1006,直接跳到1006解析那里就可以了)
头文件我就省了,不然占了不少行。。。
1001.qp师哥的亲切关怀,最水的题
这道题一开始就错了,而且错了两次(自己表示心态受到了影响),看到是最水的题自己都做不出来,还是蛮难过的(不过到了最后还好,别人也做不出来)。
代码
int main()
{
doublea, b;
cin>> a >> b;
(1) cout << int(a * b +1e-8)<< endl;
(2) intm=a*b;
cout<< m << endl;
return0;
}
0.58 100
57(如果不加1e-8的话,就会出现精度损失)
Program ended with exit code: 0
知识点
(1)最重要的:精度问题
(2)以前也有专门研究过,就是关于四舍五入到百分位或是十分位,跟直接取整数部分的一些区别,我觉得还是比较有用的。
先说这道题的直接取整数吧,答案直接用int直接转换,没什么可以说的。
再说关于四舍五入的问题(以四舍五入到百分位为例):
1.在输出时直接控制就行(例printf(“%6.2d”,a),或者直接把那个6去掉printf(“%.2d”,a),这两种都是可行的,是四舍五入,而不是直接舍去百分号之后的部分。
2.在大量数据都需要控制的时候用到下图的绿色字体
int main()
{
doublea=1.666;
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
cout<< a << endl;
return0;
}
1.67
Program ended with exit code: 0
3.当然还有更正宗的解法(以money为例)
money=money*100+0.5;
money=(int)(money);//将money乘100加上0.5后的值取整
money/=100;
第一种方法在需要大量小数运算的情况下容易损失精度,这三种方法应当灵活运用。
1002.第几天
这道题在超时一次后就过了(在刚W掉1001两次之后,又超时了简直心态爆炸),不过还好bug让我在最短时间内找出来了。
下面直接附上自己的代码(如果大佬们有其他的,更好的,更简单的可无视我的)
代码
int a[13]={0,31,0,31,30,31,30,31,31,30,31,30,31};
void judge(int x)
{
if(x%400==0 ||(x%4==0&&x%100!=0))
{
a[2]=29;
}
else a[2]=28;
}
int main ()
{
std::ios::sync_with_stdio();
int x,y,z,sum;
while (scanf(“%d/%d/%d“,&x,&y,&z)!=EOF)//因为一开始用的都是cin,这次有/,换用scanf输入,却没有加!=EOF,让它坑了自己一把,因为超时,我还加了一行std::ios::sync_with_stdio(),当然如果我不加!=EOF的话没什么卵用
{
sum=0;
judge(x);
for (int i=1;i<=y-1;i++)
{
sum=sum+a[i];
}
sum=sum + z ;
cout << sum << endl;
}
return 0;
}
错误分析
在cin 与scanf 转换之间不熟悉,while的括号内用cin用习惯了,不加!=EOF,但在使用scanf的情况下切记不可马虎。(因为这道题比较简单就不详解了)
1003.你能找到这个数字么
错误分析
(我是从头开始一道一道题做的)好吧,我承认我做不出这道题来。(一直到最后也没A出来)
在经历了四次超时后,当别人都A出好几题来的时候,当时间缓慢爬过一个多小时之后,我仍在做1003,自认为是简单题,可能这就是高估自己能力的代价吧。
啊,多么痛的领悟~~
啊,我想哭但是哭不出来~~
回顾一下我是怎么说服自己在超时一次后又把代码交上的
(1)三个for循环都是500的,肯定超时啦(我没考虑到,能力有限)
(2)所以第二次我就简单的加入了一行std::ios::sync_with_stdio();
思想简单的我以为这就行了,所以再挂一次。
(3)第三次我又把cin全都转换为scanf ,把cout全都转化为printf,以为这样能过,好吧是我单纯了。
(4)第四次,我终于长了点心眼从自己的程序入手,看能不能简化(自认为超时的程序是对的,毕竟样例过了,好吧,样例过了的,程序错的时候大有时候),我把程序中加入了break终止,以为这样可以阻止超时,当然现在看透一切的我对以前的我起不了任何歹心,毕竟是自己蠢。
在四次超时后,我实在是想不出任何办法了,才做的下一题(差距就此产生)
代码(在讲过之后又错了2次)
#include
#include
#include
usingnamespacestd;
inta[505],b[505],c[505],d[250005];
intmain ()
{
intL,N,M;
into=0;(不能写在while里,不然o的值在每次循环都会变为0;
while(cin>> L >> N >> M)
{
for(inti=1;i<=L;i++)cin>> a[i];
for(inti=1;i<=N;i++)cin>> b[i];
for(inti=1;i<=M;i++)cin>> c[i];
inttot=0;
for(inti=1;i<=L;i++)
{
for(intj=1;j<=N;j++)
{
d[++tot]=a[i]+b[j];
}
}
sort(d+1,d+1+tot);
intS;
cin>> S;
intnum;
cout<<“Case “<<++o <<“:“<<“\n“;
for(inti=1;i<=S;i++)
{
cin>> num;
ints=0;
for(intj=1;j<=M;j++)
{
intm=lower_bound(d+1, d+1+tot , num-c[j])-d;
if(d[m]==num-c[j])
{
s=1;
cout<<“YES“<< endl;
break;
}
}
if(s==0)cout<<“NO“<< endl;
}
}
return0;
}
知识点
(1)还是对++i和i++的理解不够
a[j++]=I 相当于 a[j]=I ; j++;
d[++tot]= a[i]相当于tot++; d[tot]=a[i];
以前我总是分开用,在括号内刚一看见还是有些不太习惯(人总得去适应不是)。
(2)关于lower_bound()和upper_bound()的常见用法
(当时师哥在讲lower_bound的时候我就是半懂非懂,果然要是用在实际编码上,我这个半吊子水平立马漏出了原形。从此得出真理:古人诚不欺我,实践才是检验真理的唯一标准,)
lower_bound()和upper_bound()都是利用二分查找的方法在一个排好序的数组中进行查找的。
在从小到大的排序数组中,
lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
inta[10]={0,1,2,3,4,5,6,7,8,9};
intm=lower_bound(a,a+10,8)-a;
a[m]和m的结果都是8;
inta[10]={0,1,2,3,4,5,6,7,8,9};
intm=lower_bound(a+5,a+10,8)-a;
a[m]和m最后的结果也是8;
inta[10]={0,1,2,3,4,5,6,7,8,9};
intm=lower_bound(a+5,a+10,8)-(a+5)(这样写就错了);
m最后的结果变成了3;a[m]肯定相应变了。
upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
在从大到小的排序数组中,重载lower_bound()和upper_bound()
lower_bound( begin,end,num,greater()):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num,greater()):从数组的begin位置到end-1位置二分查找第一个小于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
下面的代码帮助理解
int cmd(inta,intb)
{
returna>b;
}
intmain()
{
intnum[6]={1,2,4,7,15,34};
intpos1=lower_bound(num,num+6,7)-num;//返回数组中第一个大于或等于被查数的值
intpos2=upper_bound(num,num+6,7)-num;//返回数组中第一个大于被查数的值
cout<< pos1 <<““<< num[pos1]<< endl;
cout<< pos2 <<““<< num[pos2]<< endl;
sort(num,num+6,cmd);//按从大到小排序
intpos3=lower_bound(num,num+6,7,greater())-num;//返回数组中第一个小于或等于被查数的值
intpos4=upper_bound(num,num+6,7,greater())-num;//返回数组中第一个小于被查数的值
cout<
cout<
return0;
}
3 7
4 15
2 7
3 4
Program ended with exit code: 0
1004.小可爱们
这道水题就不仔细分析了,这道题真的是水题。
代码
int main ()
{
int n;
int a[9]={0,1,3,4,4,8,3,2,6};
while (cin >> n)
{
cout << a[n]<< endl;
}
return 0;
}
直接把代码给你们就好了
1005.英语翻译对抗赛
这道题在错了三道之后才A的。
先来看一下为什么却错了三次的原因。
错误分析
(1)在两次best的地方出了问题。(最大值里面肯定有一个是best呀,不知道当时是怎么想的)
best=max(sum+1,sum);
sum=sum+1;
best=max(sum-1,sum);
sum=sum-1;
(2)这次best最大值里面虽然有了best,但是sum的值我没有改变。
best=max(sum+1,best);
best=max(sum-1,best);
(3)最后一次是连样例都没过,我连试一下都没有,就直接交了(还是太自大了,认为这道题是一道简单题,但事实证明我并没有那么厉害)。
接下来看一下代码吧,看一下自大的后果。
if(a[i]==0&& d!=0)
{
sum=sum;
d--;
}
if(a[i]==1)
{
best=max(sum+1,best);
sum=sum+1;
}
if(a[i]==0&& d==0)
{
best=max(sum-1,best);
sum=sum-1;
}
在第一个if里面如果成功了,那么d的值可能被减到0,那么正好满足第三个if的条件,正好导致我错误了。其实每次加一个continue就可以了。
代码
int main ()
{
intn,x,m;
inta[105];
while(cin>> n >> x >> m)
{
for(inti=1;i<=n;i++)
{
cin>> a[i];
}
intsum=0;
intbest=0;
intd;
for(intk=1;k<=m;k++)
{
d=x;
for(inti=1;i<=n;i++)
{
if(a[i]==0&& d!=0)
{
sum=sum;
d--;
continue;
}
if(a[i]==1)
{
best= max( sum+1, best);
sum = sum + 1;
continue;
}
if(a[i]==0&& d==0)
{
best= max(sum-1, best);
sum=sum-1;
continue;
}
}
}
cout<< best << endl;
}
return0;
}
1006.你的心态炸了嘛?
这道题看了,心态确实炸了,就是不会。
上面的代码由于是从word里面直接复制的原因,会有些出入,大家要谨慎看待。。。
最后的总结:(跳过题目分析的人可以直接看这里)
由于时间有限(周一白天七节课,实在是写不完了)试题的更改会在之后进行补充,还是先谈一谈这段时间里我的真实感受吧。
说实话,我自己本身还是蛮享受这种时候的,因为我明显感觉到我的本领在肉眼可见的速度在增长,我的父母也支持我加入这么一个集训队,虽然确实有时候有一点累,并且累了之后发现你错过了很多东西,但我这个人好像偏于那种不愿动的人,不愿走出舒适区的人,相比于在篮球场、足球场挥洒汗水,我明显偏爱于在教室里静静的坐着。
我蛮喜欢王小波的一句话的:
我活在世上,无非想要明白些道理,遇见些有趣的事,倘能如我愿,我的一生就算成功。
——王小波
真的,从我知道学校里有这么一个类似社团的集训队后,我下意识的感觉我适合这里,相比于老师教课,我更偏爱于独自一人思考,我把当图书馆志愿者的事给推了(当时已经交了报名表,只差面试了,我连面试都没去,有了机房还去图书馆干嘛),把那些什么乱七八槽的社团也都推了,我自认为我不是去学生会的料,还是呆在机房码字比较适合我。
再说说这次比赛吧,要说自我感觉的话,总感觉自己比较弱,因为我在oj上刷的题是靠后的(很靠后),不是我不想多做点,实在是力不从心(或许真的跟自己没有付出全部努力有关),这次的比赛算是给我提了一个醒吧,我真的发现了很多漏洞,包括各个方面,我会努力改正的,这才是比赛的目的嘛。
还有在这段时间,感谢每一个给我们小萌新讲课的师哥师姐们,感谢那些甚至未曾谋面的但他们的博客给了我们灵感与知识的人们,真的十分感谢。
当时光的画笔留下了惨淡的白和污浊的黑
当岁月的利刃磨平了我们菱角分明的心
当追名逐利的狂热浊污了我们澄澈的双眼
当冰冷无情的麻木锈蚀我们灵动的身躯
当初春新抽的嫩芽再也激不起我们心中的一丝波澜……
望我也可以在以后的日子里,不忘记自己现在的所感所想,不忘记每一个人给我的忠告,努力在我大学的acm道路上,走出我自己的一片天空。
......
果然第一次写总结的时候由于写题目分析花的时间有点多,最后的总结写的有点少,以后就会好很多,等以后找机会再发一些总结吧。
在这里还是要感谢本书的六个收藏。。。