2012福建省信息学奥林匹克CCF-NOIP夏令营第九天训练(附解题思路及参考程序).doc

(完整版)2012福建省信息学奥林匹克CCF NOIP夏令营第九天训练(附解题思路及参考程序)

2012福建省信息学奥林匹克CCF NOIP夏令营第九天训练
(附解题思路及参考程序）

问题名称
文件名
输入文件
输出文件
时限
分值
房间最短路问题
door
door。in
door.out
1s
100
神秘大三角
tri
tri。in
tri。out
1s
100
数列的整除性
div
div.in
div.out
1s
100
内存限制均为256M

房间最短路问题（door)

【问题描述】
在一个长宽均为10，入口出口分别为（0，5)、（10，5）的房间里,有几堵墙，每堵墙上有两个缺口，求入口到出口的最短路经。

【输入文件】
第一排为n(n<=20），墙的数目。
接下来n排，每排5个实数x，a1,b1,a2，b2。
x表示墙的横坐标（所有墙都是竖直的）,a1—b1和a2-b2之间为空缺.
a1、b1、a2、b2保持递增,x1-xn也是递增的。
【输出文件】
输出最短距离，保留2位小数。
【样例输入】
2
4 2 7 8 9
7 3 4。5 6 7
【样例输出】
10。06
神秘大三角(tri）

【问题描述】
判断一个点与已知三角形的位置关系。
【输入文件】
前三行：每行一个坐标，表示该三角形的三个顶点
第四行：一个点的坐标,试判断该点与前三个点围成三角形的位置关系
（详见样例）
所有坐标值均为整数.
【输出文件】
若点在三角形内（不含边界），输出1；
若点在三角形外（不含边界）,输出2；
若点在三角形边界上（不含顶点),输出3；
若点在三角形顶点上，输出4。
【样例输入】
（0，0)
(3，0）
（0，3）
（1，1)
【样例输出】
1
【数据规模与约定】
对于100％数据,0〈=所有点的横、纵坐标〈=100
数列的整除性（div）

【问题描述】
对于任意一个整数数列,我们可以在每两个整数中间任意放一个符号’+’或’—',这样就可以构成一个表达式，也就可以计算出表达式的值。比如，现在有一个整数数列：17，5，—2，—15,那么就可以构造出8个表达式：
17+5+(-21)+15=16
17+5+（—21）—15=—14
17+5-（—21）+15=58
17+5-（—21）—15=28
17—5+（-21）+15=6
17-5+（—21）-15=—24
17—5—（—21）+15=48
17-5-（-21）-15=18
对于一个整数数列来说，我们能通过如上的方法构造出不同的表达式，从而得到不同的数值，如果该数值能够被k整除的话，那么我们就称该数列能被k整除。
在上面的例子中，该数列能被7整除（17+5+（—21）—15=-—14），但不能被5整除。现在你的任务是，判断某个数列是否能被某数整除.
【输入文件】
第一行是一个整数m，表示有m个子任务。接下来就是m个子任务的描述。 每个子任务有两行.第一行是两个整数n和k(1<=n〈=10000， 2〈=k〈=100)，n和k中间有一个空格。n 表示数列中整数的个数；k就是需要你判断的这个数列是否能被k 整除。第二行是数列的n个整数，整数间用空格隔开,每个数的绝对值都不超过10000。
【输出文件】
输出文件应有m 行，依次对应输入文件中的m 个子任务，若数列能被k 整除则输出 ”Divisible”,否则输出 ”Not divisible" ，行首行末应没有空格。
【样例输入】
2
4 7
17 5 —21 15
4 5
17 5 -21 15
【样例输出】
Divisible
Not divisible
房间最短路问题
题目大意:
房间中有一些墙，求从房间一头到另一头的最短路线。
解题思路：
1.路线一定是直线,弯曲只会更远
2.路线只会在端点处改变方向
枚举任意两端点求出所有可能的端点间连线
-判断线段是否相交
使用最短路算法求解
-以出入口和端点为点
—以端点间的连线为边

参考程序：
#include 〈iostream>
＃include 〈cmath>
#define eps 1e-8
＃define inf 100000000
using namespace std;

struct Wall{
double x；
double y[6］；
｝wall［20];
double dist[80］[80］;
double xmult（double x0，double y0，double x1,double y1，double x2,double y2）｛
return (x1—x0）*(y2—y0）—（x2—x0）＊(y1—y0）;
｝
int dblcmp( double a ){
if（ fabs(a)〈 eps ） return 0；
return (a〉0)？1:—1;
}
bool Cross( double x0, double y0， double x1, double y1， double x2， double y2, double x3， double y3 )｛
return （dblcmp(xmult（x0，y0，x2，y2,x3,y3)）^dblcmp(xmult(x1,y1,x2,y2，x3，y3）））==-2 ＆＆
（dblcmp(xmult（x2，y2，x0，y0，x1,y1）)^dblcmp(xmult(x3,y3,x0,y0,x1,y1)))==-2；
｝
bool Direct（ int i, int j, int p, int q ）｛ //判断从墙i的第j个点到墙p第q个点是否直达
int k， l;
for（ k= i+1； k< p; k++ ){
for( l= 0； l< 6; l+= 2 ）
if( Cross（wall[i］。x，wall［i］.y[j]，wall[p]。x，wall［p］.y［q],
wall[k]。x,wall［k］.y[l]，wall[k]。x,wall[k］.y[l+1］） )
return false；
}
return true；
｝
inline double Dist( double x1， double y1, double x2, double y2 ){
return sqrt（(x1—x2）*（x1-x2)+（y1—y2）＊(y1—y2））;
}；
typedef double elem_t;
double dijkstra（int n)｛
int v[81]，i，j，k;
double min［81］；
for (i=0;i<=n;i++）
min[i]=inf，v［i]=0;
for (min[0]=0,j=0；j<=n；j++）{
for （k=-1，i=0；i〈=n；i++)
if (！v［i］&＆(k==—1||min[i]〈min［k］）)
k=i；
for （v［k]=1,i=0;i〈=n;i++）
if （!v[i］&&min[k］+dist［k］［i]<min［i］)
min[i］=min［k]+dist[k］［i］；
}
return min［n]；
｝
int main（){
freopen(”door。in","r"，stdin);
freopen(”door.out",”w"，stdout）;
int n， i, j, k, l;
wall[0］。x= 0;
wall[0］。y［0]= 5;
int ttt=0；
scanf("%d”,&n）;
while（ ttt==0 ){
ttt=1；
for（ i= 0； i〈= n*4+1; i++ ）
for（ j= 0; j〈= n＊4+1； j++ ）
dist［i]［j］= inf;
wall[n+1］。x= 10；
wall[n+1]。y［1]= 5;
bool con= true;
for( i= 1; i〈= n; i++ ){
scanf（"％lf",＆wall［i］.x)；
for( j= 1； j〈 5； j++ ）
scanf（"％lf”,&wall［i]。y[j］)；
if（ wall[i].y［1]>5 || wall[i］。y［4]〈5 |｜ wall［i].y[2]<5＆＆wall[i］.y［3]>5 ）
con= false;
wall［i].y[0］= 0；
wall[i］。y[5］= 10；
}
if( con )｛
puts(”10。00”）；
continue；
｝
for( i= 1; i<= n； i++ )｛
for（ j= 1； j〈 5； j++ ）{
if（ i〈 n ）
for（ k= 1； k〈 5； k++ ）
dist［i*4+j-4]［i＊4+k］= Dist（wall［i]。x，wall[i]。y[j］，wall［i+1].x，wall[i+1].y［k]);
if（ Direct（ 0， 0, i, j ） ）
dist［0]［i*4+j-4]= Dist（0,5,wall［i］.x,wall［i］。y[j］);
if（ Direct( i， j， n+1, 1 ) )
dist[i＊4+j—4］［n＊4+1］= Dist（wall[i].x,wall[i].y[j］，10，5）；
for( k= i+2; k〈= n; k++ ）
for（ l= 1; l〈 5; l++ ）
if（ Direct（i,j，k，l） ）
dist［i＊4+j-4］［k＊4+l-4］= Dist(wall［i]。x,wall［i]。y［j]，wall［k].x,wall［k]。y[l］);
}
}
printf（"％.2lf\n”,dijkstra（n*4+1)）；

｝
return 0;
｝
神秘大三角
题目大意：
判断一个点与三角形的关系
解题思路:
叉积一直很好用
1。是否在顶点上？
-判断坐标是否相等
2.是否在边界上？
—1.该边与该点的叉积为0
-2.坐标在该边范围内
3.是否在三角形内？
—三边与该点的叉积都为正或都为负
参考程序:
#include 〈iostream〉
＃include 〈cstdio>
#include <cstdlib〉
#include 〈cmath〉
#include <cstring〉
using namespace std；
＃define FOR（i,a,b） for（int i=a；i<=b；i++)
#define MST（a,b) memset（a，b，sizeof（a))
struct P
{
int x,y;
｝；
P a［4］,b;
int cj（P o,P a,P b)
｛
return （a.x-o。x)*（b。y-o。y)-（b.x-o。x）＊（a。y-o。y）;
｝
double dis（P a，P b）
{
return sqrt（(a。x-b.x）＊（a.x-b。x）+（a.y-b。y）＊(a。y—b.y));
｝
int work（)
｛
FOR(i，1，3)if （（a［i］。x==b.x）＆＆（a［i]。y==b。y)) return 4;
FOR（i，0，2)
｛
double t1=dis(a[i］，a[i+1］),t2=dis(b，a［i］）+dis(b,a［i+1]）;
double eps=t1-t2;
if （eps<0）eps=—eps;
if （eps〈1e—6）return 3；
}
int sum=0；
FOR（i，0,2）
｛
int t=cj(b，a[i]，a［i+1]）；
if (t〈0）t=-t;
sum=sum+t；
}
int t=cj(a［0],a［1］,a[2］);
if (t〈0）t=-t;
if （t==sum） return 1；
return 2；
｝
int main（)
{
freopen（”tri。in”,”r",stdin）；
freopen(”tri.out”，"w”,stdout);
FOR(i,0,2）scanf（”（%d，％d)\n”,&a［i］.x，＆a[i］.y);
a［3].x=a［0］.x;
a［3]。y=a[0]。y；
scanf("(%d，%d)",&b。x,&b。y);
printf（”%d”,work(））；
｝
数列的整除性
题目大意:
在n个数间加入n—1个 + — 符号，问能否被k整除
解题思路:
数列的和可能有非常多种
只考虑是否能被k整除
只考虑被k除的余数
以数列和mod k为状态
f［i][j]表示是否存在 前i个数的和被k除的余数为j的情况
若f[i-1]［j］为真,则f[i］［j+a[i]],f［i][j-a[i］］也为真
注意对j+a［i］,j-a[i］取模时的运算
答案为f[n］[0]
参考程序：
#include <iostream>
＃include 〈cstdio>
＃include <cstdlib〉
＃include <cstring>
＃include 〈cmath>
using namespace std；
＃define FOR（i，a,b） for（int i=a；i<=b；i++)
#define MST(a,b） memset(a,b,sizeof(a））
#define MAXN 10050
#define MAXK 105
int n，k，a[MAXN］；
void init(）
{
scanf(”％d％d",＆n,＆k）；
FOR(i,1，n）scanf（”％d”,＆a［i])；
}
int f［MAXN］［MAXK];
void work（）
｛
MST（f,0）；
if (a[1］〉0)f［1][a[1]％k]=1;
else f［1]［(k+(a［1]%k）)％k］=1；

FOR（i,2，n）if (a［i］〈0）a[i]=-a［i］;
FOR(i,2，n)
FOR（j，0,k-1）
if (f[i—1］[j])
｛
f［i］[(j+a[i])％k］=1;
int t=j—（a［i］%k)；
if (t<0)t+=k;
f［i］［t］=1；
}
if (f[n］［0］）printf（"Divisible\n”）；
else printf（”Not divisible\n");
}
int main（)
{
freopen(”div。in","r"，stdin）;
freopen（”div。out”，"w",stdout);
int nn；
scanf("%d"，&nn);
FOR(ii,1,nn)
{
init()；
work();
}
}