首页 > 代码库 > Topcoder SRM 630div 2
Topcoder SRM 630div 2
A:不断的消除两个相邻的相等字符,简单题。
真心不习惯STL。。
#include<iostream>#include <string>#include <vector>using namespace std;class DoubleLetter { public: string ableToSolve(string S) { while (1){ int flag=0; for (int i=1;i<S.size();i++) if (S[i]==S[i-1]) { S.erase(i-1,2); flag=1; } if (!flag||S.size()==0) break; } if (S.size()==0) return "Possible"; else return "Impossible"; }};// Powered by FileEdit// Powered by TZTester 1.01 [25-Feb-2003]// Powered by CodeProcessor
B:给出有N个节点一棵树,求在M个两两的点距离相等求出最大的M值(N<=10);
先FLoyd求出所有点与点之间的距离。
然后用类似状态压缩DP的方式枚举满足的方案。
然后比较出最大值。
#include<iostream>#include <string>#include <vector>#include<string.h>using namespace std;int b[12345];int dis[12][12];int mp[12][12];class Egalitarianism3Easy { public: int maxCities(int n, vector <int> a, vector <int> b, vector <int> len) { memset(dis,0x3f3f3f,sizeof(dis)); for (int i=1;i<=n;i++) dis[i][i]=0; for (int i=0;i<a.size();i++) dis[a[i]][b[i]]=dis[b[i]][a[i]]=len[i]; for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); int Max=1; for (int i=1;i<(1<<n);i++) { vector<int> V; V.clear(); for (int j=0;j<n;j++) if (((i>>j)&1)==1) V.push_back(j+1); int m=V.size(); int same=dis[V[0]][V[m-1]]; int flag=1; for (int k=0;k<m;k++) for (int j=0;j<m;j++) if (k!=j&&dis[V[k]][V[j]]!=same) { flag=0; break; } if (flag) Max=max(Max,m); } return Max; }};
C:很锻炼思维的题目。
参考他人的做法:
用类似后缀数组的方式。
只是数组套数组真心醉了。
我的方案是求出满足跟S一样序号的最小的字符串,然后比较与S的值.
代码中有详细注释。
#include<iostream>#include <string>#include <vector>#include<string.h>#include<algorithm>using namespace std;class SuffixArrayDiv2 { public: string arr[100]; int p[100],a[100]; //注意P:表示字符串排完序后,所对应原来数组的下标 // A:表示原先字符串在排序后的下标 // 这里很绕,熟悉后缀数组的应该了解 char c[100]; string smallerOne(string s) { for (int i=0;i<s.size();i++) arr[i]=&s[i];//保存后缀 sort(arr,arr+s.size()); int len=s.size(); for (int i=0;i<s.size();i++){ p[i]=len-arr[i].size(); a[len-arr[i].size()]=i; } a[len]=-1; c[p[0]]=‘a‘; for (int i=1;i<len;i++){ if (a[p[i-1]+1]<a[p[i]+1]) c[p[i]]=c[p[i-1]]; //这个表示:我们确定位置为p[i]的字符, //如果当前字符串s1,与后面的字符串s2(都是排序后的字符串) //比较它们后面+1的字符串的大小。这里可以忽视我的解释 else c[p[i]]=c[p[i-1]]+1; } string ans; for (int i=0;i<len;i++) ans+=c[i]; if (ans<s) return "Exists"; else return "Does not exist"; }};int main(){ SuffixArrayDiv2 b; string s; cin>>s; cout<<b.smallerOne(s); return 0;}
Topcoder SRM 630div 2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。