0%

Codeforces - Round 837 Div 2

Practice. Solved 3 of 6.

A. Hossam and Combinatorics

题意

定义数对 满足 。给定数组 ,输出满足 最大的数对数量。

思路

  1. 既然要找出 ,那么我们就需要先把它求出来。更具体地说,我们在读入数组 的时候可以顺便记录下来最大值 和最小值 ,方便后续操作。

  2. 考虑到我们不可能再对数组进行多次遍历,我们可以在读入数组 的时候也记录一下每个数字出现的次数 ,为节省空间我们可以用 存储。

  3. ,那么对于一个数对 ,我们只需满足 ,去掉绝对值,我们便可以得到两个式子:。不妨记此时的 为左值和右值,那我们就只需遍历所有 ,判断一下 是否大于 即可。对于左值和右值,我们可以分开标记以防重复计算(看到题解并没有这么做,待考证.jpg)

  4. 对于每次遍历的统计,我们只需 即可。

时间复杂度:最坏

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, inf = 0x3f3f3f3f;

int a[N];
bool stl[N], str[N];

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        memset(a, 0, sizeof a);
        memset(stl, 0, sizeof stl);
        memset(str, 0, sizeof str);
        scanf("%d", &n);
        map<int, long long> cnt;
        int minn = inf, maxx = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            cnt[a[i]] ++;
            minn = min(minn, a[i]);
            maxx = max(maxx, a[i]);
        }
        int dist = maxx - minn;
        long long ans = 0;
        if(dist == 0) ans = (long long) n * (n - 1);
        else for(int i=0;i<n;i++){
            if(!stl[a[i]]) {
                stl[a[i]] = true;
                if (a[i] > dist && cnt[a[i] - dist] > 0) {
                    str[a[i] - dist] = true;
                    ans += cnt[a[i]] * cnt[a[i] - dist] * 2;
                }
            }
            if(!str[a[i]]) {
                str[a[i]] = true;
                if (cnt[a[i] + dist] > 0) {
                    stl[a[i] + dist] = true;
                    ans += cnt[a[i]] * cnt[a[i] + dist] * 2;
                }
            }
        }
        printf("%lld\n", ans);
    }
}

思维还是很重要滴

B. Hossam and Friends

题意

给定 组关系,约定除了这些关系外其他人都是好朋友,输出所有连续子序列中满足所有人都是好朋友的数量。

思路

  1. 我们先用一种双指针的思维来模拟一下:一开始,,然后我们将 向后移,会发现我们能向右移的范围在缩小。因为每扩大一次区间,我们就会遇到更多对陌生人。为了处理这种情况,我们可以在读入关系 的时候顺便记录下来 对应的 ,这样我们在每次遍历的时候就可以以 的时间复杂度更新右端点最大值了,当无法继续时,我们再更改 ,直到结束。

  2. 上述思路是完全正确的,但存在一个问题:暴力模拟 的复杂度绝对是超时的。

  3. 顺着不行,我们来换个方向。依然是固定 ,但这次我们从 往回推,就不难发现一个递推式子了:

    定义 为以 为左边界的满足条件的最小右边界,那么 。这里的 数组即为1中记录的关系

    很好理解,在向左移动头节点的时候,尾节点已经遍历过后面的所有值,因而我们可以直接用动态规划的思路来推出 数组。

  4. 接下来就好办了,既然对于每个左边界 ,都能找到确定的右边界 ,那么连续子区间数量就为 了。

  5. 当然, 数组和 数组完全可以合并。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, inf = 0x3f3f3f3f;

int nxt[N];

int main() {
    int T, n, m, x, y;
    scanf("%d", &T);
    while (T--) { //hey, this is easy.
        scanf("%d %d", &n, &m);
        for(int i=1;i<=n;i++) nxt[i] = n;
        for(int i=0;i<m;i++){
            scanf("%d %d", &x, &y);
            nxt[min(x, y)] = min(nxt[min(x, y)], max(x, y) - 1);
        }
        for(int i=n-1;i>=1;i--) nxt[i] = min(nxt[i], nxt[i + 1]);
        long long ans = 0;
        for(int i=1;i<=n;i++) ans += nxt[i] - i + 1;
        printf("%lld\n", ans);
    }
}

都想到双指针了,何不换个方向想想看呢

C. Hossam and Trainees

题意

给定数组 ,输出是否有满足

思路

优雅的暴力

我们只需打表,筛出所有我们需要的质数,然后分解质因数并记录每个因数出现的次数即可,只要有一个 ,那么直接判YES即可。

当然,这么暴力是绝对超时的,我们可以考虑下面的优化思路:

  1. 线性筛法,复杂度降到

  2. 既然是分解质因数,那么我们只需分解小的那一半即可,大的无需考虑,因而我们可以把边界缩小到

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector<int> primes;
bool vis[N + 1];
map<int, int> cnt;

void init() {
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) {
            primes.emplace_back(i);
        }
        for (int &j : primes) {
            if (1ll * i * j > N) break;
            vis[i * j] = true;
            if (i % j == 0) break;
        }
    }
}

bool fact(int x) {
    int max = (int) sqrt(x);
    for (int &i : primes) {
        if(i > max) break;
        if (x % i == 0) {
            while (x % i == 0) x /= i;
            cnt[i] ++;
            if(cnt[i] == 2) return true;
        }
    }
    if (x != 1) {
        cnt[x] ++;
        if(cnt[x] >= 2) return true;
    }
    return false;
}

int main() {
    init();
    int T, n;
    scanf("%d", &T);
    while (T--) {
        cnt.clear();
        scanf("%d", &n);
        bool ok = false;
        for(int i=0;i<n;i++){
            int x;
            scanf("%d", &x);
            if(ok) continue;
            if(fact(x)) ok = true;
        }
        printf(ok ? "YES\n" : "NO\n");
    }
}

有时候可以想想暴力+优化的思路呢