首页 > 代码库 > 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