2021ICPC上海站

100 阅读 0 评论 66 点赞

我是靠谱客的博主粗心手链，这篇文章主要介绍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的值

复制代码

#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;
}

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;
}