MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1590 - IP Networks
AOAPC II

UVaOJ 1590 - IP Networks

Chai
2021-11-24 0:00:00在线评测阅读 354

问题描述

p1590

原题链接:UVaOJ 1590 - IP Networks

相关说明:本题为《算法竞赛入门经典(第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 位),等于没有进行移动。

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz