1.1 vp Codeforces Round #837 (Div. 2)

A - Hossam and Combinatorics

题意：给出数组a，求数组中aj - ai == max(a) - min(a)的(i, j)对数
思路：将a数组排序，极差只可能等于最大值减最小值，也就是对数跟最大值和最小值的个数有关。
若最大值x和最小值y不同，对数就等于cntx * cnty * 2；
若相等，即为（1+2+...+n - 1） * 2;

void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	sort(a + 1, a + 1 + n);
	int cnt1 = count(a + 1, a + 1 + n, a[1]);
	int cnt2 = count(a + 1, a + 1 + n, a[n]);
	if (a[n] == a[1]) {
		LL sum = 0;
		for (int i = 1; i <= n; i ++){
			sum += n - i;
		}
		cout << sum * 2 << endl;
		return ;
	}
	cout << (LL)cnt1 * cnt2 * 2 << endl;
}

B - Hossam and Friends

题意：给出从1到n的序列，给出m对关系，关系i,j代表i和j没有朋友关系，求在1到n中有朋友关系的子段有多少个
思路：若是求没有朋友关系的子段会有重复，较为难求。故而直接求有朋友关系的子段
将m对关系保存在vector中，用multiset保存关系的右端点
枚举1到n，将当前点作为有朋友关系的左端点l，可以证明在set中保存的首个元素一定是离该关系的最近的右端点r
ans每次加上r - l后，将该端点的所有关系从set中全部去除，即有朋友关系的贡献一定是在该点里其最近的右端点产生的，剩下的不会产生贡献因此删除

vector<int> h[N];
multiset<int> s;
 
//注意观察N的大小
void solve() {
	int n, m;
	cin >> n >> m;
	s.clear();
	s.insert(n + 1);    //为了防止第n个元素没有对应关系，在n+1处放置一个关系
	for (int i = 1; i <= n; i ++) h[i].clear();
	for (int i = 1; i <= m; i ++) {
		int x, y;
		cin >> x >> y;
		if (x > y) swap(x, y);
		h[x].push_back(y);
		s.insert(y);
	}
	
	LL ans = 0;
	
	for (int i = 1; i <= n; i ++) {
		ans += *s.begin() - i;
		for (auto t : h[i]) s.erase(s.find(t));
	}
	
	cout << ans << endl;
}

C - Hossam and Trainees

题意：给出序列a，如果a中有两个元素可以同时被x整除（x > 2），输出YES,否则NO
思路：打暴力时间复杂度会超，于是想到用线性筛将所有质因子全部筛出来，然后在序列中分解质因数，如果有质因数之前出现过，说明找到了，输出YES，否则NO

int a[N];
int prime[N], cnt;
bool st[N];
 
void get_prime(int n) {
	for (int i = 2; i <= n; i ++) {
		if (!st[i]) prime[++ cnt] = i;
		for (int j = 1; prime[j] * i <= n; j ++) {
			st[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}
 
//注意观察N的大小
void solve() {
	int n;
	cin >> n;
	set<int> se;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= cnt && prime[j] <= a[i] / prime[j]; j ++) {
			if (a[i] % prime[j] == 0) {
				if (se.find(prime[j]) != se.end()) {
					cout << "Yes" << endl;
					return ;
				}
				se.insert(prime[j]);
				while (a[i] % prime[j] == 0) a[i] /= prime[j];
			}
		}
		
		if (a[i] > 1) {
			if (se.find(a[i]) != se.end()) {
				cout << "Yes" << endl;
				return; 
			}
			se.insert(a[i]);
		}
	}
	cout << "No" << endl;
}

D.Hossam and (sub-)palindromic tree

D题是个2100分的图论，暂时无能力解决

总结：目前思路上比较困难。对于技术类问题，不仅可以用划分集合的方法，也可以按照题目特性通过枚举区间累加的方法。对于有因数的题，第一时间可以想到质因子，想到用来降低时间复杂度的筛法