题解-密码锁

· · 题解

注意，如果你想要学习正解的话请略过本篇题解，本篇题解仅说明如何随机化乱搞过这道题

upd: 上传了代码

part 1 贪心

首先你可以想到一个显然假的贪心：从 1 \sim n 考虑，对于每个转圈枚举出转多少对总答案的影响最小。

但是这个贪心有后效性，所以会得到错误的解。

part 2 随机化

你发现拼合多个错误的贪心和 dp 可以得到近似解。

你考虑这个错误的贪心算法的正确性和顺序有关 ，一个好的顺序可以瞬间帮你得到正确答案。

于是你考虑随机化这个序列，然后你发现随机 300 次的时候 1 \leq k \leq 3 能得到正解，但是 k=4 的时候似乎会得到错误的解。

通过调参，可以发现随机 600 次的时候 k=4 可以得到正确的解，但是前面会被卡常，于是考虑数据点分治

然后喜提最劣解（10s）

如果 WA 了可以尝试改变随机数种子多交几发，应该是很稳定基本能过的

part 3 代码

可能有略微压行，见谅


#include<bits/stdc++.h>
using namespace std;
int n,T,k,a[200010][10];//为了随机化时连续访问所以把10开在后面
int mn[10],mx[10];
int main(){
    freopen("lock.in","r",stdin),freopen("lock.out","w",stdout);
    srand(1679057163);//此随机种子可以通过infoj的民间数据
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T>>k;
    while(T--){
        cin>>n;
        for(int i(1);i<=k;++i)for(int j(1);j<=n;++j)cin>>a[j][i];
        int ans(1e9),en(k==4?600:300);//可以发现k=4的时候n比较小
        for (int i=1;i<=en;++i) {
            random_shuffle(a+1,a+n+1);
            memset(mx,-0x3f,sizeof(mx));
            memset(mn,0x3f,sizeof(mn));
            for(int j(1);j<=n;++j){
                int v(1e9),p;
                for(int x(0);x^k;++x) {
                    int tmp(0);
                    for(int y(1);y<=k;++y){
                        const int Tmp=(y+x-1)%k+1;
                        tmp=max(tmp,max(mx[y],a[j][Tmp])-min(mn[y],a[j][Tmp]));
                    }
                    v=tmp<v?(p=x,tmp):v;
                }
                for(int y=1;y<=k;++y) {
                    const int Tmp=(y+p-1)%k+1;
                    mx[y]=max(mx[y],a[j][Tmp]);
                    mn[y]=min(mn[y],a[j][Tmp]);
                }
                if(ans<=v)break;//如果无法更新答案了就退出
            }
            int ret(0);
            for(int i=1;i<=k;++i)ret=max(ret,mx[i]-mn[i]);
            ans=min(ans,ret);
        }
        cout<<ans<<'\n';
    }
    return 0;