题解 P2216 【[HAOI2007]理想的正方形】

Social_Zhao · 2019-09-13 10:23:05 · 题解

前言

乱搞了一上午，那么让我来乱搞一篇题解吧

这题我本来是用单调队列过的，但是随手翻了翻题解，看见一个大佬拿随机乱搞过了，于是猛然想起这是一个多峰的函数：

f(x, y) = max\{w[i][j]\} - min\{w[i][j]\}

其中x∈[n,a], y∈[n,b], i∈[x-n+1,x], j∈[y-n+1]

可不可以退他一火呢？

所以我们来用玄学算法做一做。

严正声明

本题解非正解，而且很慢，甚至可以说仅供观赏。所以如果您把这个代码交了上去A不了，emm。

但是为了避免这篇题解过于无意义，我把我写的单调队列优化DP的思路也写在这里吧。

单调队列做法

思路

如果不会单调队列，请移步P1886 滑动窗口。

这道题就相当于是一个二维的滑动窗口。我们首先设fmax[i][j]表示第i行，这一行到j，关键字是原矩阵的最大值，最小值同理。

然后我们设gmax[i][j]为第i列到第j个数，关键字是fmax数组的最大值，最小值同理。

用OI队列维护。

注意

第二次的循环变量要反着写。

代码

说了这么多有点抽象，来看一下代码。（那一天和同桌比谁的马蜂毒瘤，于是写了一个NOIP初赛CSP第一轮的代码）

#include "iostream"
#include "cstdio"
#include "cstring"

const int N = 1005;
int a, b, n;
int w[N][N];
int fmax[N][N], fmin[N][N];
int gmax[N][N], gmin[N][N];
int minn[10005], h1 = 0, t1 = 0;
int maxn[10005], h2 = 0, t2 = 0;

int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    std::cin >> a >> b >> n;
    for (int _ = 1; _ <= a; _++) {
        for (int __ = 1; __ <= b; __++) {
            std::cin >> w[_][__];
        }
    } 
    for (int _ = 1; _ <= a; _++) { //横着DP
        memset(minn, 0, sizeof(minn)); h1 = 1; t1 = 0; //注意每次都要清空
        memset(maxn, 0, sizeof(maxn)); h2 = 1; t2 = 0;
        for (int __ = 1; __ <= b; __++) {
            while (minn[h1] < __ - n + 1 && h1 <= t1) h1++;
            while (maxn[h2] < __ - n + 1 && h2 <= t2) h2++; //老年选手退役
            while (w[_][minn[t1]] >= w[_][__] && h1 <= t1) t1--; 
            while (w[_][maxn[t2]] <= w[_][__] && h2 <= t2) t2--; //如果一个人比你小还比你强，那你就打不过他了
            minn[++t1] = __;
            maxn[++t2] = __; //新选手加入OI队列
            fmin[_][__] = w[_][minn[h1]];
            fmax[_][__] = w[_][maxn[h2]]; //最强选手进省队
        }
    }
    for (int _ = 1; _ <= b; _++) { //竖着DP
        memset(minn, 0, sizeof(minn)); h1 = 1; t1 = 0;
        memset(maxn, 0, sizeof(maxn)); h2 = 1; t2 = 0; //注意每次都要清空
        for (int __ = 1; __ <= a; __++) {
            while (minn[h1] < __ - n + 1 && h1 <= t1) h1++;
            while (maxn[h2] < __ - n + 1 && h2 <= t2) h2++; //老年选手退役
            while (fmin[minn[t1]][_] >= fmin[__][_] && h1 <= t1) t1--;
            while (fmax[maxn[t2]][_] <= fmax[__][_] && h2 <= t2) t2--; //如果一个人比你小还比你强，那你就打不过他了
            minn[++t1] = __;
            maxn[++t2] = __; //新选手加入OI队列
            gmin[__][_] = fmin[minn[h1]][_];
            gmax[__][_] = fmax[maxn[h2]][_]; //最强选手进省队
        }
    }
    int ZnS = 0x3f3f3f3f; //纪念一个大佬
    for(int _ = n; _ <= a; _++) {
        for(int __ = n; __ <= b; __++) {
            ZnS = std::min(ZnS, gmax[_][__] - gmin[_][__]);
        }
    }
    std::cout << ZnS << std::endl;
}

下面进入正题。

模拟退火做法

思路

如果不会模拟退火，请移步1337 [JSOI2004]平衡点 / 吊打XXX

我们这里每次生成一个向量，这个向量的长度和温度有关，即

int X = (x + ((rand() << 1) - RAND_MAX) % (int)round(T * 10)) % a + 1;
int Y = (y + ((rand() << 1) - RAND_MAX) % (int)round(T * 10)) % b + 1;
if(X < n || X > a || Y < n || Y > b) {T *= delta; continue;} 
//这步一定要乘上delta，不然会由于脸黑陷入黑洞出不来。
//（这个随机数并不是完全随机，而是取决于它的种子的伪随机数）

然后用这两个新的点进行模拟计算，求出增量

double now = calc(X, Y);
double Delta = now - ans;

如果Delta小于0，那么说明这是一个更优解，接受，其他情况以一个和温度、增量大小有关的概率接受它，温度越小、增量越大概率越小

if(Delta < 0) {
    ans = now;
    x = X;
    y = Y;
    ansx = x;
    ansy = Y;
}
else if(exp(-Delta / T) * RAND_MAX > rand()) {
    x = X;
    y = Y;
}
T *= delta;

然后再时间允许的范围内尽可能多的跑模拟退火。

注意

下面的这份代码使用的随机种子是time(NULL)，然后它在二〇一九年九月十三日九时三十九分二十二秒不知道多少毫秒产生了可以AC此题的种子。此外平均得分为90左右。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1005;
int a, b, n;
int w[N][N];

const double MAX_TIME = 0.9;
const double delta = 0.996;
int ans = INT_MAX;
int ansx, ansy;

int calc(int x, int y)
{
    int minn = INT_MAX;
    int maxn = -INT_MAX;
    for(int i = x - n + 1; i <= x; i++) {
        for(int j = y - n + 1; j <= y; j++) {
            minn = min(minn, w[i][j]);
            maxn = max(maxn, w[i][j]);
        }
    }
    return maxn - minn;
}

void Simulate_Anneal()
{
    double T = max(a, b);
    int x = ansx, y = ansy;
    while(T > 0.1) {
        int X = (x + ((rand() << 1) - RAND_MAX) % (int)round(T * 10)) % a + 1;
        int Y = (y + ((rand() << 1) - RAND_MAX) % (int)round(T * 10)) % b + 1;
        //cout << T << " " << X << " " << Y << " : " << endl;
        //system("pause");
        if(X < n || X > a || Y < n || Y > b) {T *= delta; continue;}
        double now = calc(X, Y);
        double Delta = now - ans;
        //cout << T << " " << now << endl;
        if(Delta < 0) {
            ans = now;
            x = X;
            y = Y;
            ansx = x;
            ansy = Y;
        }
        else if(exp(-Delta / T) * RAND_MAX > rand()) {
            x = X;
            y = Y;
        }
        T *= delta;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    cin >> a >> b >> n;
    for(int i = 1; i <= a; i++) 
        for(int j = 1; j <= b; j++) 
            cin >> w[i][j];
    ansx = ansy = n;    
    while ((double)clock() / CLOCKS_PER_SEC * 1.0 < MAX_TIME) Simulate_Anneal();
    cout << ans << endl;
}

总结

在这种题，如果不会正解，可以考虑随机算法，骗到分就跑。

我也该跑了。