2012年南海区青少年信息学竞赛复赛题(初中组)解题报告

《2012年南海区青少年信息学竞赛复赛题(初中组)解题报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一题：对于80%的数据，只需要开一个10A6的布尔数组，然后把在upperBound范围內的等差数列的所有项和等比数列的所有项全部作个标志，最后判断-下即可。其实，通过观察容易发现，等比数列的项的数量非常少，就算upperBound达到10N2,最多也不会超过42个,而等差数列的个数是可以通过公式直接计算出來的，因此可以令ans=等差数列的项的数量。然后逐个判断等比数列的每个项，如果不在等差数列屮，ans++,最后输出ans。参考程序如下：#includeusingnamespa

2、cestd;ifstreamfin("shulie.in");ofstreamfout("shulie.out’’);longlong(ia，b，c，d，upperBound;intmain(){fin»a»b»c»d»upperBound;longlongans=0;if(upperBound>=a){longlongm=(upperBound-a+1)/b;if(m*b=c){if(d==l){if

3、(c

4、此蚂蚁碰撞的吋刻不会超过8000,因此可以逐一吋刻的模拟蚂蚁爬到了什么位置，然后判断如果在某个特定时刻有两只或多只蚂蚁爬到同一点，那么这些蚂蚁都会消失。可以用active数组表示目前还有哪些蚂蚁是活的，然后按照上面的模拟，蚂蚁消失就设active为false。但8000个时刻过后，再统计一遍，看还有多少只蚂蚁是活的，输出答案。用C++的STL库减少代码量，当时时间杂度会差些。本题还有更高效率的算法，请读者思考。如下程序的时间复杂度是：0(8000*50*Log50)。参考程序：include

5、ream>#include〈vector〉^include

6、;intmain(){type['N'J=0;type['S']=1;type['W'J=2;type[rE'J=3;fin»n»dir;for(inti=l;i<=n;i++){fin»ant[i].x»ant[i].y;ant[ij.x*=2;ant[ij.y*=2;}for(inti=1;i<=n;i++)activefil=true;for(intt=1;t<=8001;t++){Map.clear();for(intj=1;j<=n;j++)if(active[j]){intx=ant[j

7、].x+t*dx[type[dir[j-l]]];inty=ant[j].y+t*dy[type[dir[j-l]]);Map[make_pair(x，y)].push_back(j);}map,vector>::iteratorit;for(it=Map.beginQ;it!=Map.end();it++)vectorvec=it-〉second;ints=vec.size();if(s<=1)continue;for(intk=0;k

8、active[vec[k]]=false;}}intans=0;for(inti=1;i<=n;i++)if(active[i])an$++;fout«ans«endl;return0;}第三题：设X=calc(maxT),表示代价在【l，maxT】的“合法”方案数，设Y=calc(mint-1)表示【1，minT-1】的“合法”方案数。那么我们的输出答案就是X-Y。如何求calc(T)呢？枚举选中的三个格子的高度差是h,那么根据代价的定义，那么这三个被选中的格子的宽