题解与讨论

liu_cheng_ao 2018-04-25 8:50:33 2018-07-29 8:59:07

由于作者的数学水平实在过于低下,只能写一些浅薄的局限性很大的内容,效果也并不好(尽管比标准算法优秀得多),敬请指正和补充。

标解是模拟退火,但是这题模拟退火效率不是很高,从后面的测试点 n,m 的比例就可以看出来。

首先转化一下题意,题意是让你将 n 维超立方体的每个顶点染成 m 种颜色之一,要求与每个点距离 \le 1 的点涵盖所有颜色。显然如果 (n,m) 可解,只要将第 m 种颜色全部染成第 m-1 种即可得到 (n,m-1) 的解;另外由于每个点距离 \le 1 的点只有 n+1 个,必有 m \le n+1 。故对于每个 n 存在一个最大的有解的 m ,设为 M(n)

问题

那么我们现在的问题是,给定 n ,求出或近似求出 M(n) ,并快速构造一组方案。

**这个问题是图论中控制数问题的延伸,关于这类问题已有很多研究。**竞赛中也有专门引入和研究过相关内容(如 IMO 2017 集训队讲课)。下面我们给出一个简单的 2 -近似构造方法。

n=2^k-1 的构造

我们给出一种 n=2^k-1,m=2^k 的构造,这在该条件下达到了 n=m-1 的理论下界,并且是一个关于输入 n M(n) 问题的 2 -近似算法。

N3示意图.png

(请结合这张图来理解)

设对于 n=2^k-1,m=2^k ,构造出的解为 N_k

对于 0 维情况, n=0,k=0,m=1 ,超立方体的顶点只有 2^0=1 个,且颜色也为 1 种,是一个满足条件的方案,即 N_0

假设我们已知了 N_i ,我们尝试构造出 N_{i+1}

为了描述方便,用 n 维坐标来描述超立方体的一个顶点,每一维坐标属于 \{0,1\} ;设 \mathrm{parity}(x_0,x_1,\cdots ,x_{n-1})=\sum_{i=0}^{n-1}x_i \pmod 2 表示坐标的奇偶性;令 N_k^{(j)} 表示 N_k 中颜色循环左移 j (即原来的颜色 i 换成 ((i+j-1)\bmod 2^k)+1 )位的结果, N_k+(x) 表示 N_k 中每种颜色编号加 x 的结果。

按照 N_k^{(j)} 的定义,还可以定义两个 N 的积: N_iN_j 表示将 N_i 中每个颜色 i 的点换成一个形如 N_j^{(i)} 的子空间的结果,并且可知新超立方体的大小也是原来二者的乘积,即 |N_iN_j|=|N_i||N_j| ;另外记 x N_i 的积为 N_i^x 。也可以定义两者的和:对于维数相等的 N_i,N_j N_i+N_j 是一个新的超立方体,第一维分成的两个半空间分别与二者相等,且总维数等于二者的维数加 1 ,特别地记 N_i+N_i=2N_i

那么我们可以发现 N_i^2 几乎具有了 N_{i+1} 的性质:每个点有接近两套同构的相邻颜色 —— 这可以让我们倍增颜色的数量。不过还是差了 1 k-1 变成 2k-2 ,与 2k-1 1 ),故我们再多增加一维,这样与每个点相邻的恰好是两套同构的 N_i ,让这两者的颜色独立即可。具体从 N_i 构造出 N_{i+1} 的构造步骤如下:

N_i^{[0]} 表示 N_i 仅考虑 \mathrm{parity}=0 的位置的立方体,类似地设 N_i^{[1]} 表示 N_i 仅考虑 \mathrm{parity}=1 的位置的立方体。

那么有 N_{i+1}=(N_i^{[0]}N_i \cup (N_i^{[1]}N_i+2^i)) + ((N_i^{[0]}N_i+2^i) \cup N_i^{[1]}N_i)

这是一个 2 -近似算法。

附按本题格式输出 N_k 的 C++ 代码:

#include<bits/stdc++.h>

using namespace std;

struct Cube{
	int *a,n,c,N,NN;
	Cube& operator <<= (const int x){
		for(int i=0;i<NN;i++)a[i]=(a[i]+x)%c;
		return *this;
	}
	Cube& operator += (const int x){
		for(int i=0;i<NN;i++)a[i]+=x;
		return *this;
	}
	Cube operator << (const int x){
		Cube r=*this;
		r <<= x;
		return r; 
	}
	Cube operator + (const int x){
		Cube r=*this;
		r += x;
		return r;
	}
	int& operator [] (const int x){
		return a[x];
	}
	Cube(){}
	Cube(int _n){
		n=_n;
		c=1<<n;
		N=(1<<n)-1;
		NN=1<<N;
		if(n==0){
			a = new int[NN];
			a[0] = 0;
		}else{
			Cube x(n-1);
			a = new int[NN];
			for(int i=0,j=0,s=NN/2;i<x.NN;i++,j+=x.NN)
				memcpy(a+j,((x<<x[i])+(c/2)*(__builtin_popcount(j)&1)).a,sizeof(int)*x.NN),
				memcpy(a+s+j,((x<<x[i])+(c/2)*(__builtin_popcount(s+j)&1)).a,sizeof(int)*x.NN);
			x.print();
		}
	}
	Cube(const Cube& x){
		n=x.n,c=x.c,N=x.N,NN=x.NN;
		a = new int[NN];
		memcpy(a,x.a,sizeof(int)*NN);
	}
	~Cube(){
		delete[] a;
	}
	void print(){
		for(int i=0;i<NN;i++)cout<<a[i]<<' ';
		cout<<endl;
	}
};

int main(){
	Cube(3).print(); // 本题 1 到 7 号测试点只需输出一个含 N3 子空间的超立方体即可
	return 0;
}

模拟退火

由于只有 m 种解,直接采用 M(n) 作为估价的模拟退火效率极低,需要使用一些其它的估价方法配合。

扩展

如果各位找到了资料或者有什么想法敬请讨论。

共 2 条回复

visit_world

这个二近似啊。。。在知乎上有人讨论过。。。它还是 IOI 17 的一个练习赛题

OwenOwl

我的煞笔做法…… http://owenowl.net/blogs/mcfx.html