程序设计综合实践练习

[TOC]

一，基础算法1

1249: 士兵队列训练问题

题目描述

某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。

输入

​ 本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。

输出

​ 共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。

样例输入

1
2
3
2
20
40

样例输出

1
2
1 7 19
1 19 37

思路&解决

tmp的vector不断更新，count根据奇偶性改变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n, count = 0;
	cin >> n;
	while (n--) {
		int m; cin >> m;
		vector<int>soldiers(m);
		for (int i = 0; i < m; i++) {
			soldiers[i] = i + 1;
		}
		while (soldiers.size() > 3) {
			vector<int>tmp;
			if (count % 2 == 0) {
				for (int i = 0; i < soldiers.size(); i++) {
					if ((i + 1) % 2 != 0) {
						tmp.push_back(soldiers[i]);
					}
				}
			}
			else {
				for (int i = 0; i < soldiers.size(); i++) {
					if ((i + 1) % 3 != 0) {
						tmp.push_back(soldiers[i]);
					}
				}
			}
			count++;
			soldiers = tmp;
		}
		for (int i = 0; i < soldiers.size(); i++) {
			cout << soldiers[i] << " ";
		}
		cout << endl;
	}
	return 0;
}

1198: 斐波那契数列

题目描述

斐波那契数列中, a0=0, a1=1, ,对于k > 1, ak = ak-1 + ak-2 求出斐波那契数列的第n项。

输入

第一行输入一个整数T表示样例个数,对于每个样例,输入一个整数n表示需要求出第n项斐波那契数字。

输出

对于每个样例,输出一个数字num表示第n项斐波那契数字。

样例输入

1
2
3
4
3
1
2
3

样例输出

1
2
3
1
1
2

提示

n <= 60

思路&解答

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
#define int long long
using namespace std;
signed main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> fib(n + 1);
        fib[0] = 0, fib[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        cout << fib[n] << endl;
    }
    return 0;
}

1544: [数值问题]高精度加法

题目描述

​ 输入两个高精度正整数a和b（a，b的位数<=200），求这两个数的和

输入

输入共两行，分别为a和b

输出

输出共一行，表示两个数的和。

样例输入 复制

1
2
1111111111111111111111111111111111
9999999999999999999999999999999999

样例输出 复制

1
11111111111111111111111111111111110

思考&解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstring>
using namespace std;
string reverse(string str) {
    int n = str.length();
    for (int i = 0; i < n / 2; i++) {
        swap(str[i], str[n - i - 1]);
    }
    return str;
}
string add(string a,string b) {
    string res;
    int carry = 0;
    int len1 = a.size(), len2 = b.size();
    a = reverse(a); b = reverse(b);
    int i = 0, j = 0;
    while(i<len1||j<len2){
        int sum = carry;
        if (i < len1) {
            sum += a[i] - '0';
            i++;
        }
        if (j < len2) {
            sum += b[j] - '0';
            j++;
        }
        carry = sum / 10;
        sum %= 10;
        res += (sum + '0');
    }
    if (carry) {
        res += carry + '0';
    }
    return reverse(res);
}
int main() {
	string a,b;
	cin >> a >> b;
	cout << add(a,b) << endl;
	return 0;
}

1237: 三角形个数

题目描述

​ 小b有一个仅包含非负整数的数组a，她想知道有多少个三元组(i,j,k)，满足i<j<k且a[i],a[j],a[k]可能作为某个三角形的三条边的边长。

输入

1
2
3
第一行输入一个正整数n，表示数组a中元素个数；
第二行n个非负整数，表示a中元素，以空格隔开；
其中0＜n≤1000，a中任意元素a[i]满足0≤a[i]≤1000。

输出

1
输出一个数，表示满足题意的三元组个数

样例输入

1
2
4
2 2 3 4

样例输出

1
3

思考&解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a[1000];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            int k = j + 1;
            while (k < n && a[i] + a[j] > a[k]) {
                k++;
            }
            ans += k - j - 1;
        }
    }
    cout << ans << endl;

    return 0;
}

1234: 找零

题目描述

​ 假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？如果无法支付K元，则输出-1。

输入

输入第一行为一个整数T，表示样例个数。
对于每个样例，第一行输入一个整数N表示需要找零的钱数，第二行输入7个整数表示每个纸币拥有的数量，分别表示1,2,5,10,20,50,100纸币的个数。

输出

对于每个样例，输出一个数字表示最少找零个数，输出-1表示无法找开。

样例输入 复制

1
2
3
4
5
2
107
1 1 1 1 1 1 1 
200
1 1 1 1 1 0 0

样例输出 复制

1
2
3
-1

提示

数据保证贪心可解。

思路&解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
~~~

### 1199: 汉诺塔      

**题目描述**

汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

**输入**

第一行包含一个整数T表示样例数。
 对于每个样例,输入一个n表示汉诺塔的级数。

**输出**

对于每个样例,输出一个整数表示最少需要移动的次数。

**样例输入**           复制          

```plain
3
1
2
3
```

**样例输出**          复制          

```plain
1
3
7
```

**提示**

n <= 40

**思路&解答**

~~~C++

1219: 绝对值排序

题目描述

输入n(n<=100)个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。

输入

输入数据有多组，每组占一行，每行的第一个数字为n,接着是n个整数，n=0表示输入数据的结束，不做处理。

输出

​ 对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。

样例输入

1
2
3
3 3 -4 2
4 0 1 2 -3
0

样例输出

1
2
-4 3 2
-3 2 1 0

思路&解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<algorithm>

using namespace std;
int ssort(int a, int b) {
    return abs(b) > abs(a);
}
int main() {
    int a;
    int b[1010];
    while (cin >> a) {
        for (int i = 0; i < a; i++) {
            cin >> b[i];
        }
        sort(b,b+a,ssort);
        for (int i = 0; i < a; i++) {
            cout << b[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

二，基础算法2

1110: 最多水容器

题目描述

给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离.
container-with-most-water-leetcode-puzzle-coding-exercise C++ 编程练习题 - 最多水容器 (递归) ACM题解 程序设计

输入

第一行输入一个数字N表示容器个数。第二行输入N个使用空格间隔的整数，表示容器高度。

输出

输出一个数字表示最多装水量。

样例输入

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

样例输出

1
49

提示

2 <= N <= 10

思路&解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
int a[20];//放外面不需要赋零
int main() {
	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	int sum = 0;
	for (int j = 0; j < m - 1; j++) {
		for (int k = j+1; k < m; k++) {
			int tmp = (min(a[j], a[k]) * (k - j));
			if (tmp > sum)sum = tmp;
		}
	}
	cout << sum<<endl;
	return 0;
}

1197: 区间和统计

题目描述

给定一个包含n个元素的数组,数组中元素ai保证 -1000 < ai < 1000。在数组中,从l到r(l <= r)的所有数叫做数组的一个[l, r]子区间,你需要求出,所有子区间中,和为k的区间一共有多少个。

输入

第一行包含一个整数T表示样例个数。
对于每一个样例,第一行输入两个数字,n, p其中n表示数组的长度, p代表区间和。
第二行包含n个数字表示数组的元素。

输出

对于每一个样例,输出一个数字表示和为p的子区间个数。

样例输入

1
2
3
1
5 8
4 4 4 4 4

样例输出

1
4

提示

所有的ai均为整数。
保证 n <= 1000

思路&解答

遍历数组，计算前缀和

用哈希表记录前缀和出现的次数，对于i，如果前缀和prefix_sum[i]-p在哈希表中已经出现过了，说明从上一个出现该前缀和的位置到当前位置的子数组和为p，将这些子数组的数量累加到res中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <unordered_map>
using namespace std;
int a[1010],prefix_sum[1010];//放外面
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, p;
        cin >> n >> p;
        int res = 0;
        unordered_map<int, int> mp; //哈希表记录前缀和出现的次数
        mp[0] = 1;//初始化
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            prefix_sum[i + 1] = prefix_sum[i] + a[i];
            if (mp.count(prefix_sum[i + 1] - p)) { 
                res += mp[prefix_sum[i + 1] - p]; 
//将上一个出现该前缀和的位置到当前位置的子数组和为p的数量累加到结果中 }
            mp[prefix_sum[i + 1]]++; //
        }
        cout << res << endl;
    }
    return 0;
}

1125:子矩阵求和

思路&解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
using namespace std;
long long a[1001][1001];
int main() {
	int M, N, Q;
	cin >> M >> N >> Q;
	for (int i = 0; i < M; i++)
		for (int j = 0; j < N; j++)
			cin >> a[i][j];
	for (int k = 0; k < Q; k++) {
		int sum = 0;
		int num1, num2, num3, num4;
		cin >> num1 >> num2 >> num3 >> num4;
		for (int i1 = min(num1, num3); i1 <= max(num1, num3); i1++)
			for (int j1 = min(num2, num4); j1 <= max(num2, num4); j1++)
				sum += a[i1][j1];//最大值最小值转化为标准型去计算
		cout << sum << endl;
	}
	return 0;
}

1126: 选择排序

题目描述

给你一个序列，按照从小到大的顺序重新排列，要求使用选择排序

输入

​ 第一行是一个正整数m，代表测试样例的个数
对于每组测试样例，输入一行数字，第一个数字m，代表这组样例中数字的个数，接下来的m个数字代表所给序列

输出

对于每组输出样例，输出一行，输出按照从小到大顺序排列的结果

样例输入

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

样例输出

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

思路&解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        swap(arr[i], arr[min_idx]);//交换
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int arr[n];
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        selectionSort(arr, n);
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

1257: 前m大的数

题目描述

还记得Gardon给小希布置的那个作业么？其实小希已经找回了原来的那张数表，现在她想确认一下她的答案是否正确，但是整个的答案是很庞大的表，小希只想让你把答案中最大的M个数告诉她就可以了。
给定一个包含N(N<=3000)个正整数的序列，每个数不超过5000，对它们两两相加得到的N*(N-1)/2个和，求出其中前M大的数(M<=1000)并按从大到小的顺序排列。

输入

输入可能包含多组数据，其中每组数据包括两行：
第一行两个数N和M，
第二行N个数，表示该序列。

输出

对于输入的每组数据，输出M个数，表示结果。输出应当按照从大到小的顺序排列。

样例输入

1
2
3
4
4 4
1 2 3 4
4 5
5 3 6 4

样例输出

1
2
7 6 5 5
11 10 9 9 8

思路&解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<algorithm>

#define int long long
using namespace std;
int a[3010]; int b[5000000];//注意开对数组容量

int tmp(int a, int b) {
	return b < a;//从大到小是<
}
signed main() {
	int m, n;
	while (cin >> m >> n) {
		for (int i = 0; i < m; i++) {
			cin >> a[i];
		}
		
		int uu = 0;
		for (int j = 0; j < m; j++) {
			for (int k = j + 1; k < m; k++) {
				b[uu] = a[j] + a[k];
				uu++;
			}
		}
		sort(b, b + m*(m-1)/2, tmp);//先出结果再排序，放心，够用
		for (int u = 0; u < n; u++) {
			cout << b[u] << " ";
		}cout << endl;
	}
	return 0;
}

1238: Greed

题目描述

​ Jafar has n cans of cola. Each can is described by two integers: remaining volume of cola ai and can’s capacity bi (ai ≤  bi).

​ Jafar has decided to pour all remaining cola into just 2 cans, determine if he can do this or not!

Jafar has n cans of cola. Each can is described by two integers: remaining volume of cola ai and can’s capacity bi (ai  ≤   ≤  bi). Jafar has decided to pour all remaining cola into just 2 cans, determine if he can do this or not!

贾法尔有n罐可乐。每个罐由两个整数描述：可乐的剩余体积ai和罐的容量bi（ai ≤   ≤ bi）。 贾法尔决定把所有剩下的可乐倒进两个罐子里，看看他能不能做到！

输入

​ The first line of the input contains one integer n (2 ≤ n ≤ 100 000) — number of cola cans.

​ The second line contains n space-separated integers a, *a, …, *an* (0 ≤ *ai*) — volume of remaining cola in cans.
*

​ The third line contains n space-separated integers that b, *b, …, *bn* (*ai** ≤ bi) — capacities of the cans.

输入的第一行包含一个整数n（2 ≤（2 ≤ n ≤ 100 000）-可乐罐的数量。 第二行包含n个空格分隔的整数a，a，… an（0 ≤ ai）-罐中剩余可乐的体积。 第三行包含n个空格分隔的整数，B，…，B，…bn（ai彡bi）-罐的容量。

输出

​ Print “YES” (without quotes) if it is possible to pour all remaining cola in 2 cans. Otherwise print “NO” (without quotes).

​ You can print each letter in any case (upper or lower).

如果可以将剩余的可乐倒入2罐，请打印“YES”（不带引号）。否则打印“NO”（不带引号）。 您可以在任何情况下打印每个字母（上部或下部）。

样例输入 复制

1
2
3
2
3 5
3 6

样例输出 复制

1
YES

思路解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
#include <vector>
int cans[1009];
using namespace std;

int main() {
int n;
cin >> n;
//vecctor存储每个罐子信息
vector<pair<int, int>> cans(n);
for (int i = 0; i < n; i++) {
    cin >> cans[i].first;
}
for (int i = 0; i < n; i++) {
    cin >> cans[i].second;
}

sort(cans.begin(), cans.end(), [](pair<int, int>& a, pair<int, int>& b) {
    return a.second > b.second;
});

long long total_vol = 0;
for (int i = 0; i < n; i++) {
    total_vol += cans[i].first;
}

if (total_vol <= cans[0].second + cans[1].second) {
    cout << "YES\n";
} else {
    cout << "NO\n";
}

return 0;

}

1239: 珠心算测验

题目描述

​ 珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

​ 某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

​ 最近老师出了一些测验题，请你帮忙求出答案。

​

输入

共两行，第一行包含一个整数nn，表示测试题中给出的正整数个数。 第二行有nn个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。

输出

一个整数，表示测验题答案。

样例输入

1
2
4
1 2 3 4

样例输出

1
2

提示

由1+2=3,1+3=41+2=3,1+3=4，故满足测试要求的答案为22。 注意，加数和被加数必须是集合中的两个不同的数。

n <= 1000，集合中所有的数字保证小于等于1e7.

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#define int long long
using namespace std;
bool a[10000009]; int b[1010];
signed main() {
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> b[i]; a[b[i]] = 1;
	}
	int ans = 0;
	for (int i = 0; i < N - 1; i++) {
		for (int j = i + 1; j < N; j++) {
			if (a[b[i] + b[j]] == 1) { ans++; a[b[i] + b[j]] = 0; }
		}
	}
	cout << ans << endl;
	return 0;
}

1236: Monthly Expense

题目描述

​ 给出n天中每天的花费，需要将这些天分成m组，每组包含连续的一或多天，若第i组的花费为Ki，求一种分组方法使得K=max{Ki}最小。

输入

​ 输入数据第一行为两个正整数N和M，之后输入N个正整数，分别表示第i天的费用。输出包含一行，表示上面描述的K。

输出

对于每组数据，输出一个数表示最小的花费。

样例输入 复制

1
2
3
4
5
6
7
8
7 5
100
400
300
100
500
101
400

样例输出 复制

1
500

提示

n <= 100.

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100005;
int n, m;
int a[MAXN], sum[MAXN];

bool check(int x) {
    int cnt = 1, pre = 0;
    for (int i = 1; i <= n; i++) {
        if (sum[i] - sum[pre] > x) {
            cnt++;
            pre = i - 1;
        }
    }
    return cnt <= m;
}

int main() {
    while (cin >> n >> m) {
        memset(sum, 0, sizeof(sum));
        int l = 0, r = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            sum[i] = sum[i-1] + a[i];
            r += a[i];
        }
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << l << endl;
    }
    return 0;
}

三，数据结构

1330: ip转换

题目描述

在进行基于ipv4协议的网络通讯时，用长度为32的信号表示ip地址。为了便于使用，通常会将32位信号转换为4个长度为8的信号。
例如: 01111111000000000000000000000001会被转化为 127.0.0.1

现在给出一系列ip地址的二进制表示，需要转化为它的对应十进制便于阅读的表示方式，即a.b.c.d形式。

输入

第一行包含一个整数T表示样例个数
对于每个样例，输入一个长度为32的二进制串表示ip地址。

输出

对于每个样例，输出一行字符串表示便于阅读的ip地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
#include <bitset>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        bitset<32> bs(s); // 将二进制串转换为位集
        // 通过位运算获取四个字节的值
        int a = (bs.to_ulong() >> 24) & 0xFF;
        int b = (bs.to_ulong() >> 16) & 0xFF;
        int c = (bs.to_ulong() >> 8) & 0xFF;
        int d = bs.to_ulong() & 0xFF;
        cout << a << "." << b << "." << c << "." << d << endl; // 输出点分十进制表示的 IP 地址
    }
    return 0;
}

1337: 进制转换

题目描述

输入一个十进制数N，将它转换成R进制数输出。

输入

输入数据包含多个测试实例，每个测试实例包含两个整数N(32位整数)和R（2<=R<=16, R<>10）。

输出

为每个测试实例输出转换后的数，每个输出占一行。如果R大于10，则对应的数字规则参考16进制（比如，10用A表示，等等）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string convert(int n, int r) {
    string result = "";
    bool is_negative = false;

    if (n < 0) {
        is_negative = true;
        n = -n;
    }

    while (n > 0) {
        int digit = n % r;
        if (digit < 10) {
            result += to_string(digit);
        } else {
            result += 'A' + digit - 10;
        }
        n /= r;
    }

    if (result.empty()) {
        result = "0";
    }

    reverse(result.begin(), result.end());
    if (is_negative) {
        result = "-" + result;
    }

    return result;
}

int main() {
    int n, r;
    while (cin >> n >> r) {
        string result = convert(n, r);
        cout << result << endl;
    }
    return 0;
}

1206: 简单计算器

题目描述

读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。

输入

测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。

输出

对每个测试用例输出1行，即该表达式的值，精确到小数点后2位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <stack>
#include <string>
#include <cstring>
#include <cmath>

using namespace std;

int get_priority(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else {
        return 0;
    }
}

double do_operation(double left, double right, char op) {
    if (op == '+') {
        return left + right;
    } else if (op == '-') {
        return left - right;
    } else if (op == '*') {
        return left * right;
    } else if (op == '/') {
        return left / right;
    } else {
        return 0;
    }
}

double evaluate_expression(const string& expr) {
    stack<double> num_stack;
    stack<char> op_stack;

    int n = expr.size();
    int i = 0;
    while (i < n) {
        // Skip spaces
        while (i < n && expr[i] == ' ') {
            i++;
        }

        // Read a number
        if (isdigit(expr[i])) {
            int j = i;
            while (j < n && (isdigit(expr[j]) || expr[j] == '.')) {
                j++;
            }
            double num = stod(expr.substr(i, j - i));
            num_stack.push(num);
            i = j;
        }
        // Read an operator
        else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
            char op = expr[i];
            while (!op_stack.empty() && get_priority(op_stack.top()) >= get_priority(op)) {
                double right = num_stack.top();
                num_stack.pop();
                double left = num_stack.top();
                num_stack.pop();
                char prev_op = op_stack.top();
                op_stack.pop();
                double result = do_operation(left, right, prev_op);
                num_stack.push(result);
            }
            op_stack.push(op);
            i++;
        }
        // Skip other characters
        else {
            i++;
        }
    }

    while (!op_stack.empty()) {
        double right = num_stack.top();
        num_stack.pop();
        double left = num_stack.top();
        num_stack.pop();
        char op = op_stack.top();
        op_stack.pop();
        double result = do_operation(left, right, op);
        num_stack.push(result);
    }

    return num_stack.top();
}

int main() {
    string expr;
    while (getline(cin, expr)) {
        if (expr == "0") {
            break;
        }
        double result = evaluate_expression(expr);
        printf("%.2f\n", result);
    }
    return 0;
}

1207: 队列和栈

题目描述

​ 队列和栈是两种重要的数据结构，它们具有push k和pop操作。push k是将数字k加入到队列或栈中，pop则是从队列和栈取一个数出来。队列和栈的区别在于取数的位置是不同的。

  队列是先进先出的：把队列看成横向的一个通道，则push k是将k放到队列的最右边，而pop则是从队列的最左边取出一个数。
  
  栈是后进先出的：把栈也看成横向的一个通道，则push k是将k放到栈的最右边，而pop也是从栈的最右边取出一个数。
  
  假设队列和栈当前从左至右都含有1和2两个数，则执行push 5和pop操作示例图如下：
  
       push 5     pop
  
  队列 1 2 -------> 1 2 5 ------> 2 5
  
       push 5     pop
  
  栈  1 2 -------> 1 2 5 ------> 1 2 
  现在，假设队列和栈都是空的。给定一系列push k和pop操作之后，输出队列和栈中存的数字。若队列或栈已经空了，仍然接收到pop操作，则输出error。

输入

第一行为m，表示有m组测试输入，m<100。
每组第一行为n，表示下列有n行push k或pop操作。（n<150）
接下来n行，每行是push k或者pop，其中k是一个整数。
（输入保证同时在队列或栈中的数不会超过100个）

输出

​ 对每组测试数据输出两行，正常情况下，第一行是队列中从左到右存的数字，第二行是栈中从左到右存的数字。若操作过程中队列或栈已空仍然收到pop，则输出error。输出应该共2*m行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;

int main() {
    int m;
    cin >> m;
    while (m--) {
        int n;
        cin >> n;
        queue<int> q;
        stack<int> s;
        while (n--) {
            string op;
            cin >> op;
            if (op == "push") {
                int k;
                cin >> k;
                q.push(k);
                s.push(k);
            }
            else if (op == "pop") {
                if (q.empty() || s.empty()) {
                    //cout << "error" << endl;
                    continue;
                }
                q.pop();
                s.pop();
            }
        }
        // 输出队列中的数字
        if (q.empty()) {
            cout << "error"<< endl;
        }
        else {
            while (!q.empty()) {
                cout << q.front() << " ";
                q.pop();
            }
            cout << endl;
        }
        // 输出栈中的数字
        if (s.empty()) {
            cout << "error" <<endl;
        }
        else {
            vector<int> v;
            while (!s.empty()) {
                v.push_back(s.top());
                s.pop();
            }

            for (int i = v.size() - 1; i >= 0; --i) {
                cout << v[i] << " ";
            }
            cout <<endl;
        }
    }
    return 0;
}

1325: 报数

题目描述

今天一共n位同学参加了TIEI期末考试，大家计划在期末考试后在教室玩一个游戏，n个同学编号1-n后围成一圈报数，报到7的倍数的同学将被移出队伍，然后下一位同学继续现在的报数。当剩余人数少于7时结束游戏。
请你输出剩余同学的原始编号。

输入

第一行包含一个整数T，表示样例个数。
对于每个样例，包含一个单独的整数n表示同学的编号。

输出

对于每个样例，在一行输出剩余同学的编号，使用空格分隔。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include<algorithm>
using namespace std;

// 链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 构造循环链表
ListNode* createCircleList(int n) {
    ListNode* head = new ListNode(1);
    ListNode* cur = head;
    for (int i = 2; i <= n; i++) {
        cur->next = new ListNode(i);
        cur = cur->next;
    }
    cur->next = head; // 将最后一个节点指向头节点，形成循环
    return head;
}

// 删除第k个节点，并返回下一个节点
ListNode* deleteKthNode(ListNode* head, int k) {
    ListNode* cur = head;
    ListNode* prev = NULL;
    // 找到要删除的节点
    for (int i = 1; i < k; i++) {
        prev = cur;
        cur = cur->next;
    }
    // 删除该节点
    if (prev) {
        prev->next = cur->next;
    }
    else {
        head = cur->next;
    }
    free(cur);
    // 返回下一个节点
    return prev->next;
}

// 循环报数并删除节点，直到剩余人数少于7
void countAndDelete(ListNode* head, int n) {
    int an[6] = {};
    while (n > 6) {
        head = deleteKthNode(head, 7);
        n--;
    }
    // 输出剩余同学的原始编号
    ListNode* cur = head;
    if (n < 6) {
        for (int i = 0; i < n; i++) {
            cout << cur->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
    else if (n == 6) {
        for (int i = 0; i < 6; i++) {
            an[i] = cur->val;
            cur = cur->next;
        }
        sort(an, an + 6);
        for (int i = 0; i < 6; i++)
            cout << an[i] << " ";
        cout << endl;
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        ListNode* head = createCircleList(n);
        countAndDelete(head, n);
    }
    return 0;
}

4442: 二叉树遍历1

题目描述

​ 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串：
ABC##DE#G##F###
其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入

​

​ 输入包括1行字符串，长度不超过100。

​

输出

​

​ 可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;

// 定义二叉树的节点结构体
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};

// 递归建立二叉树
TreeNode* buildTree(string s, int& i) {
    if (i >= s.length()) return NULL;
    if (s[i] == '#') {
        i++;
        return NULL;
    }
    TreeNode* root = new TreeNode(s[i++]);
    root->left = buildTree(s, i);
    root->right = buildTree(s, i);
    return root;
}

// 递归中序遍历二叉树
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    string s;
    while (getline(cin, s)) { // 循环读入多组测试数据
        int i = 0;
        TreeNode* root = buildTree(s, i); // 建立二叉树
        inorder(root); // 中序遍历二叉树并输出结果
        cout << endl;
    }
    return 0;
}

4440: 复原二叉树

题目描述

小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。

输入

输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。

输出

对于每组输入，输出对应的二叉树的后续遍历结果。

样例输入 复制

1
2
DBACEGF ABCDEFG
BCAD CBAD

样例输出 复制

1
2
ACBFGED
CDAB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <string>
using namespace std;

const int N = 30;

string pre, in, post;

void dfs(int prel, int inl, int len)
{
	if (len == 0) return;
	if (len == 1) {
		post += pre[prel];
		return;
	}
	int root = in.find(pre[prel]);

	dfs(prel + 1, inl, root - inl);
	dfs(prel + root - inl + 1, root + 1, len - (root - inl) - 1);

	post += pre[prel];

}

int main()
{
	while (cin >> pre >> in) {
		post = "";
		int n = pre.size();
		dfs(0, 0, n);
		cout << post << endl;
	}
		return 0;

}

4441: 合并果子（堆）

题目描述

​ 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入

​ 输入文件fruit.in包括两行，第一行是一个整数n（1 <= n <= 30000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 20000）是第i种果子的数目。

输出

​ 输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。

样例输入 复制

1
2
10
3 5 1 7 6 4 2 5 4 1

样例输出 复制

1
120
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <queue>
using namespace std;

int main() {
int n, ai;
long long ans = 0; // 需要使用 long long 类型存储结果，避免溢出
priority_queue<int, vector<int>, greater<int>> q; // 小根堆

cin >> n;
for (int i = 0; i < n; i++) {
    cin >> ai;
    q.push(ai);
}

while (q.size() > 1) { // 只要堆中还有两个及以上的元素，就一直合并
    int a = q.top(); q.pop();
    int b = q.top(); q.pop();
    ans += a + b;
    q.push(a + b);
}

cout << ans << endl;
return 0;

}

四，搜索算法

1264: 正方形

题目描述

有n个木棒，需要用上所有木棒，围成一个正方形，如果可以围成正方形，则输出”yes”, 否则输出”no”。

输入

第一行输入一个整数T表示样例个数。
对于每个样例，第一行输入一个整数N表示木棍的个数，第二行输入N个数字表示木棒的长度。

输出

对于每个样例，如果可以则输出”yes”, 否则输出”no”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <algorithm>
using namespace std;

bool dfs(int* a, int idx, int sum, int* visited, int n, int cnt, int target) {
    if (cnt == 3) {
        return true;
    }
    if (sum < 0) {
        return false;
    }
    if (sum == 0) {
        return dfs(a, 0, target, visited, n, cnt + 1, target);
    }
    for (int i = idx; i < n; i++) {
        if (visited[i] || a[i] > sum) {
            continue;
        }
        visited[i] = 1;
        if (dfs(a, i + 1, sum - a[i], visited, n, cnt, target)) {
            return true;
        }
        visited[i] = 0;
    }
    // 当已经找到三组数字之和等于目标和时，还需要判断最后一组是否符合要求
    if (cnt == 2 && sum == target) {
        return true;
    }
    return false;
}


bool solve(int* a, int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
    if (sum % 4 != 0) {
        return false;
    }
    int visited[25] = { 0 };
    return dfs(a, 0, sum / 4, visited, n, 0, sum / 4);
}


int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[25];
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        if (solve(a, n)) {
            cout << "yes" << endl;
        }
        else {
            cout << "no" << endl;
        }
    }
    return 0;
}

1265: prime circle

题目描述

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, …, n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

输入

n (0 < n < 20).
(multi test case)

输出

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

题目描述
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.
输入
n (0 < n < 20).
(multi test case)
输出
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.
样例输入 复制

6
8

样例输出 复制

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

1266: 棋盘问题

题目描述

<span style=”font-family:Merriweather, Full-Width-Quoration-Marks, -apple-system, blinkMacSystemFont, “font-size:15px;background-color:rgba(210, 210, 255, 0.5);”>在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

输入

<span style=”font-family:Merriweather, Full-Width-Quoration-Marks, -apple-system, blinkMacSystemFont, “font-size:15px;background-color:rgba(210, 210, 255, 0.5);”>输入含有多组测试数据。

输出

<span style=”font-family:Merriweather, Full-Width-Quoration-Marks, -apple-system, blinkMacSystemFont, “font-size:15px;background-color:rgba(210, 210, 255, 0.5);”>对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

样例输入 复制

1
2
3
4
5
6
7
8
9
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

样例输出 复制

1
2
2
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 105;

struct Point
{
    int a, b;
    bool operator< (const Point& other) const {
        return b < other.b;
    }
} p[N];

int n, m;
int cnt;
char a[8][8];
void dfs(int u, int last_b)
{
    if (u == n) {
        cnt++;
        return;
    }
    for (int i = u; i < m; i++) {
        if (p[i].b >= last_b) {
            int tmp = p[i].b;
            p[i].b = last_b;
            dfs(u + 1, tmp);
            p[i].b = tmp;
        }
    }
}

int main()
{
    while ((cin >> m >> n)&&(m != -1) && (n != -1)) {
        for (int i = 0; i < m; i++) {
            for (int j = 0,q=0; j < m; j++,q++) {
                cin >> a[i][j];
                if (a[i][j] == '#')p[q].a = i, p[q].b = j;
            }
        }
        sort(p, p + m);
        cnt = 0;
        dfs(0, -1);
        cout << cnt << endl;
    }
    return 0;
}

1268: 迷宫问题 题目描述

<span style=”font-family:Merriweather, Full-Width-Quoration-Marks, -apple-system, blinkMacSystemFont, “font-size:15px;background-color:rgba(210, 210, 255, 0.5);”>定义一个二维数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

输入

<span style=”font-family:Merriweather, Full-Width-Quoration-Marks, -apple-system, blinkMacSystemFont, “font-size:15px;background-color:rgba(210, 210, 255, 0.5);”>一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

输出

<span style=”font-family:Merriweather, Full-Width-Quoration-Marks, -apple-system, blinkMacSystemFont, “font-size:15px;background-color:rgba(210, 210, 255, 0.5);”>左上角到右下角的最短路径，格式如样例所示。

样例输入 复制

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

样例输出 复制

1
2
3
4
5
6
7
8
9
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 5;
int maze[MAXN][MAXN];
bool visited[MAXN][MAXN];
int pre[MAXN][MAXN][2];

struct Node {
    int x, y, step;
};

int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; // 上右下左

void bfs() {
    memset(visited, false, sizeof(visited));
    queue<Node> q;
    Node start = { 0, 0, 0 };
    q.push(start);
    visited[0][0] = true;
    while (!q.empty()) {
        Node cur = q.front();
        q.pop();
        int x = cur.x, y = cur.y, step = cur.step;
        if (x == MAXN - 1 && y == MAXN - 1) { // 到达终点，结束搜索
            cout << "(0, 0)" << endl;
            int pre_x = MAXN - 1, pre_y = MAXN - 1;
            vector<pair<int, int>> path; // 记录路径
            while (pre_x != 0 || pre_y != 0) {
                path.push_back({ pre_x, pre_y });
                int tmp_x = pre_x, tmp_y = pre_y;
                pre_x = pre[pre_x][pre_y][0];
                pre_y = pre[tmp_x][tmp_y][1];
            }
            for (int i = path.size() - 1; i >= 0; i--) {
                cout << "(" << path[i].first << ", " << path[i].second << ")" << endl;
            }
            return;
        }
        for (int i = 0; i < 4; i++) {
            int next_x = x + dir[i][0], next_y = y + dir[i][1];
            if (next_x < 0 || next_x >= MAXN || next_y < 0 || next_y >= MAXN) continue; // 越界
            if (maze[next_x][next_y] == 1 || visited[next_x][next_y]) continue; // 墙或者已访问过
            Node next_node = { next_x, next_y, step + 1 };
            pre[next_x][next_y][0] = x; // 记录路径
            pre[next_x][next_y][1] = y;
            q.push(next_node);
            visited[next_x][next_y] = true;
        }
    }
}

int main() {
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            cin >> maze[i][j];
        }
    }
    bfs();
    return 0;
}

1270: Find a way

题目描述

<span style=”font-family:Merriweather, Full-Width-Quoration-Marks, -apple-system, blinkMacSystemFont, “font-size:15px;background-color:rgba(210, 210, 255, 0.5);”>Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.

输入

<span style=”font-family:Merriweather, Full-Width-Quoration-Marks, -apple-system, blinkMacSystemFont, “font-size:15px;background-color:rgba(210, 210, 255, 0.5);”><span style=”font-family:Merriweather, Full-Width-Quoration-Marks, -apple-system, blinkMacSystemFont, “font-size:15px;background-color:rgba(210, 210, 255, 0.5);”>The input contains multiple test cases.

输出

​ <span style=”font-family:Merriweather, Full-Width-Quoration-Marks, -apple-system, blinkMacSystemFont, “font-size:15px;background-color:rgba(210, 210, 255, 0.5);”>For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.

样例输入 复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#

样例输出 复制

1
2
3
4
66
88
66

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 210, INF = 1e9;

int n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

struct Node
{
    int x, y, t;
};

int bfs(int sx, int sy, int tx, int ty)
{
    queue<Node> q;
    memset(st, false, sizeof st);
    memset(dist, 0x3f, sizeof dist);

    q.push({sx, sy, 0});
    st[sx][sy] = true;
    dist[sx][sy] = 0;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b] || g[a][b] == '#') continue;

            dist[a][b] = t.t + 1;
            st[a][b] = true;
            q.push({a, b, dist[a][b]});
        }
    }

    return dist[tx][ty];
}

int main()
{
    while (cin >> n >> m)
    {
        int sy, sx, ty, tx, res = INF;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
            {
                cin >> g[i][j];
                if (g[i][j] == 'Y') sx = i, sy = j;
                if (g[i][j] == 'M') tx = i, ty = j;
            }

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
            {
                if (g[i][j] == '@')
                {
                    int d1 = bfs(sx, sy, i, j);
                    int d2 = bfs(tx, ty, i, j);
                    res = min(res, d1 + d2);
                }
            }

        cout << res * 11 << endl;
    }

    return 0;
}

1282: 马的遍历

题目描述

有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入

一行四个数据，棋盘的大小和马的坐标

输出

​ 一个n*m的矩阵，同一行元素之间用空格分离。代表马到达某个点最少要走几步。不能到达则输出-1。

样例输入 复制

1
3 3 1 1

样例输出 复制

1
2
3
0 3 2
3 -1 1
2 1 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 405;
const int INF = 1e9;
int n, m, sx, sy;
int dis[MAXN][MAXN];
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

struct node {
    int x, y;
};

bool check(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

void bfs() {
    queue<node> q;
    q.push({sx, sy});
    dis[sx][sy] = 0;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y;
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (check(nx, ny) && dis[nx][ny] == INF) {
                dis[nx][ny] = dis[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    cin >> n >> m >> sx >> sy;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dis[i][j] = INF;
        }
    }
    bfs();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (dis[i][j] == INF) {
                cout << "-1 ";
            } else {
                cout << dis[i][j] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

1283: 求细胞数量

题目描述

一矩形阵列由数字 0 到 9 组成，数字 1 到 9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

输入

第一行两个整数代表矩阵大小 n 和 m。 接下来 n 行，每行一个长度为 m 的只含字符 0 到 9 的字符串，代表这个n×m 的矩阵。

输出

​ 一行一个整数代表细胞个数。

样例输入 复制

1
2
3
4
5
4 10
0234500067
1034560500
2045600671
0000000089
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 1005; // 最大矩阵大小
const int dx[] = { 0, 1, 0, -1 }; // 上下左右四个方向的坐标变化
const int dy[] = { 1, 0, -1, 0 };

int n, m;
char matrix[MAXN][MAXN]; // 输入的矩阵
bool vis[MAXN][MAXN]; // 标记每个点是否访问过
int cnt; // 细胞数量计数器

// 判断一个点是否在矩阵内
bool inMatrix(int x, int y) {
    return x >= 0 && x < n&& y >= 0 && y < m;
}

// BFS遍历整个细胞
void bfs(int sx, int sy) {
    queue<pair<int, int>> q;
    q.push({ sx, sy });
    vis[sx][sy] = true;
    while (!q.empty()) {
        auto p = q.front();
        int x = p.first, y = p.second;
        q.pop();
        for (int i = 0; i < 4; i++) { // 四个方向搜索
            int nx = x + dx[i], ny = y + dy[i];
            if (inMatrix(nx, ny) && !vis[nx][ny] && matrix[nx][ny] != '0') {
                q.push({ nx, ny });
                vis[nx][ny] = true;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> matrix[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] != '0' && !vis[i][j]) { // 如果是细胞且未访问过
                cnt++;
                bfs(i, j); // BFS搜索整个细胞
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

1284: 01迷宫

题目描述

有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。 你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入

第1行为两个正整数n,m。 下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。

输出

​ m行，对于每个询问输出相应答案。

样例输入 复制

1
2
3
4
5
2 2
01
10
1 1
2 2

样例输出 复制

1
2
4
4

提示

n <= 400

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1005;

int n;
char maze[MAXN][MAXN];
bool vis[MAXN][MAXN];

int dx[] = { -1, 0, 1, 0 };  // 上右下左
int dy[] = { 0, 1, 0, -1 };

int bfs(int sx, int sy) {
    queue<pair<int, int>> q;
    q.push({ sx, sy });
    vis[sx][sy] = true;
    int cnt = 1;

    while (!q.empty()) {
        auto p = q.front();
        int x = p.first, y = p.second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (vis[nx][ny]) continue;
            if (maze[x][y] != maze[nx][ny]) {
                vis[nx][ny] = true;
                q.push({ nx, ny });
                cnt++;
            }
        }
    }

    return cnt;
}

int main() {
    int m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> maze[i][j];
        }
    }
    memset(vis, false, sizeof(vis));
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;  // 转换成从0开始编号的坐标
        cout << bfs(x, y) << endl;
        memset(vis, false, sizeof(vis));  // 注意清空标记数组
    }
    return 0;
}

五，图论

4444: dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 10010;
vector<int> g[N];  // 存储图
bool vis[N];       // 标记是否已经访问
void dfs(int u) {
    cout << u << ' ';  // 输出当前节点编号
    vis[u] = true;     // 标记已经访问
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!vis[v]) {  // 如果节点v还没有被访问
            dfs(v);      // 继续访问节点v
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);  // 添加无向边
        g[v].push_back(u);
    }
    dfs(1);  // 从节点1开始遍历
    cout << endl;
    return 0;
}

4445: bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, e;
    cin >> n >> e;

    // 构建邻接表
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < e; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);  // 无向图
    }

    // BFS
    vector<bool> visited(n + 1, false);
    queue<int> q;
    q.push(1);
    visited[1] = true;
    while (!q.empty()) {
        int u = q.front();
        cout << u << " ";
        q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }

    return 0;
}

1298: 蜜罐

题目描述

​ 蜜蜂乔治在采蜂蜜的时候，会把蜜放进N个蜜罐中，现在需要把这N个不相邻的蜜罐构建一些双向边把它们连接起来。即有N个分立的点，同时给出M个不同的边，需要你求出这张图的最小生成树。或许你会觉得这种描述有些奇怪，不过使用如此描述完全由于出题人喜欢吃蜂蜜。

输入

​ 第一行输入一个T，表示样例个数。
对于每一个样例，第二行输入N, M，表示蜜罐数与边的数量。
第三行输入三个数字 s, t, w表示双向边的两个端点和权重。

输出

​ 对于每个样例，输出一个数字res表示生成树的权重。如果无法构成生成树，则输出-1.

样例输入 复制

1
2
3
4
5
1
3  3
1 2 3
2 3 3
1 3 3

样例输出 复制

1
6

提示

​ 1 < N, M < 2000
w < 10000

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 100010;

int n, m, s, t, w;
int dis[MAXN];
bool vis[MAXN];
vector<pair<int, int>> G[MAXN];

int prim() {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i].first, w = G[u][i].second;
            if (!vis[v] && dis[v] > w) {
                dis[v] = w;
                q.push(make_pair(dis[v], v));
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (dis[i] == INF) return -1;
        ans += dis[i];
    }
    return ans;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        for (int i = 1; i <= m; ++i) {
            cin >> s >> t >> w;
            G[s].push_back(make_pair(t, w));
            G[t].push_back(make_pair(s, w));
        }
        int ans = prim();
        cout << ans << endl;
    }
    return 0;
}

1310: 村村通

题目描述

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 “村村通工程” 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

输入

​ 输入包含若干组测试测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目n 和道路数目 m ；随后的 m 行对应 m 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 1 到 n 编号。
注意：两个城市间可以有多条道路相通。

输出

​ 对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。

样例输入 复制

1
2
3
4
5
6
7
8
9
10
11
12
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

样例输出 复制

1
2
3
4
1
0
2
998

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>

using namespace std;

// 并查集类
class UnionFind {
public:
    vector<int> parent; // 存储节点的父节点

    UnionFind(int n) { // 初始化
        parent.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) { // 查找节点所在集合的根节点
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void merge(int x, int y) { // 合并两个集合
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }

    int count() { // 统计集合的数量
        int cnt = 0;
        for (int i = 1; i < parent.size(); i++) {
            if (parent[i] == i) {
                cnt++;
            }
        }
        return cnt;
    }
};

int main() {
    int n, m;
    while (cin >> n >> m) {
        UnionFind uf(n); // 初始化并查集
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            uf.merge(u, v); // 合并u和v所在的集合
        }
        cout << uf.count() - 1 << endl; // 输出最少需要的道路数
    }
    return 0;
}

1297: 一个人的旅行

题目描述

​ 虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊）。

输入

输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。

输出

​ 输出草儿能去某个喜欢的城市的最短时间

样例输入 复制

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

样例输出 复制

1
9

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
const int MAXM = 200005;

struct Edge {
    int v, w, nxt;
}e[MAXM];

int head[MAXN], cnt = 0;
int dist[MAXN];
bool vis[MAXN];
int s[MAXN], d[MAXN];
int n, m, t, S, D;

inline void addEdge(int u, int v, int w) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

void SPFA(int s) {
    memset(dist, INF, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[s] = 0;
    vis[s] = true;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v, w = e[i].w;
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if(!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    while(scanf("%d%d%d", &t, &S, &D) == 3) {
        cnt = 0;
        memset(head, 0, sizeof(head));
        for(int i = 1; i <= t; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        for(int i = 1; i <= S; ++i) {
            scanf("%d", &s[i]);
        }
        for(int i = 1; i <= D; ++i) {
            scanf("%d", &d[i]);
        }
        int ans = INF;
        for(int i = 1; i <= S; ++i) {
            SPFA(s[i]);
            for(int j = 1; j <= D; ++j) {
                if(dist[d[j]] < ans) {
                    ans = dist[d[j]];
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

1312: 文化之旅

题目描述

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。
现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

输入

每组输入数据的第一行为五个整数N，K，M，S，T，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为1到N），文化种数（文化编号为1到K），道路的条数，以及起点和终点的编号（保证S不等于T）；
第二行为N个整数，每两个整数之间用一个空格隔开，其中第i个数Ci，表示国家i的文化为Ci。
接下来的K行，每行K个整数，每两个整数之间用一个空格隔开，记第i行的第j个数为aij，aij=1表示文化i排斥外来文化j（i等于j时表示排斥相同文化的外来人），aij=0表示不排斥（注意i排斥j并不保证j 一定也排斥i）。
接下来的M行，每行三个整数u，v，d，每两个整数之间用一个空格隔开，表示国家u与国家v有一条距离为d的可双向通行的道路（保证u不等于v，两个国家之间可能有多条道路）。

数据规模：
对于20%的数据，有2≤N≤8，K≤5；
对于30%的数据，有2≤N≤10，K≤5；
对于50%的数据，有2≤N≤20，K≤8；
对于100%的数据，有2≤N≤100，1≤K≤10，1≤M≤N2，1≤ki≤K，1≤u, v≤N，1≤d≤1000，S≠T，1≤S, T≤N。

输出

每组输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出-1）。

下面是对样例数据的解释：
样例一：
由于到国家2必须要经过国家1，而国家2的文明却排斥国家1的文明，所以不可能到达国家2。
样例二：
路线为1->2。

样例输入 复制

1
2
3
4
5
2 2 1 1 2
1 2
0 1
1 0
1 2 10

样例输出 复制

1
-1

提示

-———–
2 2 1 1 2
1 2
0 1
0 0
1 2 10
-———-
10

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 105, K = 105, INF = 0x3f3f3f3f;
int n, k, m, s, t;
int c[N], dist[N];      //某个国家的文化，到某个国家的距离 
int a[K][K], e[N][N];   //两国之间是否排斥，两国之间的距离 
bool h[K];              //已经学过的文化 

//到国家x的距离是d 
void dfs(int x, int d) {
    if (d >= dist[x] || d >= dist[t]) return;
    dist[x] = d;
    if (x == t) return;

    for (int i = 1; i <= n; i ++) {             //i国 
        if (e[x][i] == INF) continue;           //x,i两国之间没有路
        if (h[c[i]]) continue;                  //已学过该国文化 

        bool flag = false; 
        for (int j = 1; j <= k; j ++) {         //j文化 
            if (h[j] && a[c[i]][j] == 1) {      //学过j文化且i国的文化排斥j文化 
                flag = true;
                break; 
            }
        }
        if (flag) continue;

        h[c[i]] = true;
        dfs(i, d + e[x][i]);
        h[c[i]] = false;
    }   
}

int main() {
    scanf("%d %d %d %d %d", &n, &k, &m, &s, &t);
    for (int i = 1; i <= n; i ++) {             
        scanf("%d", &c[i]);                     //国家 i的文化为 Ci
    }
    for (int i = 1; i <= k; i ++) {
        for (int j = 1; j <= k; j ++) {
            scanf("%d", &a[i][j]);              //a[i][j] = 1 表示文化 i 排斥外来文化 j
        }
    }

    memset(dist, 0x3f, sizeof(dist));           //初始化 
    memset(e, 0x3f, sizeof(e));                 
    for (int i = 1; i <= m; i ++) {
        int u, v, d;
        scanf("%d %d %d", &u, &v, &d);
        e[u][v] = e[v][u] = min(e[u][v], d);    //邻接矩阵，去掉重复的边 
    }

    h[c[s]] = true;                             //学习起点国家的文化  
    dfs(s, 0);  

    if (dist[t] == 0x3f3f3f3f) printf("-1\n");
    else printf("%d\n", dist[t]);

    return 0;
}

1320: 公交线路

题目描述

​ P市有n个公交站，之间连接着m条道路。P市计划新开设一条公交线路，该线路从城市的东站（s点）修建到西站（t点），请为P市设计一条满足上述条件并且最短的公交线路图。

输入

第一行有5个正整数n，m，s，t。

接下来m行，每行3个数a,b,v描述一条无向道路a——b，长度为v。

输出

1
2
3
如果有解，输出一行，表示满足条件的最短公交线路的长度c。

否则，输出“-1”

样例输入 复制

1
2
3
4
3 3 1 2
1 2 3
2 3 4
1 3 5

样例输出 复制

1
3

提示

1 ≤ s,t ≤ n ≤ 1000
1 ≤ m ≤ 10000
1 ≤ 道路的长度 ≤ 10000

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, m, s, t; // n: 点的数量，m: 边的数量，s: 起点，t: 终点
int dis[105]; // dis[i] 表示从起点 s 到 i 的最短距离
bool vis[105]; // vis[i] 表示 i 是否已经访问过
int G[105][105]; // G[i][j] 表示 i 到 j 的边的长度

void dijkstra() {
    memset(dis, INF, sizeof(dis)); // 初始化 dis 数组为 INF
    dis[s] = 0; // 起点 s 到自己的距离为 0

        for (int i = 1; i <= n; i++) {
            int u = -1, min_dis = INF;
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && dis[j] < min_dis) {
                    u = j;
                    min_dis = dis[j];
                }
            }
            if (u == -1) break; // 所有点都已经访问过
            vis[u] = true; // 标记 u 已经访问过
            for (int v = 1; v <= n; v++) {
                if (!vis[v] && G[u][v] != INF && dis[u] + G[u][v] < dis[v]) {
                    dis[v] = dis[u] + G[u][v];
                }
            }
        }

}

int main() {
    cin >> n >> m >> s >> t;
    memset(G, INF, sizeof(G)); // 初始化 G 数组为 INF
    for (int i = 1; i <= n; i++) G[i][i] = 0; // 自己到自己的距离为 0
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u][v] = G[v][u] = w; // 无向图，所以需要同时更新 G[u][v] 和 G[v][u]
    }


        dijkstra(); // 求解最短路径

    if (dis[t] != INF) cout << dis[t] << endl; // 如果有解，输出最短距离
    else cout << -1 << endl; // 否则输出 -1

    return 0;

}

4443: 弗洛伊德

题目描述

​ 在带权有向图G中，求G中的任意一对顶点间的最短路径问题，也是十分常见的一种问题。 解决这个问题的一个方法是执行n次迪杰斯特拉算法，这样就可以求出每一对顶点间的最短路径，执行的时间复杂度为O(n3)。 而另一种算法是由弗洛伊德提出的，时间复杂度同样是O(n3)，但算法的形式简单很多。

​ 在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出每一对顶点间的最短路径长度。

​

输入

输入的第一行包含1个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。

输出

共有n行，每行有n个整数，表示源点至每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。对于某个顶点到其本身的最短路径长度，输出0。 请在每个整数后输出一个空格，并请注意行尾输出换行。

样例输入 复制

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

样例输出 复制

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

提示

在本题中，需要按照题目描述中的算法完成弗洛伊德算法，并在计算最短路径的过程中将每个顶点是否可达记录下来，直到求出每一对顶点的最短路径之后，算法才能够结束。 相对于迪杰斯特拉算法，弗洛伊德算法的形式更为简单。通过一个三重循环，弗洛伊德算法可以方便的求出每一对顶点间的最短距离。 另外需要注意的是，为了更方便的表示顶点间的不可达状态，可以使用一个十分大的值作为标记。而在题目描述中的算法示例使用了另外一个三维数组对其进行表示，这使原本的O(n3)时间复杂度增长到了O(n4)，这也是需要自行修改的部分。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 55;
int n;
int graph[MAXN][MAXN]; //邻接矩阵

void floyd() {
	//初始化
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][k] != INF && graph[k][j] != INF) {
					graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
				}
			}
		}
	}
}

int main() {
	cin >> n;
	//初始化邻接矩阵
	memset(graph, 0x3f, sizeof(graph));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int w;
			cin >> w;
			if (w > 0) {
				graph[i][j] = w;
			}
			if (i == j) {
				graph[i][j] = 0;
			}
		}
	}
	//执行弗洛伊德算法
	floyd();
	//输出结果
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (graph[i][j] == INF) {
				cout << -1 << " ";
			}
			else {
				cout << graph[i][j] << " ";
			}
		}
		cout << endl;
	}
	return 0;
}

4446: 奖学金(reward)

题目描述

期末考试终于完了，老班决定召开班委会，内容嘛，则是可爱的奖学金的问题（(^__^)），她叫来了一些班委，每位班委提出了自己的意见：“我认为同学a的奖学金应该比b多！”老班决定要找出一种奖学金方案，满足各位班委的意见，且同时使得总奖学金数最少。每位同学奖学金最少为100元且都为整数。

输入

​ 第一行两个整数n,m，表示同学总数和班委意见数；

以下m行，每行2个整数a,b，表示某个班委认为第a号同学奖学金应该比第b号同学高。

输出

若无法找到合法方案，则输出“impossible”(不含引号）；否则输出一个数表示最少总奖学金。

样例输入 复制

1
2
3
2 1
1 2

样例输出 复制

1
2
201

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline void read(int &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 10000 + 10;
struct node{
    int num;
    int mon; 
    node ():num(0),mon(100){};  
}G[maxn];
struct Edge{
	int to,next;
}g[20000 + 10];
int head[maxn],tot=0;
void add(int u,int v){
	g[++tot].to = v;
	g[tot].next = head[u];
	head[u] = tot; 
}
int cnt=0;
int q[maxn],l=0,r=0;
int main(){
//	freopen("reward.in","r",stdin);
//	freopen("reward.out","w",stdout);
    int n,m;read(n);read(m);
    bool flag = true;int a,b;
    while(m--){
        read(a),read(b);
        add(b,a);
        G[a].num++;//纪录每一个点的入度 
    }
    for (int i = 1; i <= n; i++){
        if (G[i].num == 0){
            q[r] = i;
			 ++r;
        }
    }
    int tmp;
    while (l<r){
        tmp = q[l];++l;
        for(int i = head[tmp]; i ; i = g[i].next){
            G[g[i].to].num--;
            if(G[g[i].to].mon <= G[tmp].mon)
               G[g[i].to].mon = G[tmp].mon + 1;
            if(G[g[i].to].num == 0){//入度为零则不可能再一次被更新了 
                q[r] = g[i].to ; ++r;
            }
        }
    }
    for (int i = 1; i <= n; i++){
        if (G[i].num != 0){
           flag = false;
           break;//判环 
        }
        cnt += G[i].mon;
    }
    if (!flag) printf("impossible");
    else printf("%d", cnt);
    fclose(stdin);fclose(stdout);return 0;
}

六，动态规划

4447: 冬冬爬楼梯

题目描述

冬冬爬楼梯，一步可以1级，也可以爬2级、3级。冬冬很可爱，每到一处楼梯处，他都想知道直完这个楼梯有多少种走法。但由于有的时候楼梯级数太多，可能是个天文数字，很显然，对于还处于小学5年级的冬冬是不太现实的。聪明的你，能帮冬冬实现这个愿望吗？

输入

多组测试数据，每组测试数据一行一个整数n (1<=n<=3000)

输出

对于每组测试数据，输出一个整数，为n级楼梯冬冬走完的方法数。

样例输入 复制

1
2
3
1
2
3

样例输出 复制

1
2
3
1
2
4

思路&解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstring>
#include<algorithm>
using namespace std;

const int MAXN = 3005;
string dp[MAXN];
string reverseStr(string str)
{
    int n = str.length();

    
    for (int i = 0; i < n / 2; i++)
        swap(str[i], str[n - i - 1]);
    return str;
}

string add(string a, string b) {
    string res;
    int carry = 0;  // 进位
    int len1 = a.size(), len2 = b.size();
    a = reverseStr(a); b = reverseStr(b);
    int i = 0, j = 0;
    while (i < len1 || j < len2) {
        int sum = carry;
        if (i < len1) {
            sum += a[i] - '0';
            i++;
        }
        if (j < len2) {
            sum += b[j] - '0';
            j++;
        }
        carry = sum / 10;
        sum %= 10;
        res += (sum + '0');
        //cout << carry << " " << res << endl;
    }
    if (carry) {
        res += (carry + '0');
    }
    return reverseStr(res);
}

int main() {
    int n;
    //cout << add("13", "11") << endl;
    while (cin >> n) {
        for (auto& i : dp) i = "0";
        dp[1] = "1";
        dp[2] = "2";
        dp[3] = "4";
        for (int i = 4; i <= n; i++) {
            dp[i] = add(dp[i - 1], add(dp[i - 2], dp[i - 3]));
        }
        //cout << dp[n - 1] << " " << dp[n - 2] << " " << dp[n - 3] << endl;
        cout << dp[n] << endl;
    }
    return 0;
}

4450: 最大子段和

题目描述

​ 输入若干个整数，有正有负，要求用动态规划算法计算最大子段和，并输出这个和。注意子段为一段连续的数，同时规定全是负数的子段其和为0。

输入

​ 第一行为一个整数M，代表有M组测试数据。
随后每组测试数据的第一行为N，代表该组数据有N个数。(0<n<=100000) <br=””>接下来一行给出用空格隔开的这N个整数。</n<=100000)>

输出

每组测试数据输出一行，即最大子段和。

样例输入 复制

1
2
3
1
8
-2 10 8 -4 7 5 -29 10

样例输出 复制

1
26

思路&解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#define int long long
using namespace std;

int maxSum(int a[], int n) {
	int sum = 0;
	int b = 0;
	for (int i = 0; i < n; i++) {
		if (b > 0)
			b += a[i];
		else
			b = a[i];
		if (b > sum)
			sum = b;
	}
	return sum;
}
signed main() {
	int M; cin >> M;
	while (M--) {
		int N; cin >> N;
		int* a = new int[N];
		for (int i = 0; i < N; i++) {
			cin >> a[i];
		}

		cout << maxSum(a, N) << endl;
		delete[] a;
	}
	return 0;
}

4454: 最大子阵和

题目描述

有一个包含正数和负数的二维数组。一个子矩阵是指在该二维数组里，任意相邻的下标是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（1<=N<=100），表示二维方阵的大小。接下来N行每行输入N个整数，表示数组元素，范围为[-127，127]。

输出

输出最大子阵和。

样例输入

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

样例输出

1
15

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
using namespace std;

const int N = 110;

int a[N][N], sum[N][N];

int kadane(int n, int* arr) {
    int max_sum = arr[0], cur_sum = arr[0];
    for (int i = 1; i < n; i++) {
        cur_sum = max(cur_sum + arr[i], arr[i]);
        max_sum = max(max_sum, cur_sum);
    }
    return max_sum;
}

int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> a[i][j];
                if (i == 0) sum[i][j] = a[i][j];
                else sum[i][j] = sum[i - 1][j] + a[i][j];
            }
        }
        int ans = a[0][0];
        for (int i = 0; i < n; i++) {
            int* arr = new int[n];
            for (int j = i; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (i == 0) arr[k] = sum[j][k];
                    else arr[k] = sum[j][k] - sum[i - 1][k];
                }
                ans = max(ans, kadane(n, arr));
            }
            delete[] arr;
        }
        cout << ans << endl;
    }
    return 0;
}

4449: 最长上升子序列

题目描述

给出一个由n个数组成的序列A[1..n]，求最长单调上升子序列（LIS)的长度。LIS即求最大的一个子序列长度m，使得a1<a2<……<am且A[a1]<A[a2]<……<A[am]。

输入

​ 两行：

​ 第1行：整数n (1<=n<=1000)

​ 第2行：n个整数 （int范围内），空格隔开。

输出

一行：一个整数，即最长上升子序列长度。

样例输入

1
2
10
63	11	21	36	28	20	57	37	82	4

样例输出

1
5

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
 
const int MAXN = 1010;
int a[MAXN], dp[MAXN];  // dp[i]表示以a[i]为结尾的最长上升子序列长度
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    int ans = 1;  // LIS长度至少为1
    dp[0] = 1;    // 第一个元素自成长度为1的LIS
    for (int i = 1; i < n; i++) {
        dp[i] = 1;  // 初始化dp[i]为1
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {  // 如果a[j]<a[i]，则a[i]可以接在以a[j]结尾的LIS之后形成更长的LIS
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);  // 更新最长上升子序列的长度
    }
    cout << ans << endl;
    return 0;
}

4453: 最小乘车费用

题目描述

​ 某条街上每一公里就有一汽车站，乘车费用如下表：

公里数12345678910
费用122131404958697990101

​ 而一辆汽车从不行驶超过10公里。某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案使费用最小（10公里的费用比1公里小的情况是允许的）。

输入

​ 第一行为10个不超过100的整数，依次表示行驶1～10公里的费用，相邻两数间用空格隔开；

​ 第二行为某人想要行驶的公里数(1000以内)。

输出

包含一个整数，表示该测试点的最小费用。

样例输入 复制

1
2
12 21 31 40 49 58 69 79 90 101 
15

样例输出 复制

1
147

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
 
int f[25],dp[205];
int n;
int main()
{
    memset(dp,127,sizeof(dp));
    for(int i=1; i<=10; i++)
        cin>>f[i];
    cin>>n;
    dp[0]=0;
    dp[1]=f[1];
    for (int i=2; i<=n; i++)
    {
        dp[i]=dp[i-1]+f[1];
        for (int j=1; j<=10 && j<=i; j++)
            dp[i]=min(dp[i],dp[i-j]+f[j]);
        //cout<<dp[i]<<"  ";
    }
    cout<<dp[n]<<endl;
 
    return 0;
}

4448: 方格取数

题目描述

​ 在n*n的方格阵中，从左上角出发，每次只能往正下方或右边走，找出一种路线方案，使得所经历方格中数字和最大，输出这个值。

​ （下图n=5)

​

0537539
551019238
655882899
80145068
89510410

输入

​ 第1行：一个整数n (1<=n<=1000)

​ 第2-n+1行：每行n个非负整数 （整型范围）

输出

一行：一个整数

样例输入 复制

1
2
3
4
5
6
5
0	5	37	53	9
55	10	19	23	8
65	58	82	89	9
8	0	14	50	68
89	5	10	41	0

样例输出 复制

1
467

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;
int a[N][N];
int dp[N][N];

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}

4451: 01背包

题目描述

一个旅行者有一个最多能用M公斤的背包，现在有N件物品，
它们的重量分别是W1，W2，…,Wn,
它们的价值分别为P1,P2,…,Pn.
若每种物品只有一件求旅行者能获得最大总价值。

输入

M,N
W1,P1
W2,P2
……

输出

最大总价值。

样例输入 复制

1
2
3
4
5
10 4
2 1
3 3
4 5
7 9

样例输出 复制

1
12

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    vector<int> w(n+1), p(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> p[i];
    }

    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (w[i] > j) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i]);
            }
        }
    }
    cout << dp[n][m] << endl;

    return 0;
}

4452: 完全背包

题目描述

完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO

输入

第一行： N 表示有多少组测试数据（N<7）。

接下来每组测试数据的第一行有两个整数M，V。 M表示物品种类的数目，V表示背包的总容量。(0<M<=2000，0<V<=50000)
接下来的M行每行有两个整数c，w分别表示每种物品的重量和价值(0<c<100000，0<w<100000)

输出

对应每组测试数据输出结果（如果能恰好装满背包，输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包，输出NO）

样例输入

1
2
3
4
5
6
2
1 5
2 2
2 5
2 2
5 1

样例输出

1
2
NO
1

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstring>
using namespace std;
const long long MAXN = 999999; // 物品数量的最大值
const long long MAXV = 999999; // 背包容量的最大值
long long w[MAXN], v[MAXN]; // w[i]表示第i件物品的体积，v[i]表示第i件物品的价值
long long f[MAXV]; // f[j]表示背包容量为j时的最大价值
int main()
{
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) 
        {
            cin >> w[i] >> v[i];
        }
        memset(f, -0x3f, sizeof(f)); // 初值为负无穷大
        f[0] = 0; // 容量为0时，最大价值为0
        for (int i = 1; i <= n; i++) 
        { // 枚举物品
            for (int j = w[i]; j <= m; j++) 
            { // 枚举容量
                f[j] = max(f[j], f[j - w[i]] + v[i]); // 转移方程
            }
        }
        if (f[m] < 0) 
        {
            cout << "NO" << endl;
        }
        else 
        { 
            cout << f[m] << endl;
        }
    }
    return 0;
}

七，字符串和数学实验

问题 A: 字符串

题目描述

给定连个字符串a和 b,求出b在a中第一次出现的位置。如果b没有在a中出现过,则输出-1。

输入

第一行包含一个数字T表示样例个数,对于每组样例,包含两个用空格分隔的字符串a,只包含小写字母。

输出

对于每组样例,输出b在a中第一次出现的位置。

样例输入 复制 ****

1
2
3
4
5
6
7
3
abc b
aaaab ab
ab d
1
3
-1

样例输出 复制

1
2
3
1
3
-1

思路&解答

简单查找，（基础查找）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>
using namespace std;
int main() {
    int T;cin >> T;  // 输入样例个数
    while (T--) {
        string a, b;
        cin >> a >> b;  // 输入两个字符串
        // 在a中查找b
        int pos = a.find(b);
        if (pos != string::npos) {
            cout << pos << endl;  // 输出第一次出现的位置
        } else {
            cout << -1 << endl;  // 如果b没有在a中出现过，则输出-1
        }
    }
    return 0;
}

KMP算法：（next数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 计算字符串s的前缀函数（即next数组）
vector<int> compute_prefix(const string& s) {
    int n = s.size();
    vector<int> next(n);
    next[0] = -1;
    int j = -1;
    for (int i = 1; i < n; i++) {
        while (j >= 0 && s[i] != s[j + 1]) {
            j = next[j];
        }
        if (s[i] == s[j + 1]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}
// 使用KMP算法在a中查找b的位置
int kmp(const string& a, const string& b) {
    vector<int> next = compute_prefix(b);
    int n = a.size();
    int m = b.size();
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && a[i] != b[j + 1]) {
            j = next[j];
        }
        if (a[i] == b[j + 1]) {
            j++;
        }
        if (j == m - 1) {
            return i - m + 1;
        }
    }
    return -1;
}

int main() {
    int T;
    cin >> T;  // 输入样例个数
    while (T--) {
        string a, b;
        cin >> a >> b;  // 输入两个字符串

        int pos = kmp(a, b);  // 在a中查找b
        cout << pos << endl;
    }
    return 0;
}

问题 B: Oulipo

题目描述

The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter ‘e’. He was a member of the Oulipo group. A quote from the book:

Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…

Perec would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given “word” as possible. Our task is to provide the jury with a program that counts these occurrences, in order to obtain a ranking of the competitors. These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive ‘T’s is not unusual. And they never use spaces.

So we want to quickly find out how often a word, i.e., a given string, occurs in a text. More formally: given the alphabet {‘A’, ‘B’, ‘C’, …, ‘Z’} and two finite strings over that alphabet, a word W and a text T, count the number of occurrences of W in T. All the consecutive characters of W must exactly match consecutive characters of T. Occurrences may overlap.

输入

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:

One line with the word W, a string over {‘A’, ‘B’, ‘C’, …, ‘Z’}, with 1 ≤ |W| ≤ 20,000 (here |W| denotes the length of the string W).
One line with the text T, a string over {‘A’, ‘B’, ‘C’, …, ‘Z’}, with |W| ≤ |T| ≤ 2,000,000.

输出

For every test case in the input file, the output should contain a single number, on a single line: the number of occurrences of the word W in the text T.

样例输入

1
2
3
4
5
6
7
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

样例输出

1
2
3
1
3
0

思路&解答

依旧是KMP（next数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
using namespace std;
// 计算模式串（pattern）的前缀函数（也称为最长前缀后缀）
vector<int> compute_prefix_function(const string& pattern) {
    int n = pattern.size();
    vector<int> pi(n);
    pi[0] = 0;
    int k = 0;
    for (int i = 1; i < n; i++) {
        while (k > 0 && pattern[k] != pattern[i]) {
            k = pi[k-1];
        }
        if (pattern[k] == pattern[i]) {
            k++;
        }
        pi[i] = k;
    }
    return pi;
}

// 在文本串（text）中查找模式串（pattern）的出现次数
int kmp(const string& pattern, const string& text) {
    int n = text.size();
    int m = pattern.size();
    vector<int> pi = compute_prefix_function(pattern);
    int q = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        while (q > 0 && pattern[q] != text[i]) {
            q = pi[q-1];
        }
        if (pattern[q] == text[i]) {
            q++;
        }
        if (q == m) {
            count++;
            q = pi[q-1];
        }
    }
    return count;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string pattern, text;
        cin >> pattern >> text;
        cout << kmp(pattern, text) << endl;
    }
    return 0;
}

问题 C: 本质不同的子串

题目描述

​ mfc是一个很优秀的同学，他学习认真，经常刷题。这天，他正好学习到了字符串的相关知识。为了巩固知识，他在网上找到了这样一个题目：给定n(n<=10)个字符串环，每个字符串的长度为m(m<=500)，保证每个字符串中只有小写字母，求出每个字符串环有多少个本质不同的子串（两个字符串不相同则认为本质不同）。

​ 求解本质不同的子串是一个经典的问题，mfc提出了三种效率不同的做法，最简单但是最慢的方法mfc不屑于去讲（你可以去写），当然你也可以使用字典树来记录所有的子串，时间复杂度O(m^2)，如果你也想像m队长一样厉害，也可以学习后缀自动机来求解该问题，时间复杂度O(m)。如果你可以使用效率较高的程序来解决这个问题，就可以到acm实验室与m队长一较高下！

输入

​ 一共有n+1行输入

​ 第一行输入n，表示测试实例的个数

​ 接下来的n行，每行包括一个测试实例

输出

​ 对于每个测试实例，输出该字符串环中本质不同的子串个数，每个输出占一行。

样例输入

1
2
3
2
aaa
abc

样例输出

1
2
3
9

提示

​ 字符串环是指一种形成环的字符串，例如abc，字符a后面跟着b，b后面跟着c，c后面跟着a。如下图所示

​ img

​

​ 对于第一个测试实例aaa，它有a，aa，aaa三个本质不同的子串。

​ 对于第二个测试实例abc，它有a，b，c，ab，bc，ca，abc，bca，cab九个本质不同的子串。

思路&解答：

模仿字符串“环”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<string>
#include<set>
#include<algorithm>
using namespace std;
int main() {
	set<string> str;
	string s, ss;
	int m;cin >> m;
	for (int q = 0; q < m; q++) {
		cin >> s;
		ss = s + s;//拼接
		for (int i = 0; i < ss.length(); i++)
			for (int j = 1; j <= ss.length() - i; j++)
				if (j <= s.length())
					str.insert(ss.substr(i, j));//键值对存储
		cout << str.size() << endl;
		str.clear();//清空准备下次使用
	}
	return 0;
}

自动机

字典树

问题 D: 最小公倍数

题目描述

给定两个正整数，计算这两个数的最小公倍数。

输入

输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数.

输出

对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。

样例输入

1
10 14

样例输出

1
70

思路&解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

// 辗转相除法求最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        int g = gcd(a, b);
        cout << a / g * b << endl;
    }
    return 0;
}

问题 E: 素数求和

题目描述

输入一个正整数N，求N以内所有的素数之和对于unsigned long long自然溢出后的结果。

输入

第一行一个整数N

输出

一行一个素数

样例输入

1
10

样例输出

1
17

提示

​ 数据范围：10≤N≤10^7

思路&解答

使用筛法+is_prime判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int main() {
	unsigned long long n, sum = 0;
	cin >> n;
	vector<bool>is_prime(n + 1, true);
	is_prime[0] = is_prime[1] = false;

	for (int i = 2; i <= sqrt(n); i++) {
		if (is_prime[i]) {
			for (int j = i * i; j <= n; j += i) {
				is_prime[j] = false;
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		if (is_prime[i]) {
			sum += i;
		}
	}
	cout << sum << endl;
	return 0;
 }

筛：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
#define re register
#define ll long long
#define inc(i,j,k) for(re int i=j;i<=k;i++)
#define dec(i,j,k) for(re int i=j;i>=k;i--)
using namespace std;
inline int read()
{
 re int x=0,f=1; char ch=getchar();
 while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
 while(ch>='0'&&ch<='9') {x=x*10+(ch^48); ch=getchar();}
 return x*f;
}
const int N=1e7;
bool notprime[N+5];
int pri[N],tot;
void prim()
{
 memset(notprime,0,sizeof(notprime));
 notprime[0]=notprime[1]=1; tot=0;
 inc(i,2,N)
 {
  if(!notprime[i]) pri[++tot]=i;
  for(re int j=1; j<=tot && i*pri[j]<=N; j++)
  {
   notprime[i*pri[j]]=1;
   if(!(i%pri[j])) break;
  }
 } 
}
int main()
{
 prim();
 int n=read();
 unsigned long long sum = 0;
 inc(i,1,tot){
  if(pri[i]<=n){
   sum+=pri[i];
  }else break;
 }
 cout<<sum<<endl;
}

问题 F: 人见人爱A^B

题目描述

求A^B的最后三位数表示的整数。
说明：A^B的含义是“A的B次方”

输入

输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。

输出

对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。

样例输入

1
2
3
4
2 3
12 6
6789 10000
0 0

样例输出

1
2
3
8
984
1

思路&解答

因为只要最后三位，如果多余三位，只保留后三位（%1000）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
int main() {
	int A, B;
	while (cin >> A >> B && !(A == 0 && B == 0)) {
		int ans = 1;
		while (B > 0) {
			if (B & 1) {
				ans = (ans * A) % 1000;
			}
			A = (A * A) % 1000;
			B >>= 1;
		}
		cout << ans << endl;
	}
	return 0;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
int Pow(int a, int b, int m) {
	a %= m;
	int res = 1;
	while (b > 0) {
		if (b & 1)res = res * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return res;
}
signed main() {
	int a, b, p;
	cin >> a >> b >> p;
	int k = Pow(a,b,p);
	cout << a << "^" << b << " mod " << p << "=" << k << endl;
	return 0;

}

问题 G: XORinacci

题目描述

​ Cengiz recently learned Fibonacci numbers and now he is studying different algorithms to find them. After getting bored of reading them, he came with his own new type of numbers that he named XORinacci numbers. He defined them as follows:

​ You are given three integers a, b, and n, calculate f(n).

​ You have to answer for T independent test cases.

输入

​ The input contains one or more independent test cases.

​ The first line of input contains a single integer T (1≤T≤1000), the number of test cases.

​ Each of the T following lines contains three space-separated integers a, b, and n (0≤a,b,n≤10^9) respectively.

输出

For each test case, output f(n).

样例输入

1
2
3
4
3
3 4 2
4 5 0
325 265 1231232

样例输出

1
2
3
7
4
76

提示

In the first example, f(2)=f(0)⊕f(1)=3⊕4=7

思路&解答

找规律得结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits.h>
#include <cstring>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f, INF_BIT = 0x3f;

const int N = 1e5 + 10;

int t;
int a, b, n;

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d%d%d", &a, &b, &n);
        
        if(n % 3 == 0) printf("%d\n", a);
        else if(n % 3 == 1) printf("%d\n", b);
        else if(n % 3 == 2) printf("%d\n", a ^ b);
    }
    return 0;
}

问题 H: 不同的n/i

题目描述

给定一个n，对于i从1到n，找出有多少个不同的n/i
如：n=6
有4个不同的n/i：6，3，2，1

输入

第一行一个T，表示有T组数据(T < 100000)
之后T行，每行一个n(n <= 10^18)

输出

每行输出一个数，表示不同的个数

样例输入

1
2
3
4
3
6
8
10

样例输出

1
2
3
4
4
5

提示

对于50%的数据：n <= 100000, T <= 10
对于100%的数据：n <= 10^18, T < 100000

思路&解答

依旧是找规律写代码

i=11(1)
i=22(2,3)3(4,5)
i=34(6,7,8)5(9,10,11)
i=46(12,13,14,15)7(16,17,18,19)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cmath>
#define int long long
using namespace std;

signed main() {
    int N; cin >> N;
        while (N--) {
            int i;
            cin >> i;
            int n = (int)((-1 + sqrt(1 + 4 * i)) / 2 + 1);
            int k = (int)((-1 + sqrt(1 + 4 * (i - n))) / 2 + 1);
            if (i == 1)cout << 1 << endl;
            else if (n==k+1)cout << 2 * n - 2<<endl;
            else cout << 2 * n-1<<endl;
        }
    return 0;
}