退役记坑了好久了……但还是不想写

然后这几天想玩RNN,于是预处理了一下自己BZOJ上的AC代码:

  1. 删去除 C/C++ 的其他语言
  2. 删去多余空行
  3. 将题目名称变为注释

于是,你可以点这里下载我的BZOJ AC代码。

题目描述

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

输入格式

两行,两个字符串 \(s_1,s_2\),长度分别为\(n_1, n_2\)。字符串中只有小写字母。

输出格式

输出一个整数表示答案

样例

样例输入

aabb
bbaa

样例输出

10

数据范围与提示

\(1 \leq n_1, n_2 \leq 200000\)

内存限制: 256 MiB 时间限制: 1000 ms


传送门:

https://loj.ac/problem/2064 或 http://www.lydsy.com/JudgeOnline/problem.php?id=4566


网上大部分题解都是关于SAM的……

然而我又用SA水过了QAQ

从两个串中分别取出一个后缀,对答案的贡献是他们的\(\mathrm{LCP}\)的长度;并且枚举所有后缀就是枚举了所有情况,因为实质上我们枚举的是相同子串的开头。

这样,如果将两个串加入位置在\(\mathrm{split}\)的分隔符拼接在一起变为\(S\),答案变为了$$
\sum_{i = 1} ^ {\mathrm{split} – 1} \sum_{j = \mathrm{split} + 1}^{|S|} \mathrm{LCP}(i, j)
$$转化问题到后缀数组上,那么问题就转化为分别统计对于每个\(h_i\),当他作为最小值即\(\mathrm{LCP}\)时,对答案做贡献的次数\(\mathrm{cnt}_i\)。

如果只考虑一个点,那么也就是统计经过它的符合条件的区间数。这个点左右合法区间端点必然是一个连续的区间\([L_i, R_i]\),为了避免重复我们定义\(L_i\)为最小的使得\(\mathrm{min}(h_{[L_i, i)}) \gt h_i\)的值,\(R_i\)为最小的使得\(\mathrm{min}(h_{[i, R_i]}) \geq h_i\)的值,有$$
\mathrm{cnt}_i = \sum_{l = L_i} ^ {i – 1} \sum_{r = i} ^ {R_i} h_i \cdot [(\mathrm{sa}_l < \mathrm{split} \ \mathrm{and}\ \mathrm{sa}_r > \mathrm{split}) \ \mathrm{or}\ (\mathrm{sa}_l > \mathrm{split} \ \mathrm{and}\ \mathrm{sa}_r < \mathrm{split})]
$$两个\(\sum\)可以用乘法原理和前缀和\(O(1)\)求出,剩下的问题就是求\(L_i\)和\(R_i\)了,这是一个单调栈的经典问题。

所以我们就在求出后缀数组后,\(O(N)\)解决了这道题。

/* Never Say Die */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <bitset>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int, int> pii;
#define mp(a, b) make_pair(a, b)
#define fir first
#define sec second
inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}
int ch = 0;
template <class T> inline void read(T &a) {
	bool f = 0; a = 0;
	while (ch < '0' || ch > '9') {if (ch == '-') f = 1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {a = a * 10 + ch - '0'; ch = getchar();}
	if (f) a = -a;
}

#define MAXN 400010

void Sort(int in[], int out[], int p[], int n, int m) {
	static int P[MAXN];
	for (int i = 1; i <= m; i++) P[i] = 0;
	for (int i = 1; i <= n; i++) P[in[i]]++;
	for (int i = 2; i <= m; i++) P[i] += P[i - 1];
	for (int i = n; i; i--) out[P[in[p[i]]]--] = p[i];
}

char s[MAXN];
int sa[MAXN], rk[MAXN], h[MAXN];

int n, l1;
void getsa() {
	static int t1[MAXN], t2[MAXN], *x = t1, *y = t2;
	int m = 127;
	for (int i = 1; i <= n; i++) x[i] = s[i], y[i] = i;
	Sort(x, sa, y, n, m);
	for (int j = 1, i, k = 0; k < n; m = k, j <<= 1) {
		for (i = n - j + 1, k = 0; i <= n; i++) y[++k] = i;
		for (i = 1; i <= n; i++) if (sa[i] > j) y[++k] = sa[i] - j;
		Sort(x, sa, y, n, m);
		for (swap(x, y), i = 2, x[sa[1]] = k = 1; i <= n; i++) {
			x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k : ++k;
		}
	}
	for (int i = 1; i <= n; i++) rk[sa[i]] = i;
	for (int i = 1, k = 0; i <= n; h[rk[i++]] = k) {
		k -= !!k;
		for (int j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++);
	}
}

int sta[MAXN], p[MAXN], L[MAXN], R[MAXN], s1[MAXN], s2[MAXN];

void work() {
	int top = 0; sta[0] = -1;
	for (int i = 1; i <= n; i++) {
		while (sta[top] >= h[i]) {
			R[p[top]] = i - 1;
			top--;
		}
		L[i] = p[top] + 1;
		sta[++top] = h[i], p[top] = i;
	}
	while (top) R[p[top--]] = n;
	for (int i = 1; i <= n; i++) s1[i] = s1[i - 1] + (sa[i] < l1);
	for (int i = 1; i <= n; i++) s2[i] = s2[i - 1] + (sa[i] > l1);
	LL ans = 0;
	for (int i = 2; i <= n; i++) {
		ans += (LL)h[i] * ((s2[i - 1] - s2[L[i] - 2]) * (s1[R[i]] - s1[i - 1]) + (s1[i - 1] - s1[L[i] - 2]) * (s2[R[i]] - s2[i - 1]));
	}
	printf("%lld\n", ans);
}

int main() {
	scanf("%s", s + 1);
	n = (int)strlen(s + 1);
	s[l1 = ++n] = '|';
	scanf("%s", s + n + 1);
	n += (int)strlen(s + n + 1);
	getsa();
	work();
	return 0;
}

QAQ这么搞我什么时候才能学会SAM啊……

题目描述

对于一个给定长度为 \(N\) 的字符串,求它的第 \(K\) 小子串是什么。

输入格式

第一行是一个仅由小写英文字母构成的字符串 \(S\)。

第二行为两个整数 \(T\)和 \(K\),\(T\) 为 0 则表示不同位置的相同子串算作一个。\(T\) 为 1 则表示不同位置的相同子串算作多个。\(K\) 的意义如题所述。

输出格式

输出仅一行,为一个数字串,为第 \(K\) 小的子串。如果子串数目不足 \(K\) 个,则输出 -1。

样例输入

aabc
0 3

样例输出

aab

数据范围与提示

\(N \leq 5 \times 10​ ^ 5​​, T \lt 2, K \leq 10 ^ 9 \)​​

内存限制: 256 MiB 时间限制: 1000 ms


传送门:

https://loj.ac/problem/2102http://www.lydsy.com/JudgeOnline/problem.php?id=3998


首先这道题是一个后缀自动机模板题……网上关于SAM的题解又多又好,而且这道题也是我学习SAM的动力。

不过直到学习了SAM重新审视我当时写错的SA代码,突然意识到这道题可以用SA完成,虽然常数大,但是复杂度(\(O(N)\))比SAM(\(O(N |\alpha|)\))优秀,跑得很快。

关于SAM的做法不再赘述了,我们这里考虑以SA的方式来思考这道题。

以下,\(\mathrm{sa}_i\)表示字符串\(S\)的后缀从小到大排序后开始位置,\(\mathrm{len}_i\)表示排名为\(i\)的后缀的长度(\(|S| – \mathrm{sa}_i + 1\)),\(h_i\)表示第\(i\)大后缀与第\(i – 1\)大后缀的最长公共前缀(也叫\(\mathrm{LCP}\)或者\(\mathrm{height}\)),其中\(h_1 = 0\)。

当\(T = 0\)时,我们需要统计的是本质不同的字符串。显然,对于第\(i\)大的后缀,对答案的贡献只有\(\mathrm{len}_i – h_i\),因为前一个串相同的部分已经被算过答案了,然后扫一遍就好了,复杂度\(O(N)\)。

当\(T = 1\)时,我们不仅仅需要知道本质不同的字符串的个数,还需要知道依次出现了多少次以确定答案。

首先,一个非常直观的思路是,对于新出现的每个本质不同的字符串,如果长度在\([h_i, h_{i+1}]\)范围内,可以在\(h\)数组上二分 + RMQ得到出现次数;对于\(h\)数组外的部分只会出现一次,直接统计即可。

但是这样做显然是不优秀的。我们知道求\(h\)数组时我们利用了“原串相邻的两个后缀在对应位置的\(h\)的值,靠后位置的最多比靠前位置的\(h\)小\(1\)”这个结论,然而这对\(h\)数组是不适用的。这里,\(\sum_{i = 2} ^ n max(h_i – h_{i – 1}, 0)\)是可以被卡到\(O(N ^ 2)\)级别的。卡法也很简单,我们构造一个类似于abc...xyzabc...的字符串就可以把\(\sum_{i = 2} ^ n max(h_i – h_{i – 1}, 0)\)卡到\(O(N |\alpha|)\)级别,我们可以把几个字符看做一个字符,最终就能达到\(O(N ^ 2)\)的效果了。

于是看起来,\(T = 1\)时复杂度变为了\(O(\mathrm{min}(K, N ^ 2) \log N)\),显然这个复杂度是无法接受的。

那么我们就弃疗了?不。我最开始想卡这个\(O(\mathrm{min}(K, N ^ 2) \log N)\)暴力……然而发现卡不掉,就是因为我在分析时没有意识到的情况下加了一个非常简单的优化。

考虑优化。事实上我们发现,对于一个当前一个新的长度为\(\mathrm{Len}\)二分的过程结束后会得到一个值\(\mathrm{Max}\),表示出现了当前次数的字符串长度的最大值。这两个值表明,当前位置上字符串长度为\([\mathrm{Len},\mathrm{Max}]\),均出现了同样次数。那么我们将这一部分答案一并计算,最后将寻找下一个字符串从\(\mathrm{Len}++\)变为\(\mathrm{Len} = \mathrm{Max} + 1\)。

这么做,将这一步时间复杂度变为了\(O(N \log N)\);将二分替换为单调栈,这一步的时间复杂度变为\(O(N)\)。

其实,这个复杂度证明也很简单……看起来就像最大矩形面积,如果出现次数变少,一定是之后某一个位置上的高度非常小“卡住了”。因为我们求的是本质不同的字符串数量,所以对于\(h\)数组的每个元素,最多会“卡”前面的连续段一次。这样如果采用二分自然就是\(O(N \log N)\)了。发现这个性质后其实可以用单调栈,每次弹出之前的数时,用链表/vector插入出现次数到前面所弹出的位置上;因为最多弹\(O(N)\)次,所以插入的数也只有\(O(N)\)个。

由于求后缀数组也是可以\(O(N)\)的,所以总复杂度也可以是\(O(N)\)的了。这样,我们就在\(O(N)\)的时间复杂度内解决了本题;相比起后缀自动机,与字符集大小无关是这个做法更优越的一点。(由于我不会DC3我总复杂度还是只能\(O(N \log N)\) TAT但是还是跑得速度不慢啦)

二分RMQ代码如下:(这道题在BZOJ上需要交换st数组下标来卡常TAT)

/* Never Say Die */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <bitset>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int, int> pii;
#define mp(a, b) make_pair(a, b)
#define fir first
#define sec second
inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}
int ch = 0;
template <class T> inline void read(T &a) {
	bool f = 0; a = 0;
	while (ch < '0' || ch > '9') {if (ch == '-') f = 1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {a = a * 10 + ch - '0'; ch = getchar();}
	if (f) a = -a;
}

#define MAXN 500319

char s[MAXN];

int n, T, K;

void Sort(int in[], int out[], int p[], int m) {
	static int P[MAXN]; register int i;
	for (i = 1; i <= m; i++) P[i] = 0;
	for (i = 1; i <= n; i++) P[in[i]]++;
	for (i = 2; i <= m; i++) P[i] += P[i - 1];
	for (i = n; i; i--) out[P[in[p[i]]]--] = p[i];
}

int sa[MAXN], rk[MAXN], h[MAXN];
int Min[20][MAXN], Log[MAXN];
void getsa() {
	int m = 26;
	static int t1[MAXN], t2[MAXN], *x = t1, *y = t2;
	for (int i = 1; i <= n; i++) x[i] = s[i] - 'a' + 1, y[i] = i;
	Sort(x, sa, y, m);
	for (int j = 1, k = 0, i; k < n; m = k, j <<= 1) {
		for (k = 0, i = n - j + 1; i <= n; i++) y[++k] = i;
		for (i = 1; i <= n; i++) if (sa[i] > j) y[++k] = sa[i] - j;
		Sort(x, sa, y, m);
		for (swap(x, y), i = 2, k = x[sa[1]] = 1; i <= n; i++) {
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) ? k : ++k;
		}
	}
	for (int i = 1; i <= n; i++) rk[sa[i]] = i;
	for (int i = 1, k = 0; i <= n; h[rk[i++]] = k) {
		k -= !!k;
		for (int j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++);
	}
	Log[0] = -1;
	for (int i = 1; i <= n; i++) Log[i] = Log[i >> 1] + 1;
	for (int i = 1; i <= n; i++) Min[0][i] = h[i];
	for (int k = 1; k <= Log[n]; k++) {
		for (int i = 1, d = 1 << (k - 1), j = n - (d << 1) + 1; i <= j; i++) {
			Min[k][i] = min(Min[k - 1][i], Min[k - 1][i + d]);
		}
	}
}

void work1() {
	int tot = 0;
	for (int i = 1, j; i <= n; i++) {
		for (j = h[i] + 1; j <= h[i + 1]; j++) {
			int x = i, mi = h[i + 1];
			for (int k = Log[n - i + 1]; ~k; k--) if (Min[k][x + 1] >= j) mi = min(mi, Min[k][x + 1]), x += 1 << k;
			int d = x - i + 1, cnt = mi - j + 1;
			if (K - tot - 1 <= (LL)cnt * d) {
				j += (K - tot - 1) / d;
				for (int l = 0; l < j; l++) putchar(s[sa[i] + l]);
				putchar('\n');
				return;
			}
			tot += d * cnt;
			j = mi;
		}
		int dev = n - sa[i] - j + 2;
		if (tot + dev >= K) {
			int d = int(K - tot + j - 1);
			for (j = 0; j < d; j++) putchar(s[sa[i] + j]);
			putchar('\n');
			return;
		}
		tot += dev;
	}
	puts("-1");
}

void work0() {
	int tot = 0;
	for (int i = 1; i <= n; i++) {
		int dev = n - sa[i] - h[i] + 1;
		if (tot + dev >= K) {
			int d = int(K - tot + h[i]);
			for (int j = 0; j < d; j++) putchar(s[sa[i] + j]);
			putchar('\n');
			return;
		}
		tot += dev;
	}
	puts("-1");
}

int main() {
	scanf("%s", s + 1);
	read(T); read(K);
	n = (int)strlen(s + 1);
	getsa();
	if (T) work1();
	else work0();
	return 0;
}

单调栈代码如下:

/* Never Say Die */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <bitset>
#include <list>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int, int> pii;
#define mp(a, b) make_pair(a, b)
#define fir first
#define sec second
inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}
int ch = 0;
template <class T> inline void read(T &a) {
	bool f = 0; a = 0;
	while (ch < '0' || ch > '9') {if (ch == '-') f = 1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {a = a * 10 + ch - '0'; ch = getchar();}
	if (f) a = -a;
}

#define MAXN 500319

char s[MAXN];

int n, T, K;

void Sort(int in[], int out[], int p[], int m) {
	static int P[MAXN]; register int i;
	for (i = 1; i <= m; i++) P[i] = 0;
	for (i = 1; i <= n; i++) P[in[i]]++;
	for (i = 2; i <= m; i++) P[i] += P[i - 1];
	for (i = n; i; i--) out[P[in[p[i]]]--] = p[i];
}

int sa[MAXN], rk[MAXN], h[MAXN];

void getsa() {
	int m = 26;
	static int t1[MAXN], t2[MAXN], *x = t1, *y = t2;
	for (int i = 1; i <= n; i++) x[i] = s[i] - 'a' + 1, y[i] = i;
	Sort(x, sa, y, m);
	for (int j = 1, k = 0, i; k < n; m = k, j <<= 1) {
		for (k = 0, i = n - j + 1; i <= n; i++) y[++k] = i;
		for (i = 1; i <= n; i++) if (sa[i] > j) y[++k] = sa[i] - j;
		Sort(x, sa, y, m);
		for (swap(x, y), i = 2, k = x[sa[1]] = 1; i <= n; i++) {
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) ? k : ++k;
		}
	}
	for (int i = 1; i <= n; i++) rk[sa[i]] = i;
	for (int i = 1, k = 0; i <= n; h[rk[i++]] = k) {
		k -= !!k;
		for (int j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++);
	}
}


struct Node {
	int fir, sec, nxt;
} a[MAXN];
int head[MAXN], acnt = 1, sta[MAXN], p[MAXN];

void work1() {
	int top = 0; sta[0] = -1;
	for (int i = 1; i <= n; i++) {
		int r = i;
		while (sta[top] >= h[i]) {
			r = min(r, p[top]);
			if (sta[top] > h[i]) a[++acnt] = (Node){sta[top], i - p[top], head[p[top]]}, head[p[top]] = acnt;
			top--;
		}
		sta[++top] = h[i], p[top] = r;
	}
	while (top && sta[top] > 0) {
		a[++acnt] = (Node){sta[top], n + 1 - p[top], head[p[top]]}, head[p[top]] = acnt;
		top--;
	}
	int tot = 0;
	for (int i = 1; i <= n; i++) {
		int j = h[i] + 1;
		for (int now = head[i + 1]; now; now = a[now].nxt) {
			int d = a[now].sec + 1, cnt = a[now].fir - j + 1;
			if (K - tot - 1 <= (LL) cnt * d) {
				j += (K - tot - 1) / d;
				for (int l = 0; l < j; l++) putchar(s[sa[i] + l]);
				putchar('\n');
				return;
			}
			tot += d * cnt;
			j += cnt;
		}
		int dev = n - sa[i] - j + 2;
		if (tot + dev >= K) {
			int d = int(K - tot + j - 1);
			for (j = 0; j < d; j++) putchar(s[sa[i] + j]);
			putchar('\n');
			return;
		}
		tot += dev;
	}
	puts("-1");
}

void work0() {
	int tot = 0;
	for (int i = 1; i <= n; i++) {
		int dev = n - sa[i] - h[i] + 1;
		if (tot + dev >= K) {
			int d = int(K - tot + h[i]);
			for (int j = 0; j < d; j++) putchar(s[sa[i] + j]);
			putchar('\n');
			return;
		}
		tot += dev;
	}
	puts("-1");
}

int main() {
	scanf("%s", s + 1);
	read(T); read(K);
	n = (int)strlen(s + 1);
	getsa();
	if (T) work1();
	else work0();
	return 0;
}

跑得比最快的大爷慢,在LOJ上交了一发发现预处理后缀数组用了80%的时间…TAT。

在两年前…我就想搞一个五子棋bot来愉快玩耍。然后在这么久之后,我不想写题然后颓废…我才搞出一个棋力一般的五子棋bot。(智障选手生无可恋)

当我第一次想写这个bot的时候,我就想肯定价值越大的位置越好嘛!于是直接判可以成5的位置,计算分数,然后贪最大的。当时我甚至没有怎么了解OI,所以根本不知道这个东西被称为估价函数。

结果呢?跑起来被我自己吊着打……于是当时我弃疗了,留下了一个vb写的对局棋盘框架。

究其原因,我的估价函数是非常不优秀……因为我直接取了做了估价函数;并且统计方式是,从一个点向上下左右扩展,这导致本来成不了5的点都会被统计进入答案。

一年后(去年)我重新看代码的时候发现了这个问题,于是我改变了估价方式,从统计一个点变成了对于所有成5的可能全部判一遍,并且给每种可能成5情况的所有点同时加上价值。这样做,虽然似乎不能准确地判断出死活(例如死4仍然有活4一半的价值),但是已经可以比较清晰的体现棋子位置的价值了。同时经过手动退火(……),找到了一些看起来比较优秀的估价值。跑起来,终于能下赢我自己啦!同时百度上面的智障五子棋小游戏也下平了。

然后拿去班上给同学玩,结果被吊着打。(……)

首先,这样做的话估价函数的强弱完全决定了这个bot棋力的强弱,但是事实上找到的估价函数并没有非常优秀。其次,我的统计方式本来就不太科学,例如上面的判死活等等。

然而最重要的是,贪心短视地令人嗤之以鼻。

Now Turn : #
+ 010203040506070809101112131415
01                              
02                              
03                              
04                              
05                     O        
06               #   #          
07     O ? O   O O #   #        
08       ? # O # # # O          
09         O # # O O            
10       # O O   #              
11                              
12                              
13                              
14                              
15

考虑如上的局面。此时如果是纯贪心,那么通常来说都会选择(7, 5),因为按照估计函数的计算(7, 5)更加优秀;然而事实上,如果不走(8, 5),那么白棋走(8, 5)就已经是杀棋了。

于是那时的我想起,有往后算XX步的说法,恍然大悟:哦原来可以使用搜索。然后我写了一个搜三步的程序……不过因为我当时对局面的判断取得是总和而不是最大值,效果非常差。

然后今年我又想颓废,于是我就重新看了看自己的程序,发现简直是个逗逼……

重新写了一个基于以下策略的五子棋bot:
1. Min-Max搜索,加上Alpha-Beta剪枝;
2. 为方便Alpha-Beta剪枝,每步对决策按估价函数排序,选择尽量大的先搜索;
3. 估价函数应设计为一定要能够体现出输赢,并且尽量反映局势。注意到五子棋的输赢和全局关系不大,只要一个地方非常优就可以赢了,所以这里我采用的是max(我)-max(敌)作为反应局势。

看起来非常靠谱……事实上,我调调写写搞了很久,结果效果和贪心差不多。

直到一天半后,我才发现:

哇,我botzone上面的黑白读反了。

改了以后瞬间在botzone上登顶了。(UPD: 已经被打爆啦 QAQ)

(2017.06.12 17:05)

然而实际上这个bot棋力是不够的……甚至我随便下了一个手机五子棋都下不过;一些同学也可以轻易手爆这个bot。

假定估价函数足够准确,那么采用Min-Max搜索出的结果应该是非常好的。
然而现实总是没有那么令人满意……总是。很难找到一种准确的评价局面的方式,原因和贪心的错误类似。这里如果没法准确评价局面,那么Min-Max搜出来的最好结果也不是最好的。

更正确的姿势是用蒙特卡洛树搜索,即基于一定程度随机化的搜索。这种搜索通常来说都有一个特性,以随机化为基础,并且只看游戏终局带来的影响。即,不到游戏结束,不停止往更深的地方搜索。这样虽然是随机化的,但是效果会好很多。Hob让我写uct……然而我觉得我不能继续颓废在bot上面了,于是就暂时先写到这里了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <ctime>
#include <cstdlib>
#include <iomanip>
using namespace std;

inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}
inline double min(double a, double b) {return a < b ? a : b;}
inline double max(double a, double b) {return a > b ? a : b;}

#define Lim 15
const double eps = 1e-4;

struct point {
    int x,y;
    double v;
    point () {}
    point (int a, int b, double c) {x = a, y = b, v = c;}
    bool operator < (point a) const {
        return v>a.v;
    }
} tmp[23][233];

double Src[Lim + 1];

int G[Lim + 1][Lim + 1],cnt[3];
double t1[Lim + 1][Lim + 1], t2[Lim + 1][Lim + 1], (*att)[Lim + 1] = t1, (*dfn)[Lim + 1] = t2;

string myData;

char tt[Lim * Lim];

void printBoard() {
    myData += "+ 010203040506070809101112131415\n";
    for (int i = 1; i <= Lim; i++) {
        sprintf(tt, "%02d",i); myData += tt;
        for (int j = 1;j <= Lim; j++) {
            myData += ' ';
            switch (G[i][j]) {
                case 0: myData += ' '; break;
                case 1: myData += '#'; break;
                case 2: myData += 'O'; break;
            }
        }
        myData += '\n';
    }
}

inline void check(int a,int b) {
    memset(att,0,sizeof(double) * (Lim + 1) * (Lim + 1));
    memset(dfn,0,sizeof(double) * (Lim + 1) * (Lim + 1));
    for (int i=1;i<=Lim;i++) {
        cnt[1] = cnt[2] = 0;
        for (int k = 0; k <= 3; k++) cnt[G[i][1 + k]]++;
        for (int j=1;j<=Lim-4;j++) {
            cnt[G[i][j+4]]++;
            if (cnt[b]==0) for (int k=0;k<=4;k++) att[i][j+k] += Src[cnt[a]];
            if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i][j+k] += Src[cnt[b]];
            cnt[G[i][j]]--;
        }
    }
    for (int j=1;j<=Lim;j++) {
        cnt[1] = cnt[2] = 0;
        for (int k = 0; k <= 3; k++) cnt[G[1 + k][j]]++;
        for (int i=1;i<=Lim-4;i++) {
            cnt[G[i+4][j]]++;
            if (cnt[b]==0) for (int k=0;k<=4;k++) att[i+k][j] += Src[cnt[a]];
            if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i+k][j] += Src[cnt[b]];
            cnt[G[i][j]]--;
        }
    }
    for (int i=1;i<=Lim-4;i++) {
        for (int j=1;j<=Lim-4;j++) {
            cnt[1]=cnt[2]=0;
            for (int k=0;k<=4;k++) cnt[G[i+k][j+k]]++;
            if (cnt[b]==0) for (int k=0;k<=4;k++) att[i+k][j+k] += Src[cnt[a]];
            if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i+k][j+k] += Src[cnt[b]];
        }
    }
    for (int i=5;i<=Lim;i++) {
        for (int j=1;j<=Lim-4;j++) {
            cnt[1]=cnt[2]=0;
            for (int k=0;k<=4;k++) {
                cnt[G[i-k][j+k]]++;
            }
            if (cnt[b]==0) for (int k=0;k<=4;k++) att[i-k][j+k] += Src[cnt[a]];
            if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i-k][j+k] += Src[cnt[b]];
        }
    }
}

inline void upd(int x, int y, int a, int b, int f) {
    for (int i = max(1, x - 4); i <= x && i + 4 <= Lim; i++) {
        cnt[1] = cnt[2]=0;
        for (int k=0;k<=4;k++) cnt[G[i+k][y]]++;
        if (cnt[b]==0) for (int k=0;k<=4;k++) att[i+k][y] += f * Src[cnt[a]];
        if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i+k][y] += f * Src[cnt[b]];
    }
    for (int j = max(1, y - 4); j <= y && j + 4 <= Lim; j++) {
        cnt[1] = cnt[2]=0;
        for (int k=0;k<=4;k++) cnt[G[x][j + k]]++;
        if (cnt[b]==0) for (int k=0;k<=4;k++) att[x][j + k] += f * Src[cnt[a]];
        if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[x][j + k] += f * Src[cnt[b]];
    }   
    for (int d = min(4, min(x - 1, y - 1)), i = x - d, j = y - d;i <= Lim-4 && j <= Lim-4 && i <= x;i++, j++) {
        cnt[1]=cnt[2]=0;
        for (int k=0;k<=4;k++) cnt[G[i+k][j+k]]++;
        if (cnt[b]==0) for (int k=0;k<=4;k++) att[i+k][j+k] += f * Src[cnt[a]];
        if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i+k][j+k] += f * Src[cnt[b]];
    }
    for (int d = min(4, min(Lim - x, y - 1)), i = x + d, j = y - d;i >= 4 && j <= Lim-4 && j <= y;i--, j++) {
        cnt[1]=cnt[2]=0;
        for (int k=0;k<=4;k++) cnt[G[i-k][j+k]]++;
        if (cnt[b]==0) for (int k=0;k<=4;k++) att[i-k][j+k] += f * Src[cnt[a]];
        if (cnt[a]==0) for (int k=0;k<=4;k++) dfn[i-k][j+k] += f * Src[cnt[b]];
    }
}

inline void update(int x, int y, int a, int b, int c) {
    upd(x, y, a, b, -1);
    G[x][y] = c;
    upd(x, y, a, b, 1);
    swap(att, dfn);
}

const int X = 8;

double dfs(int a, int b, int dep, double alpha, double beta) {
//  printBoard();
    if (!dep) {
        double ma = 0, mb = 0;
        for (int i = 1; i <= 15; i++)
            for (int j = 1; j <= 15; j++) {
                ma = max(ma, att[i][j]);
                mb = max(mb, dfn[i][j]);
            }
        return ma - mb;
    }
    int tot = 0;
    for (int i = 1; i <= 15; i++)
        for (int j = 1; j <= 15; j++) {
            if (att[i][j] > 1e8) return 1e20;
            else if (dfn[i][j] > 1e8) return -1e20;
            if (!G[i][j]) {
                tmp[dep][++tot].x = i;
                tmp[dep][tot].y = j;
                tmp[dep][tot].v = att[i][j] + dfn[i][j];
            }
        }
    nth_element(tmp[dep] + 1, tmp[dep] + min(tot, X), tmp[dep] + tot + 1);
    sort(tmp[dep] + 1, tmp[dep] + min(tot, X) + 1);
    for (int i = 1; i <= min(tot, X); i++) {
        nth_element(tmp[dep] + 1, tmp[dep] + i, tmp[dep] + tot + 1);
        update(tmp[dep][i].x, tmp[dep][i].y, a, b, a);
        double val = -dfs(b, a, dep - 1, -beta - eps, -alpha - eps);
        update(tmp[dep][i].x, tmp[dep][i].y, b, a, 0);
        if (val >= beta) return val;
        alpha = max(alpha, val);
    }
    return alpha;
}

int now, ene, First;

point work() {
    int stp = min(X, cnt[1] * 3);
    check(now, ene);
    int tot = 0;
    for (int i = 1; i <= 15; i++)
        for (int j = 1; j <= 15; j++) {
            if (!G[i][j]) tmp[Lim][++tot] = point(i, j, att[i][j] + dfn[i][j]);
        }
    //printBoard();

    sort(tmp[Lim] + 1, tmp[Lim] + tot + 1);
    double ma = -1e233; int x = tmp[Lim][1].x, y = tmp[Lim][1].y;
    time_t st = clock();
    for (int i = 1; i <= min(11, tot) && (clock() - st) * 1. / CLOCKS_PER_SEC  < 800; i++) {
        if (tmp[Lim][i].v <= tmp[Lim][1].v / 10) break;
        update(tmp[Lim][i].x, tmp[Lim][i].y, now, ene, now);
        double pos = -dfs(ene, now, stp, -1e233, -ma - eps);
    //  myData += to_string(pos) + " -> " + to_string(tmp[Lim][i].x) +  " " + to_string(tmp[Lim][i].y) + "\n"; 
        update(tmp[Lim][i].x, tmp[Lim][i].y, ene, now, 0);
        if (pos - eps > ma) {
            ma = pos;
            x = tmp[Lim][i].x, y = tmp[Lim][i].y;
        }
    }
    return point(x, y, 0);
}
#ifdef _BOTZONE_ONLINE
#include "jsoncpp/json.h"

int tot = 0;

void placeAt(int x, int y, int c) {
    if (x < 0) return;
    G[x + 1][y + 1] = c; cnt[c]++;
}

Json::Reader reader;
Json::Value input;

int A, B;

void read() {
    string str;
    getline(cin, str);
    reader.parse(str, input); 
    int turnID = input["responses"].size();
    for (int i = 0; i < turnID; i++) {
        placeAt(input["requests"][i]["x"].asInt(), input["requests"][i]["y"].asInt(),2);
        placeAt(input["responses"][i]["x"].asInt(), input["responses"][i]["y"].asInt(),1);
    }
    placeAt(input["requests"][turnID]["x"].asInt(), input["requests"][turnID]["y"].asInt(),2);
    if (tot&1) {
        First=0;now=2;ene=1;
    }
    else {
        First=1;now=1;ene=2;
    }
    A = cnt[1], B = cnt[2];
    cnt[0] = Lim * Lim - cnt[1] - cnt[2];
}

Json::Value Position(int x,int y) {
    Json::Value action;
    action["x"] = x-1;
    action["y"] = y-1;
    return action;
}

void print(int x,int y) {
    Json::Value ret;
//  myData = "---- " + to_string(A + B) + " ----\n" + myData + "\n";
    ret["response"] = Position(x,y);
//  if (A + B < 3) ret["globaldata"] = myData;
//  else ret["globaldata"] = input["globaldata"].asString() + myData;
    Json::FastWriter writer;
    cout << writer.write(ret) << endl;
}

#else 
void read() {
    freopen("board.in","r",stdin);
    scanf("%d",&now);
    ene=3-now;
    //printf("[%d %d]\n", now, ene);
    for (int i=1;i<=15;i++) {
        for (int j=1;j<=15;j++) {
            int ch=getchar();
            while (ch<'0') ch=getchar();
            G[i][j]=ch-'0';
            cnt[G[i][j]]++;
        }
    }
    freopen("/dev/tty", "r", stdin);
}

void print(int x, int y) {
//  cout << myData << endl;
    freopen("decision.out","w",stdout);
    printf("%d %d\n", x, y);  
    fclose(stdin);
    fclose(stdout);
}
#endif

int main() {
    for (int i = 0; i < 5; i++) Src[i] = pow(10, i);
    Src[2] *= 2.501;
    Src[5] = 1e10;
    read();
    if (cnt[0] == Lim * Lim) {
        print((Lim + 1) / 2, (Lim + 1) / 2);
        return 0;
    }
    if (cnt[1]==cnt[2]) First=1;
    else First=0;
    point p = work();
    print(p.x, p.y);
    return 0;
}

看到akb在冬令营就切了好多点分治就好慌啊qaq,然后机房里也有一堆人写点分治qaq,然后我就被点分治虐了啊qaq……

树上的点分治是一种针对树上路径统计的问题的算法,通过找到重心使得子问题规模快速下降,再将所有子问题答案合并起来,通常能够将\(O(n ^ 2)\)规模的问题优化为\(O(n \log n)\)或者\(O(n \log ^ 2 n)\)。

先看一道题:
给定一颗\(n \leq 10 ^ 5\)个节点的带权无根树,设\((i, j)\)之间的简单路径边数为\(dis(i, j)\),求所有满足\(dis(i, j) \leq K\)且\(i \lt j\)的数对\((i, j)\)的数量。(CWOJ1201

暴力做法显然,从每个节点开始dfs (bfs是等价的,后文dfs均可以用bfs解决),记录答案即可。时间复杂度为\(O(n ^ 2)\)

但是这样太慢了!我们想要更快的做法。

继续阅读