soyana66687@gmail.com
(Dino\n)
學校
:
國立臺中科技大學
編號 : 97371
來源 : [60.250.9.66]
最後登入時間 ：
2022-07-02 20:52:24
自己已經使用 判斷字串奇數 和 一比對到不符合的字直接跳出迴圈 這兩個方法使自己的程式能快一點
但是仍然TLE......
請問各位大神有甚麼辦法能夠解決?
#include <iostream>
#include <vector>
using namespace std;
int main(){
int m;
while(cin>>m){//處理輸入
vector<string>v;
int total=0;
for(int i=0;i<m;i++){
string s;
cin>>s;
v.push_back(s);
}
//處理輸出
for(int i=0;i<m;i++){
for(int j=(i+1);j<m;j++){
string comp=v[i]+v[j]//將字串結合在一起
int comp_length=comp.length();//如果字串長度是奇數，絕對不符合
if(comp_length%2!=0)continue;
int mid=(comp_length)/2;
bool compare=true;//判斷是否符合
for(int k=0;k<mid;k++){//將字串用mid分成前半後半
if(comp[k]!=comp[mid+k]){
compare=false;
break;
}
}
if(compare)total++;
}
}
cout<<total<<endl;
}
return 0;
}
自己已經使用 判斷字串奇數 和 一比對到不符合的字直接跳出迴圈 這兩個方法使自己的程式能快一點
但是仍然TLE......
請問各位大神有甚麼辦法能夠解決?
#include
#include
using namespace std;
int main(){
int m;
while(cin>>m){//處理輸入
vectorv;
int total=0;
for(int i=0;i<m;i++){
string s;
cin>>s;
v.push_back(s);
}
//處理輸出
for(int i=0;i<m;i++){
for(int j=(i+1);j<m;j++){
string comp=v[i]+v[j]//將字串結合在一起
int comp_length=comp.length();//如果字串長度是奇數，絕對不符合
if(comp_length%2!=0)continue;
int mid=(comp_length)/2;
bool compare=true;//判斷是否符合
for(int k=0;k<mid;k++){//將字串用mid分成前半後半
if(comp[k]!=comp[mid+k]){
compare=false;
break;
}
}
if(compare)total++;
}
}
cout<<total<<endl;
}
return 0;
}
這方法太慢了，先以複雜度的觀點這樣完全行不通，畢竟你不能窮舉每個字串的組合，這樣光枚舉就已經O(m^2)，就已經超過10^9，而且這還不包括判斷(複雜度可能再乘個L)，就算你加速這個方法也不行吧!
linlincaleb@gmail.com
(臨末之頌)
學校
:
新北市立板橋高級中學
編號 : 132772
來源 : [111.248.111.135]
最後登入時間 ：
2023-04-01 22:41:13