link：[2025 春晚刘谦魔术题解](https://www.luogu.com.cn/article/hgtmma1h)。居然已经一年了。 手机打开计算器。先随便选两个人分别说一个四位数和一个五位数，然后相加。然后再随便找几个人，手机朝下，任何人都看不到上面的内容，然后随机乱点一些数字。加起来是 $2162227…

## Abstract 本文使用多层感知器（Multilayer Perceptron）实现了计算加法的程序，通过了洛谷（Luogu）的题目 P1001 A+B Problem。 Lionblaze 给大家的元旦礼物，大家喜欢吗 awa。 :::info[AI 摘要] 这篇文章总结了使用多层感知器（MLP）解决洛谷P1…

给定 $a,b,n\le 10^6$，求 $\mathrm{lowbit}(a^n-b^n)$。有原题，但是在哪呢。 显然 $a,b$ 不都是奇数的情况下可以转化为都是奇数的情况或者直接求出结果，问题就在于都是奇数怎么求。 有因式分解：$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2…

# 如何卡常 友情提醒：先尝试优化你的时间复杂度。 ## 输入输出卡常（快读快写） ### 快读 大家都会 `getchar` 快读对吧。这里以只能读非负数的快读为例。 ```cpp long long fr() // 为什么不叫 read 呢，因为 read 函数在 Linux 的 unistd.h 里面声明了，并且…

流传着一种测量程序空间的方法（C++）。 ```cpp #include char _begin; // 你的所有变量，数组之类的 char _end; int main() { printf("Memory usage: %d Byte\n", &_end - &_begin); return 0; } ``` 假的…

现在只是写写。等树状数组的文章完工后会把这篇文章合并进去。 ## 树状数组做区间加法区间查询 区间加法单点查询？显然可以改为前缀加法单点查询。 做差分即可。 对于区间加法区间查询？先改为前缀加法前缀查询。 做差分：对 $1\sim y$ 加 $x$，只需要对 $d_1$ 加 $x$，$d_{y+1}$ 减 $x$ 即可…

构造一个 DAG，距离不等于 $2$ 的点对数量不多于 $n\lceil \log_2n\rceil$。 有一个非常显然的做法，分出一个点作为中转，其余点的一半连到中转点，中转点连到剩下的点。这样就有 $\left\lfloor \dfrac{n-1}{2}\right\rfloor\times \left\lceil…

经验：P3065，CF510C，P6286，ABC268G，和一堆本质相同的题。 容易发现，一个字符串 $A$（在组委会的字典序定义下，下同）要排在 $B$ 之前，需要满足 $A$ 是 $B$ 的前缀或者 $A,B$ 的第一个不同的位置下 $A$ 的对应字符在 $B$ 之前。$B$ 是 $A$ 的前缀则不可能。 好吧，…

友链：P11226。 样例很良心。 你会发现两个字符串有前缀关系的时候，它们的大小关系是确定的。否则，显然它们的大小关系不确定，两种情况可能性都是 $50\%$。 所以，一个字符串的前缀对它的排名贡献为 $1$，有它作为前缀的字符串对它排名贡献为 $0$，而其它字符串对它的贡献为 $\dfrac{1}{2}$，因为是排…

如果你看懂了题目，你会发现 $f(a)$ 其实就代表 $a$ 的小数位数。 而 $g(x,y)$ 怎么求呢？ 显然，如果 $x$ 或 $y$ 之间有整数，也就是它们的整数部分不同。如果整数部分相同，那么如果第一位小数不同，则答案为 $1$。如果整数和第一位小数都相同，但是第二位小数不同，则答案为 $2$，以此类推。 但…

::anti-ai[催审核/fendou，明天就更新咕值了] 下面把押韵称为配对。 将字符串翻转可以把问题转化为前缀的问题。考虑 Trie。对所有字符串建出 Trie 树，我们考虑贪心。 性质：如果有两个字符串配对，那么在可能的情况下，应当选尽量长的前缀。这是因为，如果选比较短的，可能会和其它字符串冲突。 所以，对 T…

> 不是，为啥要用 Trie 啊…… 首先我们根据给出的序号对字符串进行排序，比如样例 $1$ 变为 `bc` 和 `ab`，样例 $2$ 不变，样例 $3$ 变为 `ccc`，`ddd`，`bbb`。 考虑有序的充要条件（$ #include #include #include #include using name…

$N\le 22$，显然是状压 dp。根据套路，使用二进制第 $i$ 位来代表 $T$ 的第 $i$ 位选没选。 状态转移方程？注意到可能有重复计数（多个前驱状态代表的字符串相同但是掩码不同），需要去重。这里使用一个数组记录每个状态的最小与其代表字符串相同的状态编号，使用这个来计算，然后使用 STL 的 `set` 或…

因为只有模版题所以不好意思交全站推荐。 --- 笛卡尔树就是 Treap，啊不说反了，Treap 是笛卡尔树。 笛卡尔树是一棵二叉树，每个节点包含两个属性：$\mathrm{id}$ 和 $\mathrm{val}$。其中 $\mathrm{id}$ 两两不同。如果用 $\mathrm{id}$ 当做权值，则这棵树是一…

树状数组板子题。 好吧开玩笑的，这题是分块入门，我们用分块做。 --- 什么是分块？ 分块是一种**思想**，但不是一种算法。算法是基于方法的，方法又是基于思想的。 正如其名，分块就是把数列分成若干个块，然后计算答案。如何计算？如果区间问题的区间在块内则使用一种方法计算，如果不在一个块之内（块间）则使用另一种方法。通常…

> 感觉在造轮子，不管了。本人是 Python 新手，轻喷。 ## 简介 注意：因为输出是 Markdown 所以你需要 Markdown 渲染。这很简单，比如 VSCode 的 Markdownlint 插件就可以，VS 好像是原生就支持但是貌似不能直接渲染 $\KaTeX$。同时你还需要能够执行 Python 代码…

突然发现洛谷题目 id 突破了 $14000$。 显然，我们在同一个位置运用两种变换，可以让下面的图形中所有的格子反转，不妨记为图形“吅”：  （拜谢 desmos，下同） 上下运用我们造出来的图形吅就可以造出来图形“田”：…

> 赛时在代码中复制粘贴数十行“我不会 MLE！”最终真的没有 MLE。其实那个做法极限数据下是会爆炸的。 $11$ 是质数，所以乘积是 $11$ 的倍数当且仅当经过了至少一个 $11$ 的倍数格。我们把这种格子称作“关键格”。 如何计数？赛时思路是考虑第一个经过的关键格是哪一个。赛后发现把问题复杂化了（不过这个做法的…

感觉这题是整场比赛唯一难度到达绿的题。还是靠 $6$ 种情况的分类讨论搭起来的。 考虑建图，$(i,j,k)$ 代表第一个桶剩余 $i$，第二个剩余 $j$ 和第三个剩余 $k$。那么 BFS 计算 $(v,0,0)$ 到所有 $\left(\dfrac{v}{2},?,?\right)$ 的距离的最小值即可。注意如果…

> 这题咋是 B4399…… 带权区间覆盖。点 $x$ 的权值为 $x$。最小化总权值。 先看经典的区间覆盖问题——无权区间覆盖，即最小化选点数量。按照右端点从小到大排序，遇到一个目前没有被覆盖的区间就选取其右端点。显然它是正确的，因为它让每个点都尽量靠右。 回到这题。尽量靠右会发生什么？选点数量尽量小的前提下，总权值…

看起来挺难是不是？首先我们知道这里子序列等价于子集（可重集）。 完全平方数的性质：质因子分解后，每个指数都是偶数。即 $\displaystyle n\text{ 为完全平方数}\iff n=\prod_{p\in \mathbb P} p^{\alpha_p},\forall p\in \mathbb P,\alph…

我记得这题赛时题面是给每个节点有标号的？我们在代码中将节点从上到下，同一行从左到右的顺序 $1\sim 12$ 标号。 这题可以是数学题，但是我们不管那么多直接暴力一下。如果你对语法比较熟悉那么直接暴力在赛场上会是比推式子再写代码消耗时间更短的做法。不过显然右下方的未知数是可以直接算出的，可以算完再枚举排列。 C++…

模拟题。对于每个开始位置判断即可。 判断的思路是首先如果 `t` 对应位置字符是 `?` 则这一位直接判断成功，如果不是则如果相同则整个判断失败，如果不同那么忽略大小写之后应该相同否则判断失败。忽略大小写相同可以通过全部转为小写实现。 C++ 中的实现方式： 判断 `ch` 是否为大写：`ch >= 'A' && ch…

## Subtask 1 这么小的数据直接上 Pollard-rho 暴力算。对于不会 Pollard-rho 的可以直接找个质因子分解网站（如 ，下同）解密出来是 `{VerY51mpl3RSA}`。 ## Subtask 2 $p,q$ 相差太大，$q$ 太小，直接 Pollard-rho 暴力算（复杂度是 $\s…

> $\oplus$ 表示异或。 先说赛时思路，后面是结论和证明，前面可以跳过。 ## 赛时思路 题目的“连通块”有点抽象，其实就是连通的一块啦，和权值无关。 先分析样例。 第一个样例是一行八列，那么连通块必然是一个子段。所以假设从左往右是 $x_1,x_2,x_3,\dots,x_8$，那么有 $\displayst…

> 给定一个图，选定不多于 $k$ 个点，使得图中每个点都离某一个选定的点距离不多于 $\bm 2$。无需最小化选点数量。 > > 保证可以选定不多于 $k$ 个点，使得图中每个点都离某一个选定的点距离不多于 $\bm 1$。 :::warning[这是错误做法] 既然有了后面的保证，那么就考虑后面那个题怎么做？ >…

这两个选项是流传已久的**谣言**。 你自己拿 gcc/g++ 试一下就会知道 `#pragma G++` 和 `#pragma GNU optimize` 没用（在 `-Wall` 选项下会报警告 `ignoring '#pragma G ' [-Wunknown-pragmas]` 或 `ignoring '#pr…

在 $a$ 中选出一些数字（可以重复选也可以不选），平均数为 $n$。 平均数不好处理，总和好处理啊！平均数和总和之间唯一好做转换的数字就是 $0$。所以将元素全部减去 $n$，结果要求平均数为 $0$，也就是总和为 $0$。 然后考虑到 $k$ 比较大，可以进行去重。所以现在 $k$ 是 $1001$ 的范围。 是一…

我们关心的是箱子的移动次数，而不是人的。所以箱子的位置相同，人在任何位置都是等价的……吗？ 并不是，箱子会挡人。箱子可能让本来连通的部分变得不连通，但是在同一个连通块（考虑了箱子）之内的确实是等价的。 显然，我们只需要考虑人在箱子的相邻上/下/左/右四个方位的情况。其余情况要么可以转化为这四种情况，要么不可达。 我们设…

**这题目前中文翻译疑似不太有素质，答案要对 $\bm{10^9+7}$ 取模**。 容易发现 $f(x)=\varphi(x)$，也就是 $[1,x]$ 中与 $x$ 互质的元素个数。 > 证明： > > 首先理解方括号 $[P]$。这是艾弗森括号，当 $P$ 为真时值为 $1$ 否则为 $0$。 > > 那么 $\…