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

Gouryella · 2025-01-09 15:04:14 · 题解

第一眼想到状压 DP，设 f_{s,0} 表示使用了 s 里面的函数能得到的最大值，f_{s,1} 则表示能得到的最小值，转移：

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

这一部分的代码：

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，给你嗨磕到起唠。然后尝试对拍，发现拍了一万组才能拍出错，这暗示我们数据非常难造。于是写一个模拟退火，每次交换三到四个数对，调调参就能卡过去吔，或者把伪算缝进去，这样稳过咩。

码：

#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;
}