UVaOJ 1590 - IP Networks

问题描述

解法一：位运算 + 贪心

核心思路是，将输入全部处理成 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 位），等于没有进行移动。

#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;
}

#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;

}

#TODO

#TODO

AOAPC II UVaOJ