问题描述
p1590相关说明：本题为《算法竞赛入门经典（第2版）》习题 4-5
解法一：位运算 + 贪心
核心思路是，将输入全部处理成 unsigned int 形式后，从 0 开始贪心算 bits ，看多大的 bits 空间能满足当前的网络规模（实际操作就是右移 bits 运算后，看剩下的值是否相等）。将掩码 mask 初始化为 0xFFFFFFFF, 根据贪心得到的结果右移再左移 bits 位就得到了最终的掩码。
容易 Wrong Answer 的点：忽略了需要 32 个 bits 的极端情况。要知道对于 uint32 做位运算时，会先对 32 取余数，即如果右移动 32 位等于右移动 0 位，而不是直接变成 0. 这就会导致什么情况呢？如果题目输入的某个样例差异涵盖了所有的 32 位地址，即这个时候子网掩码是 0.0.0.0, 等同于不存在子网这个概念，整个 IP 范围直接从 0x00000000 到 0xFFFFFFFF. 如果不做特判，题目中的 (mask >> bits) << bits 操作为移动 32 位（即 0 位），等于没有进行移动。
|
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 |
#include <bits/stdc++.h> using namespace std; string to_ip(unsigned int value) { string ip = ""; for (int bits = 24; bits >= 0; bits -= 8) { ip += to_string(value >> bits & 0xFF); ip += bits ? "." : ""; } return ip; } int main() { int num; while (cin >> num) { char dot; unsigned int a, b, c, d, value; vector<unsigned int> address; for (int i = 0; i < num; ++i) { cin >> a >> dot >> b >> dot >> c >> dot >> d; value = (a << 24) + (b << 16) + (c << 8) + d; address.push_back(value); } int bits = 0; for (auto addr: address) for (;bits < 32 && (addr >> bits) != (value >> bits); bits++); unsigned int mask = 0xFFFFFFFF, subset; mask = (bits == 32 ? 0x00000000 : (mask >> bits) << bits); subset = value & mask; cout << to_ip(subset) << "\n" << to_ip(mask) << endl; } return 0; } |
|
1 |
#TODO |
