我是靠谱客的博主 粗心手链,这篇文章主要介绍2021ICPC上海站,现在分享给大家,希望可以做个参考。

链接:牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

E题签到题:

复制代码
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 <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long ll; int a[102400] = {0}; int main() { // system("chcp 65001"); cin.tie(0); cout.tie(0); // freopen("C:/Users/zhaochen/Desktop/input.txt", "r", stdin); int n, k; cin >> n >> k; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); int ans = 1; int pre = a[n - 1]; for (int i = n - 2; i >= 0; i--) { if (pre - a[i] >= k) { ans++; pre = a[i]; } } cout << ans; return 0; }

D题:

1.解方程法:

设x=a/b,转化为求方程qx^2-px+q=0的解,求根公式得到a=p+sqrt(dlt),b=2q

复制代码
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 <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long ll; int main() { // system("chcp 65001"); cin.tie(0); cout.tie(0); // freopen("C:/Users/zhaochen/Desktop/input.txt", "r", stdin); int t; cin >> t; while (t--) { ll p, q; cin >> p >> q; ll dlt = p * p - 4 * q * q; if (dlt < 0) { cout << 0 << ' ' << 0 << 'n'; continue; } ll d = sqrt(dlt); if (d * d == dlt) cout << p + d << ' ' << 2 * q << 'n'; else cout << 0 << ' ' << 0 << 'n'; } }

2.推公式法:

先把p、q约到最简,易推得a^2+b^2=p,ab=q,由此推得a+b=sqrt(p+2q),

a-b=sqrt(p-2q),最后判断一下是否为整数

复制代码
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 <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long ll; int main() { // system("chcp 65001"); cin.tie(0); cout.tie(0); // freopen("C:/Users/zhaochen/Desktop/input.txt", "r", stdin); int t; cin >> t; while (t--) { ll p, q; cin >> p >> q; ll gcd = __gcd(p, q); p /= gcd; q /= gcd; ll x = sqrt(p + 2 * q); ll y = sqrt(p - 2 * q); if (x * x != p + 2 * q || y * y != p - 2 * q) { cout << 0 << ' ' << 0 << 'n'; continue; } ll a = (x + y) >> 1; ll b = (x - y) >> 1; if (a + b == x && a - b == y) cout << a << ' ' << b << 'n'; else cout << 0 << ' ' << 0 << 'n'; } return 0; }

3.很捞的做法,二分枚举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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long ll; ll p, q; ll s; double f(ll a) { return 1.0 * a / (s - a) + 1.0 * (s - a) / a; } ll binarySearch(ll l, ll r) { while (l <= r) { ll mid = (l + r) >> 1; double cur = f(mid); if (abs(cur - 1.0 * p / q) < 1e-9) { return mid; } if (cur < 1.0 * p / q) { r = mid - 1; } else { l = mid + 1; } } return 0; } int main() { // system("chcp 65001"); cin.tie(0); cout.tie(0); // freopen("C:/Users/zhaochen/Desktop/input.txt", "r", stdin); int T; cin >> T; while (T--) { cin >> p >> q; ll gcd = __gcd(p, q); p /= gcd; q /= gcd; ll s2 = p + 2 * q; s = sqrt(s2); if (s * s == s2) { ll a = binarySearch(1, s / 2); if (a) { cout << a << ' ' << s - a << 'n'; continue; } } cout << 0 << ' ' << 0 << 'n'; } return 0; }

最后

以上就是粗心手链最近收集整理的关于2021ICPC上海站的全部内容,更多相关2021ICPC上海站内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(66)

评论列表共有 0 条评论

立即
投稿
返回
顶部