看着很长的一道题目,其实还可以...但我只有90分...可能有些细节没有注意到...难受!
思路:
数据结构:
string str ; 存储32位01串
int len: 前缀长度
首先将输入的ip标准化,使用了split()函数,和find(),substr()的string_STL
自定义排序
大小合并 : 从前往后
同级合并: 从后往前
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef vector <string> vs; 4 const int N=1e6+7; 5 string zero="00000000"; 6 struct node { 7 string str; 8 int len; 9 bool operator<(const node& x) const { 10 if (str==x.str) return len<x.len; 11 return str<x.str; 12 } 13 }; 14 node t[N],tmp[N]; int n; 15 vs split(string str,const char flag='.') { 16 istringstream iss(str); 17 vs ans; 18 while (getline(iss,str,flag)) 19 if (str.size()) 20 ans.push_back(str); 21 return ans; 22 } 23 int to_int (string str,int base) { 24 int ans=0; 25 for (int i=0;i<str.size();i++) 26 ans=ans*base+str[i]-'0'; 27 return ans; 28 } 29 void get_str (string &str, vs sv) { 30 for (int i=0;i<sv.size();i++) { 31 int num=to_int(sv[i],10); 32 for (int j=1;j<=8;j++) { 33 str[(i+1)*8-j]='0'+num%2; 34 num=num/2; 35 } 36 } 37 //cout<<str<<endl; 38 } 39 void input_node (node &x ) { 40 x.str=zero; 41 string str; cin>>str; 42 int pos=str.find("/"); 43 if (pos==-1) { 44 vs sv=split(str); 45 x.len=8*sv.size(); 46 get_str(x.str,sv); 47 } 48 else { 49 string s1=str.substr(0,pos),s2=str.substr(pos+1); 50 x.len=to_int(s2,10); 51 vs sv=split(s1); 52 get_str(x.str,sv); 53 } 54 } 55 void output_node (node x) { 56 for (int i=0;i<4;i++) { 57 cout<<to_int(x.str.substr(i*8,8),2); 58 if (i!=3) cout<<"."; 59 else cout<<"/"; 60 } 61 cout<<x.len<<" "; 62 } 63 bool isok (node t1,node t2) { 64 if (t1.len<t2.len) return 0; 65 for (int i=0;i<t2.len;i++) 66 if (t1.str[i]!=t2.str[i]) 67 return 0; 68 return 1; 69 } 70 void merg1() { 71 int cnt=1; 72 for (int i=2;i<=n;i++) 73 if (!isok(t[i],t[cnt])) 74 t[++cnt]=t[i]; 75 n=cnt; 76 } 77 bool isok2 (node t1,node t2) { 78 if (t1.len!=t2.len) return 0; 79 for (int i=0;i<t1.len-1;i++) 80 if (t1.str[i]!=t2.str[i]) 81 return 0; 82 return 1; 83 } 84 void merg2() { 85 int cnt=0; 86 for (int i=n;i>=1 ;i--) { 87 if (i>=2&&isok2(t[i],t[i-1])) t[i-1].len--; 88 else tmp[++cnt]=t[i]; 89 } 90 for (int i=1;i<=cnt;i++) 91 t[i]=tmp[cnt-i+1]; 92 n=cnt; 93 } 94 int main () 95 { 96 ios::sync_with_stdio(false); 97 zero+=zero; zero+=zero; 98 cin>>n; 99 for (int i=1;i<=n;i++) input_node(t[i]); 100 sort (t+1,t+1+n); 101 merg1(); 102 merg2(); 103 for (int i=1;i<=n;i++) 104 output_node(t[i]); 105 return 0; 106 }