remi-riyaの博客

花了我将近两天时间Debug的阴间题，写完感觉人生都空虚了（；´д｀）ゞ 题意还是很简单的，思路也很明显，就是记忆化搜索，或者像题解一样直接都预处理出来。 这题的图跟一般的图主要的区别在于图中的环是无法从外部进入的，因为光路是可逆的，所以光路只有两种可能，要么在一个环中死循环，要么形成一条链最后射出边界，虽然听起来很简单，但是我写了整整三个版本的代码，前两个版本都是没有考虑全面导致实现有问题，都是过60%，其中一个在我找出一个错误样例并改对后信心满满的交了一发之后从过60变成了过30…… 下面是翻车经历： 最开始的时候我只开了两个数组，一个记录是否被访问，一个记录答案，然后发现一面镜子可能在一条路径中被访问多次，于是又开了一个数组记录路径编号，交一发喜提wa（以下代码都经过多次修改，我也不确定是不是当初交的那一版_(:з)∠)_） 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686 ...

可持久化数据结构是指在每次修改后都保存了修改前版本的数据结构。在可持久化数据结构中，我们可以很方便的追溯到某次修改前的版本，以此来完成某些操作。简单来说，对于nnn次插入操作，我们就存储nnn个版本，第iii个版本对应了前iii次操作后的数据结构。当然，不可能真的存nnn个完全独立的版本，空间会直接爆炸(～￣▽￣)～。可以注意到，对于Trie和线段树等数据结构来说，每次插入只改变了一条链上的节点，因此对于每次插入操作，我们只需要新建这条链上的节点，而其他的节点可以直接白嫖上一个版本的。 常用的可持久化数据结构主要有可持久化的Trie和可持久化线段树。 可持久化Trie 首先，既然有nnn个版本，当然就对应了nnn个根节点，从不同的根节点开始遍历就可以得到不同版本的数据结构。下面简单演示一下可持久化Trie的插入过程。 最开始是一个空的Trie，插入一个字符串no（黑色节点表示根节点） 然后插入一个字符串game，由于这整个字符串都属于要改变的节点，所以都要新建，同时，为了从新建的根节点能够访问到以前插入的字符串，新的根节点也要有边连向n 继续再插入一个字符串no，但是no之前已经插 ...

（本文章主要涉及Nim博弈及相关变种，二分图博弈以后再补_(:з)∠)_） Nim博弈是最经典的博弈论问题之一，一般可以描述为如下：两个人轮流从若干堆石子中取石子，每次只能取一堆石子中的任意个，最后无法取（即所有石子都被取完）的玩家判负。Nim游戏拥有简洁的规则和优雅的结论，也是SG函数的基础。 基本概念 首先明确一些概念，Nim博弈是公平组合游戏（Impartial Combinatorial Games, ICG）的一种，所谓公平组合游戏，需要满足以下几个条件 有两个玩家 两个玩家轮流操作，在一个有限集合内任选一个进行操作，改变游戏当前局面 一个局面的合法操作只与游戏当前局面有关，与当前玩家和次序等其他因素无关（公平） 无法操作者判负 为什么要提这个呢？因为从这些条件里，我们可以得出一个最基本的定理：一局游戏的胜负只与当前的局面有关，与当前是哪个玩家在操作无关，因为当局面确定，由于合法操作不受其他因素影响，那么其所有可以进行的操作与操作后的局面都是确定的，在两个玩家都绝对理性的情况下（这是大前提，否则就没有意义了），其胜负自然也是确定的。 那么，我们就可以把所有局面分成两种：必 ...

BSGS算法（baby step giant step，大步小步算法），又叫北上广深算法（不是），是一种基于中间相遇思想求解离散对数的算法，即求解类似于ax≡b(modm)a^x\equiv b\pmod max≡b(modm)的方程。 BSGS算法 首先介绍最普通的BSGS算法。普通的BSGS算法要求mmm和aaa要互质，既然互质，那么根据欧拉定理 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1\pmod m aφ(m)≡1(modm) 也就是说，ax(modm)a^x \pmod max(modm)以φ(m)\varphi(m)φ(m)为周期循环，那么如果方程有解，解一定在000到φ(m)\varphi(m)φ(m)之间，如果暴力枚举，当mmm为质数时φ(m)\varphi(m)φ(m)最大为m−1m-1m−1，最坏复杂度为O(m)O(m)O(m)。 普通的BSGS算法就是对上述暴力算法的一个优化，我们可以把xxx改成At−BAt - BAt−B，那么原式变成aAt−B≡b(modm)a^{At - B} \equiv b \pmod maAt−B≡b(m ...

相信被头歌的禁止复制粘贴恶心到了的人肯定不止我一个，这次写一个链表的题，每一关都要用到上一关的代码，每一关都要重新把4种构造函数和4个功能函数重新打一遍，只能说很符合我对头歌的印象😅😅😅。 于是本着偷懒顺便造福大众的想法，我开始寻找解决的办法。经过一天一夜的尝试与搜索，终于找到了一种解决办法：调用系统API模拟键盘输入。 正文 如何调用系统API呢？如果是大佬当然有无数的方法，但我们作为小白，选择最简单的方法就好了，那就是我们无敌的Python（撒花） 首先，安装PyWinHook和PyUserInput PyWinHook是Python的一个第三方库，可以对键盘、鼠标进行监听，PyUserInput可以模拟键盘鼠标输入。 https://www.lfd.uci.edu/~gohlke/pythonlibs/#pywinhook 在网址中找到对应的版本下载，如我的Python版本是3.10.10 64bit，那么就下载pyWinhook‑1.6.2‑cp310‑cp310‑win_amd64.whl，cp310表示3.10，amd64表示64位。 Python版本可以在命令行输入 ...

Splay树，即二叉伸展树，是一种非严格平衡的二叉搜索树，由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明（摘自百度百科）。相比与AVL、红黑树而言，Splay树不需要额外地存储平衡信息，因此显得更为简洁，代码实现也较为简单（指150行代码），同时具有很强的扩展性，常用于算法竞赛中。 至于我为什么突然想要学Splay树，因为这是Tarjan发明的……没错，就是求强连通分量、割点、桥的Tarjan算法的那个Tarjan。事情的起因是我最近刚学完强连通分量，然后查了一下Tarjan的资料，发现原来是祖师爷级别的大佬，拿过图灵奖，发明了很多图论的重要算法和数据结构。于是就对Splay树产生了兴趣，虽然这玩意已经明显超过了我的算法水平（刚学完强连通的蒟蒻），但我还是自不量力毅然决然地花了两天手搓了Splay，然后又花了一天的时间调试。 那么废话了那么多，接下来正式介绍Splay树 （以下内容和代码部分抄袭参考自oiwiki和其他人的博客、文章等） （图片均使用开源网站ioDraw绘制，感谢开源者的贡献） 基本成员 S ...

原题链接 这题的思路其实很简单，就是直接贪心加暴力即可。有nnn个苹果和mmm个人，要想平均分配同时使切苹果的次数最少，那么就只需要切多出来的那部分就行了，也就是n mod mn \bmod mnmodm，其他的既然已经能够平均分配，切了之后也依然能平均分配，没必要画蛇添足地去切。所以只需要一个while循环就能解决： 12345int a = n % m;while (a) { ans += a; a = a * 2 % m;} 当然，如果直接这样写的话，就会发现样例都过不了。因为有些情况是无论怎么切都无法平均分配的，上述代码遇到这种情况显然会直接死循环，所以这题的关键就在于如何判断能否平均分配。 首先，假如某种情况下可以均分，比如每个人分到了1.5个苹果，那么我们就可以把那些重量为1的苹果都切成0.5，也就是切成最小的，同时苹果依然可以均分。这么做的意义在于，当我们把所有苹果都切成最小的那种时，其实就相当于在每一次切苹果时都是直接切所有苹果，也就是直接让苹果的数量翻倍。也就是说，可以均分和这个式子等价（具体的充分必要性我就不证了，绝不是不会）： \ ...

原题链接——Acwing95 解法来源《算法竞赛进阶指南》 想清楚之后并不是很难的题，但个人认为这是对思维提升非常大的一道题，刷新了我对递推和枚举的认识，故记录一下。 首先注意这一题的数据量，n≤500n \leq 500n≤500，数据量较小，同时矩阵也只有5×55 \times 55×5，那么我们可以考虑遍历状态空间，然后取最小值。 问题在于如何遍历，如果直接枚举所有选择，那么就有∑i=16C25i×n\sum_{i=1}^{6}{C_{25}^{i}} \times n∑i=16​C25i​×n种情况，大约是1e8种，大概率会T也许放牛客上能过。 那么接下来让我们回到题目本身，题目的目的是把所有灯都打开。假如我们已经枚举了第一排的可能的操作，但第一排仍有未打开的灯，那么显然只能通过开关相应的第二排的开关来把第一排还未打开的灯打开，同时第二排其他的开关又不能动，因为会破坏第一排本来已经打开的灯的状态，也就是说，第二排的开关操作是固定的，同理，如果第二排操作完后仍有灯关着，那么只能通过操作第三排的相应开关来打开……以此类推，如果在操作完最后一排后最后一排仍有灯关着或者操作步数大于6 ...

最近花了两天时间学了下树状数组，然后感觉堪比玄学，故写篇文章总结一下。 2024.08.07 UPD：添加了树状数组的树形结构解释，与树状数组上二分。 树状数组（binary indexed tree），也叫BIT，又以其发明人名字被称为Fenwick树。树状数组利用二进制下标来维护区间和，能够做到以log⁡n\log{n}logn的复杂度进行单点修改和区间求和，同时配合差分数组等结构，还能做到区间修改、单点查询和区间修改、区间查询等功能，相比与线段树来说更为简单和优雅。 基本知识 树状数组最为重要的一个设定就是lowbitlowbitlowbit——二进制最低位的1及其后面的0所组成的数字，相比与前缀和，树状数组的每一位维护的是(i−lowbit(i),i]\left(i-lowbit(i),i\right](i−lowbit(i),i]的区间和，比如6，二进制为110，那么这一位维护的就是原数组6到4100的区间和（不包含4）。 那么要如何计算一个数的lowbitlowbitlowbit呢？如果用一个1作为check来判断每一位是否是1，那么代码大概长这样： 1234for(in ...

话不多说，直接开始 xor 下载下来有一个xor的无后缀文件和一个叫_MACOSX的文件夹，里面是一个叫._xor的文件，先查壳 ._xor是一个二进制文件，就不放截图了省内存 用ida打开xor文件 用notepad–打开._xor文件 二进制文件有点意义不明，先看主函数，还是熟悉的strncmp函数，可以看到，输入的字符串是_b 从前面的程序可以看出flag长度为33，输入的字符串每一个字符跟前一个字符异或后才跟global比较，这个字符串的值也很好找，直接点就行 因为一按截图键窗口就没了，所以只能用手机拍照 那么接下来只要找出符合的输入就行了，因为异或的自反性，要还原一个字符只需将其与前一个字符异或即可 最终flag为QianQiuWanDai_YiTongJiangHu 不得不说，这个global字符串是真的抽象，一堆转义，眼睛都要看瞎了…… 所以那个二进制文件到底有什么用 helloword 是不是少了个l 下载下来一个apk文件，用jadx打开，找主函数，直接就能看到flag，虽然看不懂java reverse3 之前写过了，偷个懒 不一样的flag 一个exe ...