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

?

轉載于:https://www.cnblogs.com/forgot93/p/3931479.html

總結

以上是生活随笔為你收集整理的Topcoder SRM 630div 2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。