技术员博客      html  css  js  c++  java
  • zoj 3296 Mancher 算法 + 最小区间覆盖



    给你一个字符串,问你最少通过几次拼接可以拼成这个串,每次拼接只能拼接两个回文串,可以重叠。

    思路:先求出以每个点为对称轴的所有的最长回文子串代表的区间,本来要考虑是回文串是奇数还是偶数的,不过Mancher算法很好的解决了这个问题。。。。

    接下来就是选取最少的区间覆盖整个区间,然后就是赤裸裸的区间覆盖问题了,用个贪心就可以了:维护一个当前覆盖到的最远的距离now_end,那么接下来要选的线段应该是左端点在now_end的左边,右端点在now_end的右边,且尽可能远的向右延伸。。。。

    Mancher 学习:

    p[i]表示以i为中心的回文半径,
    p[i]-1刚好是原字符串以第i个为中心的回文串长度。
    画画图就知道了,因为两端配匹的肯定是字符g
    Mancher主算法。
    学习地址:http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
    功能:求出以i为中心的回文半径p[i];
    参数:传入构造好的字符串长度
    特殊说明:因为前面加了一个无效字符,所以下标从1开始。
    例题:
    http://acm.hdu.edu.cn/showproblem.php?pid=3068
    http://poj.org/problem?id=3974
    http://acmpj.zstu.edu.cn/JudgeOnline/showproblem?problem_id=3780
    http://acmpj.zstu.edu.cn/JudgeOnline/showproblem?problem_id=3769
    http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=12581#problem/A
    http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3661
    http://acm.hdu.edu.cn/showproblem.php?pid=3948


    本题代码:

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn= 100010;
    namespace M {
    	int n;
    	struct node {
    		int a,b;
    		node() {}
    		node(int _a,int _b):a(_a),b(_b){};
    		bool operator < (const node&cmp) const {
    			return a < cmp.a;
    		}
    	}in[50010];
    	void solve()
    	{
    		int ter = 0;
     		for(int i = 0; i < n; i++) ter = max(ter,in[i].b);
    		sort(in,in+n);
    		int ans = 0, pt = 0 , now_end = in[0].a;
    		while(true)
    		{
    			if(now_end > ter)  break;
    			int mx = -1;
    			while(pt < n)
    			{
    				if(in[pt].a <= now_end)
    				{
    					if(in[pt].b>mx)  mx=in[pt].b;
    					pt ++;
    				}
    				else 
    				{
    					break;
    				}
    			}
    			now_end = mx + 1;
    			ans ++;
    		}
    		printf("%d\n",ans-1);
    	}
    }
    struct Mancher {
    	char str[maxn];//start from index 1
    	int p[maxn];
    	char s[maxn];
    	int n;
    	void checkmax(int &ans,int b){
    		if(b>ans) ans=b;
    	}
    	inline int min(int a,int b){
    		return a<b?a:b;
    	}
    	void kp(){
    		int i;
    		int mx = 0;
    		int id;
    		for(i=1; i<n; i++){
    			if( mx > i )
    				p[i] = min( p[2*id-i], p[id]+id-i );
    			else
    				p[i] = 1;
    			for(; str[i+p[i]] == str[i-p[i]]; p[i]++) ;
    			if( p[i] + i > mx ) {
    				mx = p[i] + i;
    				id = i;
    			}
    		}
    	}
    	void pre()
    	{
    		int i,j,k;
    		n = strlen(s);
    		str[0] = '$';
    		str[1] = '#';
    		for(i=0;i<n;i++)
    		{
    			str[i*2 + 2] = s[i];
    			str[i*2 + 3] = '#';
    		}
    		n = n*2 + 2;
    		str[n] = 0;
    	}
    	void solve() // 求出所有的最长回文子串所在的区间
    	{
    		int & tot = M::n;
    		tot = 0;
    		for(int i = 2; i < n; i++)
    		{
    			if(i%2&&p[i]==1) continue;
    			if(i%2)
    			{
    				M::in[tot++] = M::node(i/2-p[i]/2+1,i/2+p[i]/2);
    				//printf("%d %d\n",i/2-p[i]/2+1,i/2+p[i]/2);
    			}
    			else 
    			{
    				M::in[tot++] = M::node(i/2-(p[i]/2-1),i/2+(p[i]/2-1));
    				//printf("%d %d\n",i/2-(p[i]/2-1),i/2+(p[i]/2-1));
    			}
    		}
    	}
    }task1;
    int main()
    {
    	while( scanf("%s", task1.s) !=EOF )
    	{
    		task1.pre();
    		task1.kp();
    		task1.solve();
    		M::solve();
    	}
    	return 0;
    }


  • 相关阅读:
    BeyondTrack 项目管理与团队协作工具
    Json简单学习
    艾伟:DynamicControl/DynamicField 例外的解决 狼人:
    百度词条近500万数据 有尝提供
    Simple way to export SQL Server data to Text Files
    Computer Programming Languages Y
    XMind:又一款开源且跨平台的思维导图软件
    上传图片时预览效果
    C++开源库详细介绍
    vi编辑器的学习使用(十八)
  • 原文地址:https://www.cnblogs.com/javawebsoa/p/2989567.html
Copyright © 2011-2022 技术员博客