题目描述

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

输入格式

两行,两个字符串 \(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;
}

2017.5.7 CTSC Day 0

早上起很早去赶飞机…然后离线了他们的数论入门题来玩耍,结果被虐了?QAQ
下午到酒店发现没和董先生谭先生分到一家酒店甚是尴尬…本来和Wuvin先生分到一间的,结果ZYQN先生和我换啦于是我跟一位现充天津大爷fnoi12bzzhan一间。(wori这位大爷秀恩爱的技巧简直炫酷
晚上去八十中吃完晚饭就滚了…打了场TC……结果rating变化迟迟不出现QAQ。
睡前和大爷瞎bb到十二点过。

2017.5.8 CTSC Day 1

吐槽!八十中的早饭一点都没有平常的饭好吃QAQ。
然后进考场发现键盘是个平板一样的东西TAT不过还好。看题,发现怎么……一点也不CTSC啊……怎么这么noi啊……然后第一题简直就是签到题,然而考场上我觉得:这tm是CTSC怎么可能让我A题呢?于是写了30+21就跑路了233.第二题不是IOI原题嘛……然而我WC睡过去了QAQ,于是写了个SPFA加剪枝的暴力感觉好虚啊…第三题是一个第一眼看上去很蠢的题,“看见了NOIP的眼神.jpg”……然后写完发现过不了样例……WTF!才发现那个贝叶斯公式是有用的,前后的确定事件都会影响中间的随机事件……于是看公式看了一个小时,看样例解释才把公式看懂。于是写了发暴力…然而我太蠢了不会反着用公式TAT于是正向NM反向只会\(O(N ^ 2M)\)……觉得很虚于是反向写了个线段树查那个线性递推。
期望:51 + 20 + 35,实际51 + 10 + 50。
第二题剪枝剪挂,居然有十分真是奇迹;\(O(wys)\)还是有用的,不然怎么解释\(O(N \log N M)\)过\(10 ^ 4\)呢233……不过这分很低就对了。第一题我真是蠢,居然不做完哎。

2017.5.9 CTSC Day 1.5

上午听十五人队吹逼。感觉那些评委就是,我不知道你在讲什么,但是他们让我提问,好尴尬怎么办啊……
于是出现了一些比较厉害的提问,包括但不限于:
“你讲的很好,我就有一个问题,什么是本质不同的子串呢?”
“可你这个和OI有什么关系呢?”
……
YJQ的提问也好劲啊233。
下午迷之王选秘书来讲王选,我觉得如果我以后去当某个很厉害的人的秘书,一定要让他死之前给我做个PPT,这样我动动嘴皮子就发达了。于是董先生选择推WA,我拖着谭先生去五道口和戴爷愉快玩耍吹逼。五道口体校真大…没自行车根本走不下来。学校还是挺漂亮的?不过到处都是一片奇怪的紫色。晚上戴爷请吃清青小火锅,于是在我踢掉五次电磁炉电源线的同时,他们开始由不严谨的证明讲到了某些奇怪的积分……于是我只能吃吃吃吃吃装作没听到QAQ。

2017.5.10 CTSC Day 2

又是奇怪的题…第一题B君的gift真是233…我硬是没想Lucas在那里打表瞎找规律,不过幸好找到A掉了233。第二题…是…什么鬼啊QAQ…好难想啊(我不知道那个定理真是尴尬),第三题是什么神几何题啊QAQ不太会啊。于是写3k代码来获取第二题的部分分,第三题推出来投影也不会做只能瞎骗分TAT。
期望:100 + 10 + 0,实际100 + 10 + 0。
于是第二题是有定理有算导数据结构后还要维护一个奥妙重重的东西……卧槽。第三题竟然是A*……标程800行太强啦!不过xumingkuan大爷居然退火+遗传怒A这题太强啦。
啊,于是毫无悬念地Ag滚了。还是太菜啦TAT。
下午看到面试名单心一沉,嗷YJQ可能进不了队了啊。然后面试,YJQ和xumingkuan的口语和其他选手的不是一个水平的啊…听着myy英语只能说,勉强听得懂QAQ。YJQ的面试好劲啊!虽然不管怎么说可能还是进不了队,但是那股自信,我可能是没有的啊QAQ。
晚上听名单简直是羞耻,念铜牌银牌和念“你们都考跪了哈哈哈”名单差不多。

2017.5.11 APIO Day -1

因为没安排就睡到了11点。然后颓颓颓,专业口胡APIO历年题目233。晚上去吃了个非常尴尬的烤鸭。
晚上打了场CF,xjb写了几道题,最后一道太麻烦了没写QAQ。

2017.5.12 APIO Day 0

把上午的培训翘了。中午去吃饭,下午听了点奇奇怪怪的东西,那个肉眼无损的拉长图形好厉害啊QwQ。
晚上不想去听算法题,在图书馆写代码直到被保安赶走。
回酒店又乱散发负能量TAT我这人怎么这样啊。

2017.5.13 APIO

早上起晚,于是和室友一起去星爸爸解决了早饭然后打的到八十中。结果这个APIO搞得好像很像USACO……233。只是我们被强制集中考试了而已。
前两道题都是迷之交互题;当然其实第一题只是强制在线的传统题而已;而第二题也其实只是个提交一个构造法的答案提交题而已。
第一题越看越像noi2016的网格…但是我奇怪的离散化建图写挂了QAQ,于是只能交前两个Subtask。第二题好有趣啊w然而玩了一个小时连minValue都没搞出来QAQ弄得我自信心下溢。弃疗看第三题,虽然一眼分数规划但是发现描述好复杂看起来好难哦,于是先用Floyd写第一个Subtask,结果写出来发现这不就是神犇(sb)题么,然后我愚蠢的写了个垃圾的东西先交Subtask2,然后去掉了重复计算,准备过第三个Subtask……结果直接A了?喵哈!
悠闲地开始玩第二题,发现随便放一个就可以找到minValue了真是233。然后构造了好久maxValue,最后在我最开始的那一个小时乱搞的思路里捡出了一个可行的,即如果每次都给已知的更大的放更多的石子,那么留下来的一定是一堆小的加大的中更大的,最后取个交就知道是哪些分数更大啦QwQ。然后我又玩不出greaterValue了,到最后我惊奇的发现如果给那两个要比较的相同的石子,一定存在一个石子数量使得一个选一个不选。太强啦!然后就二分搞搞。(后来我发现我二分上下界根据我的想法的话是设错了,然而碰到了正解233)。后面的allValue智商不足不想玩了,直接把greaterValue写成比较函数然后sort。(事后知道stable_sort分数更高的我眼泪流下来)
然后23 + 60 + 100。我明明可以考更高的,结果第一题第二题失误都还是太大了,Au也没什么卵用啊。

2017.5.14 THUPC

THUPC……哎,从入门到智障选手。
M题提示那么明显我们就是不看题……结果输出”mom”和”mother”就可以了我们还只看输入输出搞了所有单词出来,智障吧QAQ。
C题简直娱乐,直接A了。
H题想了想挺简单的?于是直接主席树二分写了……结果被卡常数卡成狗……到最后卡不动了1200ms……弃疗写整体二分才过了QAQ。
大家都不会做算法题了于是我昏天黑地地调完了阳光体育。啥?哦就是猪国杀那种。
然后A和J的思路都只差一步了QAQ但是太弱了没想出最后一步就GG了。
一共4道?然而4道最高15名,我们Fail太多直接50+了QAQ。
于是…因为董先生的选择,他正式退役了。祝好啊QAQ。
我也要准备收拾东西去杭二了QwQ,thusc再来北京。
嗷……听说他们晚上飞机命运多舛…orz。不过我还听说董先生六点才回到家,早上就返校了,简直太强了。
呐。CTSC && APIO && THUPC 2017就写到这里吧。

Day 0

上午省选集训考试……\(N ^ 3 \log K\)过\(N = 500, K = 10 ^
{12}\)是什么鬼啊……反正除了几何做不来,其他题都是Eazy AC fun吧……

下午回到了学校这边。去隔壁咖啡坐了一会儿,敲了一道模板题。走的时候被班上同学抓住嘲讽了一波……然后因为手机没电没见到某些人。

晚上难以入眠,刷着逼乎听着歌好久才睡着。

Day 1

自带的迟到buff让大家等了十分钟……真是不好意思呢QAQ。

键盘Backspace贼小,\键键位奇怪,差评。幸好这次组织得终于不像NOIp那么水了。

看题。第一题一眼傻逼,然而最开始思路偏了?敲了个链剖,然后发现自己维护的东西是错的,怒删写暴力发现跑的贼快。写暴力的时候看到有一个地方要break,突然发现做过原题(BZOJ3252),然后就写完暴力写线段树了。不过傻逼的我还是写挂了两次(幸好写了暴力),然后终于拍上了。

第二题一眼就会做了然而觉得可能并调不出来。于是先码了个不优秀的暴力。

第三题几何,不会,\(N ^ 3\)写完就没管了。

开始码第二题……数据结构调死人,特别是代码太长连翻页都很困难的时候。我调点分本来就慢……然后还有一个链剖和线段树,还有大模拟。最后半个小时发现没有调出来的希望的时候,退出去卡了卡暴力常,就扫雷去了。

下午出分等死人,然后100 + 20 + 30。幸好都拿稳了。

看到我校初三选手200?Excuse me?暴力AC了T2?

喵喵喵?BFS就能AC?

我不想在博客上说脏话,所以我无话可说。

dhc因为T1 MLE就一直很不高兴……然后他的T2写了正解并AC,听说暴力A了直接崩了……

tsw A了T3,然而因为T1手写堆挂了,10分滚?哎。

lsw和wzk好像都考得不太好样。

回家没什么心情,刷知乎颓颓颓。说好的再写遍模板,刚写完sa就不想写了。

Day 2

大家一脸视死如归地走进考场。

wzk说他今天AK都没法进队了,可怜。

dhc说他今天不AC两道题就退役了。

tsw先生……要高于200才能进队。

初三大爷和我反而压力没那么大……但是其实不过两题也是滚粗的。

才发现监考的小姐姐好萌啊qwq。

T1 sbdp,大概写完和写完暴力再加上拍上不超过15分钟吧?

T2 RMQ裸题,再加上非常恶心的输出(后来才发现那个输出比RMQ难写多了

T3 字符串,弃疗

于是怼了三个半小时T2,幸好写了对拍拍出了4个错误,但是极限数据要3.5s,后来发现不用快速乘也可以,再卡卡常,2.9s…好虚啊。

T3用STL写了个\(N ^ 2 \log N\)的暴力,过1000好悬啊,怕是没分。

出考场发现大家几乎全是退役的表情。

dhc因为心理压力太大直接先开的T2T3,结果因为太急没做出来直接带崩心态。T1都交的暴力和骗分。

lsw挂惨了。wzk也挂了貌似,他第二题用了FFT,过了大样例,但是据说处理挂了。

只有tsw写了200分……但他NOIp和DAY1都挂了不该挂的东西,也不稳。

中午dhc直接回家了,wzk也走了。我和其他两人和熊老去吃了火锅。

下午回电子科大前就听说出成绩了。然后100 + 100 + 0。
讲道理是进不了队的,但是大家都考得不好。 rk10。

初三大爷在杀完后rk15,差一名。虽然很可惜,但我觉得暴力进队这种事情本来就不该发生。

ZYQN翻盘失败了……哎。

zms也挂了,他和lxl大爷好像非常难过。本来觉得他们挺稳的啊,世事无常。

akb在两道题爆炸的情况下还能rk13……太强了。

进队本来该很高兴的……为什么我高兴不起来呢。

那一年我们望着星空
有那么多的灿烂的梦
以为快乐会永久
像不变星空陪着我

莫名提前的考前综合征让我无法入眠。

我什么都会一点,也可以叫什么都不会,因为总担心自己不会别人会的东西。

这几天……先是在UESTC校赛里被七中大爷和UESTC的三位大爷粉碎,然后又在水水的省选集训里昏昏欲睡,过着醉生梦死的生活。

不知道后天我将怎么面对结果。抑或是成功的喜悦,还是退役后如释重负呢?

我希望是前者。

与其苟延残喘,不如纵情燃烧。

就算再不自信,我也只能尽我全力说着:

SCOI2017,我准备好了。

AK is yzh.

夜未央、天未亮,我在幸存的沙场
只盼望、此生再,奔向思念的脸庞
泪未干、心未凉,是什么依然在滚烫
入阵曲,四面楚歌谁独唱

Countdown: 7 Days.

If this is to end in fire
then we shall all burn together
Watch the flames climb higher
into the night

Countdown: 8 Days.

Sometimes the only payoff for having any faith
is when it’s tested again and again everyday
I’m still comparing your past to my future
It might be your wound
but they are my sutures

Countdown: 9 Days.

此生到尽头
你是谁、曾怎么活
他们说
就让他们去说
生命如长风
吹过谁的心头
你想被记住的那个名字
将会是什么

Countdown: 10 Days.