题解：P10303 [THUWC 2020] 报告顺序

第一眼想到状压 DP，设

f_{s,0}

表示使用了

s

里面的函数能得到的最大值，

f_{s,1}

则表示能得到的最小值，转移：

f_{s,0}=\max_{t\cup\{c\}=s}(g_{f_{t,0},c},g_{f_{t,1},c})

f_{s,1}=\min_{t\cup\{c\}=s}(g_{f_{t,0},c},g_{f_{t,1},c})

其中

g_{x,y}=a_y|x|+b_y x+c_y

。

这一部分的代码：

CPP

f[0][0]=f[0][1]=s;
for(int p=1;p<=n;p++){
	for(int s=0;s<(1<<n);s++){
		int popc=__builtin_popcount(s);
		bool flag=false;
	if(popc!=p)continue;
	for(int i=0;i<n;i++){
		if((s>>i)&1){
				auto res0=f[s^(1<<i)][0],res1=f[s^(1<<i)][1];
				if(!flag){
					f[s][0]=max(Calc(res0,i),Calc(res1,i));
					f[s][1]=min(Calc(res0,i),Calc(res1,i));
					flag=true;
				}else{
					f[s][0]=max({f[s][0],Calc(res0,i),Calc(res1,i)});
					f[s][1]=min({f[s][1],Calc(res0,i),Calc(res1,i)});
				}
			}
		}
	}
}

交上去能拿 55 分且最后一个 subtask 能过十几个点才 WA，~~给你嗨磕到起唠~~。然后尝试对拍，发现拍了一万组才能拍出错，这暗示我们数据非常难造。于是写一个模拟退火，每次交换三到四个数对，调调参就能卡过去吔，或者把伪算缝进去，这样稳过咩。

码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int MaxN=15;
const double k=0.5;
mt19937 rander(chrono::steady_clock::now().time_since_epoch().count());
int n,s,a[MaxN],b[MaxN],c[MaxN],p[MaxN],pt[MaxN];
__int128 f[1<<MaxN][2];
__int128 ABS(__int128 x){return x>0?x:-x;}
__int128 Calc(__int128 x,int p){return a[p]*ABS(x)+b[p]*x+c[p];}
void Output(__int128 x){
	if(x<0)return cout<<'-',Output(-x);
	if(x>9)Output(x/10);
	cout<<char(x%10+'0');
}
__int128 FCalc(){
	__int128 t=s;
	for(int i=0;i<n;i++)t=Calc(t,p[i]);
	return t;
}
void Solve(){
	cin>>n>>s;
	for(int i=0;i<n;i++)cin>>a[i]>>b[i]>>c[i];
	for(int i=0;i<n;i++)p[i]=i;
	auto st=clock();
	auto ans=FCalc();
	double t=1;
	while((clock()-st)*1.0/CLOCKS_PER_SEC<0.9){
		t*=1.00001;
		for(int i=0;i<n;i++)pt[i]=p[i];
		for(int i=0;i<4;i++)swap(p[rander()%n],p[rander()%n]);
		auto now=FCalc();
		if(now>ans){
			ans=now;
			continue;
		}
		if(rander()%int(1e9)/1e9<=-exp(k*t))continue;
		for(int i=0;i<n;i++)p[i]=pt[i];
	}
	Output(ans);
}
int main(){
	cin.tie(0)->sync_with_stdio(false);
	Solve();
	return 0;
}

题解：P10303 [THUWC 2020] 报告顺序

文章操作

相关推荐

评论

题解：P10303 [THUWC 2020] 报告顺序