2011年台州学院第五届“星峰杯”大学生程序设计竞赛
A:Solve the Equation
我得思路是将左边和右边分开来处理分别截取到ax+b中左边得a1和b1,右边的a2和b2
如:0=2输出No solution,x+2=x+2输出Multiple solution,其他的用公式求
具体思路不唯一
B:扔硬币
水题,不发表言论
C:视频监控
我得算法是:贪心
首先对摄像头和案发地点都按从小到大排序,然后会出现以下情况
如果案发点0,我们可以得出这个案发事故无法获取,于是放弃
如果是案发点1,我们可以发现第N+1个摄像头照射不到,于是我们必须要用到N号摄像头
如果是案发点2
假如N号摄像头已经使用了,那我们就不考虑N+1号摄像头,因为我们已经能照到案发点了
假如N号摄像头没被使用过,那我们就使用N+1号摄像头,因为N号摄像头照得到的N+1号都能照 到,反之则不然。
如果是案发点3,我们就++N,然后重新从头开始判断!~
以上是贪心策略,但是我们仍没考虑一种特殊情况
对于以上案发地点,显然根据从小到大排列的话,这个点是在第N个,第N+1个,以及第N+2个摄像头下
如果第N+1和第N个都能照射,并且第N个未被使用过,我们本来是用第N+1个的,但是显然,第N个摄像头比第N+1个摄像头好!~
我得做法是先删除这种特殊情况,再去贪心
你也可以在贪心的时候对这种情况特殊处理
int s=0,temp=0;//temp是案发点个数,s是使用到的最少摄像头
while(i<n&&j<m)//i代表案发点,j代表摄像头
{
if(num[i]<b[j].min)//案发点i在摄像头j的前面
{
i++;
}
else if(num[i]>b[j].max)//案发点i在摄像头j的后面
{
j++;
}
else if(num[i]>=b[j].min&&num[i]<=b[j].max)//案发点在摄像头j的照射下
{
if(b[j].flag==true)//摄像头j已经被使用了,案发点个数+1
{
++temp;++i;
}
else if(b[j].flag==false&&j+1==m)//最后的摄像头,那么案发点个数+1,摄像像头个数+1
{
++i;
++temp,++s;
b[j].flag=true;
}
else if(b[j].flag==false&&j+1<m)//不是最后一个摄像头
{
if(b[j+1].min<=num[i])//第j+1摄像头能照到案发点i,++j,重新考虑改点
{
j++;
}
Else//第j+1个摄像头照不到,必须使用该摄像头
{
++i,++temp,++s;
b[j].flag=true;
}
}
}
}
D:MFA Algorithm
求像素值的平均值,并四舍五入,题目描述要注意W*H indicates the resolution of these images, W and H indcate the width and height of the image, or the number of colums and rows in the matrix :
E:Circle VS Triangle
用圆心与三角形两两的面积之和等于三角形的面积来判断圆心是否在三角形内,而后判断圆的半径是否小于圆心到三角形三边的距离!
注意:本题,CRQ大神精度卡得非常死,需用整数处理,请勿使用sqrt以及除法----Orz
F:电脑密码
坐等大神A掉。。。
G:The Key Locker of Cell Phone
水题
H:Number Maze
广搜,坐等大神A掉。。
I:修路问题
坐等大神A掉
J:浪漫自习
坐等大神A掉
K:自动门控制
水题