[数据结构与算法]2021暑期杭电多校第一场1，5，8，9题解

1.Mod, Or and Everything
简单结论题，打表找规律。
题目大意：现在给你一个数，你要把(n%1) | (n%2) | … | (n%n)计算出来。
思路：首先我们打表找一下规律，发现就是从1到x做或操作，其中当n是奇数时x为(n/2)，当n是偶数时x为（n/2 - 1）。观察数据我们会发现n是1e12，一半就是5e11，很明显暴力在1s的时间会爆。所以我们再观察一下。要注意的是这是二进制的运算，我们把目光投到二进制上，发现这样的一个运算得到的是1111这样的数。好的到这里就可以了。
代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ctx cout << "xxxxx" << endl
#define inf 0x3f3f3f3f
//#define int long long
#define eps 0.000000001
#define forn for(int i = 1; i <= n; i++)
#define ct1 cout << -1 << endl;
const int INF = 0x3f3f3f3f;
const double pai = acos(-1.0);

int main() {
	int t;
	cin >> t;
	while(t--) {
		ll n;
		cin >> n;
		ll tmp = 0;
		if(n & 1) {
			tmp = n/2;
		} else {
			tmp = n/2 - 1;
		}
		vector<ll> tt;
		while(tmp) {
			tt.push_back(tmp%2);
			tmp /= 2;
		}
		ll ans = 1;
		for(int i = 1; i <= tt.size(); i++){
			ans *= 2;
		}
		cout << ans - 1 << endl;
	}

}

5.Minimum spanning tree
结论题
题目大意：
给你一个数n，现在你会有从2到(n-1)的点，让他们两两相连。然后每条边的权值就是两个数的最小公倍数。
思路：
我们先思考到偶数，所有偶数与二相连就是他们本身，然后看到奇数，奇数中有两种数，一种是质数，另一种是非质数。我们看到非质数，他们如果与自己的除数相连，那就是本身。现在就剩下质数，我们把他们与质数相连，就能得到最小的2*质数。现在结论就出来了，从3加到n，然后遇到质数就加上这个质数。
代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ctx cout << "xxxxx" << endl
#define inf 0x3f3f3f3f
#define int long long
#define eps 0.000000001
#define forn for(int i = 1; i <= n; i++)
#define ct1 cout << -1 << endl;
const int INF = 0x3f3f3f3f;
const double pai = acos(-1.0);
const int maxn = 1e7 + 10;

bool book[maxn];

signed main(){
	for(int i = 2; i <= 1e7; i++){
		if(!book[i]){
			for(int j = 2; i*j <= 1e7 + 10; j++){
				book[i*j] = 1;
			}
		}
	}
	
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		int ans = (n+3)*(n-2)/2;
		
		for(int i = 3; i <= n; i++){
			if(!book[i]) ans += i; 
		}
		cout << ans << endl;
	}
	
	
} 

8.Maximal submatrix
单调栈或者悬线法，我不会。
在做本题前请要看一下：单调栈做法基础
题目大意：要在每一列找一个不递减的一段，然后合并，得到面积最大的矩形。
思路：我们每一列分开看，每一列的元素都转换成是否比上一个元素大。这样，每一列复杂的元素就变得简单起来，也可以说，那个元素表示的是当前的高度，不懂的可以自己画图观察，起点不一样是不会影响整个值的。然后对每一行都来一次寻找矩形最大面积的处理。然后取最值。
代码：

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#define ctx cout << "xxxxxx" << endl
using namespace std;
using ll = long long;
int n, m;

const int maxn = 2e3 + 10;

struct vv {
	int val, idx;
};
int b[maxn][maxn];
vv a[maxn][maxn];
void solve() {
	cin >> n >> m;
	for(int i = 1; i <= n+1; i++){
		for(int j = 1; j <= m+1; j++){
			b[i][j] = 0;
			a[i][j].val = 0, a[i][j].idx = 0;
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> b[i][j];
		}
	}
	for(int i = n; i >= 1; i--) {
		for(int j = m; j >= 1; j--) {
			if(b[i][j] <= b[i+1][j]) {
				a[i][j].val = a[i+1][j].val + 1;
			} else {
				a[i][j].val = 1;
			}
			a[i][j].idx = j;
		}
	}
	stack<vv> sk;
	sk.push({0,0});
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m+1; j++){
			while((sk.top()).val > a[i][j].val){
				vv tmp = (sk).top();
				sk.pop();
				ans = max(ans, tmp.val * (j - tmp.idx));		
			}
			sk.push(a[i][j]);
		}
	}
	cout << ans << endl;

}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while(t--) {
		solve();
	}
}

9.KD-Graph
据说是签到题，最小生成树。
题目大意：我们现在有n个点和m条边，现在我们要把他们分成k个部分，满足：

1. 每个部分至少一个点。
2. 如果顶点p和q（p≠ q）在同一组中，p和q之间必须至少有一条路径满足此路径中的最大值小于或等于D
3. 如果顶点p和q（p≠ q）在不同的组中，p和q之间不能有任何路径满足此路径中的最大值小于或等于D

思路：把边权从小到大排序，然后并查集合并。有k个部分就可以找到，并且当前合并的就是最小的D。然后你必须把边权相同的都放进去。
官方题解是一开始看作n个部分，然后合并的过程中就可以减少部分的数。然后一个大部分看作一个部分，其余点都是分别做一个部分。这样这满足题意了。当然，据说能用最小生成树做。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ctx cout << "xxxxx" << endl
#define inf 0x3f3f3f3f
#define int long long
#define eps 0.000000001
#define forn for(int i = 1; i <= n; i++)
#define ct1 cout << -1 << endl;
const int INF = 0x3f3f3f3f;
const double pai = acos(-1.0);
const int maxn = 1e6 + 10;

int fa[maxn];

inline void iit(int n) {
	for (int i = 0; i <= n; i++) fa[i] = i;
}

int findx(int x) {
	return (x == fa[x] ? x : (fa[x] = findx(fa[x])));
}

void merge(int x, int y) {
	int f_x = findx(x), f_y = findx(y);
	if (f_x != f_y) {
		fa[f_x] = f_y;
	}
}

struct vv {
	int u, v, w;
}p[maxn];

bool cmp(vv a, vv b) {
	return a.w < b.w;
}

void solve() {
	int n, m, k, now, ans;
	cin >> n >> m >> k;
	now = n, ans = 0;
	iit(n);
	for (int i = 1; i <= m; i++) {
		cin >> p[i].u >> p[i].v >> p[i].w;
	}
	sort(p + 1, p + 1 + n, cmp);
	for (int i = 1; i <= m; i++) {
		if (p[i].w != p[i - 1].w) {
			if (now == k)
			{
				cout << ans << endl;
				return;
			}
		}

		int c = findx(p[i].u), d = findx(p[i].v);
		if (c == d) continue;
		now--;
		merge(c, d);
		ans = p[i].w;

	}
	cout << (now == k ? ans : -1) << endl;

}

signed main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}