Codeforces Round #837 (Div. 2) A-C

A. Hossam and Combinatorics

题意：

给定一个长度为n的序列，求两个不同位置的数的差值等于所有数差值的最大值的数对数量。

分析：

显然排序后取最大最小就是差的绝对值最大，再统计最小数的个数与最大数的个数，这里特判一下相等的情况

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    minv = a[1], maxv = a[n];

    if (minv == maxv)
    {
        cout << (n - 1) * n << endl;
        return;
    }
    int idx1 = 1, idx2 = 1;
    for (int i = 2; i < n; i++)
    {
        if (a[i] == minv)
            idx1++;
        if (a[i] == maxv)
            idx2++;
    }
    cout << 2 * idx1 * idx2 << endl;
}

B. Hossam and Friends

题意：

给定 m 个数对，对于 1−n 的所有连续子序列中，任意一个数对都不能同时出现，这样的连续序列 [a,b] 定义为good的序列，求这样的序列的数量。

分析：

考虑对每一个左端点记录可以涵盖的最大右端点，注意单个元素也算一个good序列，这个可以在最后输出答案时加上n个单独计算。

void solve()
{
    res = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        t[i] = n;
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        if (l > r)
            swap(l, r);
        t[l] = min(t[l], r - 1);
    }

    for (int i = n - 1; i; i--)
        t[i] = min(t[i], t[i + 1]);

    for (int i = 1; i <= n; i++)
    {
        if (t[i] != i)
            res += t[i] - i;
        // cout << i << " " << t[i] << " " << res << endl;
    }
    cout << res + n << endl;
}

C. Hossam and Trainees

题意：

判断 n 个数是否两两互质。

 分析：

根据唯一分解定理：任何整数都可以分解为一些不同质数幂次方的乘积，预处理出所需要的质数后O(n)，查看每个a[i]分解出的质数是否只出现一次，若出现多次则不符合题意

void get_primes(int n)
{
    for (int i = 2; i < n; i++)
    {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] * i < n; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}
void solve()
{
    mp.clear();
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        int num = a[i];
        for (int j = 0; primes[j] * primes[j] <= num; j++)
        {
            int t = primes[j];
            if (num % t == 0)
            {
                while (num % t == 0)
                    num /= t;

                mp[t]++;
                if (mp[t] > 1)
                {
                    cout << "YES" << endl;
                    return;
                }
            }
        }
        if (num > 1)
            mp[num]++;
        if (mp[num] > 1)
        {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}