题解：P9591 「PFLOI R1」PFL 变换

不想说话真君 · 2025-10-08 22:58:26 · 题解

第一发自己写的紫，写题解庆祝一下。

前置知识

模拟退火，随机化算法。

关于模拟退火

大概思想是若当前答案不劣，则接受此答案，若当前答案更劣，则有一定几率接受此答案，否则不接受。

关于当前答案更劣时接受答案的几率为（k 为当前答案，ans 为最优答案，r 为一个随机数，mr 为随机数最大值，t 为当前温度）：

代码形式：

abs(exp((ans - abs(mmm - su)) / t)) < (double)rand() / (double)RAND_MAX

exp 是啥我也不知道，建议自行百度。

原理好像是我们要让高温时接受劣解概率高，温度越低，接受劣解的概率越低，逐渐收敛至稳定解。

思路

我们可以用近似与 分金币 的思路，将要吃的放左边，不吃的放右边，两边抽一个互换即可。

细节

参数要慢慢调，如果你不想调就看我参数试试，记得特判 n 和 m 相等，区间异或可以先将序列第 1 至 m 取异或，然后互换时将两点都异或一下就行了，因为两个相等的数异或后为 0。

代码

#include <bits/stdc++.h>
using namespace std;
int n, a[1001000], ans = 0x3f3f3f3f;
int sum = 0;
int m;
bool flag = 0;
inline void SA()
{
    int su = pow(2, (int)log2(n) + 1) - 1;
    double beg = 10000, end = 1e-11, tt = 0.996;
    int mmm = 0;
    for (int i = 1; i <= m; ++i)
        mmm ^= a[i];
    for (double t = beg; t > end; t *= tt)
    {
        int x = (rand() % m) + 1, y = (n != m ? (rand() % (n - m)) : 0) + 1 + m;
        mmm ^= a[x];
        mmm ^= a[y];
        swap(a[x], a[y]);
        if (mmm < su)
            ans = mmm;
        else if (mmm > su && abs(exp((ans - abs(mmm - su)) / t)) < (double)rand() / (double)RAND_MAX){
            swap(a[x], a[y]);
            mmm ^= a[x] ^ a[y];
        }
        else if (mmm == su)
        {
            for (int i = 1; i <= m; i++)
            {
                cout << a[i] << " ";
            }
            flag = 1;
            cout << endl;
            break;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    srand((unsigned)time(NULL));
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        sum = 0;
        for (int i = 1; i <= n; i++)
        {
            a[i] = i;
            sum ^= i;
        }
        cin >> m;
        if (n == m)
        {
            if (pow(2, (int)log2(n) + 1) - 1 == sum)
            {
                for (int i = 1; i <= n; i++)
                    cout << a[i] << " ";
                cout << endl;
            }
            else
            {
                cout << -1 << endl;
            }
            continue;
        }
        int rt = 0;
        if(n < 10000) rt = 50;
        else rt = 110;
        for (int k = 0; k < rt; k++)
        {
            SA();
            if (flag == 1)
            {
                break;
            }
        }
        if (flag == 0)
        {
            cout << -1 << endl;
        }
        ans = 0x3f3f3f3f;
        flag = 0;
    }
    return 0;
}

要多交几次，毕竟是随机化算法。