【日常小测】友好城市

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法

有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$

然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了

Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int 
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ]; 
struct Query{
	int l, r, blk, id;
	inline bool operator < (const Query &Q) const {
		return blk < Q.blk || (blk == Q.blk && r < Q.r);
	}
}qy[QQ];
struct Bitset{
	UI v[5];
	inline void flip(int x) {
		v[x >> 5] ^= 1 << (x & 31);
	}
	inline void set(int x) {
		v[x >> 5] |= 1 << (x & 31);
	}
	inline void reset() {
		memset(v, 0, sizeof(v));
	}
	inline bool operator [](int x) {
		return v[x >> 5] & (1 << (x & 31));
	}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
 	a1[u].set(v);
 	a2[v].set(u);
}

class Kosaraju{
	vector<int> que;
	Bitset vis;
public:
	inline int solve() {
		vis.reset();
		que.clear();
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.reset();
		int ret = 0;
		for (int j = n - 1; ~j; j--) {
			int i = que[j];
			if (!vis[i]) {
				int cnt = dfs1(i);
				ret += cnt * (cnt - 1) / 2;
			}
		}
		return ret;
	}
private:
	inline void dfs0(int w) {
		vis.flip(w);
		for (int i = 0; i < 5; i++) {
			for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					dfs0(t);
				}
			}
		}
		que.push_back(w);
	}
	inline int dfs1(int w) {
		vis.flip(w);
		int ret = 1;
		for (int i = 0; i < 5; i++) {
			for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					ret += dfs1(t);
				}
			}
		}
		return ret;
	}
}scc;

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		U[i] = read();
		V[i] = read();
		AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
	}
	for (int i = 1; i <= q; i++) {
		qy[i].l = read(); 
		qy[i].r = read();
		qy[i].blk = qy[i].l / BlockSize;
		qy[i].id = i;
	}
	sort(qy + 1, qy + 1 + q);
	Bitset CurG[N], CurRG[N];
	for (int i = 1, L = 1, R = 0; i <= q; i++) {
		if (qy[i].blk != qy[i - 1].blk || i == 1) {
			L = qy[i].blk + 1;
			R = L - 1;	
			for (int j = 1; j <= n; j++) {
				CurG[j].reset();
				CurRG[j].reset();
			}
		}
		if (qy[i].r / BlockSize - 1 > R) {
			for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
				for (int k = 1; k <= n; k++) {
					for (int h = 0; h < 5; h++) {
						CurG[k].v[h] ^= PreG[j][k].v[h];
						CurRG[k].v[h] ^= PreRG[j][k].v[h];
					}
				}
			}
			R = qy[i].r / BlockSize - 1;
		}
		if (L <= R) {
			for (int i = 1; i <= n; i++) {
				g[i] = CurG[i];
				rg[i] = CurRG[i];
			}
			for (int l = qy[i].l; l < L * BlockSize; l++) {
				AddEdge(U[l], V[l], g, rg);
			}
			for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
				AddEdge(U[r], V[r], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		} else {
			for (int i = 1; i <= n; i++) {
				g[i].reset();
				rg[i].reset();
			}
			for (int j = qy[i].l; j <= qy[i].r; ++j) {
				AddEdge(U[j], V[j], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

【BZOJ 3577】玩手机

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3577
神犇题解:http://www.cnblogs.com/clrs97/p/4403242.html

解题报告

之前一直都是线段树优化建图
这题需要用$ST$表来优化建图

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int INF = 1e9;
const int N = 500000;
const int M = 2000000;

int S,T,E,tot,A,B,Y,X,n2[2][70][70][8]; 
int head[N],nxt[M],to[M],flow[M],n1[2][70][70];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v, int f) {
	assert(u); assert(v);
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class NetworkFlow{
	int dis[N],cur[N];
	queue<int> que;
	public:
		inline int MaxFlow() {
			int ret = 0;
			while (BFS()) {
				memcpy(cur, head, sizeof(cur));
				ret += DFS(S, INF);
			}
			return ret;
		}
	private:
		inline bool BFS() {
			memset(dis, 60, sizeof(dis));
			dis[S] = 0;
			for (que.push(S); !que.empty(); que.pop()) {
				int w = que.front();
				for (int i = head[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] > INF) {
						dis[to[i]] = dis[w] + 1;
						que.push(to[i]);
					}
				}
			}
			return dis[T] <= INF;
		}
		inline int DFS(int w, int f) {
			if (w == T) {
				return f;
			} else {
				int ret = 0;
				for (int &i = cur[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] == dis[w] + 1) {
						int tmp = DFS(to[i], min(f, flow[i]));
						ret += tmp; f -= tmp;
						flow[i] -= tmp; flow[i ^ 1] += tmp;
						if (!f) {
							break;
						}
					}
				}
				return ret;
			}
		}
}Dinic;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	X = read(); Y = read(); 
	A = read(); B = read();
	S = ++tot; T = ++tot;
	E = 1; 
	for (int i = 1; i <= X; ++i) {
		for (int j = 1; j <= Y; ++j) {
			n1[0][i][j] = ++tot;
			n1[1][i][j] = ++tot;
			AddEdge(n1[0][i][j], n1[1][i][j], read());
		}
	}
	for (int i = X; i; --i) {
		for (int j = Y; j; --j) {
			for (int a = 0, len = 1; i + len - 1 <= X && j + len - 1 <= Y; ++a, len <<= 1) {
				n2[0][i][j][a] = ++tot;
				n2[1][i][j][a] = ++tot;
				if (!a) {
					AddEdge(n2[0][i][j][a], n1[0][i][j], INF);
					AddEdge(n1[1][i][j], n2[1][i][j][a], INF);	
				} else {
					int llen = len >> 1;
					AddEdge(n2[0][i][j][a], n2[0][i][j][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i + llen][j][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i][j + llen][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i + llen][j + llen][a - 1], INF);
					
					AddEdge(n2[1][i][j][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i][j + llen][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i + llen][j][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i + llen][j + llen][a - 1], n2[1][i][j][a], INF);
				} 
			}	
		}
	}
	for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= A; ++i) {
		p0 = ++tot; p1 = ++tot;
		w = read(); 
		x1 = read(); y1 = read();
		x2 = read(); y2 = read();
		AddEdge(S, p0, INF);
		AddEdge(p0, p1, w);
		
		int len = x2 - x1 + 1, lg = 0, d = 1;
		for (; (d << 1) <= len; lg++, d <<= 1);
		AddEdge(p1, n2[0][x1][y1][lg], INF);
		AddEdge(p1, n2[0][x1][y2 - d + 1][lg], INF);
		AddEdge(p1, n2[0][x2 - d + 1][y1][lg], INF);
		AddEdge(p1, n2[0][x2 - d + 1][y2 - d + 1][lg], INF);
	}
	for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= B; ++i) {
		p0 = ++tot;	p1 = ++tot;
		w = read();
		x1 = read(); y1 = read();
		x2 = read(); y2 = read();
		AddEdge(p0, p1, w);
		AddEdge(p1, T, INF);
		
		int len = x2 - x1 + 1, lg = 0, d = 1;
		for (; (d << 1) <= len; lg++, d <<= 1);
		AddEdge(n2[1][x1][y1][lg], p0, INF);
		AddEdge(n2[1][x1][y2 - d + 1][lg], p0, INF);
		AddEdge(n2[1][x2 - d + 1][y1][lg], p0, INF);
		AddEdge(n2[1][x2 - d + 1][y2 - d + 1][lg], p0, INF);
	}
	assert(tot < N);
	assert(E < M);
	printf("%d\n", Dinic.MaxFlow());
	return 0;
}

【BZOJ 2006】[NOI2010] 超级钢琴

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2006
数据传送门:noi_2010_piano

这题很经典!很好!
首先肯定是求前缀和,然后搞n个结构体,第i个表示左端点在i的线段的最值
每次取出最大的结构体进行拓展,需要用函数式线段树来支持区间k大
时间复杂度:O(k*log(值域))
另外这题还有ST表的做法,但还不是很会 qwq

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500000+9;
const int M = 20000000+9;
const int BAS = 500000010;
const int INF = 1000010000;

int n,k,L,R,arr[N];
struct Query{
	int pos,num,val;
	bool operator < (const Query & B) const {
		return val < B.val;
	}
};
priority_queue<Query> que;

namespace Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],sum[M],cnt,root[N],ans_tmp;
	
	void insert(int p, int &w, int l, int r, int v) {
		w = ++cnt; sum[w] = sum[p] + 1;
		memcpy(ch[w],ch[p],sizeof(ch[0]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (v < mid) insert(ch[p][0], ch[w][0], l, mid-1, v);
			else insert(ch[p][1], ch[w][1], mid, r, v);
		} 
	} 
	
	inline void insert(int p, int w) {
		insert(root[p-1], root[p], 1, INF, w);
	} 
	
	void query(int p, int w, int l, int r, int num) {
		if (l == r) ans_tmp = l;
		else {
			int mid = l + r + 1 >> 1;
			if (sum[ch[w][1]] - sum[ch[p][1]] >= num) query(ch[p][1], ch[w][1], mid, r, num);
			else query(ch[p][0], ch[w][0], l, mid-1, num - (sum[ch[w][1]] - sum[ch[p][1]]));
		}
	}
	
	inline int query(int l, int r, int num) {
		query(root[l-1],root[r],1,INF,num);
		return ans_tmp;
	}
};

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	n = read(); k = read(); L = read(); R = read();
	for (int i=1;i<=n;i++) arr[i] = arr[i-1] + read();
	for (int i=1;i<=n;i++) CT::insert(i,arr[i] + BAS);
	for (int i=1;i+L-1<=n;i++) {
		Query tmp; tmp.pos = i; tmp.num = 1;
		tmp.val = CT::query(i+L-1, min(n,i+R-1), 1) - BAS - arr[i - 1];
		que.push(tmp);
	}
	
	LL vout = 0;
	for (int i=1,p;i<=k;i++) {
		Query tmp = que.top(); que.pop();
		vout += tmp.val; 
		if (tmp.num < R - L + 1) {
			tmp.num++; p = tmp.pos;
			if (n - (p+L-1) + 1 < tmp.num) continue;
			tmp.val = CT::query(p+L-1, min(n,p+R-1), tmp.num) - arr[p - 1] - BAS;
			que.push(tmp);
		}
	}
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 4516】[SDOI2016] 生成魔咒

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4516

考试的时候,一看到要动态维护就把SA扔一边凉快去了QAQ
想一想,不能这么草率啊!
来说一说SA和SAM两种做法

1) SAM:
很明显就是求一个字符串本质不同的字串个数
SAM本身就是增量构造,于是就成裸题了

2) SA:
考虑离线之后,先逆序建一个完整的出来
那么加入一个字符,实际上就是加入了一个后缀
那么其对于答案的贡献,就是原来的height数组搞一搞
实现的话,搞一个RMQ什么的就好
代码的话,我们来召唤Menci:https://oi.men.ci/sdoi2016-incantation/

自己太懒,于是就只写了SAM的代码:

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define LL long long
using namespace std;
using namespace tr1;

const int N = 200000+9; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

namespace Suffix_Automaton{
	#define SAM Suffix_Automaton
	int len[N],fail[N],cnt,tail;
	unordered_map<int,int> ch[N]; 
	
	inline int Extend(int c) {
		int w = tail; tail = ++cnt; len[tail] = len[w] + 1;
		while (w&&!ch[w]) ch[w] = cnt, w = fail[w];
		if (!w) fail[tail] = 1;
		else {
			if (len[ch[w]] == len[w]+1) fail[tail] = ch[w];
			else {
				int to = ch[w]; ch[++cnt] = ch[to];
				fail[cnt] = fail[to]; fail[to] = cnt; fail[tail] = cnt; 
				len[cnt] = len[w] + 1; while (ch[w] == to) ch[w] = cnt, w = fail[w];
			}
		} return len[tail] - len[fail[tail]];
	}
	
	inline void solve(int n) {
		cnt = tail = 1; 
		for (LL i=1,vout=0;i<=n;i++) 
			printf("%lld\n",vout+=Extend(read()));
	}
};

int main(){
	SAM::solve(read());
	return 0;
}

—– UPD 2016.9.29 —–
这™map比unordered_map快这么多有几个意思QAQ
475864785645
这种感觉……
真·生无可恋
V5[YANBJ`4%A2`%PIH$BH_F

【BZOJ 4569】[SCOI2016] 萌萌哒

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4569

这题,出题人是怎么想到的QAQ
真心服 Orz

考虑网络流的区间建边的方法:先搞出一个像线段树的玩意
然而这个题目没办法了,因为线段树的区间拆分是不规则的,对不上 QAQ
于是考虑ST表,用ST表来搞一搞,其实是用来去掉区间合并中的重复部分

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int MOD = 1000000007;

int n,m,fa[18][N],vout=1;

inline int find(int p, int w) {
	int f = fa[p][w], tmp;
	while (f != fa[p][f]) f = fa[p][f];
	while (w != f) tmp = fa[p][w], fa[p][w] = f, w = tmp;
	return f;
} 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

void merge(int t, int a, int b){
	int t1 = find(t,a), t2 = find(t, b);
	if (t1 == t2) return; fa[t][t1] = t2;
	if (!t) return; t--, merge(t,a,b), merge(t,a+(1<<t),b+(1<<t));
}

int main(){
	n = read(); m = read(); if (n == 1) return puts("10"), 0;
	for (int j=0;j<=17;j++) for (int i=1;i<=n;i++) fa[j][i] = i;
	for (int i=1,a,b,c,d,stp;i<=m;i++) 
		a = read(), b = read(), c = read(), d = read(), stp = 31 - __builtin_clz(b-a+1),
		merge(stp,a,c), merge(stp,b-(1<<stp)+1,d-(1<<stp)+1);
	for (int i=1,tag=1;i<=n;i++) if (find(0,i) == i) vout = vout*(tag?9LL:10LL) % MOD, tag = 0;
	return printf("%d\n",vout), 0; 
}

另外说到压代码这个事,Claris我是真心服 (:зゝ∠)
545646454
第一眼看上去,还以为只有主要的函数QAQ
再次 Orz

【UOJ 213】[UNR #1] 争夺圣杯

题目传送门:http://uoj.ac/problem/213
原厂题解:http://c_sunshine.blog.uoj.ac/blog/1860

我发现这道题目,我写了30分的暴力,60分的乱搞,100分的乱搞QAQ

说一说100分的乱搞O(nlogn):
考虑每一个区间的右端点右移一格,左端点不动
那么区间mx要么变成最右边那个,要么不动
考虑计算最右边那货对于答案的贡献,实际上就是区间加减
于是线段树维护一下

其实搞到这里,O(n)的做法就很明显了
因为线段树那里,只需要区间加减,不需要支持中途询问
于是搞一个差分就可以把线段树给去掉

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int MAXN = 1000000+9;
const int MOD = 998244353;

int n,arr[MAXN],vout,que[MAXN],lft[MAXN],MX[MAXN],BUF[MAXN]; 

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline void prework(){
	int tot = 0;
	for  (int i=1;i<=n;i++) {
		while (tot && arr[que[tot]] < arr[i]) tot--;
		BUF[1] = (BUF[1]+arr[i])%MOD;
		BUF[i-que[tot]+1] = ((BUF[i-que[tot]+1] - arr[i]) % MOD + MOD ) %MOD;
		lft[i] = i-que[tot]; que[++tot] = i; 
	} tot = 0; que[0] = n+1;
	for (int i=n;i;i--) {
		while (tot && arr[que[tot]] <= arr[i]) tot--;
		if(tot) {
			BUF[que[tot]-i+1] = ((BUF[que[tot]-i+1]-arr[i]) % MOD + MOD) % MOD; 
			BUF[que[tot]-i+lft[i]+1] = (BUF[que[tot]-i+lft[i]+1] + arr[i]) % MOD;
		} que[++tot] = i;
	}
	for (int i=n;i;i--) MX[i] = max(MX[i+1], arr[i]);
}

inline void solve(){
	int tmp = 0, delta = 0;
	for (int i=1;i<=n;i++) {
		delta = ((delta + BUF[i]) % MOD + MOD) % MOD;
		tmp = ((tmp + delta) % MOD + MOD) % MOD;
		vout ^= tmp;
		tmp -= MX[n-i+1];
	}
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) arr[i] = read();
	prework(); solve();
	printf("%d\n",vout);
	return 0;
}

【NOI六连测】[D2T1] 矩阵

题目传送门:http://pan.baidu.com/s/1pLvQmx1
离线版题目:http://paste.ubuntu.com/18292275/
数据传送门:http://pan.baidu.com/s/1dFDf8p7

哎呀,第一次看到这个题,一脸懵逼。之前在POJ上倒是做过矩阵的KMP,但这货没有模式串啊!
但是乱搞了一阵之后,如有神助般想到了二分+Hash,时间复杂度O(n^2*log(n))嗯,刚刚好!
于是就开始码Hash,码完之后不放心,还写了一个O(n^4)的SA来对拍,然后满心欢喜,终于可以A题啦!
然后被卡T了 QAQ, 只有暴力分QAQ, 然后今天就爆炸了,这题写了4h+啊!60分滚粗

下面说一点正事,这题正解也是Hash,那么能体现出优劣的就是Hash的方式了
Ⅰ.Sparse_Table版本http://paste.ubuntu.com/18292055/
在考试的时候YY出来的,提前处理出以每一个点为右上角、边长为2的整次方幂的Hash值
然后任意一个矩阵都可以用4个矩阵拼起来
但是预处理是O(n^2*log(n))的时间复杂度
所以大的点全部跑了1.09-1.27s不等,全部被判T。然而std最大的点都跑了0.6s+啊!被卡常了( ▼-▼ )
Ⅱ.前缀和版本http://paste.ubuntu.com/18292096/
这个是std的算法。统计二维的前缀和,然后每一维单独乘以一个以幂的级数递增的质数
然后要提取矩阵的时候,前缀和减一减,然后统一次数即可。于是预处理只需要O(n^2)即可
Ⅲ.常规矩阵Hashhttp://paste.ubuntu.com/18292122/
之前两个算法都可以做到随机访问。这个Hash方式不行。
它是把x轴和y轴分开Hash,然后滑动窗口,虽然不能做到O(1)的随机访问,但是遍历的话,还是可以做到O(1)的
总结:三种Hash方式应该都是不错的,但从时间复杂度和代码的优美程度来讲,我以后会选择第二种

另外,Hash都会涉及到判重的问题,一般来讲,大家都是使用set
但这一次lcr给我提供了一个很好的解决方案:sort+unique
理论复杂度一样,但实测效果比set快了3-4倍
有图有真相:matrix_set_versionmatrix_unique_version

贴一份前缀Hash+unique的版本:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define UL unsigned long long 
using namespace std;

const int MAXN = 500+9;
const int N = MAXN*MAXN;
const UL P = 131313131;
const UL Q = 49999;

int n,m,lim; char pat[MAXN];
UL mat[MAXN][MAXN],PP[MAXN*2],QQ[MAXN*2],tmp[N];

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}	

inline UL GetHash(int x, int y, int L){
	UL ret = 0;
	ret = mat[x][y] + mat[x+L][y+L];
	ret -= mat[x+L][y] + mat[x][y+L];
	return ret*PP[1000-y]*QQ[1000-x];
}

inline void init(){
	m = read(); n = read();
	UL p=P,q; lim = min(n,m);
	for (int j=1;j<=m;j++){
		scanf("%s",pat+1);	
		q = Q;
		for (int i=1;i<=n;i++,q*=Q)
			mat[i][j] = (UL)pat[i]*q*p;
		p *= P;
	}
	for (int i=n;i;i--) for (int j=m;j;j--)
		mat[i][j] += mat[i+1][j]+mat[i][j+1]-mat[i+1][j+1];
	QQ[1] = Q; PP[1] = P;
	for (int i=2;i<=1000;i++) 
		QQ[i] = QQ[i-1]*Q,
		PP[i] = PP[i-1]*P;
}

inline bool judge(int L){
	int cnt = 0;
	for (int i=1;i<=n-L+1;i++) 
		for (int j=1;j<=m-L+1;j++)
			tmp[++cnt] = GetHash(i,j,L);
	sort(tmp+1,tmp+1+cnt);
	int tot = unique(tmp+1,tmp+1+cnt) - tmp - 1;
	return tot != cnt;
}

int main(){
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	init();
	int l=1,r=lim,mid,vout=0;
	while (l <= r){
		mid = (l+r)/2;
		if (judge(mid)) l = mid+1, vout = mid;
		else r = mid - 1;
	}
	printf("%d\n",vout);
	return 0;
}

【BZOJ 3676】[Apio2014] 回文串

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3676
离线版题目:http://paste.ubuntu.com/17527319/
数据生成:http://paste.ubuntu.com/17528560/

哎呀,现在是下午5:47,我为了写这道题,现在周末作业只完成了1/3,呵呵呵呵!
来说一说坎坷的历程吧:
1. 10min 确定 SA + manacher
2. 1h 码完代码
3. 6h 调试代码,BZOJ仍然超时QAQ
4. UOJ上发现原题,提交,通过!
讲到这里,我只能说,BZOJ数据好强!
————————————————— 我是华丽丽的分割线,下面才是正文 ———————————————————
解题思路:manacher找出所有本质不同的回文串,sa来查询出现了多少次
被卡原因:SA模板出错,ST表模板出错,manacher的使用还有一点小问题
HINT:
1.网上很多代码都有问题,比如hzwer的就可以被“abbababbbb”卡掉,正解7,hzwer输出8(他的马拉车写错了)
2.BZOJ数据太强,SA + manacher要T,不过UOJ可过(其实在manacher那里分类讨论的话,也是可以卡过的
3.会用SAM的就不要用SA做死啦(或者你要用DC3应该也是可以过的,但是我不会QAQ
4.会用回文自动机的就不要用manacher做死啦!
5.刚才都说了网上的代码可能有错,所以能过就好
6.此题必须不放过任意一个本质不同的回文串,否则正确性有问题,哎呀刚才自己出的那组数据找不到了QAQ
7.答案会爆int
Inspiration:对于manacher来说,本质不同的回文串一定是能使右边界指针向右移的串
AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 1210000;

char BUF[MAXN],pat[MAXN];
int n,rep[MAXN],LEN[MAXN];
LL vout=1;

inline void init(){
	gets(BUF+1);
	n = strlen(BUF+1);
	for (int i=1;i<=n;i++){
		pat[i*2-1] = 123;
		pat[i*2] = BUF[i];
	} n = n*2+1;
	pat[n]=123; LEN[1] = 0;
	for (int i=2;i<=n;i++)
		LEN[i] = LEN[i>>1]+1;
}

namespace Suffix_Array{
	#define SA Suffix_Array
	#define SIGMA_SIZE 30
	int sa[MAXN],bot[MAXN],t1[MAXN],t2[MAXN],*tmp,*rank;
	int m,height[MAXN];

	namespace Sparse_Table{
		#define ST Sparse_Table
		int mx[MAXN][17];

		inline void init(){
			for (int i=1;i<=n;i++)
				mx[i][0] = height[i];
			for (int i=1,len=1;len<=n;i++,len*=2){
				for (int j=1;j<=n;j++)
					mx[j][i] = min(mx[j][i-1],mx[j+len][i-1]);
			}
		}

		inline int query(int l, int r){
			int t=LEN[r-l+1];
			return min(mx[l][t],mx[r-(1<<t)+1][t]);
		}
	};

	inline void GetHeight(char *s){
		for (int i=1,t=0;i<=n;i++){
			if (t) t--;
			int p1 = i+t, p2 = sa[rank[i]-1]+t;
			while (s[p1++] == s[p2++]) t++;
			height[rank[i]] = t;
		}
		pat[n+1]=125; pat[0]=124;
		ST::init();
	}

	inline void build(char *s){
		m = SIGMA_SIZE; tmp = t1; rank = t2;
		for (int i=1;i<=n;i++) bot[tmp[i]=s[i]-'a'+1]++;
		for (int i=2;i<m;i++) bot[i] += bot[i-1];
		for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
		rank[sa[1]] = m = 1;
		for (int i=2;i<=n;i++)
			if (s[sa[i]] != s[sa[i-1]]) rank[sa[i]] = ++m;
			else rank[sa[i]] = m;

		for (int k=1,T=0;k<=n;k*=2,T=0){
			for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
			for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k;
			for (int i=1;i<=m;i++) bot[i] = 0;
			for (int i=1;i<=n;i++) bot[rank[i]]++;
			for (int i=2;i<=m;i++) bot[i] += bot[i-1];
			for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];

			swap(tmp,rank);
			rank[sa[1]] = m = 1;
			for (int i=2;i<=n;i++)
				if (tmp[sa[i]]==tmp[sa[i-1]] && tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]] = m;
				else rank[sa[i]] = ++m;

			if (m >= n) break;
		}

		GetHeight(s);
	}


	inline int match_right(int s,int len){
		int l = 1, r = n-s,ret=1;
		while (l <= r){
			int mid = (l + r) / 2;
			if (ST::query(s+1,s+mid) >= len) ret = mid, l=mid+1;
			else r = mid-1;
		}
		return ret;
	}

	inline int match_left(int s,int len){
		int l = 1, r = s,ret=1;
		while (l <= r){
			int mid = (l + r) / 2;
			if (ST::query(s-mid+1,s) >= len) ret = mid, l=mid+1;
			else r = mid-1;
		}
		return ret;
	}

	inline int search(int s, int len){
		int ret = 1, pos = rank[s];
		if (height[pos] >= len && pos > 1) ret += match_left(pos,len);
		if (height[pos+1] >= len && pos < n) ret += match_right(pos,len);
		return ret;
	}
};

inline void solve(int i){
	int beg = i-rep[i];
	int t = SA::search(beg,rep[i]*2+1);
	vout = max(vout, (LL)t*(LL)rep[i]);
}

inline void manacher(){
	int itr=0;
	for (int i=1;i<=n;i++){
		if (rep[itr]+itr > i) rep[i] = min(rep[itr*2-i],rep[itr]+itr-i);
		else rep[i] = 0;
		int p1 = i+rep[i], p2 = i-rep[i];
		while (pat[--p2]==pat[++p1])
			rep[i]++, solve(i);
		if (rep[i]+i > rep[itr]+itr) itr = i;
	}
	printf("%lldn",vout);
}

int main(){
	init();
	SA::build(pat);
	manacher();
	return 0;
}

来补一发后缀自动机,这简直是屠场啊!
AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 300000+9;

char pat[MAXN];

namespace Palindromic_Tree{
	#define PAM Palindromic_Tree
	#define SIGMA_SIZE 26
	int ch[MAXN][SIGMA_SIZE],sz[MAXN],fail[MAXN];
	int n,cnt,last,len[MAXN];

	inline void init(){
		cnt = 1;
		fail[0] = fail[1] = 1;
		len[1] = -1;
	}

	inline void expend(int pos, int c, char *s){
		int cur = last;
		while (s[pos-len[cur]-1] != s[pos]) cur = fail[cur];
		if (!ch[cur]){
			int w = ++cnt, k = fail[cur];
			len[w] = len[cur] + 2;
			while (s[pos-len[k]-1] != s[pos]) k = fail[k];
			fail[w] = ch[k]; ch[cur] = w;
		}
		last = ch[cur];
		sz[last]++;
	}

	inline void build(char *s){
		init();
		n = strlen(s+1);
		for (int i=1;i<=n;i++)
			expend(i,s[i]-'a',s);
	}

	inline LL solve(){
		LL ret = 1;
		for (int i=cnt;i;i--){
			sz[fail[i]] += sz[i];
			ret = max(ret, (LL)len[i]*(LL)sz[i]);
		}
		return ret;
	}
};

int main(){
	scanf("%s",pat+1);
	PAM::build(pat);
	printf("%lldn",PAM::solve());
	return 0;
}