CVBB ACM Team

题意:我也是加把劲骑士

题解:全部木大

题意:给定一定长度为$n$的序列，问是否除了$sum[1,n]$的区间和的最大值是否比$sum[1,n]$小。

题解:维护前缀最小值，扫一遍。最后以$n$为结尾的单独扫一遍即可。

题意:给定$X$，求正整数$a,b$使得$LCM(a, b)=X$且$max(a, b)$最小。$(1 \le X \le 10^{12})$

题解:分解质因子，每种质因子只给$a$或只给$b$，质因子种类很小，暴力枚举所有可能即可。

题意:给定长度为$n$的序列$a$，求$X$使得$\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$最小。$(1\le n \le 10^5, 0 \le a_i \le 2^{30}-1)$

题解:将$a$排序。然后有点类似$XOR-MST$那题，一段区间如果某一位都相同，那么显然这一位异或后可以为$0$，继续递归即可。否则这一位异或后必然会有一段连续区间为$1$，因此分成两个区间，分治处理每个区间当这一位异或后为$1$能得到最小值即可。

#include <bits/stdc++.h>
#define maxn 100086
 
using namespace std;
 
int n;
int a[maxn];
int ans = 1 << 30;
 
void dfs(int l, int r, int x, int y){
	if(!y){
		ans = min(ans, x);
		return;
	}
	int mid = r;
	for(int i = l;i <= r;i++){
		if(a[i] & y){
			mid = i - 1;
			break;
		}
	}
	if(mid == l - 1){
		dfs(mid + 1, r, x, y >> 1);
	}else if(mid == r){
		dfs(l, mid, x, y >> 1);
	}else{
		dfs(l, mid, x + y, y >> 1);
		dfs(mid + 1, r, x + y, y >> 1);
	}
}
 
int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++) scanf("%d", &a[i]);
	sort(a + 1, a + 1 + n);
	dfs(1, n, 0, 1 << 29);
	printf("%d", ans);
}

题意:给定$n$个线段，可能退化成点，坐标都是整数，问删掉哪条可以使剩下的线段组成的连通块最多。

题解:离散化，按套路进行线段树覆盖，但发现退化成点不太好处理，所以可以把每个点拆成两个，这样每个点表示到下一个点的那段线段，就可以进行线段树覆盖了。

题意:给定一个序列$a$，求$\max\limits_{1 \le i < j \le n} LCM(a_i,a_j)$。$(2 \le n \le 10^5)$

题解:题越短越难。考虑枚举$gcd$，然后从大到小枚举剩下的部分即$\frac{X}{gcd}$，每遍历到一个数将这个数入栈，现在需要处理对于一个数$x$，栈中有有多少个数与它互质。因为我们如果知道有多少个数与它互质，我们就可以一直弹栈直到栈中没有数与$x$互质，显然这些被弹的这些数比最后一个弹出来的数小，不会影响最优解。这样每个元素如果只进栈出栈一次，如果元素进出栈处理的复杂度以及查询栈中有有多少个数与它互质的复杂度均为$O(m)$我们就可以在$O(nm\log n)$内解决这个问题。设$cnt_i$表示栈中有多少个元素是$i$的倍数，那么我们可以对$x$每个质因子进行容斥得到答案，而莫比乌斯函数在有平方因子时为$0$，否则系数为$(-1)^k$，$k$为质因子个数，正好符合容斥原理的系数，因此答案为$\sum_{d|x} \mu(d)*cnt_d$。预处理出每个数的因子和莫比乌斯函数，就可以做到上述做到的$O(m) = O(\log n)$，因此时间复杂度为$O(n \log ^ 2 n)$。另外要注意这个算法没有考虑两个数相同时的$lcm$，因此要单独考虑一下。