AcWing 3269. CIDR合并
原题链接
中等
作者:
自由的犇儿哥
,
2021-08-26 21:41:40
,
所有人可见
,
阅读 315
主要的思路就是将IP地址转换为一个32位的无符号正整数。只要这一步做到了,后面的工作就容易了
- 代码无法通过最后一个测试数据,原因是超时
- 官网测评为90分,原因也是超时
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <string>
using namespace std;
#define MAX 100500
#define GAP 1 << 8
inline unsigned int getlen(int c)
{
return 1 << (c * 8);
}
struct Item
{
string addrstr;
int len;
unsigned int addr;
bool operator<(const Item &a)const
{
if (addr != a.addr)
return addr < a.addr;
else
{
return len < a.len;
}
}
void getaddr(vector<unsigned int> num)
{
addr = 0;
for (int i = 0; i < num.size(); i++)
{
addr |= (num[i] << ((3 - i) * 8));
}
}
} items[MAX];
int countpoint(string &str)
{
int ans = 0;
for (char &c : str)
{
if (c == '.')
ans++;
}
return ans;
}
void getnums(string &str, vector<unsigned int> &num)
{
int l = 0, r = 0;
while (r < str.size())
{
while (r < str.size() && str[r] != '.')
r++;
string tnum = str.substr(l, r - l);
num.push_back(stoi(tnum));
l = r + 1;
r++;
}
}
void dealaddstr(string &str, int id)
{
int loc = str.find('/');
if (loc == string::npos)
{
//省略长度型
int cnt = countpoint(str);
vector<unsigned int> num;
getnums(str, num);
items[id].addrstr = str;
items[id].len = (cnt + 1) * 8;
items[id].getaddr(num);
}
else
{
string add = str.substr(0, loc);
string lenstr = str.substr(loc + 1);
int len = stoi(lenstr);
vector<unsigned int> num;
getnums(add, num);
items[id].addrstr = add;
items[id].len = len;
items[id].getaddr(num);
}
}
unsigned int getmask(int prelen)
{
if (prelen == 0)
return 0;
unsigned int mask = 0xffffffff;
unsigned int maskpost = mask << (32 - prelen);
return mask & maskpost;
}
bool merge2(int l, int r)
{
unsigned int left = items[l].addr;
unsigned int right = items[r].addr;
int len = items[l].len;
unsigned int mask = getmask(len);
return (left & mask) == (right & mask);
}
bool merge3(int l, int r, Item &newItem)
{
unsigned int left = items[l].addr;
unsigned int right = items[r].addr;
int len = items[l].len - 1;
unsigned int mask = getmask(len);
bool flag = ((left & mask) == (right & mask));
if (flag == 0)
return false;
else
{
newItem.len = len;
newItem.addr = left & mask;
return true;
}
}
void dealnum(unsigned int num, int len)
{
unsigned int n1 = (num & (unsigned int)0xff000000) >> 24;
unsigned int n2 = (num & (unsigned int)0x00ff0000) >> 16;
unsigned int n3 = (num & (unsigned int)0x0000ff00) >> 8;
unsigned int n4 = num & (unsigned int)0x000000ff;
cout << n1 << "." << n2 << "." << n3 << "." << n4 << "/" << len << endl;
}
int main()
{
// freopen("sb.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
dealaddstr(str, i);
}
sort(items, items + n);
for (int i = 0; i < n - 1;)
{
if (1 && merge2(i, i + 1))
{
for (int k = i + 1; k < n - 1; k++)
{
items[k] = items[k + 1];
}
n--;
}
else
{
i++;
}
}
for (int i = 0; i < n - 1;)
{
if (items[i].len != items[i + 1].len)
{
i++;
continue;
}
else if (merge3(i, i + 1, items[i]))
{
for (int k = i + 1; k < n; k++)
{
items[k] = items[k + 1];
}
n--;
if (i)
i--;
}
else
{
i++;
}
}
// cout << n << endl;
for (int i = 0; i < n; i++)
{
dealnum(items[i].addr, items[i].len);
}
return 0;
}