【51NOD 1154】回文串划分

相关链接

题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1154
数据生成器:http://paste.ubuntu.com/24310870/

解题报告

可以用鏼爷今年WC讲的技巧把时间复杂度优化到$O(n \log n)$
为了好写,我套了一个$PAM$,不过鏼爷讲直接维护就可以了

Code

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

const int N = 1000000;
const int SGZ = 26;
const int INF = 1e9;

class Palindromic_Tree{
	int tot,cnt,last,fail[N],len[N],ch[N][SGZ];
	int dif[N],nxt[N],ans[N],f[N];
	public:
		inline int build(char *s) {
			fail[0] = fail[1] = cnt = last = 1; 
			tot = strlen(s); len[1] = -1; 
			for (int i=0;i<tot;i++) {
				insert(s, i, s[i]-'a');
				update(i);
			}
			return ans[tot-1];
		}
	private:
		inline void insert(char *s, int p, int c) {
			int w = last;
			for (;s[p-len[w]-1]!=s[p];w=fail[w]);
			if (!ch[w]) {
				int nw=++cnt, t=fail[w]; len[nw] = len[w] + 2;
				for (;s[p-len[t]-1]!=s[p];t=fail[t]);
				fail[nw] = ch[t]; ch[w] = nw;
				
				dif[nw] = len[nw] - len[fail[nw]];
				if (dif[nw] == dif[fail[nw]]) nxt[nw] = nxt[fail[nw]];
				else nxt[nw] = fail[nw];	
			} 
			last = ch[w]; 
		}
		inline void update(int cur) {
			ans[cur] = INF;
			for (int w=last;len[w]>0;w=nxt[w]) {
				f[w] = ans[cur-len[nxt[w]]-dif[w]] + 1;
				if (dif[w] == dif[fail[w]]) f[w] = min(f[w], f[fail[w]]);
				ans[cur] = min(ans[cur], f[w]);
			}
		}
}PAM;

int main() {
	char pat[N]; cin>>pat;
	cout<<PAM.build(pat);
	return 0;
}

【Tsinsen 1393】Palisection

题目传送门:http://www.tsinsen.com/A1393
离线版题目:http://paste.ubuntu.com/17953857/
数据生成器:http://paste.ubuntu.com/17953893/

这一道题目想了很久很久。没有想出来。想统计的量,对于每一个位置是变动的,貌似没有什么数据结构可以维护
于是可耻地看了题解 >︿<
好吧,是在下输了。统计相交的情况比较麻烦,但可以统计不相交的 QAQ
另外提个醒:本题可能会求的回文串的数量,这货最多是O(n)的,有些地方不要忘了开long long或及时取模

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

const int MAXN = 2000000+9;
const LL MOD = 51123987;

char pat[MAXN];
int n;

namespace Palindromic_Tree{
	#define PAM Palindromic_Tree
	#define SIGMA_SIZE 26
	int ch[MAXN][SIGMA_SIZE],sz[MAXN];
	int fail[MAXN],len[MAXN],cnt,last;
	int num[MAXN],rnum[MAXN],ti[MAXN]; 
	LL Sum;
	
	inline int newnode(){
		int ret = ++cnt;
		memset(ch[ret],0,sizeof(ch[ret]));
		len[ret] = fail[ret] = sz[ret] = ti[ret] = 0;
		return ret;
	}
	
	inline void extend(int p, int c){
		int w = last;
		while (pat[p-len[w]-1] != pat[p]) w = fail[w];
		if (!ch[w]){
			int nw = newnode(), k = fail[w];
			while (pat[p-len[k]-1] != pat[p]) k = fail[k];
			len[nw] = len[w]+2; fail[nw] = ch[k]; ch[w] = nw;
			ti[nw] = ti[fail[nw]] + 1; 
		}
		last = ch[w];
		sz[last]++;
	}
	
	inline void build(){
		last = cnt = 1;
		fail[0] = fail[1] = 1;
		len[1] = -1; len[0] = 0;
		for (int i=1;i<=n;i++)
			extend(i,pat[i]-'a'),
			num[i] = ti[last];
		
		last = 1; cnt = -1;
		newnode(); newnode();
		fail[0] = fail[1] = 1;
		len[1] = -1; len[0] = 0;
		for (int i=1;i<=n/2;i++) swap(pat[i],pat[n-i+1]);
		for (int i=1;i<=n;i++) extend(i,pat[i]-'a'), rnum[n-i+1] = (ti[last]+rnum[n-i+2]) % MOD; for (int i=cnt;i>1;i--)
			sz[fail[i]] = (sz[fail[i]]+sz[i]) % MOD,
			Sum = (Sum+sz[i])%MOD;
	}
	
	inline int solve(){
		LL ret = 0;
		for (int i=1;i<n;i++)
			ret = (ret+(LL)num[i]*(LL)rnum[i+1]) % MOD; 
		ret = (Sum*(Sum-1)/2LL)%MOD - ret;
		return int((ret%MOD+MOD)%MOD);
	}
};

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

【Codeforces 100548G】The Problem to Slow Down You

题目传送门:http://codeforces.com/gym/100548 ps:是G题

首先,这个题目肯定可以用manacher配合SA/SAM来完成,然而SA/SAM的代码不好写QAQ
但是我们发现,需要的所有串都是回文串,所以可以建两个PAM,然后一起跑DFS
1A 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*

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

const int MAXN = 200000+9;
const int SIGMA_SIZE = 26;

struct Palindromic_Tree{
	#define PAM Palindromic_Tree
	int ch[MAXN][SIGMA_SIZE],fail[MAXN];
	int cnt,last,n,sz[MAXN],len[MAXN];
	char *pat; LL ret;
	
	inline int newnode(){
		cnt += 1;
		memset(ch[cnt],0,sizeof(ch[cnt]));
		fail[cnt] = sz[cnt] = len[cnt] = 0;
		return cnt;
	}
	
	inline void init(){
		cnt = last = 1; 
		fail[0] = fail[1] = 1;
		sz[0] = sz[1] = len[0] = 0; len[1] = -1;
		memset(ch[0],0,sizeof(ch[0]));
		memset(ch[1],0,sizeof(ch[1]));
	}
	
	inline void extend(int p, int c){
		int w = last;
		while (pat[p-len[w]-1] != pat[p]) w = fail[w];
		if (!ch[w]){
			int nw = newnode(),k=fail[w]; len[nw] = len[w]+2;
			while (pat[p-len[k]-1] != pat[p]) k = fail[k];
			fail[nw] = ch[k]; ch[w] = nw;
		}
		last = ch[w];
		sz[last]++;
	}
	
	inline void build(char *s){
		init(); pat = s;
		n = strlen(s+1);
		for (int i=1;i<=n;i++)
			extend(i,s[i]-'a');
		for (int i=cnt;i;i--)
			sz[fail[i]] += sz[i];
	}
	
	void DFS(int pa, int pb, PAM *s){
		if (pa > 1 && pb > 1) ret += (LL)sz[pa]*(LL)s->sz[pb];
		for (int i=0;i<SIGMA_SIZE;i++)
			if (ch[pa][i] && s->ch[pb][i])
				DFS(ch[pa][i],s->ch[pb][i],s);
	}
	
	inline LL solve(PAM *a){
		ret = 0LL;
		DFS(0,0,a);
		DFS(1,1,a);
		return ret;
	}
}A,B;

char sa[MAXN],sb[MAXN];

int main(){
	int T,TT=0; cin>>T;
	while (T--){
		scanf("%s%s",sa+1,sb+1);
		A.build(sa); B.build(sb);	
		printf("Case #%d: %I64d\n",++TT,A.solve(&B));
	}
	return 0;
} 

【Ural 1960】Palindromes and Super Abilities

题目传送门:http://acm.timus.ru/problem.aspx?space=1&num=1960

PAM板题,一个节点就是一个本质不同的字符串

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

const int MAXN = 100000+9;

char pat[MAXN];

namespace Palindromic_Tree{
	#define PAM Palindromic_Tree
	#define SIGMA_SIZE 26
	int ch[MAXN][SIGMA_SIZE],len[MAXN];
	int fail[MAXN],last,cnt;
	
	inline void extend(int pos, int c){
		int w = last;
		while (pat[pos-len[w]-1] != pat[pos]) w = fail[w];
		if (!ch[w]){
			int nw = ++cnt, k=fail[w]; len[nw] = len[w]+2;
			while (pat[pos-len[k]-1] != pat[pos]) k = fail[k];
			fail[nw] = ch[k]; ch[w] = nw; 
		}
		last = ch[w];
	}
	
	inline void build(char *s){
		fail[0] = fail[1] = 1;
		last = 1; cnt = 1; len[1] = -1;
		int n = strlen(s+1);
		for (int i=1;i<=n;i++)
			extend(i,s[i]-'a'),
			printf("%d ",cnt-1);
	}
};

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

【Tsinsen 1280】最长双回文串

题目传送门:http://www.tsinsen.com/ViewGProblem.page?gpid=A1280
离线版题目:http://paste.ubuntu.com/17832836/

参考BZOJ_3676

#include<iostream>
#include<cstdio>
#include<cstring>
#include
<map>
using namespace std;

const int MAXN = 200000+9;
char pat[MAXN],BUF[MAXN/2];
int n,len[MAXN],vout;

map<int,int>::iterator itr;
map<int,int> Q;

inline void manacher(){
    int mx = 0;
    for (int i=1;i<=n;i++){ if (mx+len[mx] > i) len[i] = min(len[mx*2-i],mx+len[mx]-i);
        else len[i] = 0;
        while (pat[i+len[i]+1] == pat[i-len[i]-1]) len[i]++;
        if (len[i]+i > len[mx]+mx) mx = i;
    }
}

inline void init(){
    scanf("%s",BUF+1);
    n = strlen(BUF+1); vout = 2;
    for (int i=1;i<=n;i++){
        pat[i*2-1] = '*';
        pat[i*2] = BUF[i];
    } pat[n*2+1] = '*';
    n=n*2+1; pat[0]='@'; pat[n+1]='&';
}

inline void solve(){
    for (int i=1;i<=n;i++){ itr = Q.lower_bound(i-len[i]); if (itr != Q.end()){ int p = itr->second;
            vout = max(vout,i-p);
        }
         
        if ((Q.insert(make_pair(i+len[i], i))).second){
            itr = Q.find(i+len[i]);
            if (i >= (++itr)->second && itr != Q.end()) Q.erase(--itr);  
            else{
                itr--;
                while (itr != Q.begin() && (--itr)->second >= i) Q.erase(itr), itr=Q.find(i+len[i]);
            }
        }
    }
}

int main(){
    init();
    manacher();
    solve();
    printf("%d\n",vout);
    return 0;
}

【Tsinsen 1255】拉拉队排练

题目传送门:http://www.tsinsen.com/A1255
离线版题目:http://paste.ubuntu.com/17831783/
数据生成:http://paste.ubuntu.com/17831834/

眼残,没看到只求长度为奇数,调了好久好久 QAQ
另外k可能会爆int QAQ

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

const int MAXN = 1000000+9;
const LL MOD = 19930726;

char pat[MAXN];
int n;

namespace Palindromic_Tree{
    #define PAM Palindromic_Tree
    #define SIGMA_SIZE 26
    int ch[MAXN][SIGMA_SIZE];
    int len[MAXN],sz[MAXN],fail[MAXN],ord[MAXN];
    int last,cnt; char *s; LL tag;
    
    inline bool cmp_sort(const int &a, const int &b){
        return len[a] > len[b];
    }
    
    inline void extend(int pos, int c){
        int w = last;
        while (s[pos-len[w]-1] != s[pos]) w = fail[w];
        if (!ch[w]){
            int nw = ++cnt,k=fail[w];
            len[nw] = len[w]+2;
            while (s[pos-len[k]-1] != s[pos]) k = fail[k];
            fail[nw] = ch[k]; ch[w] = nw; 
        }
        last = ch[w];
        sz[last] ++;
    }
    
    inline void GetSum(){
        for (int i=cnt;i;i--){
            sz[fail[i]] += sz[i];
            ord[i] = i; 
			if (len[i]&1) tag += sz[i];
        }
    }
    
    inline void build(char *S){
        fail[0] = fail[1] = 1; s = S;
        cnt = 1; len[1] = -1; last = 1;
        n = strlen(s+1);
        for (int i=1;i<=n;i++)
            extend(i,s[i]-'a');
        GetSum();
    }
    
    inline LL pow(LL a, LL t){
        LL ret = 1;
        while (t){
            if (t&1) ret *= a, ret %= MOD;
            a *= a; a %= MOD; t >>= 1;
        }
        return ret%MOD;
    }
    
    inline int solve(LL k){
        if (tag < k) return -1;
        else {
            sort(ord+1,ord+1+cnt,cmp_sort); LL ret = 1;
            for (int j=1,i=ord[1];j<=cnt && k;j++,i=ord[j]){
                if (!(len[i]&1)) continue;
				ret *= pow(len[i],min(k,(LL)sz[i]));
                ret %= MOD;
                k = max(0LL,k-(LL)sz[i]);
            }
            return int(ret%MOD);
        }
        
    }
};
int main(){
    LL n,k; cin>>n>>k;
    scanf("%s",pat+1);
    PAM::build(pat);
    printf("%d\n",PAM::solve(k));
    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;
}