抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

一方の笔记本

The only source of knowledge is experience.

博客

随笔

朋友

归档

关于

算法日常练习7

算法学习题解

发布于：2021年11月12日

2021年11月12日练习。

BJTU-ALGO 2015

做题做的人有点麻，来道签到题。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> nums(n,vector<int>(m));
	for (auto& i : nums) {
		for (auto& j : i) {
			cin >> j;
		}
	}
	for (int j = 0; j < m; j++) {
		for (int i = n - 1; i >= 0; i--) {
			cout << nums[i][j] << ' ';
		}
		cout << endl;
	}
	return 0;
}

BJTU-ALGO 1007

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
#define square(x) ((x)*(x))
using namespace std;
int main() {
	int N;
	double R, C = 0.0;
	cin >> N >> R;
	vector<pair<double, double>> points(N, pair<double, double>());
	for (int i = 0; i < N; i++) {
		cin >> points[i].first >> points[i].second;
	}
	for (int i = 1; i < N; i++) {
		C += sqrt(square(points[i].first - points[i - 1].first) + square(points[i].second - points[i - 1].second));
	}
	C += sqrt(square(points[0].first - points[N - 1].first) + square(points[0].second - points[N - 1].second));
	cout << setiosflags(ios::fixed) << setprecision(2);
	cout << C + acos(-1) * 2.0 * R << endl;
	return 0;
}

BJTU-ALGO 1054

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 <bits/stdc++.h>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<bool>> land(n, vector<bool>(m, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int temp;
			cin >> temp;
			land[i][j] = temp;
		}
	}
	vector<vector<int>>dp(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (land[i][j]) {
				if (i == 0 || j == 0) {
					dp[i][j] = 1;
				}
				else {
					dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}

BJTU-ALGO 2039

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 <bits/stdc++.h>
using namespace std;

int product_counts(int i) {
	int ans = 0;
	for (int j = 1; j <= i; j++) {
		if (i % j == 0) {
			ans++;
		}
	}
	return ans;
}

int main() {
	int K;
	bool s = false;
	cin >> K;
	for (int i = 1; i <= 2000; i++) {
		if (product_counts(i) == K) {
			cout << i << endl;
			s = true;
		}
	}
	cout << (s ? "" : "NO SOLUTION\n");
	return 0;
}

BJTU-ALGO 1083

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.math.*;
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        BigInteger n = new BigInteger(s);//当2^(i) <= n < 2^(i+1)时，输出1+2*(n-2^i)
        BigInteger pow = new BigInteger("1");
        while(pow.compareTo(n) <= 0){
            pow = pow.multiply(new BigInteger("2"));
        }
        input.close();
        System.out.print(n.multiply(new BigInteger("2")).subtract(pow).add(new BigInteger("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
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
using namespace std;
struct big_int {//只在正数范围内进行求解
	vector<int> nums;//实际数字的低位存在数组的低位较为容易计算
	big_int():nums(vector<int>()){}
	big_int(int _init) :nums(vector<int>()) {
		while (1) {
			nums.emplace_back(_init % 10);
			_init /= 10;
			if (_init == 0) {
				break;
			}
		}
	}
	big_int(const string& _init):nums(vector<int>()) {
		for (int i = _init.size() - 1; i >= 0; i--) {
			nums.emplace_back(_init[i] - '0');
		}
	}
	big_int operator*(const big_int& ano){
		big_int ans(0);
		int n = nums.size(), m = ano.nums.size();
		ans.nums.resize(m + n, 0);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				ans.nums[i + j] += nums[i] * ano.nums[j];
			}
		}
		int c = 0;
		for (int i = 0; i < m + n; i++) {
			ans.nums[i] += c;
			c = ans.nums[i] / 10;
			ans.nums[i] %= 10;
		}
		for (int i = m + n - 1; i >= 0; i--) {
			if (ans.nums[i] == 0) {
				ans.nums.pop_back();
			}
			else {
				break;
			}
		}
		if (c != 0) {
			ans.nums.emplace_back(c);
		}
		return ans;
	}
	big_int pow(int n) {
		big_int ans(1);
		for (int i = 1; i <= n; i++) {
			ans = ans * (* this);
		}
		return ans;
	}
	bool operator<(const big_int& _ano) const{
		if (nums.size() != _ano.nums.size()) {
			return nums.size() < _ano.nums.size();
		}
		else {
			int n = nums.size();
			for (int i = n - 1; i >= 0; i--) {
				if (nums[i] < _ano.nums[i]) {
					return true;
				}
				else if (nums[i] == _ano.nums[i]) {
					continue;
				}
				else {
					return false;
				}
			}
			return false;
		}
	}
	bool operator==(const big_int& _ano) const{
		return _ano.nums == nums;
	}
	bool operator<=(const big_int& _ano) const{
		return *this < _ano || *this == _ano;
	}
	big_int operator+(const big_int& _ano) const{
		big_int ans;
		int n = nums.size(), m = _ano.nums.size();
		int i = 0, j = 0, c = 0, k = 0;
		ans.nums.resize(max(m, n), 0);
		while (i < n && j < m) {
			ans.nums[k] += (c + nums[i] + _ano.nums[j]);
			c = ans.nums[k] / 10;
			ans.nums[k] %= 10;
			i++;
			j++;
			k++;
		}
		while (i < n) {
			ans.nums[k] += (c + nums[i]);
			c = ans.nums[k] / 10;
			ans.nums[k] %= 10;
			i++;
			k++;
		}
		while (j < m) {
			ans.nums[k] += (c + _ano.nums[j]);
			c = ans.nums[k] / 10;
			ans.nums[k] %= 10;
			j++;
			k++;
		}
		if (c != 0) {
			ans.nums.emplace_back(c);
		}
		return ans;
	}
	big_int operator-(const big_int& _ano) const{//*this > _ano
		big_int ans;
		int n = nums.size(), m = _ano.nums.size();
		int c = 0;
		ans.nums.resize(n, 0);
		for (int i = 0; i < n; i++) {
			int temp = (i < m ? nums[i] - _ano.nums[i] + c : nums[i] + c);
			ans.nums[i] = (temp >= 0 ? temp : temp + 10);
			c = (temp >= 0 ? 0 : -1);
		}
		for (int i = n - 1; i >= 0; i--) {
			if (ans.nums[i] == 0) {
				ans.nums.pop_back();
			}
			else {
				break;
			}
		}
		return ans;
	}
};

ostream& operator<<(ostream& os, const big_int& _output)  {
	for (int i = _output.nums.size() - 1; i >= 0; i--) {
		os << _output.nums[i];
	}
	return os;
}

int main() {
	string n;
	cin >> n;//当2^(i) <= n < 2^(i+1)时，输出2n+1-2^(i+1)
	int i = 0;
	while (1) {
		if (!(big_int(2).pow(i) <= big_int(n) && big_int(n) < big_int(2).pow(i + 1))) {
			i++;
		}
		else {
			break;
		}
	}
	cout << big_int(2) * big_int(n) + big_int(1) - big_int(2).pow(i + 1) << endl;
	return 0;
}

BTW，好久不用 list ，顺便复习一下。 

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 <bits/stdc++.h>//约瑟夫环121报数版本
using namespace std;
int main() {
	for (int n = 1; n <= 1000; n++) {
		list<int> l;
		for (int i = 1; i <= n; i++) {
			l.emplace_back(i);
		}
		auto iter = l.begin();
		iter++;
		while (l.size() > 1) {
			auto cur_out = iter;
			for (int i = 1; i <= 2; i++) {//学习list的使用
				iter++;
				if (iter == l.end()) {
					iter = l.begin();
				}
			}
			l.erase(cur_out);
		}
		cout << "n = " << n << ':' << l.front() << endl;
	}
	return 0;
}

BJTU-ALGO 1101

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
//AC代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll ans = 0;
int n, k;

void dfs(int last_sum, int last_num,int cur_depth) {
	if (cur_depth == k - 1) {
		if (n - last_sum >= last_num) {//减少一层深度就过了
			ans++;
		}
		return;
	}
	for (int i = last_num; i <= n - last_sum; i++) {
		dfs(last_sum + i, i, cur_depth + 1);
	}
}

int main(){
	cin >> n >> k;
	for (int i = 1; i <= n / k + 1; i++) {
		dfs(i, i, 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
24
25
26
27
//80分代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll ans = 0;
int n, k;

void dfs(int last_sum, int last_num, int cur_depth) {
	if (cur_depth == k) {
		if (last_sum == n) {
			ans++;
		}
		return;
	}
	for (int i = last_num; i  = n - last_sum; i++) {
		dfs(last_sum + i, i, cur_depth + 1);
	}
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n / k + 1; i++) {
		dfs(i, i, 1);
	}
	cout << ans << endl;
	return 0;
}

BJTU-ALGO 1106

本题最佳解法是直接计算卡特兰数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//本题实际上是计算卡特兰数的裸题
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	int n;
	cin >> n;
	ll ans = 1;//卡特兰数
	for (int i = 2 * n; i >= n + 2; i--) {
		ans *= i;
	}
	for (int i = n; i >= 2; i--) {
		ans /= i;
	}
	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
24
25
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll ans = 0;
int n;

void dfs(int stack_elements, int next_in) {
	if (next_in > n) {
		ans++;
		return;
	}
	else {
		dfs(stack_elements + 1, next_in + 1);//进栈
		if (stack_elements > 0) {
			dfs(stack_elements - 1, next_in);//出栈
		}
	}
}

int main() {
	cin >> n;
	dfs(0, 1);
	cout << ans << endl;
	return 0;
}

评论