北航算法上机题目

亮灭状态为 Lg1,Lg2,....,LgN (Lgi为1或0，表示灯泡的亮或灭)。为了满足MM的要求，XiaoM一开始应该如何设置L1，L2，L3，..., LN 呢？

输入

多组测试数据

每组测试数据有两行，第一行是一个正整数N (1<=N<=10000),第二行是N个只能取0或1的整数Lg1,Lg2,...,LgN

输出

对于每组测试数据，输出L1，L2，..., LN,占一行，Li和L(i+1)之间有一个空格，行末无多余的空格 样例输入 3 1 1 1 样例输出 0 1 1

提示

scanf and printf is recommended.

the bee 时间限制：1000 ms | 内存限制：65536 KB 描述

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。如图。

试求蜜蜂从蜂房a爬到蜂房b的可能路线数。 输入

第一行一个整数表示数据组数（多组数据），对于每组数据只一行有两个整数a,b (1≤a < b≤40) 输出

对于每组输入，输出一行，即从蜂房a爬到蜂房b的可能路线数。

样例输入 1 1 5

样例输出 5

矩形图像覆盖 时间限制：2000 ms | 内存限制：65535 KB 描述

由一种大写字母围成了一个封闭的矩形，矩形的长、宽至少为3，矩形的边的厚度严格为1，如下图所示：

这是一个8x6的矩形。每条边的厚度都严格是1。对于每个矩形，围成边的大写字母只有一种。不同矩形，大写字母不同。 XiaoM有一部特殊的摄像机，他把一个RxC的矩形完整拍摄在一个NxM的底片上(R<=N,C<=M)。很明显，拍摄的位置不同，我们可以得到不同的照片，（注意：不能旋转矩形，也不能旋转底片，也即：在最后的照片里，底片还必须是N行M列，矩形还必须是R行C列，矩形还必须是完整的）例如，把上面8x6的矩形拍摄在9x7的底片上时，可以得到的全部照片如下：

图中的'.'表示透明部分，大写字母表示矩形部分、不透明的。设想将以下两张9x7的照片叠放在一起：

其中第一幅在底部，第二幅在上面，那么将会得到如下结果：

该结果中，非透明部分的面积是：32（即有32个字母）显然，如果改变这两个矩形框的在底片中的拍摄位置，那么覆盖后得到的非透明部分的面积就会不同。你的任务是，给出底片大小RxC,在底部的矩形大小N1xM1,在顶部的矩形大小N2xM2，给出覆盖后非透明部分的最大面积。 输入

多组测试数据（不超过20组）每组测试数据占一行，给出四个正整数：R C N1 M1 N2 M2 其中： 3<=R,C<10, 3<=N1,N2<=R, 3<=M1,M2<=C

输出

一个整数，覆盖后的非透明部分的最大面积，每组测试数据占一行

样例输入 9 7 3 3 3 3 样例输出 16

改进版N皇后 时间限制：5000 ms | 内存限制：65535 KB 描述

某年月日，N个皇后又聚到了一起，她们不想再玩老掉牙的N皇后游戏了，于是乎，她们学会了“马”的步法??

在NXN格的国际象棋棋盘上摆放N个“加强版”皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，而且，通过国际象棋中“马”的步法也不能互相攻击

“马”的攻击范围如图所示：

问在新规则下，共有多少种摆法。 输入

第一行为一个整数T，表示有T组数据。 以下T行，每行有一个整数n（0

对于每组数据输出一行，即问题的答案。

样例输入 2 1

10 样例输出 1 4

算法上机2a

Eason的时光倒流 时间限制：1000 ms | 内存限制：65535 KB 描述

童年你与谁渡过、圣诗班中唱的歌,再哼一哼可以么,当时谁与你排着坐、白色恤衫灰裤子、再穿一穿可以么、遗憾我当时年纪不可亲手拥抱你欣赏、童年便相识、余下日子多闪几倍光、谁让我倒流时光一起亲身跟你去分享、能留下印象、阅览你家中每道墙、拿着你歌书、与你合唱??

Eason是一名出色的歌手，同时是一位深情的诗人、哲学家、爱情家。“时光倒流二十年”打动了无数的痴男痴女，终于，上帝也被深深感动了?于是，上帝给了Eason回到过去的机会?Wonderful and Romantic? Right？ Of Course。

上帝给Eason开了n扇门，编号1到n，门的种类有两种：A类、B类。A类门能让Eason穿越时空，回到那个她的童年，而如果Eason很不幸进了B类门，那么Eason将还是停留在现在。Eason选择第i扇门的概率是Pi。这里保证P1+P2+?+Pn=1,并且0<=Pi<=1.上帝会给Eason最多m次的机会，每次Eason以上述的概率分布选择一扇门，如果Eason选中了A类门，那么能够实现时光倒流，Eason将直接回到过去。否则，Eason将还是绕回到原地，然后Eason将再以同样的概率分布选择其中一扇门（即：如果上一次Eason选择了B类的门j，那么下次选择门j的概率还是原来的Pj）。当然，如果Eason选择的次数达到了m次还没有回到过去，那么Eason就不能再选择了，他只能留在现在。Eason将一直随机选择某个门进入直到时光倒流或者用尽所有机会。

现在，请你帮Eason计算他回到过去的概率是多少。

输入

多组测试数据，每组测试数据占两行，第一行有两个正整数n,m （1<=n<=10,0<=m<=10），表示n扇门，Eason有m次机会。第二行有n个浮点数Qi(1<=i<=n), 如果Qi>=0,那么表示这扇门是A类的（能回到过去），Eason选中它的概率是Pi=Qi。如果Qi<0，那么表示这扇门是B类的（还是回到现在），并且，Eason选中它的概率是Pi=-Qi。 Eason每次选择门的事件都是独立的。保证|Q1|+|Q2|+?+|Qn|=1.

输出

对于每组测试数据，输出一行，如果Eason回到过去的概率，保留到3位小数。 样例输入 2 1 0.5 0.5 2 1 0.5 -0.5 2 1 0 -1 样例输出 1.000 0.500 0.000

扫雷英雄榜 时间限制：1000 ms | 内存限制：65536 KB 描述

说起豆豆同学在扫雷方面的造诣，那可是在整个宿舍都数一数二的~从小学开始，豆豆就对扫雷产生了浓厚的兴趣??（以下省略数万字）可是最近他遇到点小麻烦：当他把“扫雷英雄榜”刷到5', 34', 133'之后，就没再刷新过，一段时间下来，豆豆觉得很没成就感，但他又不想清除原来的记录，于是，他就把目光瞄准了室友的电脑??

这天，豆豆以自己的电脑在实验室为由，借来了室友的电脑。由于室友电脑上的扫雷还没玩过，所以记录都是默认的999（单位：秒）。于是，豆豆选定高级开始扫雷。只听鼠标噼里啪啦一阵乱响，豆豆已经获胜了N局了。现在，分别给你这N局的用时，问：豆豆一共刷新了多少次记录呢？

（注：只有本局游戏获胜且用时小于当前记录时，才算刷新一次记录） 输入

第一行为一个整数T，表示有T组数据。 每组数据中，第一行一个整数N（0

第二行有N个小于999的整数，表示获胜的每局游戏的用时。 输出

对于每组数据输出一行，即问题的答案。

样例输入 3 3

200 190 180 3

140 140 140 2

150 160 样例输出 3 1 1

合并排序 时间限制：1000 ms | 内存限制：65536 KB 描述

给出一组数，要求用合并排序的方法，求出从小到大排序后的序列。

如果只是这些，一个sort（a，a+N）就搞定了??所以，本题要求输出排序的中间结果。

给出合并排序的伪代码：（分治的思想）

merge_sort(int a[], int s, int f){

如果s和f相等，则直接返回

否则{

M=(s+f)/2;

merge_sort(a, s, m);

merge_sort(a, m+1, f);

// 为保证输出的唯一性，这里规定，排序a[s~f]时，将s ~ (s+f)/2分为一段，(s+f)/2+1 ~ f分为一段

把已经排好序的a[s~m], a[m+1~f]两段合并成一段有序序列，存放在a[s~f]里（可以暂存到另一数组中，再copy过去）

///// 在这里输出排好序的a[s~f]序列，每两个数之间一个空格，末尾换行 } }

例如：5 4 3 2 1，输出结果为：

4 5 //merge_sort(a,0,1)（注：这里是按下标从0开始写的，从1开始不会影响输出结果）

3 4 5 //merge_sort(a,0,2)

1 2 //merge_sort(a,3,4)

1 2 3 4 5 //merge_sort(a,0,4) 输入

第一行为一个整数T，表示有T组数据。 每组数据中，第一行一个整数N（2<=N<100）

第二行有N个整数，表示待排序的数组。 输出

见伪代码中的描述及样例，每组数据末尾输出一个空行

样例输入 2 5

5 4 3 2 1 9

8 6 4 2 9 7 5 3 1

样例输出 4 5 3 4 5 1 2

1 2 3 4 5 6 8 4 6 8 2 9

2 4 6 8 9 5 7 1 3 1 3 5 7

1 2 3 4 5 6 7 8 9 提示

注意每组数据后输出空行(样例中未显示出最后一组的空行)

我要偷菜 时间限制：1000 ms | 内存限制：65536 KB 描述

豆豆虽然没开农场，但还是看别人玩过的。在农场里，为了得到最大的收益，除了自己辛苦种菜之外，去别人农场偷菜就成了赚钱的另一种方式。

话说某天，豆豆在周围某些同学的威逼利诱下，也开通了农场。他想迅速赚钱升级，但又不想花太多时间整天看着，于是，他开始观察大家的种菜习惯，发现每个人种菜的时间是有规律的??