题解：P13553 [IOI 2025] 神话三峰 triples Part 2

在 Part 1 中，我们将匹配根据

h

的关系分成了六种类型。其中有五种都是很好做的，第六种可以通过三元环计数来完成。

观察匹配形式，其实我们应该去尽可能构造第六种。因为前五种之所以简单是它们可以一推二，也就是三元组中确定了某一个可以推导到另一个，这是我们很不希望了，这意味着三元组的变化很小基本很固定，难以让其数量增多。

故应该从第六种入手，这个变化多。我们应该让三元环个数尽可能多。有一个很基础的想法就是我们用很少的点，然后造一堆连在它们之间的边，这样子三元组的个数就会很多。首先应该注意到点的个数不能太少，因为通过两个点之间的信息解二元一次方程可以唯一确定一组

(i,h_i)

，也就是说不能有重边。

自己做这题的时候就止步于此，因为我觉得自己造点很考验技术，随机造点又不太靠谱的样子。于是就瞎输出了一些很小的序列的组合获得了

78 \rm pts

。后来看了别人的代码，发现这种思路确实可行，而且正是随机！

具体来说我们随机取一些

[0,M]

之间的偶数（不要太多，防止点很多导致边比较分散，但也不能太少不然的话就无法填充

h

数组了），取偶数的目的是为了解方程一定有解。然后在选择偶数中枚举所有数对，通过解方程确实

(i,h_i)

。肯定有一些

h_i

到最后也没有被覆盖，我们就统一赋值为

1

。

使用在 Part 1 中写的计数函数进行计算，多次随机，取最大的一次输出即可。

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int maxn=4e5+10;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
int h[maxn],from[maxn],deg[maxn],n; 
int p[maxn],rk[maxn],vis[maxn]; map<int,int> id;
vector<int> G[maxn],L[maxn],R[maxn]; 
pair<int,int> E[maxn];
bool cmp(int x,int y){ return deg[x]<deg[y]||(deg[x]==deg[y]&&x<y); }
ll count_triples(vi H){
	n=H.size(); ll ans=0;
	for(int i=1;i<=n;i++) h[i]=H[i-1];
	//(i,j,k)
	//Hi=max{Hi,Hj,Hk}
	for(int i=1;i<=n;i++){
		int k=i+h[i];
		if(k>n) continue;
		int j=i+h[k];
		if(j<k&&j+h[j]==k) ans++;
		if(k-h[k]!=j){
			j=k-h[k];
			if(i<j&&j-h[j]==i) ans++;
		}
	}
	//Hk=max{Hi,Hj,Hk}
	for(int k=1;k<=n;k++){
		int i=k-h[k];
		if(i<1) continue;
		int j=i+h[i];
		if(j<k&&j+h[j]==k) ans++;
		if(k-h[i]!=j){
			j=k-h[i];
			if(i<j&&j-h[j]==i) ans++;
		}
	}
	//Hj=max{Hi,Hj,Hk}
	for(int i=1;i<=n;i++){
		if(i+h[i]<=n) L[i+h[i]].pb(i);
		if(i-h[i]>=1) R[i-h[i]].pb(i);
	}
	for(int i=1;i<=n;i++){
		for(auto u:R[i]) vis[u]=1;
		for(auto u:L[i])
			if(u+h[i]<=n&&vis[u+h[i]]&&h[u+h[i]]!=h[u]) ans++;
		for(auto u:R[i]) vis[u]=0;
	}
	int tot=0;
	for(int i=1;i<=n;i++){
		int h1=i+h[i];
		int h2=i-h[i];
		if(id.find(h1)==id.end()) id[h1]=++tot;
		if(id.find(h2)==id.end()) id[h2]=++tot;
		h1=id[h1]; h2=id[h2];
		E[i]=mp(h1,h2); deg[h1]++; deg[h2]++;
	}
	for(int i=1;i<=tot;i++) p[i]=i;
	sort(p+1,p+1+tot,cmp);
	for(int i=1;i<=tot;i++) rk[p[i]]=i;
	for(int i=1;i<=n;i++){
		int u=E[i].fi,v=E[i].se;
		if(rk[u]<rk[v]) G[u].pb(v);
		else G[v].pb(u);
	}
	for(int u=1;u<=tot;u++){
		for(auto v:G[u]) from[v]=u;
		for(auto v:G[u])
			for(auto w:G[v])
				if(from[w]==u) ans++;
	}
	for(int i=1;i<=n;i++) L[i].clear(),R[i].clear(); 
	for(int i=1;i<=tot;i++){
		G[i].clear(); deg[i]=0;
	} id.clear();
	return ans;
}
vi ans; int m;
void add(int x,int y){
	if(x<y) swap(x,y);
	int i=(x+y)/2,j=(x-y)/2;
	if(!ans[i]) ans[i]=j;
}
vi construct_range(int M,int K){
	ans.resize(M); int lim=2700,seed=330;
	double st=clock(); vi res; ll cur=0;
	while((clock()-st)/CLOCKS_PER_SEC<=1.8){
		mt19937 rnd(seed); vi vec;
		for(auto &z:ans) z=0;
		for(int i=0;i<=M;i+=2) vec.pb(i);
		shuffle(vec.begin(),vec.end(),rnd);
		if(vec.size()>lim) vec.resize(lim);
		for(int i=0;i<vec.size();i++)
			for(int j=0;j<i;j++) add(vec[i],vec[j]);
		for(auto &z:ans) 
			if(!z) z=1;
		int z=count_triples(ans);
		if(count_triples(ans)>cur){
			cur=z; res=ans;
		} seed++;
	}
	return res;
}

题解：P13553 [IOI 2025] 神话三峰 triples Part 2

文章操作

相关推荐

评论

题解：P13553 [IOI 2025] 神话三峰 triples Part 2