dfs类的题，感觉应该还能再优化，时间用了0.9s+，挺长的。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<vector>
using namespace std;
struct Node{
string s;
unsigned long long t;
Node *left,*right;
Node():t(0),left(NULL),right(NULL){}
};
Node *root;
int cnt1,cnt2,cnt;
vector<unsigned long long>heavy;
Node* newnode(){
return new Node;
}
void build(Node* a,int n){
int i,k=0;
if(a->s.find("[")==string::npos){
stringstream ss(a->s);
ss>>a->t;
cnt1++;
heavy.push_back(a->t<<n);
return;
}
a->left=newnode();
for(i=1;i<a->s.length();i++){
if(a->s[i]=='[') k++;
if(a->s[i]==']') k--;
if(!k&&a->s[i]==',') break;
a->left->s+=a->s[i];
}
a->right=newnode();
for(i++;i<a->s.length()-1;i++)
a->right->s+=a->s[i];
build(a->left,n+1);
build(a->right,n+1);
return;
}
int main(){
int t;
cin>>t;
while(t--){
string s;
cin>>s;
cnt1=0;
cnt2=cnt=1;
root=newnode();
root->s=s;
build(root,0);
sort(heavy.begin(),heavy.end());
for(int i=0;i<heavy.size()-1;i++){
if(heavy[i]==heavy[i+1]) cnt++;
else cnt=1;
cnt2=max(cnt2,cnt);
}
cout<<cnt1-cnt2<<endl;
heavy.clear();
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **