包含标签：oi 的文章
-
一种无递归、无栈、无parent指针的红黑树实现
前言 红黑树是一种复杂的平衡树，在大部分情况下都会使用父指针或者递归实现。假如我们一定要三无实现呢？ 本文必须配合OI-Wiki食用！！ 基础结构 #define BLK_COLOR 0 #define RED_COLOR 1 #define LEFT 0 #define RIGHT 1 #define Color(node) (node==NULL?BLK_COLO……XGN 2024年10月12日
-
一种基于维护高度的无递归、无栈、无parent指针的AVL树实现方式
感谢XLH同学指出blog中的一些错误，本文已于2024/9/28更新 引入 AVL树有种种实现方式，其中最自然的是采用递归的写法，毕竟AVL树是递归定义的。但是，有的老师认为“递归时间常数大”，觉得应该用迭代。但是，还有老师认为迭代要用栈，“栈空间大（指占用了 O(\log n) ）…… -
Orange Boy Can You Solve It Out? Ep. 61
思考题 featuring Hikari again! Guess the string Hikari and her master Ninetail are playing a game. Hikari thinks of a string S with lower-case letters, and Ninetail asks her to make q modifications one by one. Each modification can only be one of t…… -
Orange Boy Can You Solve It Out? Ep. 61
思考题 from Maths homework again... 数学小题两道 Problem A You are given a bipartite graph G, find a proper coloring of the complement of G that uses minimum colors. |G|\leq 100 Problem B Given integer N. Find any n\geq N such that n+\varphi(n) is …… -
YZHT Ep.3: 简单最小割
呃呃，笔者最大流水平真是哈哈了，请见本题： 104871C 一眼网络流，怎么构图？ Hint:有费用的网络但是不是最小费用流？那就考虑一下最小割吧！ 一个蛋糕可以考虑成：选择蛋糕->选择工具。一个蛋糕被创造需要：选择蛋糕、选择所有工具。「所有」二字让我们考虑最小割！…… -
YZHT Ep.2: 少见的三分
题目：给出一个圆和两点，求这两点间最短路线的距离，要求路线经过圆内部或边上的任意一点。 链接：104871G 如果两个点有一个在圆内（上）就好了…… 如果两个都在圆外，设经过的圆上一点有仰角\alpha，那么注意到答案关于\alpha一定只有一个极小值。就可以三分了！ 难…… -
YZHT Ep.1: 最大流+图论优质好题
欢迎来到YZHT系列，这个系列我将分享我遇到的OI好题。 第一题 笔者最近正在学习数学图论，但是在OI中正巧碰到了这样一道从来没见过的最大流题。虽然难度不大，但是思路比较新： Problem B of 2023-2024 ICPC Southwestern European Regional Contest (SWERC 2023) 顺…… -
Orange Boy Can You Solve It Out? Ep. 60
Solved! Difficulty: Div2C :O 竟然有60期了！！ 本期题目来源于Group Theory作业，，，难度不高 Congratulations on the 60th entry!! This problem is from my Group Theory homework (not very hard). Z(Sym(n))=ONE In the world of MATHS, a permutation i…… -
Orange Boy Can't You Solve It Out? Ep. 59
思考题 aimed for inexperienced participants? Silenced! Ookami and her teammates are taking an English class. The team has n people(animals?) in total. Initially, each person can raise his/her hand and speak freely. However, once a student has raise…… -
Orange Boy Can You Solve It Out? Ep. 57
trivial 思考题 I am Banach This is a classic problem by Banach nearly without any change. There are N boys and M girls. Each boy loves a single girl and each girl loves a single boy. Your task is to divide the boys into two groups A_0 and A_1 and t……