子网（出题人题解）

题解应该只给思路，参考实现也是这样，所以我就给 rust 的

这题就是一个计算机网络的题目，难度的话应该算区域赛的签到题吧。

题目大意

给你一个CIDR的 IPv6 的网段，判断 $n$ 个 IP 是不是它的子网。

思路

这题难点主要在还原地址，其实我们可以这样想，用两数组，分解记录::前后的字段，然后求出缺多少个字段，最后补 $0$ 就好了。

然后转成二进制，判断二进制表示前 $mask$ 位是否相同就好了（$mask$ 就是 / 后面那个数字）

模拟思路

这题要用到进制转换，要先还原缩写之前的地址，然后要将还原后的地址 $16$ 进制转换到二进制，然后。对于十六进制换成二进制这里就有两种思路。

• 直接打表二进制字符串，用字典（映射）或者分支语句来暴力转换。

• 直接用一个无符号 $128$ 位整数来存下这个地址。

对于第二种方法，有的同学有点懵，其实就是对底层不够熟悉。我们知道，计算机是用二进制补码来存数字的，无论是整数，浮点数还是字符等等，本质都是二进制，只是解析方法不同。

比如说 $65_{(10)} = 1000001_{(2)} = 65_{int} = A_{char} = (9.108440018111310961004242*10^{-14})_{float}$

所以我们可以忽略 $128$ 位整数的整数解析表示这个性质，自定义一种解析方法，直接解析成 IPv6。

在这里，我们不是用实现这个东西，脑子里自己知道就好

我们直接实现方法 $2$

use std::io::{stdin, stdout, BufWriter, Write, Result};
use fast_io::*;

fn convert_ipv6(ipv6_address: &str) -> u128 {
    let mut before_abbreviation = Vec::new();
    let mut after_abbreviation = Vec::new();
    let mut current = &mut before_abbreviation;
    // 一个 IPv6 中，:之间的数最长为 4 位
    let mut lexeme = Vec::with_capacity(4);
    for token in ipv6_address.chars() {
        if token != ':' {
            lexeme.push(token);
            continue;
        }
        if lexeme.is_empty() {
            // Cpp 中可以用指针来实现指向改变，Py 可以用列表是引用类型的性质
            current = &mut after_abbreviation;
            continue;
        }
        // Cpp 中可以用 stoi 函数来转换十六字符串成十进制整数，Py 可以用 int 来转换
        current.push(u16::from_str_radix(String::from_iter(&lexeme).as_str(), 16).unwrap());
        lexeme.clear();
    }
    if !lexeme.is_empty() {
        current.push(u16::from_str_radix(String::from_iter(&lexeme).as_str(), 16).unwrap());
        drop(lexeme);
    }
    // 一个 IPv6 最多有 8 个段，看看缩写了多少个
    let abbreviation_length = 8 - before_abbreviation.len() - after_abbreviation.len();
    // 拼接，中间补 0
    let lexemes = [before_abbreviation, vec![0; abbreviation_length], after_abbreviation].concat();
    let mut result = 0;
    for lexeme in lexemes {
        result <<= 16;
        result |= lexeme as u128;
    }
    result
}

fn is_subnet(network: u128, mask: u8, subnet: u128) -> bool {
    if mask == 0 {
        true
    } else {
        let offset = 128 - mask;
        (network >> offset) == (subnet >> offset)
    }
}

fn solve(input: &mut FastReader<impl BufRead>, output: &mut BufWriter<impl Write>) -> Result<()> {
    let (network, mask) = {    // 输入，并分割处理 CIDR 格式，取出网段和掩码
        let line = input.nextln();
        let [network, mask] = line.split('/').collect::<Vec<&str>>()[..] else { todo!() };
        (convert_ipv6(network), u8::from_str_radix(mask, 10).unwrap())
    };
    for _ in 0..input.next() {
        let subnet = convert_ipv6(input.nextln().as_str());
        writeln!(output, "{}", if is_subnet(network, mask, subnet) { "Yes" } else { "No" })?;
    }
    Ok(())
}

const T_CASE: bool = false;
fn main() {
    let mut input = FastReader::new(stdin().lock());
    let mut output = BufWriter::new(stdout().lock());
    if T_CASE {
        let n = input.next::<i32>();
        for _ in 0..n {
            _ = solve(&mut input, &mut output);
        }
    } else {
        _ = solve(&mut input, &mut output);
    }
}
mod fast_io {
    pub use std::io::BufRead;
    use std::io::BufReader;
    use std::str::FromStr;
    pub struct FastReader<R: BufRead> {
        reader: BufReader<R>,
    }
    impl<R: BufRead> FastReader<R> {
        pub fn new(stream: R) -> Self {
            Self {
                reader: BufReader::new(stream),
            }
        }
        pub fn nextln(&mut self) -> String {
            let mut line = String::new();
            self.reader.read_line(&mut line).unwrap();
            line.trim().to_string()
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.nextln().parse::<T>().ok().unwrap()
        }
        pub fn readln<T: FromStr>(&mut self) -> Vec<T> {
            self.nextln()
                .split_ascii_whitespace()
                .flat_map(|s| s.parse::<T>().ok())
                .collect()
        }
        pub fn has_next(&mut self) -> bool {
            self.reader.fill_buf().unwrap().len() > 0
        }
    }
}

奇技淫巧

这个就在题解里说过了，绝大部分现代的编程语言的都有网络库（除了上古的 C++），可以直接调库来判断。这里 OJ 的 rust 版本还没支持to_bits()，所以过不了编译。

use std::io::{stdin, stdout, BufWriter, Write, Result};
use std::net::Ipv6Addr;
use std::str::FromStr;
use fast_io::*;

fn is_subnet(network: u128, mask: u8, subnet: u128) -> bool {
    if mask == 0 {
        true
    } else {
        let offset = 128 - mask;
        (network >> offset) == (subnet >> offset)
    }
}
fn solve(input: &mut FastReader<impl BufRead>, output: &mut BufWriter<impl Write>) -> Result<()> {
    let (network, mask) = {    // 输入，并分割处理 CIDR 格式，取出网段和掩码
        let line = input.nextln();
        let [network, mask] = line.split('/').collect::<Vec<&str>>()[..] else { todo!() };
        (Ipv6Addr::from_str(network).unwrap().to_bits(), u8::from_str_radix(mask, 10).unwrap())
    };
    for _ in 0..input.next() {
        let subnet = Ipv6Addr::from_str(input.nextln().as_str()).unwrap().to_bits();
        writeln!(output, "{}", if is_subnet(network, mask, subnet) { "Yes" } else { "No" })?;
    }
    Ok(())
}
const T_CASE: bool = false;

fn main() {
    let mut input = FastReader::new(stdin().lock());
    let mut output = BufWriter::new(stdout().lock());
    if T_CASE {
        let n = input.next::<i32>();
        for _ in 0..n {
            _ = solve(&mut input, &mut output);
        }
    } else {
        _ = solve(&mut input, &mut output);
    }
}
mod fast_io {
    pub use std::io::BufRead;
    use std::io::BufReader;
    use std::str::FromStr;
    pub struct FastReader<R: BufRead> {
        reader: BufReader<R>,
    }
    impl<R: BufRead> FastReader<R> {
        pub fn new(stream: R) -> Self {
            Self {
                reader: BufReader::new(stream),
            }
        }
        pub fn nextln(&mut self) -> String {
            let mut line = String::new();
            self.reader.read_line(&mut line).unwrap();
            line.trim().to_string()
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.nextln().parse::<T>().ok().unwrap()
        }
        pub fn readln<T: FromStr>(&mut self) -> Vec<T> {
            self.nextln()
                .split_ascii_whitespace()
                .flat_map(|s| s.parse::<T>().ok())
                .collect()
        }
        pub fn has_next(&mut self) -> bool {
            self.reader.fill_buf().unwrap().len() > 0
        }
    }
}