题解 | #光#

首先我们看这个题目，它就很像要从暴力优化到正解啊。所以我反手就是一个 $\mathrm{O}(abcd)\backslash mathrm\; O(abcd)$ 的暴力上去。

然后很显然的，我们不用枚举第四个格子，于是复杂度降到了 $\mathrm{O}(abc)\backslash mathrm\; O(abc)$。

接着我不会优化，但是我们看这个数据范围，小常数有机会过 $15001500$，于是我们随便剪一下枝，就像这样：

for(int i=0;i<=a;i++)
	for(int j=0;j+(bool)j*((i>>1))<=b;j++)
		for(int k=0;k+(bool)k*((i>>1)+(j>>2))<=c;k++)
		{
			int l=max(0,
				max(
					max((a-(i+(j>>1)+(k>>1)))<<2,
						(b-((i>>1)+j+(k>>2)))<<1),
					max((c-((i>>1)+(j>>2)+k))<<1,
						d-((i>>2)+(j>>1)+(k>>1))))
				);
			if(i+j+k+l<answer)
				answer=i+j+k+l;
			if(!l)
				break;
		}

具体原理就是看第四个格子已经到 $00$ 了就没必要再搞下去了。然后显然靠其它格子贡献不如自己贡献，于是每个格子亮度带一个上限就是目标亮度加 $11$。

接着玄学乱搞，我们发现如果把奇数变成偶数可以有 $22$ 的贡献，所以我们考虑强行把每个格子设成偶数（尝试打表想到的）。但是很显然是错的：

17 0 0 0

接着最玄学的就来了啊，我们考虑按刚才的方式找到假的最优解，然后对这个解的前三个格子尝试 $\mathrm{O}(k^3)\backslash mathrm\; O(k^3)$ 的小扰动，并取最优解，具体来讲就是枚举每一个亮度偏移多少。

这个看起来就不像对的啊？是的，这是个错解，但是随机数据下它的错误率在 $\frac{1}{200}\backslash frac1\{200\}$ 以下（甚至可能在 $\frac{1}{1000}\backslash frac1\{1000\}$ 以下，我取的扰动值是 $\pm 10\backslash pm10$）。然后这玩意还是 $\mathrm{O}(abc)\backslash mathrm\; O(abc)$ 啊？但是常数太小了，它还是过了。

Code:

#include <iostream>

using namespace std;

int main(int argc,char *argv[],char *envp[])
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int a,b,c,d,answer=16777216,ansa,ansb,ansc;
	cin>>a>>b>>c>>d;
	for(int i=0,tmp;i<4;i++)
		if(max(max(a,b),max(c,d))!=a)
			tmp=a,a=b,b=d,d=c,c=tmp;
	for(int i=0;i-1<=a;i+=2)
		for(int j=0;j+(bool)j*((i>>1))-1<=b;j+=2)
			for(int k=0;k+(bool)k*((i>>1)+(j>>2))-1<=c;k+=2)
			{
				int l=max(0,
					max(
						max((a-(i+(j>>1)+(k>>1)))<<2,
							(b-((i>>1)+j+(k>>2)))<<1),
						max((c-((i>>1)+(j>>2)+k))<<1,
							d-((i>>2)+(j>>1)+(k>>1))))
					);
				if(i+j+k+l<answer)
					ansa=i,ansb=j,ansc=k,answer=i+j+k+l;
				if(!l)
					break;
			}
	for(int i=max(ansa-10,0);i<=ansa+10;i++)
		for(int j=max(ansb-10,0);j<=ansb+10;j++)
			for(int k=max(ansc-10,0);k<=ansc+10;k++)
			{
				int l=max(0,
					max(
						max((a-(i+(j>>1)+(k>>1)))<<2,
							(b-((i>>1)+j+(k>>2)))<<1),
						max((c-((i>>1)+(j>>2)+k))<<1,
							d-((i>>2)+(j>>1)+(k>>1))))
					);
				if(i+j+k+l<answer)
					ansa=i,ansb=j,ansc=k,answer=i+j+k+l;
				if(!l)
					break;
			}
	cout<<answer;
 	return 0;
}