\(\text{luogu-14148}\)
构造一个长度为 \(n\) 的排列 \(p\)，满足 \(\bigoplus\limits_{i=1}^n (p_i+k\times i)=0\)。
其中 \(\oplus\) 表示按位异或。无解输出 -1。
\(1\le n\le 10^6\)，\(1\le k\le 7\)。
考虑随机化。
初始排列为 \(1 \sim n\)，然后随机交换两个值，直到异或和为 \(0\)。
\(1s\) 内大概可以交换 \(3 \times 10^7\) 次，每次交换大概是 \(O(1)\) 的。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<ctime>
#include<random>
using namespace std;
#define MAXN 1000005long long read() {long long x = 0, f = 1;char c = getchar();while(c > 57 || c < 48) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); }return x * f;
}long long n, k, a[MAXN], res;
mt19937 rnd(time(0));int main() {n = read(), k = read();for(int i = 1; i <= n; i ++) a[i] = i, res ^= (a[i] + k * i);for(int i = 1; i <= 2e7; i ++) {if(!res) {for(int j = 1; j <= n; j ++) cout << a[j] << " ";cout << "\n"; return 0;}long long x = rnd() % n + 1, y = rnd() % n + 1;res ^= (a[x] + k * x), res ^= (a[y] + k * y);swap(a[x], a[y]);res ^= (a[x] + k * x), res ^= (a[y] + k * y);}cout << "-1\n";return 0;
}
\(\text{luogu-1559}\)
羽毛球队有男女运动员各 \(n\) 人。给定 \(2\) 个 \(n \times n\) 矩阵 \(P\) 和 \(Q\)。\(P_{i,j}\) 是男运动员 \(i\) 和女运动员 \(j\) 配对组成混合双打的男运动员竞赛优势；\(Q_{i,j}\) 是女运动员 \(i\) 和男运动员 \(j\) 配合的女运动员竞赛优势。
但是，由于技术配合和心理状态等各种因素影响，\(P_{i,j}\) 不一定等于 \(Q_{j,i}\)。男运动员 \(i\) 和女运动员 \(j\) 配对组成混合双打的男女双方竞赛优势为 \(P_{i,j} \times Q_{j,i}\)。
现在，请你设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。
\(1 \le n \le 20\)。
数据范围这么小，貌似随便随机化一下就能过？
实际上并不是这样，有两个点过不了。
考虑模拟退火：
- 一次交换若更优，则更新答案。
- 若交换不优，则概率接受答案。
直接跑极限 \(0.9s\) 就好了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<random>
using namespace std;
#define MAXN 25
#define MOD 1000000000int read() {int x = 0, f = 1;char c = getchar();while(c > 57 || c < 48) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); }return x * f;
}int n, a[MAXN][MAXN], b[MAXN][MAXN], p[MAXN], res, ans;
mt19937 rnd(time(0));void sp(int x, int y) {res -= a[p[x]][x] * b[x][p[x]], res -= a[p[y]][y] * b[y][p[y]];swap(p[x], p[y]);res += a[p[x]][x] * b[x][p[x]], res += a[p[y]][y] * b[y][p[y]];return;
}int main() {n = read();for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) a[i][j] = read();for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) b[i][j] = read();for(int i = 1; i <= n; i ++) p[i] = i, res += a[i][i] * b[i][i];ans = res;while(clock() < 0.95 * CLOCKS_PER_SEC) {res = 0; double T = 5000;for(int i = 1; i <= n; i ++) p[i] = i, res += a[i][i] * b[i][i];while(T > 1e-12) {int x = rnd() % n + 1, y = rnd() % n + 1, t = res;sp(x, y);if(t < res) ans = max(ans, res);else if(exp((res - t) / T) * MOD < rnd() % MOD) sp(x, y);T *= 0.985; }}cout << ans << "\n";return 0;
}