有的题还没写完）咕咕咕））

NENU OJ算法2例题

这学期写算法2的思路并不都很详细，不过如果有想交流的也可以评论区或者私信，学校oj的题大多比较简单，这里的所有代码或许只保证通过学校的弱测试数据，~~因为其他地方OJ我还没有试过~~。

算法2递归A

1241: A001 猴子吃桃

题目描述

猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第10天早上想再吃时，就只剩下一个桃子了。求第1天共摘了多少个桃子。

输入

输入第一行为正整数n，为测试数据组数。后面n行为测试数据，每组测试数据包括两个整数m，k，分别表示第m（m>1)天后剩余的桃子数k(k>=0)。

输出

输出猴子第一天摘的桃子数，每组数据占一行。

样例输入

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4
    int n;cin >> n;
5
    while (n--) {
6
        int m, k;cin >> m >> k;
7
        int sum = k;
8
        for (int i = 0;i < m - 1;i++) {
9
            sum++;
10
            sum *= 2;
11
        }
12
        cout << sum << endl;
13
    }
14

15
    return 0;
16
}

1242: A002 最大公约数

题目描述

输入两个正整数，求其最大公约数。数论中有一个求最大公约数的算法称为辗转相除法，又称欧几里德算法。其基本思想及执行过程为（设m为两正整数中较大者，n为较小者）：（1）令u=m,v=n；（2）取u对v的余数，即r=u%v，如果r的值为0，则此时v的值就是m和n的最大公约数，否则执行第（3）步；（3）u=v，v=r，即u的值为v的值，而v的值为余数r。并转向第（2）步。

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括两个正整数m和n。

输出

n行，每行输出对应一个输入。输出应是一个正整数，为m和n的最大公约数。

样例输入

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4
    int t;cin >> t;
5
    while (t--) {
6
        int m, n;cin >> m >> n;
7
        int yu = m % n;
8
        while (yu) {
9
            m = n;n = yu;
10
            yu = m % n;
11
        }
12
        cout << n << endl;
13
    }
14

15
    return 0;
16
}

1243: A003 经典的Hanoi(汉诺塔)问题

题目描述

有一个汉诺塔，塔内有A,B,C三个柱子。起初，A柱上有n个盘子，依次由大到小、从下往上堆放，要求将它们全部移到C柱上；在移动过程中可以利用B柱，但每次只能移到一个盘子，且必须使三个柱子上始终保持大盘在下，小盘在上的状态。要求编程输出移动的步骤。

输入

输入文件中包含多行，每行为一个整数n，代表初始A柱子上的盘子的个数。

输出

对输入文件中的每个整数n列出具体的汉诺塔移动步骤。两组输出之间有一空行。

样例输入

样例输出

1
A-->C
2
A-->B
3
C-->B
4
A-->C
5
B-->A
6
B-->C
7
A-->C
8

9
A-->C

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
void hanoi(int n, int from, int to) {
4
    if (n == 0) return;     // 全部移完，终止递归
5
    // 把from位置上的上面的n-1个移到不是from也不是to的位置
6
    hanoi(n - 1, from, (3 - from - to));
7
    // 移动最底下的最大的那个，并输出记录
8
    cout << char(from + 'A') << "-->" << char(to + 'A') << endl;
9
    // 把之前移走的n-1个移到to位置
10
    hanoi(n - 1, (3 - from - to), to);
11
}
12
int main() {
13
    int n;
14
    while (cin >> n) {
15
        hanoi(n, 0, 2);
16
        cout << "\n";
17
    }
18

19
    return 0;
20
}

1244: A004 菲波那契数列

题目描述

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数a，要求菲波那契数列中第a个数是多少。

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 <= a <= 20)。

输出

输出有n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数的大小。

样例输入

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
int fib(int n) {
5
    if (n == 1 || n == 2)return 1;
6
    return fib(n - 1) + fib(n - 2);
7
}
8

9
int main() {
10
    int t;cin >> t;
11
    while (t--) {
12
        int a;cin >> a;
13
        cout << fib(a) << endl;
14
    }
15

16
    return 0;
17
}

1245: A005 另一个Fibonacci数列

题目描述

定义另外一个Fibonacci数列：F(0)=7,F(1)=11,F(n)=F(n-1)+F(n-2)，（n≥2）。

输入

输入文件中包含多行，每行为一个整数n，n<1000000。

输出

对输入文件中的每个整数n，如果F(n)能被3整除，输出yes，否则输出no。

样例输入

样例输出

1
no
2
no
3
yes
4
no

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4
    long long na;
5
    while (cin >> na) {
6
        if (na % 8 == 2 || na % 8 == 6)cout << "yes\n";
7
        else cout << "no\n";
8
    }
9

10
    return 0;
11
}

1246: A006 分形（Fractal）

题目描述

分形是存在“自相似”的一个物体或一种量，从某种技术角度来说，这种“自相似”是全方位的。盒形分形定义如下：度数为1的分形很简单，为： X

度数为2的分形为：

X X

如果用B(n-1)代表度数为n-1的盒形分形，则度数为n的盒形分形可以递归地定义为：

B(n-1) B(n-1)

B(n-1)

B(n-1) B(n-1)

你的任务是输出度数为n的盒形分形。

输入

输入文件包含多个测试数据，每个测试数据占一行，包含一个正整数n，n ≤ 7。输入文件的最后一行为-1，代表输入结束。

输出

对每个测试数据，用符号“X”表示输出盒形分形。在每个测试数据对应的输出之后输出一个短划线符号“-”，在每行的末尾不要输出任何多余的空格，否则得到的是“格式错误”的结果。

样例输入

样例输出

1
X X
2
 X
3
X X
4
-
5
X X   X X
6
 X     X
7
X X   X X
8
   X X
9
    X
10
   X X
11
X X   X X
12
 X     X
13
X X   X X

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int maxlen = pow(3, 8);
4
// string mp[maxlen];
5
char mp[maxlen][maxlen];
6
int xpos[maxlen];
7

8
void tocpyRec(int deg, int tox, int toy,int fillblank) {
9
    int len = pow(3, deg - 1);
10
    // 左上角标记
11
    for (int i = 0;i < len;i++) {
12
        for (int j = 0;j < len;j++) {
13
            // cout << mp[i][j] << ":" << i << "-" << j << endl;
14
            if (fillblank)
15
                mp[tox * len + i][toy * len + j] = ' ';
16
            else
17
                mp[tox * len + i][toy * len + j] = mp[i][j];
18
        }
19
    }
20
}
21

22
void fw(int deg) {
23
    if (deg > 1) {
24
        fw(deg - 1);
25
    }
26
    for (int i = 0;i < 3;i++) {
27
        for (int j = 0;j < 3;j++) {
28
            if ((i + j) % 2 == 0 && (i || j)) {
29
                // 有内容的块坐标
30
                tocpyRec(deg - 1, i, j, 0);
31
            }
32
            else if (i || j) {
33
                tocpyRec(deg - 1, i, j, 1);
34
            }
35
        }
36
    }
37
}
38

39
int main() {
40
    mp[0][0] = 'X';
41
    int n;
42
    int flag = 0;
43
    while (cin >> n && n != -1) {
44
        if (flag)cout << "-\n";
45
        flag = 1;
46
        fw(n);
47
        int len = pow(3, n - 1);
48
        for (int i = 0;i < len;i++)
49
            for (int j = 0;j < len;j++)
50
                if (mp[i][j] == 'X')
51
                    xpos[i] = j;
52

53
        for (int i = 0;i < len;i++) {
54
            for (int j = 0;j <= xpos[i];j++) {
55
                cout << mp[i][j];
56
            }
57
            cout << endl;
58
        }
59
    }
60

61
    return 0;
62
}

1247: A007 二叉树

题目描述

如图所示，由正整数1, 2, 3, …组成了一棵无限大的二叉树。从某一个结点到根结点（编号是1的结点）都有一条唯一的路径，比如从10到根结点的路径是(10, 5, 2, 1)，从4到根结点的路径是(4, 2, 1)，从根结点1到根结点的路径上只包含一个结点1，因此路径就是(1)。对于两个结点x和y，假设他们到根结点的路径分别是(x1, x2, … ,1)和(y1, y2, … ,1)（这里显然有x = x1，y = y1），那么必然存在两个正整数i和j，使得从xi 和 yj开始，有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,… 现在的问题就是，给定x和y，要求xi（也就是yj）。

输入

输入有多行，每行包括两个正整数x和y，这两个正整数都不大于1000。

输出

每行输出只有一个正整数xi。

样例输入

1
10 4

样例输出

1
2

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N = 12;
4
int ax[N], ay[N];
5
int main() {
6
    int x, y;
7
    // 找重合的路径
8
    while (cin >> x >> y) {
9
        int kx = 0;
10
        while (x) {
11
            ax[kx++] = x % 2;
12
            x /= 2;
13
        }
14
        int ky = 0;
15
        while (y) {
16
            ay[ky++] = y % 2;
17
            y /= 2;
18
        }
19
        int kmii = kx > ky ? ky : kx;
20
        int ans = 0;
21
        for (int i = 1;i <= kmii;i++) {
22
            if (ax[kx - i] == ay[ky - i]) {
23
                ans <<= 1;
24
                ans += ax[kx - i];
25
            }
26
            else break;
27
        }
28
        cout << ans << endl;
29
    }
30

31
    return 0;
32
}

1248: A008 波兰表达式

题目描述

波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) _ 4的波兰表示法为_ + 2 3 4。本题求解波兰表达式的值，其中运算符包括+ - * /四个。

输入

输入第一行为一个整数n，然后是n行，每行为一组测试数据，其中运算符和运算数之间都用空格分隔，运算数是浮点数。

输出

输出n行，每行表达式的值，保留3位小数输出。

样例输入

1
1
2
* + 11.0 12.0 + 24.0 35.0

样例输出

1
1357.000

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
double dox() {
5
    string st;cin >> st;
6
    switch (st[0])
7
    {
8
    case '+':
9
        return dox() + dox();
10
    case '-':
11
        return dox() - dox();
12
    case '/':
13
        return dox() / dox();
14
    case '*':
15
        return dox() * dox();
16
    default:break;
17
    }
18
    return atof(st.c_str());
19
}
20

21
int main() {
22
    int t;cin >> t;
23
    while (t--) {
24
        cout << fixed << setprecision(3) << dox() << endl;
25
    }
26

27
    return 0;
28
}

1249: A009 放苹果

题目描述

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法（用K表示）？注意：5，1，1和1，5，1 是同一种分法。

输入

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1 <= M，N <= 10。

输出

对输入的每组数据M和N，用一行输出相应的K。

样例输入

样例输出

1
8

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N = 15;
4
int dp[N][N];
5

6
int divx(int apl, int pla) {
7
    if (apl == 0 || pla == 1)
8
        return dp[apl][pla] = 1;
9
    if (pla > apl)
10
        return dp[apl][pla] = divx(apl, apl);
11
    return dp[apl][pla] = divx(apl, pla - 1) + divx(apl - pla, pla);
12
}
13

14
int main() {
15
    int t;cin >> t;
16
    int m, n;
17
    while (t--) {
18
        cin >> m >> n;
19
        cout << divx(m, n) << endl;
20
    }
21

22
    return 0;
23
}

1250: A010 递归练习1

题目描述

有5个人坐在一起，问第5个人多少岁？他说比第4个人大两岁。问第4个人的岁数，他说比第3个人大两岁。问第3个人的岁数，又说比第2个人大两岁。问第2个人的岁数，说比第1个人大两岁。最后问第1个人的岁数，他说是10岁。请问第5个人多少岁？

输入

输入有多行，每行3个整数，依次为m,n,k。m表示一共有几个人，n表示大的岁数，k表示第一个人的岁数。

输出

输出第m个人的岁数，每个一行。

样例输入

1
5 2 10

样例输出

1
18

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
int m, n, k;
5
int age(int ind) {
6
    if (ind == 1)return k;
7
    return age(ind - 1) + n;
8
}
9

10
int main() {
11
    while (cin >> m >> n >> k) {
12
        cout << age(m) << endl;
13
    }
14

15
    return 0;
16
}

1251: A011 递归练习2

题目描述

根据递推式子C(m,n)=C(m-1,n)+C(m-1,n-1)，求组合数C(m,n)。注意递推的终止条件是C(m,1)=m；以及一些m和n取值的一些特殊情况，如m < 0或n < 0或m < n时，C(m,n)值为0，m和n相等时，C(m,n)=1等。

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数m和一个正整数n。

输出

输出组合数C(m,n)。

样例输入

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
int C(int m, int n) {
5
    if (n == 1)return m;
6
    if (m < 0 || n < 0 || m < n)return 0;
7
    if (m == n)return 1;
8
    return C(m - 1, n) + C(m - 1, n - 1);
9
}
10

11
int main() {
12
    int t;cin >> t;
13
    while (t--) {
14
        int m, n;cin >> m >> n;
15
        cout << C(m, n) << endl;
16
    }
17

18
    return 0;
19
}

1252: A012 递归练习3

题目描述

核反应堆中有α和β两种粒子。每秒钟内一个α粒子可以产生3个β粒子，而一个β粒子可以产生1个α粒子和2个β粒子。若在t=0时刻反应堆中有一个α粒子，求t时刻反应堆中分别有多少个α粒子和β粒子。

输入

输入有多个整数t，每个一行。

输出

输出t时刻反应堆里分别有多少个α粒子和β粒子。

样例输入

1
6

样例输出

1
183 546

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
pair<int, int> qut(int n) {
5
    if (n == 0)return make_pair(1, 0);
6
    int tempa = qut(n - 1).first, tempb = qut(n - 1).second;
7
    int a = tempb, b = 3 * tempa + 2 * tempb;
8
    return make_pair(a, b);
9
}
10

11
int main() {
12
    int t;
13
    while (cin >> t) {
14
        cout << qut(t).first << " " << qut(t).second << endl;
15
    }
16

17
    return 0;
18
}

插一句：这里用了pair数据类型，或许有同学并没有接触到…一般函数会返回1个值，有时候想返回两个或以上的时候可以试试自定义struct数据类型，再去定义一个struct的函数，不过c++自有一个pair可以用，还是挺方便的。

1253: A013 红与黑

题目描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入

包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下 1）‘.’：黑色的瓷砖； 2）‘#’：白色的瓷砖； 3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。当在一行中读入的是两个零时，表示输入结束。

输出

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

样例输入

1
6 9
2
....#.
3
.....#
4
......
5
......
6
......
7
......
8
......
9
#@...#
10
.#..#.
11
0 0

样例输出

1
45

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int maxh = 25;
4
string mp[maxh];
5
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
6

7
int w, h;
8
int move(int x, int y, int allstep) {
9
    for (int i = 0;i < 4;i++) {
10
        int nx = x + dx[i], ny = y + dy[i];
11
        if (nx > -1 && nx<h && ny>-1 && ny < w && mp[nx][ny] == '.'){
12
            mp[nx][ny] = '#';
13
            allstep = move(nx, ny, allstep + 1);
14
        }
15
    }
16
    return allstep;
17
}
18

19
int main() {
20
    while (cin >> w >> h && w != 0 && h != 0) {
21
        int si, se;
22
        for (int i = 0;i < h;i++) {
23
            cin >> mp[i];
24
            if (mp[i].find("@") != string::npos) {
25
                si = i;se = mp[i].find("@");
26
            }
27
        }
28
        int steps = move(si, se, 1);
29
        cout << steps << endl;
30
    }
31

32
    return 0;
33
}

1254: A014 城堡问题

题目描述

1 2 3 4 5 6 7 #############################

1 # | # | # | | #

#####---#####---#---#####---#

2 # # | # # # # #

#---#####---#####---#####---#

3 # | | # # # # #

#---#########---#####---#---#

4 # # | | | | # #

#############################

(图 1)

‘#’ = Wall ‘|’ = No wall ’-’ = No wall

图1是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成m*n(m≤50，n≤50)个方块，每个方块可以有0~4面墙。

输入

程序从标准输入设备读入数据。第一行是两个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。

输出

城堡的房间数、城堡中最大房间所包括的方块数。

样例输入

1
4
2
7
3
11 6 11 6 3 10 6
4
7 9 6 13 5 15 5
5
1 10 12 7 13 7 5
6
13 11 10 8 10 12 13

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N = 60;
4
int wall[N][N], fw[N][N];
5
int roomnum = 0, sizea = 0;
6
void dfs(int x, int y) {
7
    // 查找点(x,y)的信息
8
    if (fw[x][y]) return;
9
    sizea++;
10
    fw[x][y] = roomnum;
11
    if ((wall[x][y] & 1) == 0)dfs(x, y - 1);
12
    if ((wall[x][y] & 2) == 0)dfs(x - 1, y);
13
    if ((wall[x][y] & 4) == 0)dfs(x, y + 1);
14
    if ((wall[x][y] & 8) == 0)dfs(x + 1, y);
15
}
16

17
int main() {
18
    int h, w;cin >> h >> w;
19
    for (int i = 1;i <= h;i++){
20
        for (int j = 1;j <= w;j++){
21
            cin >> wall[i][j];
22
        }
23
    }
24
    int maxroom = 0;
25
    for (int i = 1;i <= h;i++) {
26
        for (int j = 1;j <= w;j++) {
27
            if (!fw[i][j]) {
28
                // (i,j)没被找过(新的area)
29
                roomnum++;
30
                dfs(i, j);
31
                maxroom = max(maxroom, sizea);
32
                sizea = 0;
33
            }
34
        }
35
    }
36
    cout << roomnum << endl << maxroom << endl;
37

38
    return 0;
39
}
40

41
/*
42
  2
43
1   4
44
  8
45
*/

1255: A015 分解因式

题目描述

给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 _ a2 _ a3 _ … _ an，并且1 < a1 <= a2 <= a3 <= … <= an，问这样的分解的种数有多少。注意到a = a也是一种分解。

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (1 < a < 32768)。

输出

n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数。

样例输入

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int ans = 0;
4
void dfs(int tar, int now) {
5
    if (tar != 1) {
6
        for (int i = now;i <= tar;i++)
7
            if (tar % i == 0)
8
                dfs(tar / i, i);
9
    }
10
    else {
11
        ans++;return;
12
    }
13
}
14

15
int main() {
16
    int t;cin >> t;
17
    while (t--) {
18
        ans = 0;
19
        int n;cin >> n;
20
        if (n == 2) {
21
            cout << 1 << endl;
22
            continue;
23
        }
24
        dfs(n, 2);
25
        cout << ans << endl;
26
    }
27

28

29
    return 0;
30
}

1256: A016 数字拼凑

题目描述

现在给你这样一个任务，要求找出具有下列性质数的个数（包含输入的正整数 n）。先输入一个正整数 n(n <= 500)，然后对此正整数按照如下方法进行处理：

不作任何处理；
在它的左边拼接一个正整数，但该正整数不能超过原数的一半或者是上一个被拼接数的一半；
加上数后，继续按此规则进行处理，直到不能再加正整数为止。

输入

一个正整数n。

输出

一个正整数，表示具有该性质数的个数。

样例输入

1
6

样例输出

1
6

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int fx[1010];
4
int f(int n) {
5
    if (n == 1)return 1;
6
    if (fx[n])return fx[n];
7

8
    int cnt = 0;
9
    for (int i = 1;i <= n / 2;i++)
10
        cnt += f(i);
11
    return fx[n] = cnt + 1;
12
}
13

14
int main() {
15
    int n;
16
    cin >> n;
17
    cout << f(n) << endl;
18

19
    return 0;
20
}

算法2排序B

1257: B001 快乐的蠕虫

题目描述

有一只快乐的蠕虫居住在一个m×n大小的网格中。在网格的某些位置放置了k块石头。网格中的每个位置要么是空的，要么放置了一块石头。当蠕虫睡觉时，它在水平方向或垂直方向上躺着，把身体尽可能伸展开来。蠕虫的身躯既不能进入到放有石块的方格中，也不能伸出网格外。而且蠕虫的长度不会短于2个方格的大小。本题的任务是给定网格，要计算蠕虫可以在多少个不同的位置躺下睡觉。

输入

输入文件的第1行是一个整数t，1<=t<=11,表示测试数据的个数。每个测试数据的第1行为3个整数：m,n和k(0<=m,n,k<=200000),接下来有k行，每行为2个整数，描述了一块石头的位置（行和列，最左上角位置为（1,1））。

输出

对每个测试数据，输出占一行，为一个整数，表示蠕虫可以躺着睡觉的不同位置的数目。

样例输入

样例输出

1
9

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 1e5 + 50;
5
int n, m, k;
6

7
struct node {
8
    int x, y;
9
    node(int x, int y) : x(x), y(y) {}
10
};
11
bool cmp1(node a, node b) {
12
    if (a.x == b.x)
13
        return a.y < b.y;
14
    return a.x < b.x;
15
}
16
bool cmp2(node a, node b) {
17
    if (a.y == b.y)
18
        return a.x < b.x;
19
    return a.y < b.y;
20
}
21

22
vector<node> a;
23
int ans = 0;
24
void search(bool f) {
25
    for (int i = 1;i < a.size();i++) {
26
        int nx = a[i].x, ny = a[i].y;
27
        int px = a[i - 1].x, py = a[i - 1].y;
28
        if (f) {
29
            if (nx != px)continue;
30
            if (ny - py > 2)ans++;
31
        }
32
        else {
33
            if (ny != py)continue;
34
            if (nx - px > 2)ans++;
35
        }
36
    }
37
}
38

39
void solve() {
40
    cin >> m >> n >> k;
41
    ans = 0;
42
    a.clear();
43
    for (int i = 0;i < k;i++) {
44
        int x, y;cin >> x >> y;
45
        a.push_back(node(x, y));
46
    }
47
    for (int i = 0;i < m + 2;i++) {
48
        a.push_back(node(i, 0));
49
        a.push_back(node(i, n + 1));
50
    }
51
    for (int i = 0;i < n + 2;i++) {
52
        a.push_back(node(0, i));
53
        a.push_back(node(m + 1, i));
54
    }
55
    sort(a.begin(), a.end(), cmp1);
56
    search(true);
57
    sort(a.begin(), a.end(), cmp2);
58
    search(false);
59
    cout << ans << endl;
60
}
61

62
int main() {
63
    int t;cin >> t;
64
    while (t--)
65
        solve();
66

67
    return 0;
68
}

1258: B002 单词重组

题目描述

在美国数以百万计的报纸中，有一种单词游戏称为猜词。游戏的目标是猜谜，为了找出答案中缺少的字母，有必要对4个单词的字母顺序重新调整。在本题中，你的任务是编写程序实现对单词中的字母顺序重新调整。

输入

输入文件包含4部分：（1）一部字典，包含至少1个单词，至多100个单词，每个单词占一行；

（2）字典后是一行字符串“XXXXXX”，表示字典结束；

（3）一个或多个被打乱字母顺序的“单词”，每个单词占一行，你必须整理这些字母的顺序；

（4）输入文件的最后一样为字符串“XXXXXX”，代表输入文件结束。

所有单词，包括字典中的单词和被打乱字母顺序的单词，都只包含小写英文字母，并且至少包含一个字母，至多包含6个字母。字典中的单词不一定是按顺序排列的，但保证字典中的单词是唯一的。

输出

对输入文件中每个被打乱字母顺序的单词w，按字母顺序输出字典中所有满足以下条件的单词的列表：通过调整单词w中的字母顺序，可以变成字典中的单词。列表中的每个单词占一行。如果列表为空（即单词w不能转换成字典中的任何一个单词），则输出一行字符串“NOT A VALID WORD”。以上两种情形都在列表后，输出一行包含6个星号字符的字符串，表示列表结束。

样例输入

1
tarp
2
given
3
score
4
refund
5
only
6
trap
7
work
8
earn
9
course
10
pepper
11
part
12
XXXXXX
13
resco
14
nfudre
15
aptr
16
sett
17
oresuc
18
XXXXXX

样例输出

1
score
2
******
3
refund
4
******
5
part
6
tarp
7
trap
8
******
9
NOT A VALID WORD
10
******
11
course
12
******

参考代码

算法2查找C

1264: C001 字符串计数

题目描述

给出m个字符串，要求输出重复n次的字符串有几个。

输入

先给定一个N，N≤100000，接着输入N个字符串。

输出

对于每组测试数据，输出若干行，每行两个正整数，第一个数表示重复的次数，第二个数表示在此重复次数下有几种不同的字符串。

样例输入

1
5
2
BBA
3
BBA
4
BEA
5
DEC
6
CCF

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N = 1e5 + 50;
4
int nx[N];
5

6
int main() {
7
    int n;cin >> n;
8
    map<string, int>sts;
9
    string st;
10
    while (n--) {
11
        cin >> st;
12
        if (sts.find(st) != sts.end()) {
13
            map<string, int>::const_iterator it = sts.find(st);
14
            int cnt = (*it).second;
15
            sts[st] = ++cnt;
16
        }
17
        else
18
            sts.insert(make_pair(st, 1));
19
    }
20
    map<string, int>::const_iterator it = sts.begin();
21
    for (;it != sts.end();it++) {
22
        nx[(*it).second]++;
23
    }
24
    for (int i = 1;i <= sts.size();i++) {
25
        if (nx[i])
26
            cout << i << " " << nx[i] << endl;
27
    }
28

29
    return 0;
30
}

1265: C002 赌徒

题目描述

N个赌徒一起决定玩一个游戏：游戏刚开始的时候，每个赌徒把赌注放在桌上并遮住，侍者要查看每个人的赌注并确保每个人的赌注都不一样。如果一个赌徒没钱了，则他要借一些筹码，因此他的赌注为负数。假定赌注都是整数。最后赌徒们揭开盖子，出示他们的赌注。如果谁下的赌注是其他赌徒中某3个人下的赌注之和，则他是胜利者。如果有多于一个胜利者，则下的赌注最大的赌徒才是最终的胜利者。例如，假定赌徒为：Tom、Bill、John、Roger和Bush，他们下的赌注分别为：2、3、5、7和12 。因此最终获胜的是Bush（并且没有其他人是胜利者），因为他下的赌注为12，而其他的人下的赌注之和也等于12：2+3+7=12。

输入

输入文件中包含了多组赌徒下的赌注。每组赌注的数据第1行是一个整数n,1<=n<=1000,代表赌徒的个数，然后是他们下的赌注，每个人的赌注占一行，这些赌注各不相同，并且范围是[-536870912,+536870911]。输入文件的最后一行为0，代表输入结束。

输出

对每组赌注，输出胜利者下的赌注，如果没有解，则输出“no solution”。

样例输入

样例输出

1
12
2
no solution

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 1050;
5

6
int n;
7
int gbr[maxn];
8
void solve() {
9
  for (int i = 0;i < n;i++) {
10
    cin >> gbr[i];
11
  }
12
  sort(gbr, gbr + n);
13
  for (int pi = n - 1;pi >= 3;pi--) {
14
    for (int i = pi - 1;i >= 2;i--) {
15
      for (int j = i - 1;j >= 1;j--) {
16
        for (int k = j - 1;k >= 0;k--) {
17
          int sum = gbr[i] + gbr[j] + gbr[k];
18
          if (sum == gbr[pi]) {
19
            cout << gbr[pi] << "\n";
20
            return;
21
          }
22
        }
23
      }
24
    }
25
  }
26
  cout << "no solution\n";
27
}
28

29
int main() {
30
  // int t;cin >> t;
31
  // while (t--)
32
  while (cin >> n && n)
33
    solve();
34

35
  return 0;
36
}

1266: C003 半素数

题目描述

素数的定义：对于一个大于１的正整数，如果除了１和它本身没有其他的正约数了，那么这个数就称为素数。例如，2,11,67,89是素数，8,20,27不是素数。半素数的定义：对于一个大于1的正整数，如果它可以被分解成2个素数的乘积，则称该数为半素数，例如6是一个半素数，而12不是。你的任务是判断一个数是否是半素数。

输入

输入文件中有多个测试数据，每个测试数据包含一个整数N，2<=N<=1,000,000。

输出

对每个测试数据，如果N是半素数，则输出YES，否则输出NO。

样例输入

样例输出

1
NO
2
YES
3
YES
4
NO

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 1e6 + 100;
5
bool isnp[maxn];
6
vector<int>primes;
7
void Prime(int n) {
8
    for (int i = 2;i <= n;i++) {
9
        if (!isnp[i])
10
            primes.push_back(i);
11
        for (int p : primes) {
12
            if (p * i > n)break;
13
            isnp[p * i] = true;
14
            if (i % p == 0)
15
                break;
16
        }
17
    }
18
}
19
int main() {
20
    Prime(maxn - 50);
21
    int n;
22
    while (cin >> n) {
23
        bool f = false;
24
        for (int i = 2;i * i <= n;i++) {
25
            if (n % i == 0 && !isnp[i] && !isnp[n / i]){
26
                f = true;break;
27
            }
28
        }
29
        f ? cout << "YES\n" : cout << "NO\n";
30
    }
31

32
    return 0;
33
}

1267: C004 棍子的膨胀

题目描述

当一根长度为L的细长金属棍子加热n度后，它会膨胀到一个新的长度L’=(1+n*C)*L,其中C为该金属的热膨胀系数。当一根细长的金属棍子固定在两堵墙之间，然后加热，则棍子会变成圆弓形，棍子的原始位置为该圆弓形的弦，如图所示。

![1699328671418](D:\Tencent&&\新建文件夹\WeChat Files\wxid_j7esazuly79422\FileStorage\Temp\1699328671418.png)

图膨胀的金属棍子（上为膨胀前，下为膨胀后）你的任务是计算棍子中心的偏离距离。

输入

输入文件包含多个测试数据，每个测试数据占一行。每个测试数据包含3个非负整数：棍子的初始长度，单位为毫米；加热前后的温差，单位为度；该金属的热膨胀系数。输入数据保证膨胀的长度不超过棍子本身长度的一半。输入文件的最后一行为3个负数，代表输入结束，该测试数据不需处理。

输出

对每个测试数据，输出金属棍子中心加热后偏离的距离，单位为毫米，保留小数点后3位有效数字。

样例输入

1
1000 100 0.0001
2
15000 10 0.00006
3
10 0 0.001
4
-1 -1 -1

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const double eps = 1e-12;
5
const double pi = 3.1415926535;
6
int main() {
7
    double l, t, c;
8
    while (cin >> l >> t >> c) {
9
        if (l < 0 && t < 0 && c < 0)break;
10
        double nl = (1.0 + t * c) * l;
11
        double dr = pi, dl = 0.0;
12
        while (1) {
13
            double mid = (dr + dl) / 2;
14
            double r = l / (sin(mid / 2) * 2);
15
            if (dr - dl < eps) {
16
                double ans = r - r * cos(mid / 2.0);
17
                printf("%.3lf\n", ans);
18
                break;
19
            }
20
            double bar = mid * r;
21
            if (bar > nl)dr = mid;
22
            else dl = mid;
23
        }
24
    }
25

26
    return 0;
27
}

1268: C005 电缆主

题目描述

奶牛的居民决定举办一场编程区域赛。裁判委员会自告奋勇并宣称要举办有史以来最公正的比赛。队员们的电脑采用“星型”拓扑结构互连（也就是说要把所有电脑都连在一个中央集线器上）。为了让比赛尽可能公正，裁判委员会的头头们决定：将比赛队员们平均地安置在集线器周围，距离集线器有一个相同的距离。裁判委员会为了采买网络电缆，联系了一家当地的网络方案提供商，要求他们提供一些登等长的电缆。这些电缆应越长越好，从而使得队员们与其他队员的距离越大。这家公司的电缆工来办这件事。他知道仓库里每个电缆的长度（精确到厘米）。他每次切割电缆时的精度也是厘米。但他现在不知切多少，所以完全茫然中。你要写个程序计算出一条电缆最多多长使之可以提供一定能够数目的电缆，帮着这位电缆工完成任务。

输入

第一行是两个整数N和K，N（1<=N<=10000）是仓库里的电缆数，K（1<=K<=10000）是所需电缆数。接下来的N行每一行一个数，表示电缆的长度（单位是米）。电缆长度最小为1米，最大为100千米。每个表示长度的数均表示为带两位小数的浮点数（即精确到厘米）。

输出

所需的电缆一条最长有多少米（精确到厘米，即保留小数点两位）。如果不能提供K条大于等于1厘米的等长电缆就输出“0.00”。

样例输入

样例输出

1
2.00

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 10050;
5
int len[maxn];
6
int n, k;
7
int cnt(int l) {
8
    int ret = 0;
9
    for (int i = 0;i < n;i++) {
10
        ret += len[i] / l;
11
    }
12
    return ret;
13
}
14
int main() {
15
    cin >> n >> k;
16
    int left = 1, right = 0;
17
    for (int i = 0;i < n;i++) {
18
        double ni;cin >> ni;
19
        ni *= 100;
20
        right = max(right, (int)ni);
21
        len[i] = (int)ni;
22
    }
23
    if (cnt(1) < k) {
24
        cout << "0.00\n";
25
        return 0;
26
    }
27
    int ans = 0;
28
    while (left <= right) {
29
        int mid = (left + right) / 2;
30
        if (cnt(mid) < k)right = mid - 1;
31
        else {
32
            ans = mid;
33
            left = mid + 1;
34
        }
35
    }
36
    printf("%.2lf", 1.0 * ans / 100);
37

38
    return 0;
39
}

1269: C006 宝贝鱼

题目描述

你刚刚从奶牛搬到一个大城市里。这里的人说一种让人理解不能的外文方言。万幸，你有本字典可以帮助你理解。

输入

输入包含多达100，000个字典词条，然后是一个空行，然后是一条消息，这条消息包含多达100，000个单词。每个词条占一行，先是一个英语单词，然后是一个空格，然后是一个外文方言词。一个方言词在字典中出现不超过一次。消息是一个外文方言词序列，一个词占一行。每个词是一个最长为10的小写字母序列。

输出

将消息的外文词翻译成英语，一个词一行。查不到的词应该翻译成“eh”。

样例输入

1
dog ogday
2
cat atcay
3
pig igpay
4
froot ootfray
5
loops oopslay
6

7
atcay
8
ittenkay
9
oopslay

样例输出

1
cat
2
eh
3
loops

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 10050;
5
map<string, string>mp;
6
int main() {
7
    string s1, s2;
8
    while (1) {
9
        char t = getchar();
10
        if (t == '\n')break;
11
        cin >> s1 >> s2;
12
        s1.insert(s1.begin(), t);
13
        mp.insert(make_pair(s2, s1));
14
        cin.get();
15
    }
16
    string word;
17
    while (cin >> word) {
18
        auto pos = mp.find(word);
19
        if (pos != mp.end()) {
20
            cout << pos->second << endl;
21
        }
22
        else cout << "eh\n";
23
    }
24

25
    return 0;
26
}

1270: C007 星空

题目描述

将夜空抽象成二维平面，每个星星一个(X,Y)坐标。这些点可以形成多少正方形？

输入

多组输入。对于每组数据，第一行是n（1<=n<=1000）表示已知星星数，然后是n行，每行一个坐标值。坐标绝对值小于20000。n=0表示结束。

输出

对于每组数据输出形成正方形的个数。

样例输入

样例输出

1
1

参考代码

算法2动态规划D

1272: D001 数字三角形

题目描述

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

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

输入

输入的第一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出

输出最大的和。

样例输入

样例输出

1
30

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 120;
5
ll number[maxn][maxn];
6
ll dp[maxn][maxn]; // 记录走到(i,j)点时最好的和
7

8
int main() {
9
    int n;
10
    while (cin >> n) {
11
        for (int i = 1;i <= n;i++)
12
            for (int j = 1;j <= i;j++)
13
                cin >> number[i][j];
14
        for (int i = 1;i < n;i++)
15
            dp[n][i] = number[n][i];
16
        for (int i = n;i > 1;i--) {
17
            for (int j = 1;j <= i;j++) {
18
                dp[i - 1][j] = max(dp[i][j], dp[i][j + 1]) + number[i - 1][j];
19
            }
20
        }
21
        cout << dp[1][1] << endl;
22
    }
23

24
    return 0;
25
}

1273: D002 最长上升子序列

题目描述

一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … <iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入

输入有很多组，每组输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

输出

输出每组的最长上升子序列的长度。

样例输入

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

样例输出

参考代码

1
#include<iostream>
2
#include<vector>
3
using namespace std;
4
typedef long long ll;
5
const int maxn = 1010;
6
int a[maxn];
7
// int dp[maxn];
8
int main() {
9
    int n;
10
    while (cin >> n) {
11
        for (int i = 1;i <= n;i++)cin >> a[i];
12
        vector<int> lmax;
13
        lmax.push_back(a[1]);
14
        for (int i = 2;i <= n;i++) {
15
            if (a[i] > lmax.back()) {
16
                lmax.push_back(a[i]);
17
            }
18
            else if (a[i] < lmax.back()) {
19
                int l = 0, r = lmax.size() - 1;
20

21
                while (l < r) {
22
                    int md = (l + r) / 2;
23
                    if (lmax[md] <= a[i])l = md + 1;
24
                    else r = md;
25
                }
26
                lmax[l] = a[i];
27
            }
28
            // for (int j = 0;j < lmax.size();j++)
29
            //     cout << lmax[j] << " ";
30
            // cout << endl;
31
        }
32
        cout << lmax.size() << endl;
33
    }
34

35
    return 0;
36
}

1274: D003 Help Jimmy

题目描述

“Help Jimmy” 是在下图所示的场景上完成的游戏：

场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。 Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。设计一个程序，计算Jimmy到地面时可能的最早时间。

输入

第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。1<= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）。所有坐标的单位都是米。 Jimmy 的大小和平台的厚度均忽略不计。如果Jimmy 恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy一定能安全到达地面。

输出

对输入的每组测试数据，输出一个整数，Jimmy到地面时可能的最早时间。

样例输入

样例输出

1
23

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 2e4 + 20;
5
struct PT {
6
    int x1, x2, h;
7
    bool operator<(const PT& P)const {
8
        return h > P.h;
9
    }
10
}pt[maxn];
11
int n, x, y, mx;
12
int findnext(int id, int x) {
13
    // 寻找x下的第一块板
14
    for (int i = id + 1;i <= n + 1;i++) {
15
        if (pt[i].x1 <= x && pt[i].x2 >= x) {
16
            return i;
17
        }
18
    }
19
    return -1;
20
}
21
int fun[maxn];
22
int dfs(int id, int p, int from) {
23
    // cout << id << " " << p << " " << from << endl;
24
    int lp = pt[id].x1, rp = pt[id].x2;
25
    // 当前是否到达终点
26
    if (id == n + 1)
27
        return 0;
28
    int lenl = -1, lenr = -1;
29
    // 左走
30
    int lpid = findnext(id, lp);
31
    if (lpid != -1 && pt[id].h - pt[lpid].h <= mx) {
32
        // 可走
33
        lenl= dfs(lpid, lp, id);
34
    }
35
    // 右走
36
    int rpid = findnext(id, rp);
37
    if (rpid != -1 && pt[id].h - pt[rpid].h <= mx) {
38
        // 可走
39
        lenr= dfs(rpid, rp, id);
40
    }
41
    if (lenl != -1 && lenr != -1)
42
        return fun[id] = min(lenl + p - lp, lenr + rp - p);
43
    else if (lenl == -1)
44
        return fun[id] = lenr + rp - p;
45
    else if (lenr == -1)
46
        return fun[id] = lenl + p - lp;
47
    else
48
        return 0;
49
}
50

51
int main() {
52
    int t;cin >> t;
53
    while (t--) {
54
        cin >> n >> x >> y >> mx;
55
        pt[0].x1 = x;pt[0].x2 = x;pt[0].h = y;
56
        for (int i = 1;i <= n;i++) {
57
            cin >> pt[i].x1 >> pt[i].x2 >> pt[i].h;
58
        }
59
        pt[n + 1].h = 0;pt[n + 1].x1 = -maxn;pt[n + 1].x2 = maxn;
60
        sort(pt, pt + n + 1);
61
        // 从高到低排列
62
        dfs(0, x, -1);
63
        cout << y + fun[0] << endl;
64
    }
65

66
    return 0;
67
}

1275: D004 最长公共子序列

题目描述

我们称序列Z = < z1, z2, …, zk >是序列X = < x1, x2, …, xm >的子序列当且仅当存在严格上升的序列< i1, i2, …, ik >，使得对j = 1, 2, … ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b,c, f, b, c >的子序列。现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。

输入

输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。

输出

输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。

样例输入

1
abcfbc abfcab
2
programming contest
3
abcd mnp

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int maxn = 220;
4
int dp[maxn][maxn];
5
int main() {
6
    ios::sync_with_stdio(false);
7
    cin.tie(0);
8
    cout.tie(0);
9
    string s, t;
10
    while (cin >> s >> t) {
11
        s = " " + s;t = " " + t;
12
        memset(dp, 0, sizeof(dp));
13
        for (int i = 1;i < s.size();i++) {
14
            for (int j = 1;j < t.size();j++) {
15
                if (s[i] == t[j])
16
                    dp[i][j] = dp[i - 1][j - 1] + 1;
17
                else
18
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
19
            }
20
        }
21
        cout << dp[s.size() - 1][t.size() - 1] << endl;
22
    }
23

24
    return 0;
25
}

1276: D005 陪审团的人选

题目描述

在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。

输入

输入包含多组数据。每组数据的第一行是两个整数n和m，n是候选人数目，m是陪审团人数。注意，1<=n<=200, 1<=m<=20而且m<=n。接下来的n行，每行表示一个候选人的信息，它包含2个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0。

输出

对每组数据，先输出一行，表示答案所属的组号, 如 ‘Jury #1’, ‘Jury #2’, 等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。

样例输入

样例输出

1
Jury #1
2
Best jury has value 6 for prosecution and value 4 for defence:
3
2 3

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
const int N = 205;
5
const int inf = 0x3f;
6
int dp[N][25][4 * N], a[N], b[N];
7
vector<int> mark;
8

9
int main()
10
{
11
    int n, m, T = 1;
12
    while (cin >> n >> m && n) {
13
        mark.clear();
14
        memset(dp, -inf, sizeof(dp));
15
        dp[0][0][400] = 0;
16
        for (int i = 1;i <= n;i++) {
17
            cin >> a[i] >> b[i];
18
        }
19
        for (int i = 1;i <= n;i++) {
20
            for (int j = 0;j <= m;j++) {
21
                for (int k = 0;k <= 800;k++) {
22
                    dp[i][j][k] = dp[i - 1][j][k];
23
                    int tt = k - a[i] + b[i];
24
                    if (tt < 0 || tt >= 800)
25
                        continue;
26
                    if (j == 0)
27
                        continue;
28
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][tt] + a[i] + b[i]);
29
                }
30
            }
31
        }
32
        int t = 0;
33
        while (dp[n][m][t + 400] < 0 && dp[n][m][-t + 400] < 0) t++;
34
        if (dp[n][m][t + 400] > dp[n][m][-t + 400]) t += 400;
35
        else t = 400 - t;
36

37
        int nn = n, mm = m, cnt = 0;
38
        while (mm) {
39
            if (dp[nn][mm][t] == dp[nn - 1][mm][t]) {
40
                nn--;
41
            }
42
            else {
43
                mark.push_back(nn);
44
                t -= a[nn] - b[nn];
45
                nn--;mm--;
46
                cnt++;
47
            }
48
        }
49
        int sum1 = 0, sum2 = 0;
50
        for (int i = 0;i < cnt;i++) {
51
            sum1 += a[mark[i]];
52
            sum2 += b[mark[i]];
53
        }
54
        cout << "Jury #" << T++ << "\nBest jury has value " << sum1 << " for prosecution and value " << sum2 << " for defence:\n";
55
        for (int i = cnt - 1;i >= 0;i--)
56
            cout << mark[i] << ' ';
57
        cout << "\n\n";
58
    }
59

60
    return 0;
61
}

1277: D006 最大和

题目描述

给定一个n个整数的集合：A={a1, a2,…, an}，我们如下定义函数d(A)：

$$ d(A)=\max\limits_{1\leq s_1\leq t_1\leq s_2\leq t_2\leq n} \begin{aligned} \sum_{i=s_1}^{t_1}a_i+\sum_{j=s_2}^{t_2}a_j\ \end{aligned} $$

你的任务就是计算函数d(A)的函数值。提示：对于样例，我们选择{2,2,3,-3,4} 和 {5}，进行想加得到函数d(A)的函数值。输入量大，建议使用scanf();

输入

输入包含 T(<=30)个样例，在输入的第一行即是整数T。每个样例包含两行，第一行是整数 n(2<=n<=50000)，第二行包含了n个整数： a1, a2, …, an. (|ai| <= 10000)。

输出

对于每个输入样例，输出一行，即如上定义函数d(A)的函数值。

样例输入

1
1
2
10
3
1 -1 2 2 3 -3 4 -4 5 -5

样例输出

1
13

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int maxn = 2200;
4
int a[maxn];
5
int leftt[maxn], rightt[maxn];
6
int lmax[maxn], rmax[maxn];
7
int main() {
8
    int t;cin >> t;
9
    while (t--) {
10
        int n;cin >> n;
11
        for (int i = 1;i <= n;i++)
12
            cin >> a[i];
13
        leftt[1] = a[1];rightt[n] = a[n];
14
        lmax[1] = a[1];rmax[n] = a[n];
15
        for (int i = 2;i <= n;i++) {
16
            leftt[i] = max(leftt[i - 1] + a[i], a[i]);
17
            lmax[i] = max(lmax[i - 1], leftt[i]);
18
        }
19
        for (int i = n - 1;i > 0;i--){
20
            rightt[i] = max(rightt[i + 1] + a[i], a[i]);
21
            rmax[i] = max(rmax[i + 1], rightt[i]);
22
        }
23
        int ans = a[1];
24
        for (int i = 2;i <= n;i++)
25
            ans = max(ans, lmax[i - 1] + rmax[i]);
26
        cout << ans << endl;
27
    }
28

29
    return 0;
30
}

1278: D007 最大子矩阵

题目描述

给你一个二维矩阵，元素是整数，有正有负。一个子矩阵就是最小1*1最大包含这个矩阵本身的矩阵。一个矩阵的和就是矩阵中所有元素求和，最大子矩阵就是所有子矩阵中和最大的那个字矩阵。下面是一个例子： 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 最大子矩阵在左下角 9 2 -4 1 -1 8 和值是15。

输入

输入的第一行是整数N，即表示要输入一个N * N的整数矩阵。接下来是N^2 个整数，每个整数之间被空格或者空行分开，这些整数即为矩阵中的数，按照列优先的顺序排列，即第一行整数从左至右输入，第二行从左至右输入…. 第n行从左至右输入。N不会大于100，矩阵中的整数范围为 [-127,127]。

输出

输出最大矩阵的和。

样例输入

1
4
2
0 -2 -7 0 9 2 -6 2
3
-4 1 -4  1 -1 8  0 -2

样例输出

1
15

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int maxn = 120;
4
int rec[maxn][maxn];
5
int pre[maxn][maxn];
6
int dp[maxn][maxn];
7
int main() {
8
    int n;cin >> n;
9
    pre[0][0] = 0;
10
    // 二维前缀和
11
    for (int i = 1;i <= n;i++) {
12
        for (int j = 1;j <= n;j++) {
13
            cin >> rec[i][j];
14
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + rec[i][j];
15
        }
16
    }
17
    // for (int i = 1;i <= n;i++) {
18
    //     for (int j = 1;j <= n;j++) {
19
    //         cout << pre[i][j] << " ";
20
    //     }
21
    //     cout << endl;
22
    // }
23
    int ans = -200;
24
    for (int xi = 1;xi <= n;xi++) {
25
        for (int yi = 1;yi <= n;yi++) {
26
            for (int xj = xi;xj <= n;xj++) {
27
                for (int yj = yi;yj <= n;yj++) {
28
                    int sum = pre[xj][yj] - pre[xi - 1][yj] - pre[xj][yi - 1] + pre[xi - 1][yi - 1];
29
                    ans = max(ans, sum);
30
                }
31
            }
32
        }
33
    }
34
    cout << ans << endl;
35

36
    return 0;
37
}

算法2搜索E

1281: E001 数的划分

题目描述

将整数n分成k份，且每份不能为空，任意两种分法不能相同（不考虑顺序）。例如：n=7，k=3，下面三种分法被认为是相同的。 1,1,5；1,5,1；5,1,1；问有多少种不同的分法。

输入

每组数据由一行上的2个整数n，k构成（6<n≤200,2≤k≤6）。

输出

对每组测试数据，输出不同的分法整数。

样例输入

1
7 3

样例输出

1
4

参考代码

1
#include<bits/stdc++.h>
2
#define AUTHOR "DODOLA"
3
using namespace std;
4
typedef long long ll;
5
const int maxn = 220;
6
ll dp[maxn][maxn];  // i个小球放入j个盒子没有空盒的方法数
7
int main() {
8
    int n, k;
9
    cin >> n >> k;
10
    for (int i = 1;i <= n;i++) {
11
        dp[i][1] = 1;dp[i][0] = 1;
12
    }
13
    for (int i = 2;i <= n;i++) {
14
        for (int j = 2;j <= k;j++) {
15
            if (i > j)
16
                dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
17
            else
18
                dp[i][j] = dp[i - 1][j - 1];
19
        }
20
    }
21
    cout << dp[n][k] << endl;
22

23
    return 0;
24
}

1282: E002 闪避湖泊

题目描述

农夫约翰的农场在最近的一场暴风雨中被水淹没。但保险公司仅根据他得农场中最大的“湖泊”的大小赔偿一个数额。农场可表示为N行M列的长方形网格，（1≤N≤100,1≤M≤100）。网格中的每个单元或是干的或是被淹没的，且恰有K个单元被水淹没，（1≤K≤N*M）。正如人们所希望的，湖泊是一个中间单元，它与其他的单元共享一条长边（不是角落）。任何与中间单元共享一条长边或者与连通单元共享一条长边的单元是一个连通单元，是湖泊的一部分。

输入

有多组数据。每组的第1行有3个整数N，M和K。第2行到第K+1行，是整数R和C，表示被淹没的位置。

输出

对每组测试数据，输出有最大湖泊的单元的数目。

样例输入

样例输出

1
4

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 150;
5

6
int n, m, k;
7
bool fd[maxn][maxn];
8
int mv[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
9

10
int ans;
11
int dfs(int r, int c) {
12
    if (r<1 || r>n || c<1 || c>m || !fd[r][c])return 0;
13
    fd[r][c] = false;
14
    int ret = 1;
15
    for (int i = 0;i < 4;i++) {
16
        ret += dfs(r + mv[i][0], c + mv[i][1]);
17
    }
18
    return ret;
19
}
20

21
void solve() {
22
    fill(fd[0], fd[0] + maxn * maxn, false);
23
    ans = 0;
24
    for (int ki = 0;ki < k;ki++) {
25
        int r, c;cin >> r >> c;
26
        fd[r][c] = true;
27
    }
28
    for (int i = 1;i <= n;i++) {
29
        for (int j = 1;j <= m;j++) {
30
            if (fd[i][j]) {
31
                ans = max(ans, dfs(i, j));
32
            }
33
        }
34
    }
35
    cout << ans << "\n";
36
}
37

38
int main() {
39
    while (cin >> n >> m >> k)
40
        solve();
41

42
    return 0;
43
}
44
/*
45
0 1 0 0 0
46
0 0 1 1 0
47
0 1 1 0 0
48
*/

1283: E003 信道分配

题目描述

当无线电台在一个非常大的区域上传播信号时，为了每个接收器都能得到较强信号，使用转发器转发信号。然而，需要仔细地选择每个转发器使用的频道，以使附近的转发器不彼此干扰。如果邻近的转发器使用不同的频道，条件就得到满足。因为无线电波的频谱是宝贵的资源，转发器所需频道的数量应减到最少。编程任务：读取转发器网络的描述信息，并计算出所需频道的最小使用量。

输入

输入包含许多转发器网络图。每幅图的第一行是转发器数目（1~26）。转发器用连续的大写字母表示，从A开始。例如，10个转发器的名称分别是A，B，C，…，I和J。当转发器的个数是0时，表示输入结束。转发器数目之后，是其邻近关系的列表。每行的格式为 A：BCDH 表示转发器B、C、D和H与转发器A邻近。第一行描述与转发器A邻近的，第二行描述与B邻近的，直到描述完所有的转发器。如果某个转发器不与其他转发器相邻，它的形式为 A：转发器依字母顺序列出。注意：相邻是对称的关系；如果A与B相邻，那么B与A也相邻。因为转发器位于水平面内，由相邻的转发器构成的网络图没有相交的线。

输出

对于每幅图（除了最后一个没有转发器），输出一行，是转发器不互相干扰所需的最少频道数。输出格式参考样例输出。注意：频道数为1的话，“channel”为单数。

样例输入

1
2
2
A:
3
B:
4
4
5
A:BC
6
B:ACD
7
C:ABD
8
D:BC
9
0

样例输出

1
1 channel needed.
2
3 channels needed.

参考代码

1
#include<iostream>
2
#include<stdio.h>
3
#include<string.h>
4
#include<algorithm>
5
using namespace std;
6
typedef long long ll;
7
const int maxn = 120;
8
bool fd[maxn][maxn];
9
int ind[30], t;
10
bool dfs(int from, int clr) {
11
    // 从from着色
12
    for (int i = 0;i < clr;i++) {
13
        bool f = true;ind[from] = i;
14

15
        for (int j = 0;j < from;j++) {
16
            if (ind[j] == i && fd[from][j]) {
17
                f = false;
18
                break;
19
            }
20
        }
21

22
        if (f && (from == t - 1 || dfs(from + 1, clr)))
23
            return true;
24
    }
25
    return false;
26
}
27

28
int main() {
29
    while (cin >> t) {
30
        cin.get();
31
        if (t == 0)break;
32
        memset(fd, 0, sizeof(fd));
33
        memset(ind, 0, sizeof(ind));
34
        bool f = true;
35
        for (int i = 0;i < t;i++) {
36
            string msg;cin >> msg;
37
            if (msg.size() == 2)
38
                continue;
39
            f = false;
40
            int pid = msg[0] - 'A';
41
            for (int j = 2;j < msg.size();j++) {
42
                fd[pid][msg[j] - 'A'] = true;
43
                fd[msg[j] - 'A'][pid] = true;
44
            }
45
        }
46
        if (f)
47
            cout << "1 channel needed.\n";
48
        else if (dfs(1, 2))
49
            cout << "2 channels needed.\n";
50
        else if (dfs(1, 3))
51
            cout << "3 channels needed.\n";
52
        else
53
            cout << "4 channels needed.\n";
54
    }
55

56
    return 0;
57
}

1284: E004 移动的骑士

题目描述

你的一个朋友正在研究骑士旅行问题（TKP）。在一个有n个方格的棋盘上，你得找到一条最短的封闭骑士旅行的路径，使能够遍历每个方格一次。他认为问题的最困难部分在于，对两个给定的方格，确定骑士移动所需的最小步数。所以你帮助他编写一个程序，解决这个“困难的”部分。你的任务是：输入有两个方格a和b，确定骑士在最短路径上从a到b移动的次数。

国际象棋中的骑士在棋盘上可移动的范围如下图：

输入

输入包含一组或多组测试例。每个测试例一行，是两个方格，用空格隔开。棋盘上的一个方格用一个字符串表示，字母（a-h）表示列，数字（1-8）表示行。

输出

对每个测试例，输出一行：“To get from xx to yy takes n knight moves.”。

样例输入

1
e2 e4
2
a1 b2
3
b2 c3
4
a1 h8
5
a1 h7
6
h8 a1
7
b1 c3
8
f6 f6

样例输出

1
To get from e2 to e4 takes 2 knight moves.
2
To get from a1 to b2 takes 4 knight moves.
3
To get from b2 to c3 takes 2 knight moves.
4
To get from a1 to h8 takes 6 knight moves.
5
To get from a1 to h7 takes 5 knight moves.
6
To get from h8 to a1 takes 6 knight moves.
7
To get from b1 to c3 takes 1 knight moves.
8
To get from f6 to f6 takes 0 knight moves.

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 150;
5

6
string fs, ts;
7
int mv[8][2] = { {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1} };
8

9
void bfs(int x1, int y1, int x2, int y2) {
10
    if (x1 == x2 && y1 == y2) {
11
        cout << "To get from " << fs << " to " << ts << " takes 0 knight moves.\n";
12
        return;
13
    }
14
    int stp = 0;
15
    queue<pair<int, int>> q;
16
    q.push({ x1, y1 });
17
    while (!q.empty()) {
18
        queue<pair<int, int>> qs;
19
        while (!q.empty()) {
20
            auto [x, y] = q.front();q.pop();
21
            for (int i = 0;i < 8;i++) {
22
                int nx = x + mv[i][0], ny = y + mv[i][1];
23
                if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8)continue;
24
                if (nx == x2 && ny == y2) {
25
                    cout << "To get from " << fs << " to " << ts << " takes " << stp + 1 << " knight moves.\n";
26
                    return;
27
                }
28
                qs.push({ nx, ny });
29
            }
30
        }
31
        stp++;
32
        q = qs;
33
    }
34

35
}
36

37
void solve() {
38
    int x1 = fs[0] - 'a', y1 = fs[1] - '1', x2 = ts[0] - 'a', y2 = ts[1] - '1';
39
    bfs(x1, y1, x2, y2);
40
}
41

42
int main() {
43
    while (cin >> fs >> ts)
44
        solve();
45

46
    return 0;
47
}

1285: E005 图像周长

题目描述

病理学实验室的技术人员需要分析幻灯片的数字图像。幻灯片上有许多要分析的目标，由鼠标单击确定一个目标。目标边界的周长是一个有用的测量参数。编程任务：确定选中目标的在周长。数字化的幻灯片是一个矩形的网格，里面有点’.’，表示空的地方；有大写字母‘X’，表示目标的一部分。简单网格如下所示

方格中的一个X是指一个完整的网络方形区域，包括其边界和目标本身。网格中心的X与其边界上8个方向的X都是相邻的。任何两个相邻的X，其网格方形区域在边界或者拐角处是重叠的，所以他们的网格方形区域是相邻的。一个目标是由一系列相邻X的网格方形区域连接起来构成的。在网格1中，一个目标填充了全部网格；在网格2中有两个目标，其中一个目标只占左下角的一个网格方形区域，其余的X属于另一个目标。技术人员总是能单击到一个X，以选中包含该X的目标，记录单击时的坐标。行列号是从左上角开始，从1开始编号的。在网格1中，技术人员可以单击行2和列2选择目标；在网格2中，单击行2和列3就可以选中较大目标，单击行4和列3就不能选中任何目标。一个有用的统计参数是目标的周长。假定每个X的每条边上有一个方形的单元。在网格1中目标的周长是8（4个边，每个边上有2个方形的单元）；在网格2中，较大目标的周长是18，如下图所示。

目标中不会包含任何完全封闭的孔，所以下面最左边的网格不会出现，应该是右边的网格样式。

输入

输入有多组网格。对每个网格，第一行是网格的行列数（rows，columns），鼠标单击的行列号（row，column），其整数范围都是1-20.接下来就是rows行，由字符‘.’和‘X’构成。当一行是4个0时，标志输入结束。一行中的4个数字之间各有一个空格。网格数据的行之间没有空行。

输出

对每个网络输出一行，是选中目标的周长。

样例输入

1
2 2 2 2
2
XX
3
XX
4
6 4 2 3
5
.XXX
6
.XXX
7
.XXX
8
...X
9
..X.
10
X...
11
5 6 1 3
12
.XXXX.
13
X....X
14
..XX.X
15
.X...X
16
..XXX.
17
0 0 0 0

样例输出

参考代码

1
#include<bits/stdc++.h>
2
#define AUTHOR "DODOLA"
3
// #include<queue>
4
// #include<iostream>
5
// #include<string>
6
using namespace std;
7
const int maxn = 250;
8
typedef long long ll;
9
int r, c, x, y;
10
vector<string>mp(maxn);
11

12
int mv[8][2] = {
13
    {1,0},{0,1},{-1,0},{0,-1},
14
    {1,1},{1,-1},{-1,-1},{-1,1},
15
};
16
int ans;
17
bool ck[maxn][maxn];
18

19
void dfs(int px, int py) {
20
    // cout << px << " " << py << endl;
21
    // cout << ans << endl;
22
    if (mp[px][py] != 'X' || ck[px][py])return;
23
    ck[px][py] = true;
24

25
    for (int j = 0;j < 4;j++) {
26
        int xj = px + mv[j][0], yj = py + mv[j][1];
27
        if (mp[xj][yj] != 'X')
28
            ans++;
29
    }
30

31
    for (int i = 0;i < 8;i++) {
32
        int xi = px + mv[i][0];
33
        int yi = py + mv[i][1];
34
        dfs(xi, yi);
35
    }
36
}
37

38
string s0('.', maxn - 1);
39
void solve() {
40
    ans = 0;
41
    fill(ck[0], ck[0] + sizeof(ck), false);
42
    fill(mp.begin(), mp.end(), s0);
43
    for (int i = 1;i <= r;i++) {
44
        cin >> mp[i];
45
        mp[i] = " " + mp[i] + " ";
46
    }
47
    dfs(x, y);
48
    cout << ans << "\n";
49
}
50

51
int main() {
52
    mp[0] = s0;
53
    while (cin >> r >> c >> x >> y) {
54
        if (!r && !c && !x && !y)break;
55
        solve();
56
    }
57

58
    return 0;
59
}

1286: E006 移动的骑士

题目描述

Somurolov先生是一个国际象棋高手，他声称在棋盘上将骑士棋子从一点移动到另外一点，没有人比他快，你敢挑战他吗？你的任务是编程计算出将一个骑士棋子从一点移动到另外一点，最少需要移动的步数。显而易见，这样你就有赢得Somurolov先生的机会。国际象棋中的骑士在棋盘上可移动的范围如下图：

输入

首先输入测试样例的个数n。接下来是n组输入数据，每组测试数据由三行整数组成：第一行是棋盘的边长l (4 <= l <= 300)，整个棋盘的面积也就是 ll；第二行和第三行分别是骑士棋子的初始位置和目标位置，表示为整数对形式{0, …, l-1}{0, …, l-1}。保证棋子的初始和目标位置是棋盘上的合法位置。

输出

对于每一个输入的测试样例，请你算出骑士从初始位置移动到目标位置最小移动步数。如果初始位置和目标位置相同，那么骑士移动的距离就是0。最后单独一行输出所求距离。

样例输入

样例输出

1
5

参考代码

1
#include <iostream>
2
#include <queue>
3
#include <cstring>
4
#define AUTHOR "DODOLA"
5
using namespace std;
6

7
struct P {
8
    int x;
9
    int y;
10
    int step;
11
};
12

13
int mv[8][2] = {
14
    {1, 2}, {2, 1}, {-1, 2}, {-2, 1},
15
    {1, -2}, {2, -1}, {-1, -2}, {-2, -1}
16
};
17

18
int bfs(int n, int x1, int y1, int x2, int y2)
19
{
20
    if (x1 == x2 && y1 == y2)
21
    {
22
        return 0;
23
    }
24
    bool gnd[n][n];
25
    queue<P> q;
26
    memset(gnd, 0, sizeof(gnd));
27
    P start, node;
28
    start.x = x1;
29
    start.y = y1;
30
    start.step = 0;
31
    q.push(start);
32
    while (!q.empty()) {
33
        int x0, y0, step;
34
        start = q.front();
35
        q.pop();
36
        x0 = start.x;
37
        y0 = start.y;
38
        step = start.step;
39
        for (int j = 0; j < 8; j++) {
40
            int x3 = x0 + mv[j][0];
41
            int y3 = y0 + mv[j][1];
42
            if (x3 == x2 && y3 == y2)
43
                return step + 1;
44
            if (x3 >= 0 && x3 < n && y3 >= 0 && y3 < n && !gnd[x3][y3]) {
45
                node.x = x3;
46
                node.y = y3;
47
                node.step = step + 1;
48
                q.push(node);
49
                gnd[x3][y3] = 1;
50
            }
51
        }
52
    }
53
    return 0;
54
}
55

56
int main() {
57
    int t;
58
    cin >> t;
59
    while (t--) {
60
        int x1, y1, x2, y2, n;
61
        cin >> n >> x1 >> y1 >> x2 >> y2;
62
        cout << bfs(n, x1, y1, x2, y2) << endl;
63
    }
64
    return 0;
65
}

1287: E007 寻找M

题目描述

给出一个整数n，编程求出一个非零整数m，使得m是n的倍数，并且m的十进制表示中只有1和0。给出的n不大于200并且肯定存在对应的m，m是十进制数并且不大于100位。

输入

输入包含多组测试数据。每组测试数据只有一个整数n (1 <= n <= 200)。整数0标志输入的结束。

输出

对于每个n输出对应的整数m，m的十进制表示不多于100位。如果对于一个n存在多个合法的m，你只需输出一个即可。

样例输入

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 10;
5
int n;
6

7
bool ck(int x) {
8
    while (x) {
9
        if (x % 10 == 0 || x % 10 == 1) {
10
            x /= 10;
11
            continue;
12
        }
13
        else return false;
14
    }
15
    return true;
16
}
17

18
void solve() {
19
    for (int i = 1;;i++) {
20
        int m = i * n;
21
        bool f = ck(m);
22
        if (f) {
23
            cout << m << endl;
24
            return;
25
        }
26
    }
27
}
28

29
int main() {
30
    while (cin >> n) {
31
        if (n == 0)break;
32
        solve();
33
    }
34

35
    return 0;
36
}

1288: E008 红与黑

题目描述

有一个矩形的房间，房间铺着正方形的地砖。每个地砖被涂上红色或者黑色。初始时你站在房间里的某个黑色地砖上，你每次只能移动到相邻的四个地砖之一，即上下左右移动，并且你每次只能移动到黑色的地砖上，不能走到红色地砖。编程计算出按照上述要求你能走到的黑色地砖的个数。

输入

输入包含多组测试数据。每组测试数据第一行包括2个整数W和H；W和H是房间的宽度和长度，分别表示为房间的x和y坐标轴。W和H不大于20。接下来是H行每行W个地砖的房间，每个地砖表示如下： ‘.’——黑色地砖 ‘#’——红色地砖 ‘@’ ——你在房间里的初始位置（房间只出现一次）。输入的最后一行是两个整数0，不用处理。

输出

对每个测试样例，输出一行，即你能走到的黑色地砖的个数（包括你初始站在的黑色地砖）。

样例输入

1
6 9
2
....#.
3
.....#
4
......
5
......
6
......
7
......
8
......
9
#@...#
10
.#..#.
11
11 9
12
.#.........
13
.#.#######.
14
.#.#.....#.
15
.#.#.###.#.
16
.#.#..@#.#.
17
.#.#####.#.
18
.#.......#.
19
.#########.
20
...........
21
0 0

样例输出

参考代码

1
#include <iostream>
2
#include <queue>
3
#include <cstring>
4
const int maxn = 120;
5
using namespace std;
6
int r, c;
7
char mp[maxn][maxn];
8
int mv[4][2] = {
9
    {0,1},{0,-1},{1,0},{-1,0},
10
};
11

12
int ans;
13

14
void dfs(int x, int y) {
15
    if (x < 0 || x == c || y < 0 || y == r)return;
16
    if (mp[x][y] == '#')return;
17
    ans++;
18
    mp[x][y] = '#';
19
    for (int i = 0;i < 4;i++) {
20
        int xi = x + mv[i][0];
21
        int yi = y + mv[i][1];
22
        dfs(xi, yi);
23
    }
24
}
25

26
void solve() {
27
    ans = 0;
28
    int px, py;
29
    for (int i = 0;i < c;i++) {
30
        for (int j = 0;j < r;j++) {
31
            cin >> mp[i][j];
32
            if (mp[i][j] == '@') {
33
                px = i;py = j;
34
            }
35
        }
36
    }
37
    dfs(px, py);
38
    cout << ans << endl;
39
}
40

41
int main() {
42
    while (cin >> r >> c) {
43
        if (!r && !c)break;
44
        solve();
45
    }
46

47
    return 0;
48
}

1289: E009 小木棒

题目描述

George有一些长度相等的木棒，他随意的将这些木棒切成长度最多是50的小木棒。麻烦来了，他现在想将这些杂乱的小木棒恢复到原来的木棒，但是他忘记了原来到木棒的数量和长度。请你帮助他设计一个程序计算出原来木棒可能的最小长度，所有小木棒的长度均表示为大于0的整数。

输入

每组输入数据包括两行。第一行是George切后小木棒的个数，最多有64根小木棒；第二行是这些小木棒的长度，这些长度表示为空格分开的整数。输入样例以整数0表示结束。

输出

输出一行，即为原始木棒可能的最小长度。

样例输入

1
9
2
5 2 1 5 2 1 5 2 1
3
4
4
1 2 3 4
5
0

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int maxn = 80;
4

5
int n, a[maxn], maxv, tot, vis[maxn], k, len;
6

7
bool cmp(int a, int b) {
8
    return a > b;
9
}
10
bool dfs(int i, int rest, int p) {
11
    if (i > k)
12
        return 1;
13
    int fail = 0;
14
    for (int x = p + 1;x <= n;x++) {
15
        if (!vis[x]) {
16
            if (a[x] == a[fail]) continue;
17
            if (rest > a[x]) {
18
                vis[x] = 1;
19
                bool w = dfs(i, rest - a[x], x);
20
                vis[x] = 0;
21
                if (!w) fail = x;
22
                if (w) return 1;
23
            }
24
            else if (rest == a[x]) {
25
                vis[x] = 1;
26
                bool w = dfs(i + 1, len, 0);
27
                vis[x] = 0;
28
                return w;
29
            }
30
            if (p == 0) return 0;
31
        }
32
    }
33
    return 0;
34
}
35

36
void solve() {
37
    fill(vis, vis + n + 5, 0);
38
    maxv = tot = 0;
39
    for (int i = 1;i <= n;i++) {
40
        cin >> a[i];
41
        maxv = max(maxv, a[i]);
42
        tot += a[i];
43
    }
44
    sort(a + 1, a + 1 + n, cmp);
45
    for (len = maxv;len <= tot;len++) {
46
        if (tot % len == 0) {
47
            k = tot / len;
48
            if (dfs(1, len, 0)) {
49
                cout << len << endl;
50
                break;
51
            }
52
        }
53
    }
54
}
55

56
int main() {
57
    while (cin >> n && n)
58
        solve();
59

60
    return 0;
61
}

算法2贪心F

1290: F001 木棒加工问题

题目描述

现有n根木棒，已知它们的长度和重量。要用一部木工机一根一根地加工这些木棒。该机器在加工过程中需要一定的准备时间，是用于清洗机器，调整工具和模板的。木工机需要的准备时间如下：（1）第一根木棒需要1min的准备时间；（2）在加工了一根长为l，重为w的木棒之后，接着加工一根长为l’（l≤l’），重为w’（w≤w’）的木棒是不需要任何准备时间的。否则需要一分钟的准备时间。给定n根木棒，你要找到最少的准备时间。例如现在有长和重分别为（4,9），（5,2），（2,1），（3,5）和（1,4）的五根木棒，那么所需准备时间最少为2min，顺序为（1,4），（3,5），（4,9），（2,1），（5,2）。

输入

输入有多组测试例。输入数据的第一行是测试例的个数（T）。每个测试例两行：第一行是一个整数n（1≤n≤5000），表示有多少根木棒；第二行包括n*2个整数，表示l1,w1,l2,w2,l3,w3,…,ln,wn,全部不大于10000，其中li和wi表示第i根木棒的长度和重量。数据由一个或多个空格分隔。

输出

输出是以分钟为单位的最少准备时间，一行一个。

样例输入

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

样例输出

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 1e5 + 50;
5

6
int n;
7
bool ck[maxn];
8
void solve() {
9
    cin >> n;
10
    fill(ck, ck + 5050, false);
11
    vector<pair<int, int>> len;
12
    for (int i = 0; i < n; i++) {
13
        int l, w;cin >> l >> w;
14
        len.push_back(make_pair(l, w));
15
    }
16
    sort(len.begin(), len.end());
17
    int cnt = 0, ans = 0;
18
    while (cnt < n) {
19
        ans++;
20
        int ki = 0;
21
        int li = 0, wi = 0;
22
        for (int i = 0;i < n;i++) {
23
            if (!ck[i]) {
24
                ki = i;
25
                li = len[i].first, wi = len[i].second;
26
                ck[i] = true;
27
                cnt++;
28
                break;
29
            }
30
        }
31
        // cout << ki << " " << li << " " << wi << endl;
32
        for (int i = 0;i < n;i++) {
33
            if (ck[i])continue;
34
            if (li <= len[i].first && wi <= len[i].second) {
35
                ck[i] = true;
36
                cnt++;
37
                li = len[i].first, wi = len[i].second;
38
            }
39
        }
40
    }
41
    cout << ans << endl;
42
}
43
int main() {
44
    int t;cin >> t;
45
    while (t--)
46
        solve();
47

48
    return 0;
49
}

1291: F002 装箱

题目描述

一个工厂生产的产品形状都是长方体，高度都是h，主要有1x1，2x2，3x3，4x4，5x5，6x6等6种。这些产品在邮寄时被包装在一个6x6xh的长方体包裹中。由于邮费很贵，工厂希望减小每个订单的包裹数量以增加他们的利润。因此他们需要一个好的程序帮他们解决这个问题。你的任务就是设计这个程序。

输入

输入包括多组测试数据，每一行代表一个订单。每个订单里的一行包括六个整数，用空格隔开，从小到大分别为这6种产品的数量。6个0表示文件结束。

输出

针对每个订单输出一个整数，占一行，代表对应的订单所需的最小包裹数。没有多余的空行。

样例输入

1
0 0 4 0 0 1
2
7 5 1 0 0 0
3
0 0 0 0 0 0

样例输出

参考代码

1
// #include<bits/stdc++.h>
2
#include<iostream>
3
using namespace std;
4
typedef long long ll;
5
const int maxn = 2e5 + 50;
6

7
int n;
8
int b1, b2, b3, b4, b5, b6;
9
int l3[4] = { 0,7,6,5 };
10
int l2[4] = { 0,5,3,1 };
11
int l1[9] = { 0,32,28,24,20,16,12,8,4 };
12
void solve() {
13
    int ans = b6 + b5 + b4 + (b3 + 3) / 4;
14
    int n2 = 5 * b4 + l2[b3 % 4];;
15
    if (n2 >= b2) {
16
        int n1 = b5 * (36 - 25) + (n2 - b2) * 4 + l3[b3 % 4];
17
        if (n1 < b1)
18
            ans += (b1 - n1 + 35) / 36;
19
    }
20
    else {
21
        int m2 = b2 - n2;
22
        ans += (m2 + 8) / 9;
23
        int n1 = b5 * (36 - 25) + l3[b3 % 4] + l1[m2 % 9];
24
        if (n1 < b1)
25
            ans += (b1 - n1 + 35) / 36;
26
    }
27
    cout << ans << endl;
28
}
29

30
int main() {
31
    while (cin >> b1 >> b2 >> b3 >> b4 >> b5 >> b6 && (b1 || b2 || b3 || b4 || b5 || b6))
32
        solve();
33
}

1292: F003 移动桌子

题目描述

著名的ACM（Advanced Computer Maker）公司租用了一层有400个房间的办公楼，结构如下。

这层楼沿着走廊南北向的两边各有200个房间。最近，公司要做一次装修，需要在各个办公室之间搬运办公桌。由于走廊狭窄，办公桌都很大，走廊里一次只能通过一张办公桌。必须制定计划提高搬运效率。经理制定如下计划：一张办公桌从一个房间移动到另一个房间最多用十分钟。当从房间i移动一张办公桌到房间j，两个办公室之间的走廊都会被占用。所以，每10分钟内，只要不是同一段走廊，都可以在房间之间移动办公桌。为了说得更清楚一些，经理举例说明哪些情况可以同时移动，哪些情况不能同时移动。

每个房间，只有一张办公桌进出。现在，经理想找到一种方案，使移动桌子的事情尽快完成。请编写程序解决经理的难题。

输入

输入数据有T组测试例，在第一行给出测试例个数（T）。每个测试例的第一行是一个整数N（1≤N≤200），表示要搬运办公桌的次数。接下来N行，每行两个正整数s和t，表示一张桌子，是从房间号码s移到房间号码t。有多组输入数据，输入第一行为一个表示输入数据总数的整数N，然后是N组输入数据。

输出

每组输入都有一行的输出数据，为一整数T，表示完成任务所花费的最少时间。

样例输入

样例输出

参考代码

1
// #include<bits/stdc++.h>
2
#include<iostream>
3
#include<algorithm>
4
#include<vector>
5
using namespace std;
6
typedef long long ll;
7
const int maxn = 2e5 + 50;
8

9
int n;
10
void solve() {
11
    cin >> n;
12
    int pass[220] = {};
13
    for (int i = 1;i <= n;i++) {
14
        int x, y;cin >> x >> y;
15
        x = (x + 1) / 2;
16
        y = (y + 1) / 2;
17
        if (x > y) {
18
            x = x ^ y;y = x ^ y;x = x ^ y;
19
        }
20
        for (int j = x;j <= y;j++) {
21
            pass[j]++;
22
        }
23
    }
24
    int ans = *max_element(pass + 1, pass + 201);
25
    cout << 10 * ans << endl;
26
}
27

28
int main() {
29
    int t;cin >> t;
30
    while (t--)
31
        solve();
32
}

1293: F004 基因集合

题目描述

随着大量的基因组DNA序列数据被获得，它对于了解基因越来越重要（基因组DNA的一部分，是负责蛋白质合成的）。众所周知，在基因组序列中，由于存在垃圾的DNA中断基因的编码区，真核生物（相对于原核生物）的基因链更加复杂。也就是说，一个基因被分成几个编码片段（称为外显子）。虽然在蛋白质的合成过程中，外显子的顺序是固定的，但是外显子的数量和长度可以是任意的。大多数基因识别算法分为两步：第一步，寻找可能的外显子；第二步，通过寻找一条拥有尽可能多的外显子的基因链，尽可能大地拼接一个基因。这条链必须遵循外显子出现在基因组序列中的顺序。外显子i在外显子j的前面的条件是i的末尾必须在j开头的前面。本题的目标是，给定一组可能的外显子，找出一条拥有尽可能多的外显子链，拼接成一个基因。

输入

给出几组输入实例。每个实例的开头是基因组序列中可能的外显子数n(0 < n < 1000)。接着的n行，每行是一对整数，表示外显子在基因组序列中的起始和结束位置。假设基因组序列最长为50000。当一行是0时，表示输入结束。

输出

对于每个实例，找出最可能多的外显子链，输出链中的外显子，并占一行。假如有多条链，但外显子数相同，那么可以输出其中任意一条。

样例输入

样例输出

1
3 1 5 6 4

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 2e5 + 50;
5

6
struct node {
7
    int x;int y;
8
    int i;
9
    bool operator<(const node& p)const {
10
        return x < p.x;
11
    }
12
}wxz[maxn];
13

14
int n;
15
void solve() {
16
    for (int i = 1;i <= n;i++) {
17
        cin >> wxz[i].x >> wxz[i].y;
18
        wxz[i].i = i;
19
    }
20
    sort(wxz + 1, wxz + 1 + n);
21
    vector<node>ans;
22
    ans.push_back(wxz[1]);
23
    for (int i = 2;i <= n;i++) {
24
        struct node ni = ans.back();
25
        if (ni.y > wxz[i].y) {
26
            ans.pop_back();ans.push_back(wxz[i]);
27
        }
28
        else if (ni.y < wxz[i].x) {
29
            ans.push_back(wxz[i]);
30
        }
31
    }
32
    for (int i = 0;i < ans.size();i++) {
33
        cout << ans[i].i << " ";
34
    }
35
    cout << '\n';
36
}
37

38
int main() {
39
    while (cin >> n && n)
40
        solve();
41
}

1294: F005 主框架

题目描述

多纳先生是ACM（Agent on Computing of Mathematics，计算数学代理商）大型计算机的管理员。该代理商为一些公司承担在大型计算机上的计算工作，完成工作后获得报酬，因此大型计算机对这个代理商来说太重要了。多纳先生需要为这些在大型计算机上运行的作业安排顺序。一旦要运行某个作业，他就要检查运行该作业所需要的空闲资源。如果空闲资源足够的话，他就为该作业分配这些资源；否则就将该作业挂起，直至有足够的资源投入运行。刚开始他并不熟悉这项工作，把事情搞得很乱。日积月累，他就胜任这项工作了。而且他还总结了一套规则：（1）大型计算机有M个CPU和N大小的内存空间可供分配。

（2）对等待运行的作业有一个等待队列。可以假定这个队列足够长，能够存放所有等待运行的作业。

（3）假定作业Ji需要Ai个CPU和Bi的内存空间，在时间Ti到达等待队列，需要在时间Ui之前完成。成功运行后，代理商可以获得Vi()的报酬；如果能在规定的时间之前完成，则每小时还可以额外获得Wi()的奖金；如果工期拖延，则每小时赔偿Xi()。例如，假定一个作业的报酬是10，时限8小时，每拖欠一小时罚2。如果该作业在10小时完成，则代理商可以获得10-(10-8)*2=6。

（4）当一个作业开始后，就独占了分配给它的CPU和内存空间，不能同时再分配给其他作业。当该作业运行结束后，这些资源被释放。如果资源足够多，同时可以运行多个作业。

（5）为了最大限度地发挥大型计算机的计算能力，每个作业在开始运行后刚好一小时就完成。你可以假定每个作业的运行时间就是一小时。

（6）没有作业运行时，机器空闲，一直到一个作业进入作业等待队列。

（7）如果有多个作业进入作业等待队列，则报酬高的作业优先。可以假定这些作业的报酬都不相等。

（8）如果某个作业的空闲CPU或内存空间不能满足，它就是被挂起一小时，也不占用任何资源。一小时后，再次为该作业检查资源，而不需要考虑等待队列里的其他作业。如果资源仍不满足要求，那就继续挂起一小时，把资源分配给其他在等待队列里的作业。否则，该作业将独占CPU和存储空间并投入运行。

（9）当多个作业挂起时，采取先来先服务的原则。

使用这些规则，多纳先生把事情安排得井井有条。现在除了日常公务外，代理商要求他根据作业列表计算收入。给定某个时间F，计算出已经完成的作业和应该被完成的作业。对作业Ji，如果它的时限Ui>F并且仍未完成，就不需要统计收入。对已经完成的作业或Ui≤F的作业都要统计。如果工作没有完成，它不会给代理商带来报酬，但到这个时间F为止的罚款仍要计算。

他不会程序设计，又不想手工做，现在你帮助他解决这个问题。

输入

有多组测试例。每个测试例描述大型计算机的资源和作业列表，第一行是整数F（0≤F≤10000），表示时限。接下来的一行是三个整数M，N和L（M，N，L≥0），M是机器CPU的数量，N是存储空间的大小，L是作业等待队列中作业的数量。最多有10000个作业。后面的L行是作业的信息。描述作业Ji的数据是7个整数：Ai，Bi，Ti，Ui，Vi，Wi，Xi。Ai和Bi（Ai，Bi≥0）指出了该作业对CPU和内存的需求。Ti和Ui表示作业的到达时间和时限（0≤Ti≤Ui）。Vi，Wi，Xi分别是工作的报酬、奖励和罚款。一个空的测试例（F=0）表示输入结束，该测试点无需处理。

输出

根据作业列表计算总收入。对每个测试例，输出测试例编号，一个冒号，一个空格，然后是收入。测试例之间有一个空行。注意：对尚未投入运行的、且时限超过F的作业，不必统计。

样例输入

1
10
2
4 256 3
3
1 16 2 3 10 5 6
4
2 128 2 4 30 10 5
5
2 128 2 4 20 10 5
6
0

样例输出

1
Case 1: 74

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 1e5 + 20;
5

6
struct JOB {
7
    int a, b, t, u, v, w, x;
8
    bool ok;
9
    JOB(int a, int b, int t, int u, int v, int w, int x) :a(a), b(b), t(t), u(u), v(v), w(w), x(x), ok(false) {}
10
    bool operator<(const JOB& N)const {
11
        if (N.t == t)
12
            return v > N.v;
13
        return t < N.t;
14
    }
15
};
16
int ind = 1;
17
int f;
18
int m, n, l;
19
int mi, ni;
20
void solve() {
21
    cin >> m >> n >> l;
22
    vector<JOB>tot;
23
    for (int i = 0;i < l;i++) {
24
        int a, b, t, u, v, w, x;
25
        cin >> a >> b >> t >> u >> v >> w >> x;
26
        tot.push_back(JOB(a, b, t, u, v, w, x));
27
    }
28
    sort(tot.begin(), tot.end());
29
    int ans = 0;
30
    for (int i = 1;i <= f;i++) {
31
        mi = m;ni = n;
32
        for (int j = 0;j < l;j++) {
33
            if (tot[j].t >= i)
34
                break;
35
            if (tot[j].ok || mi < tot[j].a || ni < tot[j].b)
36
                continue;
37
            tot[j].ok = true;
38
            mi -= tot[j].a;
39
            ni -= tot[j].b;
40
            ans += tot[j].v;
41
            if (i > tot[j].u)
42
                ans -= (i - tot[j].u) * tot[j].x;
43
            else if (i < tot[j].u)
44
                ans += (tot[j].u - i) * tot[j].w;
45
        }
46
    }
47
    for (int i = 0;i < l;i++) {
48
        if (!tot[i].ok && tot[i].u <= f)
49
            ans -= (f - tot[i].u) * tot[i].x;
50
    }
51
    printf("Case %d: %d\n\n", ind, ans);
52
    ind++;
53
}
54

55
int main() {
56
    while (cin >> f && f)
57
        solve();
58

59
    return 0;
60
}

1295: F006 整数区间

题目描述

一个整数区间[a,b] (a < b)，是一个从a到b连续整数的集合。现在给你n个整数区间，编程找出一个集合R，使得n个集合中的每个集合都有2个整数出现在R中，并且这个集合R包含的整数个数最少。

输入

输入有多组数据，每组第一行包含整数n(1 <= n <= 10000)，表示整数区间的个数。接下来n行，每行包含两个整数a和b(0 <= a < b <= 10000, a < b)。

输出

输出符合条件的集合R中元素的个数。

样例输入

样例输出

1
4

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 1e5 + 50;
5

6
int cnt[maxn];
7
int n;
8
int ck[maxn];
9
bool hasi[maxn];
10
void solve() {
11
    while (cin >> n) {
12
        fill(hasi, hasi + 10005, false);
13
        fill(ck, ck + n + 5, 0);
14
        fill(cnt, cnt + 10005, 0);
15
        if (!n)return;
16
        vector<pair<int, int>> v;
17
        for (int i = 0;i < n;i++) {
18
            int a, b;
19
            cin >> a >> b;
20
            v.push_back(make_pair(a, b));
21
            for (int j = a;j <= b;j++) {
22
                cnt[j]++;
23
            }
24
        }
25
        int ans = 0;
26
        while (true) {
27
            int mx = max_element(cnt, cnt + 10005) - cnt;
28
            // cout << mx << endl;
29
            if (cnt[mx] == 0)break;
30
            hasi[mx] = true;
31
            ans++;
32
            fill(cnt, cnt + 10005, 0);
33
            for (int i = 0;i < n;i++) {
34
                if (ck[i] == 2)continue;
35
                if (v[i].first <= mx && v[i].second >= mx) {
36
                    ck[i]++;
37
                }
38
                if (ck[i] == 2)continue;
39

40
                for (int j = v[i].first;j <= v[i].second;j++) {
41
                    if (hasi[j])
42
                        continue;
43
                    cnt[j]++;
44
                }
45
            }
46
        }
47
        cout << ans << endl;
48
    }
49
}
50

51
int main() {
52
    // int t;cin >> t;
53
    // while (t--)
54
    solve();
55

56
    return 0;
57
}

1296: F007 安装雷达

题目描述

我们假设海岸线是一条无限直线：以海岸线为界，陆地和海洋被分开，在海边分布着很多小岛。现在，我们在海岸线上安装雷达，每个雷达有固定的通讯范围（以d为半径的圆形区域），这样，海边的小岛就可以被某个雷达信号覆盖。这里我们使用笛卡尔坐标系，定义海岸线为x轴，x轴上方是海洋，下方是陆地。给出分布在海边每个小岛的坐标位置和雷达信号能覆盖的范围d，你的任务是计算出最小需要安装的雷达数目，使得这些雷达信号能覆盖到所有海边的小岛。每个小岛的坐标格式为(x,y)。如下图所示，给出第一个输入样例的坐标表示，这样在(-2,0),(1,0)上分别安装雷达就可以覆盖所有的小岛（p点），所以我们只需要安装2个雷达。

输入

输入包含多组测试样例。每组测试第一行包含两个整数n(1<=n<=1000)和d，n表示小岛的数目，d表示雷达能覆盖的范围的半径。接下来n行，每行由整数x和y组成，表示n个小岛的坐标位置。每两组数据之间有一个空行。输入0 0表示输入的结束。

输出

对于每一组输入，按照输出样例中的格式输出：包含输出序号和最少需要安装雷达的数目。如果找不到解决方案，即不能找到一种安装方案覆盖所有的小岛，输出”-1”。

样例输入

样例输出

1
Case 1: 2
2
Case 2: 1

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
struct node {
6
    double x, y;
7
    node(double x, double y) :x(x), y(y) {}
8
    bool operator < (const node& a) const {
9
        return y < a.y;
10
    }
11
};
12
int n;
13
int d;
14
int ind;
15
void solve() {
16
    ind = 1;
17
    while (cin >> n >> d) {
18
        if (n == 0 && d == 0)return;
19
        bool f = true;
20
        vector<node> q;
21
        for (int i = 0;i < n;i++) {
22
            int x, y;cin >> x >> y;
23
            if (d < y)
24
                f = false;
25
            if (!f)continue;
26
            double ei = sqrt(1.0 * d * d - 1.0 * y * y);
27
            q.push_back(node{ x - ei,x + ei });
28
        }
29
        if (!f) {
30
            printf("Case %d: -1\n", ind);
31
            ind++;
32
            continue;
33
        }
34
        sort(q.begin(), q.end());
35
        int ans = 1;
36
        double yi = q[0].y;
37
        for (int i = 1;i < q.size();i++) {
38
            if (q[i].x <= yi) {
39
                continue;
40
            }
41
            else {
42
                ans++;
43
                yi = q[i].y;
44
            }
45
        }
46
        printf("Case %d: %d\n", ind, ans);
47
        ind++;
48
    }
49
}
50

51
int main() {
52
    // int t;cin >> t;
53
    // while (t--)
54
    solve();
55

56

57
    return 0;
58
}

1297: F008 排队买饭

题目描述

周晓晓吃完中午饭后又觉得没吃饱，因此想要再去食堂买点饭，当她走进食堂发现已经有n个人排队了，她知道每个人买饭需要的时间。她想帮助大家尽快的买到饭，即让n个人的平均等待时间最小，周晓晓已经饿的无法想出办法，只想知道他们最小的平均等待时间是多少，你能帮助她吗?

输入

输入可能有多组，每组第一行为一个整数n。第二行 n 个整数，第 i 个整数 Ti 表示第i个人的等待时间Ti。

输出

每组输出占一行，为每组最小的平均等待时间（输出结果精确到小数点后两位）。

样例输入

1
10
2
56 12 1 99 1000 234 33 55 99 812

样例输出

1
532.00

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 1e5 + 20;
5
int a[maxn];
6

7
int n;
8
void solve() {
9
    for (int i = 0;i < n;i++)cin >> a[i];
10
    sort(a, a + n);
11
    int ans = 0;
12
    int tmp = 0;
13
    for (int i = 0;i < n;i++) {
14
        tmp += a[i];
15
        ans += tmp;
16
    }
17
    printf("%.2lf\n", 1.0 * ans / n);
18
}
19

20
int main() {
21
    while (cin >> n)
22
        solve();
23

24
    return 0;
25
}

1298: F009 放书

题目描述

周小小最近想为自己的图书室添置一个巨型书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。所有N(1<=N<=2000)把椅子都有一个确定的高度Hi（1<=Hi<=1000）。为了够到书架顶，周小小想像演杂技一般，将椅子一个一个的叠在一起，并上去把书架的空间补上。显然，椅子叠的越多，就越不稳定，于是小小希望在够到书架顶的前提下，让椅子数量尽量少，作为聪明的你，一定能帮助他计算出这个最小数量吧。

输入

第1行: 2个用空格隔开的整数：N和B，表示有N把椅子和书架的高度；第2行到N+1行: 第i+1行是1个整数：Hi，表示椅子的高度。可能存在多组输入数据。

输出

输出1个整数，即最少要多少把椅子。（如果到不了顶端，输出-1）

样例输入

样例输出

1
3

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 2010;
5
int h[maxn];
6

7
int n, b;
8
void solve() {
9
    for (int i = 0;i < n;i++)
10
        cin >> h[i];
11
    sort(h, h + n);
12
    int sum = 0, cnt = 0;
13
    for (int i = n - 1;i >= 0;i--) {
14
        sum += h[i];
15
        cnt++;
16
        if (sum >= b) {
17
            cout << cnt << endl;
18
            return;
19
        }
20
    }
21
    cout << -1 << endl;
22
}
23

24
int main() {
25
    while (cin >> n >> b)
26
        solve();
27

28
    return 0;
29
}