红黑树的小屋

下一站：奇迹

主站
◆◆ 祝大家 2024 新年快乐！
新的一年，大家有事没事多留点评论吧（
这个可能稍微有点小错位不要太在意（划掉

【置顶】未解之谜

3 条评论 杂事 无标签
如果你有会的，可以告诉我做法。给定 $n$，和一个长度为 $n$ 的数组 $r$。按照如下方式生成一个数组 $x$：对于每个 $1 \leq i \leq n$，在 $\left[1, r_i\right]$ 中随机选一个整数，作为 $x_i$。求期望逆序对数量。$1 \leq n, r_i \leq 100$，时限 $1$ 秒。样例输入 1：3 5 2 7样例输出 1：1.057143给定...

【合集】算点无聊的东西

0 条评论 杂事 无标签
20240420三个东西，每次等概率随机一个东西，拿走之后会放回去。问期望几次能摸过所有三个东西。你当然可以 Min - Max 容斥，但是我觉得好像生成函数算更简单一些。先稍微分析一下，第一次一定会拿到一个东西。第二次如果不拿到第一次已经拿到的东西就是又拿到了一个东西。拿完第二个东西之后只要拿到新的东西就是拿到新的东西了（好像说了一堆废话）。设现在已经拿到了第一种东西（此时花费 $1$ 次...

CF249D Donkey and Stars 做题笔记

0 条评论 做题笔记 动态规划
题意给出平面直角坐标系上的 $n$ 个点。求最多有多少个点依次连成的折线上的线段的斜率都在给定的范围内。$1 \leq n \leq 10^5$题解首先来看一看什么情况下一个点能接在另一个点后面。以给定的两个斜率代表的向量为基（即把 $x$ 轴和 $y$ 轴换成这两个项链所构成的坐标系），如果一个点的横坐标和纵坐标都大于另一个点，那么他们就可以接一起了。这样的话就简单了，按照横坐标排序后就是...

QOJ 4363 Branch Assignment 做题笔记

0 条评论 做题笔记 动态规划
题意给定 $n, b, s, r$。有 $n$ 个点，$r$ 条边的有向图，边有边权，表示通信成本。编号为 $b + 1$ 的点是中转点，任意两点发送信息都要先送到 $b + 1$，再由 $b + 1$ 送到目标点。你要把前 $b$ 个点任意分成 $s$ 组，每组里的任意两个点都要互发消息。总代价为所有组的通信成本之和。求出最小可能的总代价。$2 \leq n \leq 5000$题解设 $...

真假硬币王

0 条评论 做题笔记 Matrix67
复读 https://www.matrix67.com/blog/archives/6970$9$ 个硬币，有一个假币。你有一个天平，可以告诉你哪边重或一样重。天平上可以放任意多枚硬币，问你至少几次保证知道哪个是假币。假币一定比正常币轻一些。两次就可以。这个问题大家小学五年级就在课本上看过了。那假设这个天平离线了，两次称完之后才会告诉你两次的结果呢？为了方便描述，我们管这玩意叫“天平鸡”！（...

多项式全家桶

0 条评论 学习笔记 多项式
约定设 $F\left[i\right]$ 表示 $x_i$ 的系数。四则运算加减法$$ F \left(x\right) \pm G\left(x\right) = \sum\limits_{i = 0}\left(F\left[i\right] \pm g\left[i\right]\right) x^i $$就是对应项做对应运算。乘法不必多说除法$$F\left(x\right) / ...

QOJ 7612 Matrix Inverse 做题笔记

0 条评论 做题笔记 无标签
题意给定 $n \times n$ 的可逆矩阵 $A$，和一个矩阵 $C$，$C$ 与 $A$ 的逆矩阵不同的位置为 $k \leq 12$ 个。求 $A$ 的逆。$1 \leq n \leq 2000$题解大家应该都做过一道经典题：给定 $2000 \times 2000$ 的矩阵 $A$ 和 $B$，判断 $AB$ 是否等于 $I$。随机长度为 $n$ 的向量 $x$，然后看 $ABx$...

一些网络流模型

0 条评论 学习笔记 网络流
请输入密码访问

由红黑树维护的基于 Gitea 的 git 服务器诞生

0 条评论 杂事 无标签
地址：https://git.rbtr.ee/先声明一下，由于我寄术高超，请不要在此 git 服务器上上传重要不可找回文件。服务器没有备份！服务器没有备份！服务器没有备份！哪个男孩不想把整个世界都装进自己的口袋里呢？今天，我朝这个目标又迈进了一小步。由红黑树维护的基于 Gitea 的 git 服务器诞生啦 (*^▽^*)！FAQQ: 为什么使用由红黑树维护的基于 Gitea 的 git 服务...

深入探究大楼丢鸡蛋问题

0 条评论 做题笔记 动态规划 动态规划优化
前言之前写过一篇大楼丢鸡蛋问题，今天看到以前写的东西纯属胡扯，所以重写一下，因为今天有幸见到了大楼丢鸡蛋的终极强化版本：$10^3 \times 10^{18}$。题目URAL - 1597有一个 $N$ 层的大楼，你有 $K$ 个鸡蛋。每个鸡蛋的硬度都是相同的。碎鸡蛋不能用来测试。你要求出 至少扔多少次才能保证测出鸡蛋的硬度。假设你在第 $x$ 层扔下鸡蛋，如果鸡蛋碎了，说明鸡蛋硬度不能承...

从线性变换角度看莫比乌斯（Möbius）反演和二项式反演

0 条评论 学习笔记 无标签
清晰版定义简单来讲（不严谨）若一个变换 $\mathscr A$ 是线性变换，则对于线性空间中的任意元素 $\alpha$ 和 $\beta$ 它必须满足：$\mathscr A\left(\alpha + \beta\right) = \mathscr A\left(\alpha\right) + \mathscr A\left(\beta\right)$对于该数域上的任意值 $k$，有 ...

非公开训练题目

0 条评论 做题笔记 无标签
请输入密码访问