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

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