简介
- 这题乍一看很像操作系统内存管理的 伙伴(Buddy)算法
- 这里给出一个类似线段树的算法,一共 63 行
- 官网测试为 125 ms,这里测试为 237 ms,应该算是一个正解
算法原理
- 线段树的原理就不谈了
- 线段树的根结点表示的地址区间为无符号整数的取值范围
[0u, ~0u]
- 可以证明:此线段树的每一个结点与每一种 IP 前缀一一对应
算法流程
- 线段树结点维护一个
tag
标记
tag
值为 0
:表示不存在这个区间的地址
tag
值为 1
:表示这个区间的地址全部存在
tag
值为 2
:表示这个区间的地址部分存在
- 初始化区间为
[0u, ~0u]
,即最小地址和最大地址
- 插入时向下寻找区间范围
[l, r]
与地址范围相等的一个结点
- 最后一趟 dfs 输出结果
- 遇到
tag == 1
的结点:输出地址区间
- 遇到
tag == 2
的结点:向下递归
- 遇到
tag == 0
的结点:什么也不做
注意点
- 插入时遇到
tag == 1
的结点表明此区间已全部存在,不应该继续向下
- 注意各个地方的取值,避免溢出
C++ 代码
#include <iostream>
using namespace std;
typedef unsigned uint;
const int N = 1e7 + 5;
struct Node
{
int tag;
int lc, rc;
} tr[N];
int idx = 1;
#define cur tr[x]
#define lch tr[cur.lc]
#define rch tr[cur.rc]
#define mid ((l >> 1) + (r >> 1))
void merge(int x)
{
cur.tag = lch.tag == 1 && rch.tag == 1 ? 1 : 2;
}
void pushdown(int x)
{
if (!cur.lc)
cur.lc = ++idx, cur.rc = ++idx;
}
uint L, R;
void insert(int x, uint l, uint r)
{
if (cur.tag == 1)
return;
else if (l == L && r == R)
cur.tag = 1;
else
{
pushdown(x);
if (mid >= L)
insert(cur.lc, l, mid);
if (mid < R)
insert(cur.rc, mid + 1, r);
merge(x);
}
}
void print(uint l, uint r)
{
uint size = r - l;
int mask = 32;
while (size)
size >>= 1, mask--;
int num[4];
for (int i = 3; i >= 0; i--)
num[i] = l & 255u, l >>= 8;
for (int i = 0; i <= 3; i++)
printf("%d%c", num[i], i == 3 ? '/' : '.');
printf("%d\n", mask);
}
void dfs(int x, uint l, uint r)
{
if (cur.tag == 1)
print(l, r);
else if (cur.tag == 2)
dfs(cur.lc, l, mid), dfs(cur.rc, mid + 1, r);
}
int n;
void process(string s)
{ // 转化IP前缀为取值区间,插入线段树
uint l = 0u;
int i = -1, j = 0, mask = -1, cnts = 0;
for (; j != s.size() && s[j] != '/'; j++)
if (s[j] == '.')
cnts++, i++, l = l << 8 | stoi(s.substr(i, j - i)), i = j;
i++, l = l << 8 | stoi(s.substr(i, j - i));
if (j != s.size())
mask = 32 - stoi(s.substr(j + 1));
else
mask = 24 - 8 * cnts;
l <<= 8 * (3 - cnts);
L = l, R = l | (1u << mask) - 1,
insert(1, 0u, ~0u);
}
char s[20];
int main()
{
scanf("%d", &n);
while (n--)
scanf("%s", s), process(s);
dfs(1, 0u, ~0u);
}
dalao%%%