【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;
}

【Tricks】STL容器使用指南

1.set.insert() 的返回值是 pair;, 其中bool表示是否插入成功
2.set/map当中的earse() 是完全没有检查机制的(我TM都比他写得好!),使用的时候一定要小心
3.set/map/priority_queue可以仅重载其中的比较符号,例如:

struct CMP{
	bool operator () (const int &a, const int &b){
		return a < b;
	}
};

set<int,CMP> S;
map<int,int,CMP> M;
priority_queue<int,vector<int>,CMP> Q;

4.map使用[]进行访问的时候,即使仅仅是查询、不是赋值,map仍然会新建一个节点
5.sort排序传进去的尾地址不会参与排序

【BZOJ 3790】神奇项链

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3790
离线版题目:http://paste.ubuntu.com/17470379/
吐槽:板题,直接上代码不解释

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

const int MAXN = 120000;

char pat[MAXN],chr[MAXN];
int n,l[MAXN],r[MAXN],len[MAXN],ord[MAXN];

namespace FenwickTree{
	#define BIT FenwickTree
	#define low(x) (x&(-x))
	#define INF 1000000000
	int arr[MAXN],buf[MAXN];

	inline void init(){
		for (int i=1;i<=n;i++)
			arr[i] = buf[i] = INF;
	}

	inline int query(int left, int right){
		if (right < left) return INF; else { int ret = INF; while (right >= left){
				if (right-low(right)+1>=left) ret = min(ret,arr[right]),right-=low(right);
				else ret = min(ret,buf[right]), right--;
			}
			return ret;
		}
	}

	inline void modify(int pos, int nv){
		if (buf[pos] > nv) {
			buf[pos] = nv;
			for (int i=pos;i<=n;i+=low(i)) if (arr[i] > nv) arr[i] = nv;
				else break;
		} else return;
	}
};

inline bool sort_cmp(const int &A, const int &B){
	return r[A] < r[B];
}

inline int manacher(){
	int m=n*2+1,itr=0;
	for (int i=1;i<=n;i++)
		chr[i*2-1] = '@',
		chr[i*2] = pat[i];
	chr[m] = '@'; chr[m+1] = '#'; chr[0] = '$';

	for (int i=1,p1,p2;i<=m;i++){ if (itr+len[itr] > i)  len[i] = min(len[2*itr-i],itr+len[itr]-i);
		else len[i] = 0;
		p1 = i-len[i]; p2 = i+len[i];
		while (chr[--p1] == chr[++p2]) len[i]++;
		if (itr+len[itr] < i+len[i]) itr = i;
	}

	for (int i=1;i<=m;i++)
		r[i] = i+len[i],
		l[i] = i-len[i],
		ord[i] = i;
	sort(ord+1,ord+m,sort_cmp);

	n = m; BIT::init(); BIT::modify(1,0);
	for (int j=1,i=ord[j],tmp;j<=n;j++,i=ord[j]){
		tmp = BIT::query(l[i],r[i]-1)+1;
		BIT::modify(r[i],tmp);
	}

	return BIT::query(m-1,m)-1;
}

int main(){
	while (~scanf("%s",pat+1)){
		n = strlen(pat+1);
		printf("%dn",manacher());
	}
	return 0;
}