CF1712.

A. Wonderful Permutation

考虑到这是个排列，所以最优解一定是把 \(1 \sim k\) 都放在 \([1,k]\) 里面，因此答案是 \([1,k]\) 中满足 \(p_i>k\) 的 \(i\) 的个数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int t, n, k, a[105];
void solve() {
	n=read(), k=read();
	for(int i=1;i<=n;++i) a[i]=read();
	int ans=0;
	for(int i=1;i<=k;++i) if(a[i]>k) ++ans;
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}

B. Woeful Permutation

如果 \(a,b\) 互质，那么 \(\operatorname{lcm}(a,b) = a \times b\)。

由于这是个排列，而相邻两数必定互质，所以先令 \(p_i = i\)，从大到小贪心地两两交换即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int t, n, a[N];
void solve() {
	n=read();
	for(int i=1;i<=n;++i) a[i]=i;
	for(int i=n;i>0;i-=2) {
		if(i>=2) swap(a[i],a[i-1]);
	}
	for(int i=1;i<=n;++i) printf("%lld%c",a[i]," \n"[i==n]);
}
signed main() {
	t=read();
	while(t--) solve();
}

C. Sort Zero

由于最终序列单调不降，所以 \(0\) 一定是一段前缀。

考虑如果存在由重复元素围成的峰，例如1 2 1，那么这一段必然全部为 \(0\)；如果存在由重复元素围成的谷，例如2 1 2，那么这一段也必然全部为 \(0\)。

以上两种情况，均可以推得那一段前缀全部为 \(0\)。

但是，取最靠后的峰或谷的末尾，就一定可行吗？

考虑

3 3 2

不存在峰和谷，但是由于存在逆序对导致不满足单调不降，所以必须将这个逆序对破坏掉。

也就是说，假设 \(a_{i-1}\) 和 \(a_i\) 构成了逆序对，那么 \(a_{i-1}\) 必须为 \(0\)，进而 \([1,i-1]\) 必须全为 \(0\)。

同理

4 1 5 3 2

有峰有谷，但是不满足由重复元素围成。考虑到有峰有谷就一定存在逆序对，那么仍然按照上面的方法就行。

最后找到全部为 \(0\) 的前缀 \([1,d]\)，答案为 \([1,d]\) 中不同元素的数量。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int t, n, a[N];
set<int> s, st;
void solve() {
	n=read();
	s.clear(), st.clear();
	for(int i=1;i<=n;++i) a[i]=read();
	int d=0;
	for(int i=1;i<=n;++i) {
		if(s.count(a[i])&&a[i]!=a[i-1]) d=i;
        // 如果s.count(a[i])成立，说明有重复元素
        // 如果a[i]!=a[i-1]成立，说明这两个重复元素必然构成峰或谷
        // 重复元素相邻的情况则不用考虑
		s.insert(a[i]);
	}
	for(int i=n;i>d+1;--i) if(a[i]<a[i-1]) { d=i-1; break; }
    // 找到最后一个逆序对的位置
	int ans=0;
	for(int i=1;i<=d;++i) {
		if(st.count(a[i])) continue;
		++ans, st.insert(a[i]);
	}
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}

D. Empty Graph

一个结论：这张图的直径一定来自于两个相邻的节点。

证明：假设直径的两个端点 \(l\) 与 \(r\)，不满足 \(l+1=r\)，那么将 \(r\) 改为 \(r-1\) 后，由于 \(\min_{i=l}^r{\{ a_i \}} \le \min_{i=l}^{r-1}{a_i}\)，所以这时候两点之间的距离不会变小。也就是说，对于一个固定的左端点 \(l\)，不断让左右端点靠近，结果一定不会变差。

因此可以二分直径长度 \(mid\)，判断能否使用不超过 \(k\) 次操作使得存在某个点对之间的距离大于等于 \(k\)。

从 \(i\) 到 \(i+1\) 的最短路有 \(3\) 种，一是直接走 \(\min(a_i,a_{i+1})\)，二是从 \(i\) 走到 \([i+2,n]\) 中满足 \(a_j\) 最小的 \(j\) ，再走回 \(i+1\)，三是从 \(i+1\) 走到 \([1,i-1]\) 中满足 \(a_j\) 最小的 \(j\) 再走回 \(i\)。

设 \(p_i = \min_{j=1}^i{\{a_j\}}\)，\(q_i = \min_{j=i}^n {\{ a_j \}}\)，则第二种的长度为 \(2 \cdot p_{i-1}\)，第三种的长度为 \(2 \cdot q_{i+2}\)。

如何安排操作呢？仔细思考发现，操作是牵一发而动全身的。假如 \(a_i<mid\)，那么修改 \(a_i\) 之后，必须让其他决策全部不能优于 \(a_i\)。即如果 \(a_{i+1} < mid\)，那么不用考虑，否则就要修改它到大于等于 \(a_i\)。同理如果修改了 \(p_{i-1}\)，那么还要修改其他 \([1,i-1]\) 中满足 \(a_j < mid\) 的 \(j\)，使得它们不对最短路产生影响。

更进一步地，所有权值小于 \(mid\) 的路径都要修改，而无论取哪个决策，操作数量是不会变化的。

因此设 \(c_i\) 为 \([1,i]\) 中满足 \(2 \cdot a_j < mid\) 的 \(j\) 的个数，\(d_i\) 为 \([i,n]\) 中满足上述条件的 \(j\) 的个数。对于一个点对 \((i,i+1)\)，将这两点之间的距离作为直径的操作数是 \[ \Delta + c_{i-1} + d_{i+2} \] 其中 \(\Delta\) 为 \(a_i\) 和 \(a_{i+1}\) 中，小于 \(mid\) 的个数。

每次二分用 \(O(n)\) 的时间找到最小操作数，判断是否小于等于 \(k\) 即可。

复杂度为 \(O(n \log_2 n)\)。

另外还有排序再贪心的方法，可以参考这篇博客。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int t, n, k, a[N], c[N], d[N];
bool check(int x) {
	for(int i=0;i<=n+1;++i) c[i]=d[i]=0;
	int ans=n;
	for(int i=1;i<=n;++i) {
		c[i]=c[i-1];
		if(2*a[i]<x) ++c[i];
	}
	for(int i=n;i;--i) {
		d[i]=d[i+1];
		if(2*a[i]<x) ++d[i];
	}
	for(int i=1;i<n;++i) {
		int q=(a[i]<x)+(a[i+1]<x);
		ans=min(ans,q+c[i-1]+d[i+2]);
	}
	return ans<=k;
}
void solve() {
	n=read(), k=read();
	int l=1, r=1e9;
	for(int i=1;i<=n;++i) a[i]=read();
	while(l<r) {
		int mid=(l+r+1)/2;
		if(check(mid)) l=mid; else r=mid-1;
	}
	printf("%lld\n",l);
}
signed main() {
	t=read();
	while(t--) solve();
}

E1. LCM Sum (easy version)

正难则反，考虑用三元组的总数减去满足 \(\operatorname{lcm}(i,j,k) < i+j+k\) 的三元组的个数。

由于 \(i,j,k\) 有序，设 \(len = r-l+1\)，则总数为 \[ \frac{len(len-1)(len-2)}{P_3^3} = \frac{len(len-1)(len-2)}{6} \] 考虑到 \(i < j < k\)，那么 \(i+j+k < 3k\)，因此 \(\operatorname{lcm}(i,j,k) < 3k\)，所以 \(\operatorname{lcm}(i,j,k)\) 只能为 \(k\) 或者 \(2k\)。

枚举 \(k\)，再枚举 \(2k\) 的每个约数 \(j\)，再枚举 \(i\)，逐一判断即可。时间限制为 \(3.5s\)，加上剪枝就能过了。

具体看代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=2e5+5;
int t, l, r;
vector<int> factor[2*N]; 
void solve() {
	l=read(), r=read();
	int len=r-l+1;
	int ans=(len*(len-1)*(len-2))/6;
	for(int k=l+2;k<=r;++k) {
		for(auto j:factor[2*k]) {
			if(j<l||k%j&&2*j<=k) continue;
            // 不在区间内的就不要了
            // k%j!=0，说明lcm(i,j,k)=2k
            // 如果2*j<=k，那么由于i<j，所以i+j<k，所以i+j+k<2k，也就是lcm(i,j,k)>i+j+k
            // 矛盾
			if(j>=k) break;
			for(auto i:factor[2*k]) {
				if(i<l) continue;
				if(i>=j) break;
				if(k%j||k%i) ans-=(2*k)<(i+j+k);
                // 任何一个成立，说明lcm(i,j,k)=2k，直接判断
				else --ans;
                // 否则lcm(i,j,k)=k，一定小于i+j+k
			}
		}
	}
	printf("%lld\n",ans);
}
signed main() {
	for(int i=1;i<=4e5;++i)
		for(int j=2*i;j<=4e5;j+=i)
			factor[j].push_back(i);
    // O(nlogn)的时间里求出[1,n]中每个数的约数
	t=read();
	while(t--) solve();
}