当前位置：网站首页>The 2021 ICPC Asia Shanghai Regional Programming Contest D、E

The 2021 ICPC Asia Shanghai Regional Programming Contest D、E

2022-08-10 19:07:00 【eyuhaobanga】

Problem - D - Codeforces
解方程
正解设 $\frac{p}{q}=k$ , $\frac{a}{b}=x$ ,那么原方程就变成了 $x^{2}-k*x+1=0$ ,那么就成了二元一次方程组来判断有无实根的情况，判别式为 $\Delta =k^{2}-4$ ，幼儿园数学可知 $\Delta$ 大于等于0有实数根，小于0没有实数根，所以有解情况为 $p^{2}\geq 4*q^{2}$ ,然后再根据求根公式得到 $x=\frac{p\pm \sqrt{p^{2}-4*q^{2}}}{2*q}$ ,因此 $\sqrt{p^{2}-4*q^{2}}$ 一定是个整数，进而可知a、b的值，最后把a、b化简
AC代码：
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    rep (oo, 0, T) {
        LL p, q;
        cin >> p >> q;
        if (p * p < 4 * q * q) {
            cout << "0 0\n";
            continue;
        }
        LL tmp = p * p - 4 * q * q;
        LL z = sqrt(tmp);
        if (z * z != tmp) {
            cout << "0 0\n";
            continue;
        }
        function<LL(LL, LL)> gcd = [&](LL x, LL y) {
            return y == 0 ? x : gcd(y, x % y);
        };
        tmp = z;
        LL d = gcd(p + tmp, 2 * q);
        cout << (p + tmp) / d << " " << (2 * q) / d << '\n';
    }

    return 0;
}
E. Strange Integers
选择任意一些数，使得任意两个数之间的差值的绝对值大于等于k，求最多选多找个，直接贪心去选，排一下序从小到大能选即选
AC代码：
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    stack<int> st;
    st.push(a[0]);
    for (int i = 1; i < n; i++) {
        if (a[i] - st.top() >= k) {
            st.push(a[i]);
        }
    }
    cout << st.size() << '\n';

    return 0;
}