TH911 Blog

「光阴不可测，岁月亦无歌。」

浅谈分数取模

费马小定理 | 欧拉定理 | 扩展欧几里得

费马小定理 定理 若 $p$ 为质数且 $\gcd(a,p)=1$，有 $a^{p-1}\equiv1\pmod p$，即 $a^p\equiv a\pmod p$。 证明 取一质数 $p$ 和整数 $a$ 满足 $\gcd(a,p)=1$，即 $a$ 不为 $p$ 的倍数。 则有： \(\prod\limits_{i=1}^{p-1}i\equiv\prod\limits_{i=...

Posted by TH911 on November 27, 2024

FHQ Treap 之区间操作

例题：文艺平衡树 | 洛谷P3391

例题链接 您需要写一种数据结构（可参考题目标题），来维护一个有序数列。 其中需要提供以下操作：翻转一个区间，例如原有有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。 前置知识：FHQ Treap 参见FHQ Treap (无旋 Treap) 详解。 平衡树维护区间信息 原理 普通平衡树维护...

Posted by TH911 on November 22, 2024

FHQ Treap (无旋 Treap) 详解

例题：普通平衡树 | 洛谷P3369,P6136

例题链接 例题加强版链接 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 插入一个数 $x$。 删除一个数 $x$（若有多个相同的数，应只删除一个）。 定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。 查询数据结构中排名为 $x$ 的数。 求 $x$ 的前驱（前驱定义为小于 $...

Posted by TH911 on November 21, 2024

C++神奇错误之switch内定义变量

[Error] jump to case label [-fpermissive]

出现 [Error] jump to case label [-fpermissive] 的原因是因为 switch 结构内不能够定义变量。 比如： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 case 1: scanf("%d %d",&x,&y); auto p=color[y].upper_bound(dfn[x]); ...

Posted by TH911 on November 21, 2024

C++神奇错误之结构体内变量

undefined reference

写了一棵 FHQ Treap，但是报错： 1 2 C:\Users\ADMINI~1\AppData\Local\Temp\ccYwKop1.o 未命名2.cpp:(.rdata$.refptr._ZN5treap4rootE[.refptr._ZN5treap4rootE]+0x0): undefined reference to `treap::root' D:\1234\collec...

Posted by TH911 on November 21, 2024

如何通过js在IOS锁屏封面显示播放歌曲的信息

有些话不得不说，虽然我不太信任百度的AI只能回答，但这次给的真是正经答案…… 原本各类CSDN、百度知道、腾讯云……给出的回答都是不能，只有应用程序才能，但是我去 StackOverFlow 上搜索，竟然还搜到了：link。 通过一个叫做 Media Session API 的东西可以，然后尝试，成功。 然而，这是 百度AI 给的答案： 代码： 1 2 3 4 5 6 7 ...

Posted by TH911 on November 21, 2024

题解：[USACO19DEC] Milk Visits S

强化版：[USACO19DEC] Milk Visits G

题目传送门 强化版：[USACO19DEC] Milk Visits G。 题意重述 给定一棵无根树，每次给出 $a_i,b_i,c_i$，求 $a_i\sim b_i$ 的路径上是否存在一个点的权值为 $c_i$。 题意分析 首先这样一眼树链剖分，将一对多的非线性信息转化为线性信息后处理即可。 但是，本题还存在更简单的算法：倍增。 可以参考倍增 LCA，在从 $u...

Posted by TH911 on November 21, 2024

NOI大纲（2023修订版）

此处。

Posted by TH911 on November 20, 2024

题解：[AGC032E] Modulo Pairing

AtCoder AGC032E

题目传送门 （实话实说，不明白为什么要评紫，因为做题不需要完全严谨证明。就算加上证明难度也最多蓝。模拟赛场切，却根本不会证明……建议评绿） 题意分析 证明参见”相关证明“部分。 给定 $n,m$ 和 $2n$ 个正整数 $a_1,a_2,a_3,\cdots,a_{2n}$，将其分为 $n$ 对，两两组成一队。若 $x,y$ 为一对，则其权值为 $(x+y)\bmod m$。...

Posted by TH911 on November 20, 2024

NOI Linux使用笔记

启动过程 打开VMware Workstation Pro。 打开 NOI Linux 后找监考员建立共享文件夹，否则无法访问D盘。 不要点击 NOI Linux 的更新按钮，否则重启的时间不予以补时。 各类命令 ls：列出文件、文件夹。 cd：切换文件目录（cd ..：回退） mkdir：新建文件夹 r...

Posted by TH911 on November 19, 2024

FEATURED TAGS
树状数组 题解 提高+/省选− 省选/NOI− DP 普及+/提高 基础算法 数学 组合数学 普及/提高− 贪心 字符串 线段树 未完 图论 平衡树 数论 树形 DP 搜索 Tarjan Trie 二分 位运算 二分答案 状态压缩 FHQ Treap 前端 无聊时候的一点思考 最短路 树链剖分 NOI/NOI+/CTSC
ABOUT ME

要做一个优秀的 OIER

FRIENDS