OI笔记 | 杂类模板
字符串模板先放这，因为现在只学了一个，之后如果还有学的话单独开。
KMP
给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l, r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。
现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。
定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。
对于 $s_2$，你还需要求出对于其每个前缀 $s’$ 的最长 border $t’$ 的长度。
题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 10;
char a[MAX_N], b[MAX_N];
int p[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
scanf("%s%s", a + 1, b + 1);
int la = strlen(a + 1), lb = strlen(b + 1), j = 0;
for(int i = 2; i <= lb; i++) {
while(j > 0 && b[i] != b[j + 1]) j = p[j];
if(b[i] == b[j + 1]) j++;
p[i] = j;
}
j = 0;
for(int i = 1; i <= la; i++) {
while(j > 0 && a[i] != b[j + 1]) j = p[j];
if(a[i] == b[j + 1]) j++;
if(j == lb) write(i - lb + 1), putchar('\n'), j = p[j];
}
for(int i = 1; i <= lb; i++) write(p[i]), putchar(' ');
return 0;
}
康托展开
可以用树状数组来维护比 $a_i$ 小的数的数量。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 10, MOD = 998244353;
ll a[MAX_N], tree[MAX_N], fac[MAX_N], n, ans;
inline ll read() {...}
inline void write(ll x) {...}
inline int lowbit(int x) {return x & -x;}
inline void update(int pos, int k) {for(int i = pos; i <= n; i += lowbit(i)) tree[i] += k;}
inline int query(int pos) {
int ret = 0;
for(int i = pos; i >= 1; i -= lowbit(i)) ret += tree[i];
return ret;
}
int main() {
n = read();
fac[0] = 1;
for(int i = 1; i <= n; i++) {
a[i] = read();
update(a[i], 1);
fac[i] = (fac[i - 1] * i) % MOD;
}
for(int i = 1; i <= n; i++) {
(ans += query(a[i] - 1) * fac[n - i] % MOD) %= MOD;
update(a[i], -1);
}
write(ans + 1);
return 0;
}
模拟退火
我们直接来看一道板子题「JSOI2016」炸弹攻击。
游戏地图可以简单认为是一个二维平面。JYY 建造了 $N$ 个建筑，每个建筑都是一个圆，其中第 $i$ 个建筑的圆心位于 $(x_i,y_i)$ 且半径为 $r_i$。地图上一共有 $M$ 个敌人，一个敌人可以近似看成一个平面上的点，其中第 $i$ 个敌人位于 $(p_i,q_i)$。JYY 可以使用一枚可以设置半径的炸弹，可以设置一个不超过 $R$ 的范围，然后选择平面上的一个点引爆，范围内的所有敌人全部消灭。
当然，由于炸弹威力巨大，如果爆炸范围接触到 JYY 的建筑，那么 JYY 的建筑也会受到损伤。（注：如果炸弹的爆炸范围仅接触到了 JYY 建筑的边界，则不会对 JYY 的建筑造成损伤；如果敌人出现在了爆炸范围的边界，则该敌人被消灭）JYY 可以自由控制炸弹的爆炸地点和爆炸半径。作为一个保守的玩家，他希望在保证自己建筑毫发无损的情况下，消灭尽量多的敌人。
对于 $100\%$ 的数据，满足 $0 \le N \le 10, 0 \lt M \le 10^3 , 1 \le R, r_i \le 2\times 10^4 ,\lvert p_i\rvert ,\lvert q_i\rvert,\lvert x_i\rvert ,\lvert y_i\rvert \le 2\times 10^4$。
题解
一道很好的模拟退火题。
首先是初温的设置，不能设置得太大。由于我们使用 nx = ansx + t * (rand() * 2 - RAND_MAX) 来生成新解，如果初温太大，容易偏移到没有任何敌人的地方去，所以综合考虑数据范围并多次调参，我们把它设为 7e3。
降温的设置个人感觉影响没有很大，这里设为玄学的 0.996633。末温同理，这里设为 1e-10。
答案的计算，我们先找到最大的不与建筑接触的 $r$，然后统计有多少个敌人在当前的圆内。
这样还不是很稳，这是因为在平面上的敌人可能是很稀疏的，测试发现模拟退火途中有大量的答案 $cnt=0$。第一篇题解告诉了我们一种方式，即在返回函数中加入因素：离最近的敌人还差多远。设 $m=\min\limits_{i=1}^M (d_i-r)$，其中 $d_i$ 为当前坐标到第 $i$ 个敌人的距离， $r$ 为当前选择的半径，则模拟退火的能量 $e=-k_1\cdot m+k_2\cdot cnt$，其中 $k_1,k_2$ 为常数，这里设为 $13.14$ 和 $5.20$（一些玄学数字）。这样如果距离越远，答案越劣；摧毁的敌人越多，答案越优。
再加上卡时，这题出解的概率就很高了。事实上，在洛谷上调完参后我直接交到 LOJ 上也能一遍过，可见比较稳定。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 35;
const double BEGIN = 7e3, DOWN = 0.996633, MIN_T = 1e-10;
int n, m, R, ans, sumx, sumy, nans;
double ansx, ansy, anse;
inline bool check() {return (double)clock() / CLOCKS_PER_SEC > 0.97;}
struct bd {int x, y, r;} bds[22];
struct enm {int x, y;} e[1010];
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
double dis(double x, double y, double xx, double yy) {return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));}
double cal(double x, double y) {
double r = R, mn = 1e18;
nans = 0;
for(int i = 1; i <= n; i++)
r = min(r, dis(x, y, bds[i].x, bds[i].y) - bds[i].r);
for(int i = 1; i <= m; i++) {
double d = dis(x, y, e[i].x, e[i].y);
if(d <= r) nans++;
mn = min(mn, d - r);
}
return -max(0.0, mn) * 13.14 + nans * 5.20;
}
void SA() {
double t = BEGIN, nx = 0, ny = 0;
while(t > MIN_T) {
if(check()) return;
nx = ansx + t * (rand() * 2 - RAND_MAX), ny = ansy + t * (rand() * 2 - RAND_MAX);
double ne = cal(nx, ny);
ans = max(ans, nans);
int delta = ne - anse;
if(delta > 0 || exp(delta / t) * RAND_MAX > rand()) ansx = nx, ansy = ny, anse = ne;
t *= DOWN;
}
}
int main() {
srand(19260817);
n = read(), m = read(), R = read();
for(int i = 1; i <= n; i++)
bds[i].x = read(), bds[i].y = read(), bds[i].r = read();
for(int i = 1; i <= m; i++)
e[i].x = read(), e[i].y = read(), sumx += e[i].x, sumy += e[i].y;
ansx = (double)sumx / m, ansy = (double)sumy / m;
anse = cal(ansx, ansy);
ans = nans;
while(!check())
SA(), srand(rand());
write(ans);
return 0;
}
离线算法
♥