解题报告

A:Pump

题目意思：就是有一个河塘，然后河塘有n个水泵，每个水泵的ai表示只用这个水泵，ai个小时可以放满（正的时候）或者可以放完（负的时候），1/ai 就是每个小时可以放的水。

我的方法：

输入后，取 1/ai 保存在double定义数组 s[]中，所有 1/ai 加起来求出和sum，判断sum>1e-6(写成0的话会错，精度问题)，成立的话，求出 1/sum 向上取整，输出。

不成立的话，对s[]数组从小到大排序，sum不断减去s[i] 直到sum>1e-6（还是精度问题）

如果 i 等于 n都是负数的情况输出Impossible，

否则输出 NO i

特别注意1e-6 的精度问题

B:Conflicting Lists

题目意思：取前面尽量少的个数 k ，使上下2个数组的前k个可以对应（就是上面的数组出现过什么，下面的数组也要出现过什么，比如上面出现1 2 3 下面出现2 3 1，那么前面1个不对应，2个也不对应，3个对应）

解法:看样例

3 5 7 1 2 4 6 8 9 10 数组1

1 2 3 4 7 5 6 8 9 10 数组 2

在数组2中由前往后找到数组1的第一个元素3 ，找到第三个位置，把前面的1 2 标记好，

s1数组再往后是5，5没有标记过，再在数组2中从3的后面一个往后面找，找到第6个位置，找过的数都标记下来，

s1数组再往后是7，已经标记过，然后1，标记过，2标记过，4标记过，这时数组1也找到了第6个位置，跳出循环

输出 6 就是题目要求的答案

for(i=0,j=0;i<n;i++)
{
if(f[s[i]]==0)
{
  for(j=x+1;j<n;j++)//x开始是-1
  {
   f[d[j]]=1;
   if(s[i]==d[j]) break;
  }
  x=j;
}
if(i==x||x==n-1) break;
}//s[]和d[]是输入的2个数组，f[]是标记数组，x用来标记数组d找到什么位置。

C:0/1 Tiles

其实是一个斐波那契数列，%15746就可以了，

1 1

2 00 11

3 100 001 111

4 0000 1100 1001 0011 1111

第四组其实就是第二组后面加00，第三组后面加1，后面类推。

D:Please your Friends

题目意思：自己有1到n的礼物，每行是每个人喜欢的礼物编号，判断是否可以让每个人都拿到自己喜欢的礼物。

用字符串输入，一个一个取出里面的数定义这样一个结构体来保存

struct In
{
int num[100],len;
};

然后用深搜

int bj[100],biaoji,n;//一个标记数组，一个标记，人的个数（行数）n
void ss(int i)
{
int j;
if(i==n) biaoji=1;//结束的条件
if(biaoji==1) return ;
for(j=0;j<s[i].len;j++)//一个个遍历
{
  if(bj[s[i].num[j]]==0)//这个礼物还没有送出去
  {
   bj[s[i].num[j]]=1;//送出去
   ss(i+1);//送下一个人，
   bj[s[i].num[j]]=0;//到这里说明不应送出去，回溯
  }
}
}

E:Pair Isograms

判断出现的字符是不是2个

F:Candy Store

点 s[0]到s[1]到s[2]...的过程中距理商店的最小距离，就是点到线段的距离，用向量可解

1个点的时候要特殊判断。

假设 A点B点的过程中离C点最短的距离

cos（a）=（AB*AC）/(|AB|*|AC|) AB，AC，都是向量 a是AB和AC的夹角

如果cos（a）的值是负的，那么角CAB是钝角，那么点到线段的距离就是AC的长度。

正的时候，设过C垂直AB的点为H，那么 AH/AC=cos（a），那么|AH|=cos(a)*|AC|=（AB*AC）/|AB|

那么如果|AH|>|AB| ,C到线段AB的最短距离是|BC|，反之CH就是最短距离

|CH|=sqrt（|AC|*|AC|-|AH|*|AH|)---------勾股定理

循环所有路径找到最短的距离，输出即可。