跳至主要內容
Xanadu13's Blog

Xanadu13's Blog

记录你不想忘记的东西

素数筛

题目传送门：洛谷3383

题意：给定一个范围 nn ，有 qq 个询问，每次输出第 kk 小的素数。

Xanadu132024年11月19日大约 2 分钟luogualgorithmcpp
HDOJ-1010 Tempter of the Bone

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1010

题目大意

小狗要逃离一个N×MN×M的长方形迷宫，迷宫出口的门仅在第 TT 秒时开一瞬间（不到1秒）。因此，小狗必须恰好在第 TT 秒到达门口才能逃离。 每一秒，它可以向上下左右任意移动一格，且所有格子至多走一次。

Xanadu132023年11月13日大约 3 分钟hdojalgorithmBFSDFScpp
编译原理期末复习笔记

第二章：形式文法和形式语言

句型

从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串（S =*=> α）。句型可以既包含终结符号又包含非终结符号。

句子

只包含终结符号的句型称为句子。句子是一种特殊的句型。

语言

文法 G 推导出的所有句子组成的集合，称为语言，记为 L(G)，即：

L(G)={x∣S=∗>x且x∈VT∗}L(G)=\{x | S =*> x \text{且} x∈V_T*\}

Xanadu132025年1月6日大约 2 分钟Compiler Principle
Nodejs中报错“Error: spawn EINVAL”

这是由于执行子进程存在安全漏洞，因此在18.x, 20.x, 21.x版本中直接禁止了。

详见：https://nodejs.org/en/blog/vulnerability/april-2024-security-releases-2

需要在报错的包对应的scripts/install.js文件中加上shell: true：

'use strict'

const os = require('os');
const path = require('path');
const spawn = require('child_process').spawn;

const gypArgs = ['rebuild'];
if (process.env.NODE_PTY_DEBUG) {
  gypArgs.push('--debug');
}
const gypProcess = spawn(os.platform() === 'win32' ? 'node-gyp.cmd' : 'node-gyp', gypArgs, {
  shell: true,
  cwd: path.join(__dirname, '..'),
  stdio: 'inherit'
});

gypProcess.on('exit', function (code) {
  process.exit(code);
});
Xanadu132024年12月24日小于 1 分钟Nodejs
C语言中的union

共用内存

union中的字段是共用内存的，比如可以用下面的代码判断机器是小端序还是大端序：

#include <stdio.h>
union U
{
    char c;
    int i;
}u;

int main()
{
    u.i = 1;
    if(u.c == 1)
    {
        printf("little-endian");
    }
    else
    {
        printf("big-endian");
    }
}
Xanadu132024年12月21日小于 1 分钟CC
C++中原生编译时字符串混淆实现

C++中具有强大的模板元编程，可以不依赖任何外部库，仅使用C++ std实现编译时的字符串混淆。

原始版本

在我的另一篇文章中提到过一个C++中字符串混淆的简易版本：

但其中0x55是硬编码的，我们需要引入编译时随机数来消除这一硬编码。

Xanadu132024年12月17日大约 3 分钟C++C++Metaprogrammingstring obfuscation
C++高级特性实例

constexpr初探——阶乘

#include <iostream>
using namespace std;

constexpr int fac(int n)
{
    return n <= 1 ? 1 : (n * fac(n-1));
}

int main() {
    constexpr auto x = fac(5);
}
Xanadu132024年12月17日大约 2 分钟C++C++Metaprogramming
Rust 学习笔记

Rust具有一些让人眼前一亮的特点：无GC也不需手动管理内存、高性能、安全性强等等。但其诸多优点背后的代价，就是学习曲线相当陡峭。

Rust的困难，不在于语言特性，而在于：

  • 具体实践中如何运用学到的技巧
  • 遇到了坑时（生命周期、借用错误，自引用等）如何迅速、正确的解决
  • 大量的标准库API的熟练使用，这是保证开发效率的关键

使用原生指针和unsafe实现自引用

algo.course.rs上的实现，在此记录一下

pub struct Tree {
    count: usize,
    root: *mut Node,
}

#[derive(Debug)]
struct Node {
    data: i32,

    // Null指针这里代表"None`; right.is_null() ==> 没有right child
    left: *mut Node,
    right: *mut Node,
    parent: *mut Node,
}

impl Tree {
    pub fn new() -> Self {
        Self {
            count: 0,
            root: std::ptr::null_mut(),
        }
    }

    // 返回tree的节点数量
    pub fn node_count(&self) -> usize {
        assert!(self.count != 0 || self.root.is_null());
        self.count
    }


    // 在tree中新增一项，插入成功则返回true,若给定的数据在tree上已经存在，则返回false
    pub fn insert(&mut self, data: i32) -> bool {
        if self.root.is_null() {
            self.root = Node::new(data);
        } else {
            if !insert_node(self.root, data) {
                return false;
            }
        }

        self.count += 1;
        true
    }

    // 找到tree上的指定项，若找到，返回true
    pub fn find(&self, data: i32) -> bool {
        !find_node(self.root, data).is_null()
    }

    // 返回tree的字符串形式，用于Debug
    pub fn display(&self) -> String {
        display_node(self.root, 0)
    }

    // 使用中序遍历来返回tree中的所有数据
    pub fn inorder(&self) -> Vec<i32> {
        let mut v = vec![];
        if !self.root.is_null() {
            let mut node = leftmost_child(self.root);
            loop {
                if node.is_null() {
                    break;
                }
                unsafe {
                    v.push((*node).data);
                }
                node = successor_of_node(node);
            }
        }
        v
    }

    // 从tree上移除指定项, 若该项存在且被成功移除，则返回true，否则都返回false
    pub fn remove(&mut self, data: i32) -> bool {
        let node = find_node(self.root, data);
        if node.is_null() {
            false
        } else {
            self.remove_node(node);
            self.count -= 1;
            true
        }
    }

    // 在tree上找到指定项的继任者
    pub fn successor(&self, data: i32) -> Option<i32> {
        unsafe {
            let node = find_node(self.root, data);
            if !node.is_null() {
                let nodesucc = successor_of_node(node);
                if !nodesucc.is_null() {
                    return Some((*nodesucc).data);
                }
            }
            None
        }
    }

    // 从tree上移除指定的节点
    fn remove_node(&mut self, node: *mut Node) {
        unsafe {
            let lchild = (*node).left;
            let rchild = (*node).right;
            if lchild.is_null() && rchild.is_null() {
                // 节点没有子节点，所以可以安全移除
                self.replace_node(node, std::ptr::null_mut());
            } else if !lchild.is_null() && !rchild.is_null() {
                // 节点的左右子节点都在，我们需要找到该节点的继任者，然后将继任者的数据赋给当前节点，然后再递归删除继任者
                let succ = successor_of_node(node);
                assert!(!succ.is_null());
                (*node).data = (*succ).data;
                self.remove_node(succ);
            } else if !lchild.is_null() {
                // 节点只有左子节点，所以使用后者替代前者
                self.replace_node(node, lchild);
            } else if !rchild.is_null() {
                // 节点只有右子节点，所以使用后者替代前者
                self.replace_node(node, rchild);
            } else {
                panic!("unreachable");
            }
        }
    }

    // 使用`r`节点来替换目标`node`节点
    fn replace_node(&mut self, node: *mut Node, r: *mut Node) {
        unsafe {
            let parent = (*node).parent;
            if parent.is_null() {
                // Removing the root node.
                self.root = r;
                if !r.is_null() {
                    (*r).parent = std::ptr::null_mut();
                }
            } else {
                if !r.is_null() {
                    (*r).parent = parent;
                }
                if (*parent).left == node {
                    (*parent).left = r;
                } else if (*parent).right == node {
                    (*parent).right = r;
                }
            }

            // 被替换的节点不再被使用，因此可以回收它：通过`Box`拿走它的所有权，然后它会被自动drop
            Box::from_raw(node);
        }
    }
}

impl Drop for Tree {
    fn drop(&mut self) {
        // 也许不是性能最高的实现，但是简单，而且有用
        while !self.root.is_null() {
            self.remove_node(self.root);
        }
    }
}

impl Node {
    fn new(data: i32) -> *mut Self {
        Box::into_raw(Box::new(Self {
            data,
            left: std::ptr::null_mut(),
            right: std::ptr::null_mut(),
            parent: std::ptr::null_mut(),
        }))
    }

    fn new_with_parent(data: i32, parent: *mut Node) -> *mut Self {
        Box::into_raw(Box::new(Self {
            data,
            left: std::ptr::null_mut(),
            right: std::ptr::null_mut(),
            parent,
        }))
    }
}

// 在节点子树上创建新的节点
fn insert_node(node: *mut Node, data: i32) -> bool {
    unsafe {
        if (*node).data == data {
            false
        } else if data < (*node).data {
            if (*node).left.is_null() {
                (*node).left = Node::new_with_parent(data, node);
                true
            } else {
                insert_node((*node).left, data)
            }
        } else {
            if (*node).right.is_null() {
                (*node).right = Node::new_with_parent(data, node);
                true
            } else {
                insert_node((*node).right, data)
            }
        }
    }
}

// 在`fromnode`的子树上寻找目标数据，如果没找到则返回`null`
fn find_node(fromnode: *mut Node, data: i32) -> *mut Node {
    unsafe {
        if fromnode.is_null() || (*fromnode).data == data {
            fromnode
        } else if data < (*fromnode).data {
            find_node((*fromnode).left, data)
        } else {
            find_node((*fromnode).right, data)
        }
    }
}


// 返回`node`子树的字符串形式，同时指定缩进字符数
fn display_node(node: *const Node, indent: usize) -> String {
    let indent_str = " ".repeat(indent);
    if node.is_null() {
        indent_str + ".\n"
    } else {
        unsafe {
            let mut s = format!("{}{}\n", indent_str, (*node).data);
            s.push_str(&display_node((*node).left, indent + 2));
            s.push_str(&display_node((*node).right, indent + 2));
            s
        }
    }
}

// 找到`node`最左边的子节点，如果没有，就返回`node`自身, `node`不能为null
fn leftmost_child(node: *mut Node) -> *mut Node {
    unsafe {
        if (*node).left.is_null() {
            node
        } else {
            leftmost_child((*node).left)
        }
    }
}


// 在tree上找到`node`的继任者
fn successor_of_node(node: *mut Node) -> *mut Node {
    unsafe {
        if !(*node).right.is_null() {
            // 若node有一个右子节点，则继任者是该右子节点的最左子节点，若该右子节点没有子节点，则继任者就是右子节点
            leftmost_child((*node).right)
        } else {
            // 没有右子节点，则找到一个父节点，当前node是该父节点的左子节点, 若在root之前都没找到，说明node没有继任者
            parent_with_left(node)
        }
    }
}

// 在`node`的祖先中找到它的父节点,且`node`必须是该父节点的左子节点
fn parent_with_left(node: *mut Node) -> *mut Node {
    unsafe {
        // 若`node`有父节点，且该父节点拥有左子节点，同时`node`就是这个左子节点，那么该父节点就是我们的目标
        let parent = (*node).parent;
        if !parent.is_null() {
            if std::ptr::eq((*parent).left, node) {
                return parent;
            }
            return parent_with_left(parent);
        }

        // `node`没有父节点
        std::ptr::null_mut()
    }
}

fn main() {
    
}
Xanadu132024年12月11日大约 6 分钟Rustdata structure
到底了，不要再拉了~
Copyright © 2025 Xanadu13