Practice. Solved 3 of 6.
A. Hossam and Combinatorics
题意
定义数对 \((a_i,a_j)\) 满足 \(i \neq j\)。给定数组 \(a\)，输出满足 \(|a_i-a_j|\) 最大的数对数量。
思路
既然要找出 \(\max(|a_i-a_j|)\)，那么我们就需要先把它求出来。更具体地说，我们在读入数组 \(a\) 的时候可以顺便记录下来最大值 \(maxx\) 和最小值 \(minn\)，方便后续操作。
考虑到我们不可能再对数组进行多次遍历，我们可以在读入数组 \(a\) 的时候也记录一下每个数字出现的次数 \(cnt\)，为节省空间我们可以用 \(map\) 存储。
令 \(maxx-minn=dist\)，那么对于一个数对 \((a_i,a_j)\)，我们只需满足 \(|a_i-a_j|=dist\)，去掉绝对值，我们便可以得到两个式子：\(a_j=a_i-dist\)，\(a_j=a_i+dist\)。不妨记此时的 \(a_j\) 为左值和右值，那我们就只需遍历所有 \(a_i\)，判断一下 \(cnt[a_j]\) 是否大于 \(0\) 即可。对于左值和右值，我们可以分开标记以防重复计算（看到题解并没有这么做，待考证.jpg)
对于每次遍历的统计，我们只需 \(ans+=cnt[a_i] \times cnt[a_j] \times 2\) 即可。
时间复杂度：最坏 \(O(n)\)
对应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
题意
给定 \(m\) 组关系，约定除了这些关系外其他人都是好朋友，输出所有连续子序列中满足所有人都是好朋友的数量。
思路
我们先用一种双指针的思维来模拟一下：一开始，\(l=0,r=0\)，然后我们将 \(r\) 向后移，会发现我们能向右移的范围在缩小。因为每扩大一次区间，我们就会遇到更多对陌生人。为了处理这种情况，我们可以在读入关系 \((x,y)\) 的时候顺便记录下来 \(\min(x,y)\) 对应的 \(\max(x,y) -1\)，这样我们在每次遍历的时候就可以以 \(O(1)\) 的时间复杂度更新右端点最大值了，当无法继续时，我们再更改 \(l\)，直到结束。
上述思路是完全正确的，但存在一个问题：暴力模拟 \(1e10\) 的复杂度绝对是超时的。
顺着不行，我们来换个方向。依然是固定 \(l\)，但这次我们从 \(n-1\) 往回推，就不难发现一个递推式子了： 定义 \(nxt[i]\) 为以 \(i\) 为左边界的满足条件的最小右边界，那么 \(nxt[i]=\min(e[i],nxt[i+1])\) 。这里的 \(e\) 数组即为1中记录的关系 \((x,y)\)。 很好理解，在向左移动头节点的时候，尾节点已经遍历过后面的所有值，因而我们可以直接用动态规划的思路来推出 \(nxt\) 数组。
接下来就好办了，既然对于每个左边界 \(i\)，都能找到确定的右边界 \(nxt[i]\)，那么连续子区间数量就为 \(nxt[i]-i+1\) 了。
当然，\(e\) 数组和 \(nxt\) 数组完全可以合并。
时间复杂度： \(O(n)\)
对应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
题意
给定数组 \(a\)，输出是否有满足 \(gcd(a_i,a_j)>1,i \neq j\) 的 \(i,j\)。
思路
优雅的暴力
我们只需打表，筛出所有我们需要的质数，然后分解质因数并记录每个因数出现的次数即可，只要有一个 \(cnt \geq 2\)，那么直接判YES即可。
当然，这么暴力是绝对超时的，我们可以考虑下面的优化思路：
时间复杂度： \(O(\frac{n \sqrt{A}}{\log n})\)
对应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");
}
}有时候可以想想暴力+优化的思路呢