首页 > 其他分享 >UVA 1204

UVA 1204

时间:2022-11-03 14:13:06浏览次数:68  
标签:std 子串 包含 1204 即可 字符串 UVA 减去

好久没写题解了,现在写一篇。

首先我们可以想到一个\(O(n^2)\)DP——\(f(S,i,0/1)\)表示当前我们考虑字符串集合为\(S\),最后一个字符串为\(i\),是正着还是反着放的。(这类“正反”是相较于第一个字符串而言)

转移时,枚举下一个字符串,减去和\(i\)相交的部分长度即可,最后统计答案时,由于是个环,我们还要减去最后一个选择的字符串和第一个字符串的相交部分长度。

真的就这么简单吗?

有两个问题:

  1. 出现包含关系怎么办?

  2. 如果有一个或多个子串串是转了很多圈得到的怎么办?

第一个问题很好解决——对于一个字符串\(S\),存在另一个子串\(T\)的子串\(T'=S\),那么\(S\)完全包含于\(T\)中,去掉\(S\)即可。

比如样例\(2\),GBBBG是BGGGBBBGG的子串,那么我们就只考虑BGGGBBBGG即可。

第二个问题困扰了我很久。其实是没有关系的。

设最终答案长为\(L\)。

如果\(A\)是转了\(a\)圈的,剩下\(a'\)个字符(\(|A|=a\times L+a'\)),\(B\)是转了\(b\)圈,剩下\(b'\)个字符的(\(|B|=b\times L+b'\))。

如果\(a<b\),那么\(A\)将完全包含在\(B\)中;否则如果\(a>b\),\(B\)将包含在\(A\)中;\(a=b\)时,我们减去相交的部分,剩下的长度不会超过\(L\)。

所以即使\(|A|,|B|\)都大于\(L\),我们仍然能得到正确的答案。

还有,注意特判去掉包含关系后,只剩下一个字符串的情况。我们只需枚举最终环长\(L\),暴力检查即可。

附上冗余的代码:

#include<bits/stdc++.h>
#define debug(...) std::cerr<<#__VA_ARGS__<<" : "<<__VA_ARGS__<<std::endl
int n,share[20][2][20][2],f[1<<20][20][2];
int main() {
	while(std::cin>>n&&n) {
		memset(share,0,sizeof share);
		std::vector<std::string> str(n);
		for(auto &item : str) std::cin>>item;
		for(int i=0;i<(int)str.size();) {
			bool is=1;
			for(int j=0;j<(int)str.size();j++) {
				if(i==j||str[j].size()<str[i].size()) continue;
				for(int k=0;k<=(int)str[j].size()-(int)str[i].size();k++) {
					if(str[j].substr(k,(int)str[i].size())==str[i]) {
						is=0;
						break;
					}
				}
				if(!is) break;
			}
			if(!is) {
				str.erase(str.begin()+i);
			} else i++;
		}
	//	for(auto item : str) std::cout<<item<<'\n';
		if((int)str.size()==1) {
			std::string s=str[0];
			if(s.size()==1) printf("2\n");
			else {
				for(int leap=2;leap<=(int)s.size();leap++) {
					bool chk=1;
					for(int i=leap;i<(int)s.size();i++) {
						if(s[i]!=s[i%leap]) {
							chk=0;
							break;
						}
					}
					if(chk) {
						printf("%d\n",leap);
						break;
					}
				}
			}
			continue;
		}
		for(int i=0;i<(int)str.size();i++) for(int j=0;j<(int)str.size();j++) {
			if(i==j) continue;
			for(int p1=0;p1<2;p1++) for(int p2=0;p2<2;p2++) {
				std::string x=str[i],y=str[j];
				if(p1) std::reverse(x.begin(),x.end());
				if(p2) std::reverse(y.begin(),y.end());
				for(int k=0;k<(int)x.size();k++) {
					if(k+(int)y.size()<=(int)x.size()) continue;
					int is=1;
					for(int l=k,m=0;l<(int)x.size();l++,m++) {
						if(x[l]!=y[m]) {
							is=0;
							break;
						}
					}
					if(is) {
						share[i][p1][j][p2]=(int)x.size()-k;
						break;
					}
				}
			}
		}
		int S=1<<(int)str.size();
		for(int i=0;i<S;i++) {
			for(int j=0;j<n;j++) {
				for(int p=0;p<2;p++) {
					f[i][j][p]=1000000000;
				}
			}
		}
		f[1][0][0]=(int)str[0].size();
		for(int i=0;i<S;i++) {
			for(int j=0;j<n;j++) {
				for(int p=0;p<2;p++) {
					if(f[i][j][p]==1000000000) continue;
					for(int k=0;k<n;k++) {
						if(i>>k&1) continue;
						for(int q=0;q<2;q++) {
							f[i|(1<<k)][k][q]=std::min(f[i|(1<<k)][k][q],f[i][j][p]+(int)str[k].size()-share[j][p][k][q]);
						}
					}
				}
			}
		}
		int ans=1000000000;
		for(int j=1;j<n;j++) {
			for(int p=0;p<2;p++) {
				if(f[S-1][j][p]==1000000000) continue;
				ans=std::min(ans,f[S-1][j][p]-share[j][p][0][0]);
			}
		}
		printf("%d\n",std::max(ans,2));
	}
	return 0;
}

标签:std,子串,包含,1204,即可,字符串,UVA,减去
From: https://www.cnblogs.com/Nastia/p/16854263.html

相关文章

  • uva 12563 Jin Ge Jin Qu hao
    01背包,这题设计状态f[i][j]为刚好用完时间j时的歌曲数,这样方便找到用时(初始化设置一下就好 #include<iostream>#include<algorithm>#include<cstring>usingna......
  • uva
    数轴上有 nn 个施工队 a[1…n],m 个受损的防御位点 b[1…m],每个施工队都要进入一个防御位点,而且每个防御位点都要有人进入,问施工队最少需要移动多少距离。 先排序......
  • UVA12003 Array Transformer(分块,块内二分)
    我们考虑用分块来水过此题我们先将原序列进行分块,对于某个块\(B\)内的数,我们把它们放进一个数组\(block[B][\]\)里,再对数组进行排序。那么我们就得到了\(\sqrt{n}\)......
  • UVA11297 Census(kd-tree)
    题意:给定一个\(n\timesn\)的网格,要求支持修改和询问某个矩阵的最大值和最小值。解法多样,可以用二维线段树,我用的是\(kd-tree\)。那么这题就很裸了,我在这里只提几点需......
  • UVA10384 推门游戏 The Wall Pushers(IDA_,A_)
    题目大意给你一个\(4\times6\)的网格图,网格边缘上可能有墙。对于每一个网格有一个权值\(val\),其中\[\begin{aligned}val=&&1(\text{如果这个网格左边缘(西边缘)有墙......
  • uva 590
    一共有n座城市,要在这n座城市旅游k天,从城市1出发,第k天到达城市n。输入有n*(n-1)行,每n-1行代表i到除了i之外的其他城市航班的天数以及价格。求最小花费。  #include......
  • uva 473
    有n首歌,每首时长Ti,要把这n首歌装进m个光盘里面,每个光盘最多能存的时长为t. 要求这些歌在光盘里面要按照所给歌的先后顺序存入,不能改变前后顺序. 例如有4首歌,按顺序......
  • uva 442
    矩阵连乘用栈处理表达式((AB)C)#include<iostream>#include<cstdio>#include<string>#include<stack>usingnamespacestd;structM{inta,b;......
  • uva 10453
    将字符串变为回文串最少需要几次操作(在任意位置插入字符),并输出变化后的回文串f[l][r]=f[l+1][r-1]//a[i]==a[j]=min(f[l+1][r],f[l][r-1])#include<iostre......
  • uva 10163
    n个仓库,安排m个人看守,每个仓库只由一个人看守,每个人对应a[i],表示能量(薪水)如果某个人看守k个仓库,每个仓库能量值a[i]/k求仓库能量最小值最大时,所支付薪水最少值  ......