人类智慧导论——最优化问题杀手

· · 个人记录

作为人类，发扬人类智慧是我们的光荣职责。

我们应该坚信，在最优化问题中，出题人往往缺乏全面人类智慧，甚至完全缺乏人类智慧。三个oier，顶个dinner。我们充分发扬人类智慧，想出精密的乱搞做法，跳开出题人的人类智慧范畴，终能让我们走向胜利✌️。（AK就别想了，这不是正解）

下给出人类智慧举例：（按时间顺序）

1、zr2023noip d2T3

题面：1e6次询问，每次给出n=xp^2，其中p是质数。求正整数a,b,c使得n=ab+ac+bc，或报告无解。开subtask。

老哥的想法（对代码瞪眼出来的，可能有误）：可以发现大多数情况都是有解的，并且可以手动构造，于是把能想到的比较好的手动构造方法放一起，并尝试a，b很小的情况。

开了subtask+多测也不要怕，后来发现每个sub就一个点。

结果：小sub挂了，80pts后三个sub都过了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
ll x,p,s;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&x,&p);
        if(x>=p){
            printf("%lld %lld %lld\n",p,x+1-p,p*p-p);
            continue;
        }
        if(p==2){
            puts("-1");
            continue;
        }
        s=1;
        while(x%4==0){
            x/=4;
            s*=2; 
        }
        if(x%2==1){
            ll a=1,b=1,c=(x*p*p-1)/2;
            printf("%lld %lld %lld\n",a*s,b*s,c*s);
            continue;
        }
        if(x==2){
            ll a=1,b=2,c=2*(p*p-1)/3;
            printf("%lld %lld %lld\n",a*s,b*s,c*s);
            continue;
        }
        bool vis=0;
        for(int i=1;i<=100;i++){
            for(int j=i;j<=100;j++){
                ll k=(x*p*p-i*j)/(i+j);
                if(k*(i+j)+i*j==x*p*p){
                    printf("%lld %lld %lld\n",i*s,j*s,k*s);
                    vis=1;
                    break;
                }
            }
            if(vis)break;
        }
    }
    return 0;
}

另一位老哥pollard-rho冲过了……代码比较【数据删除】，遂不放。

结论：我们要勇于突破信息学竞赛的天花板，天马行空，就是胜利✌️。

2.国庆某日。

题面：【数据删除】。输出yes或no。计算几何问题。多测，不开sub。

还是那位老哥。可以退火！自己设一个评判函数，变成最优化问题！

获得了55pts的高分。但凡写个数据分治就90了！老哥懊悔不已。

没有代码。

结论：小数据记得写数据分治，有的时候小数据反而容易挂。大多数有的时候出题人懒得多去卡卡，所以也不要怕多测。yes no问题也是可以退火的。

3.CSP前某日

题面：一张无向图，敌人基地在1号点，你要选另一个点，通过【数据删除】的规则计算其他点会被你还是敌人占领。求你最多占领多少点。不开sub。n=1e5.

我的思路：规则中可知你选的点的邻居都会被自己占领，并且之后有优势。所以就选度数最大的1000个点来算。我还拿1号店的前200个领居来算，实则没有一点用。

后面只寄了两个点。可是写的15pts树的数据分治竟然TLE。放OJ上测，十几ms。已经获得了75pts的全场mvp，够了。

没有代码。

结论：大概率是对的东西是值得去发现的。

4.CSP前某日

题面：在n×n的网格中【数据删除】。有一些操作，每次操作完回答yes no。开sub。n=100,n=700,n=5000,n=100000,q<=3e6还有一档有随机性质。

新的一位老哥的思路:网格很大的时候答案大概率是yes。可以，总司令！n<=100写数据分治。

结果:时限5s，删了一些点。没过700,过5000！过随机性质！（虽然随机性质也可以卡，但是出题人有dinner了）

令人忍俊不禁瞬间详见CSP2023游记。

不需要代码。

结论：我们要勇于总司令，出题人没准就是懒了。

5.zr附加赛day3，CF1267H。不开sub。

我的思路：如果一种灯只有一个，那跨过他两边的所有区间都不用再考虑了。所以每次新来一个在k级区间的灯时就给他颜色k，并将这个区间分成左右两个独立的k+1级区间。在随机数据下挺优秀的。

还能更好。一个元素来到一个新区间的时候先lazy在那里，等到第二个元素来了，看哪个元素更接近区间中心，就选哪个元素给颜色k，另一个下放到新分的左右区间去。

再好一点。加入随机化因子。从大到小改变更接近区间中心的元素给颜色k的概率，知道找到解为止。（测下来多了10pts）

结果：80pts的好成绩！排名最高zr比赛。

//promote human intelligence
//create another miracle
#include<bits/stdc++.h>
# define rep(i, j, k) for (int i = j; i <= k; ++i)
# define l(id) tr[id].l
# define r(id) tr[id].r
# define lson(id) tr[id].lson
# define rson(id) tr[id].rson
# define dep(id) tr[id].dep
# define now(id) tr[id].now
using namespace std;

int n, k, p[12105], cnt, d[12105], T;
struct segment
{
    int l, r, lson, rson, dep, now;
} tr[2000005];

void kai(int l, int r, int d)
{
    tr[++cnt] = (segment) {l, r, 0, 0, d, 0};
}

void add(int id, int u)
{
    if (lson(id)) {add(u < now(id) ? lson(id) : rson(id), u); return;}
    if (l(id) == r(id)) {now(id) = u; return;}
    if (!now(id)) {now(id) = u; return;}
    int gdps = (l(id) + r(id)) / 2;
    if ((abs(now(id) - gdps) > abs(u - gdps)) ^ (rand() % 1000 < T))
    {
        kai(l(id), u - 1, dep(id) + 1); lson(id) = cnt;
        kai(u + 1, r(id), dep(id) + 1); rson(id) = cnt;
        add(now(id) < u ? lson(id) : rson(id), now(id)); now(id) = u;
    }
    else
    {
        kai(l(id), now(id) - 1, dep(id) + 1); lson(id) = cnt;
        kai(now(id) + 1, r(id), dep(id) + 1); rson(id) = cnt;
        add(u < now(id) ? lson(id) : rson(id), u);
    }
}

bool solvehumanintelligence()
{
    rep(i, 1, cnt) tr[i] = {0, 0, 0, 0, 0, 0};
    tr[cnt = 1] = {1, n, 0, 0, 1, 0};
    rep(i, 1, n) {add(1, p[i]); if (cnt >= 1900000) return false;}
    rep(i, 1, cnt) if (now(i)) {if (dep(i) > k) return false; d[now(i)] = dep(i);}
    rep(i, 1, n) cout << d[i] << ' '; return true;
}

void solvehumanhumanintelligence()
{
    cnt = 0;
    for (T = 1; T <= 500; ++T) if (solvehumanintelligence()) {return;}
}

int main()
{
    srand(time(NULL));
//  freopen("a.in", "r", stdin);
//  freopen("a.out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> n >> k;
    rep(i, 1, n) cin >> p[i];
//  random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);random_shuffle(p + 1, p + n + 1);
    if (!solvehumanintelligence()) solvehumanhumanintelligence();
    return 0;
}

结论：寻找随机数据下的好方法，也是一种策略。一般情况下很多都是随机数据，不要以为每个都会卡。

祝所有oier智慧出奇迹，将西西弗数据打入信息学竞赛的下水管，取得胜利✌️✌️✌️！