理解后缀自动机 2022/4/4重新看了一遍 我确信此时此刻我已经完全看懂了 可惜这里地方太小写不下 专门对克隆节点这一地方做了一张图 希望未来的我还能看得懂 Orz 2022-04-04 笔记 #SAM #字符串 #抽象
git进阶 git存储原理git的存储比我想象的暴力的多( 自己尝试了一下发现,先提交一个10M的压缩包上去,.git 文件的大小是10M多一点 然后随便改这个压缩包的一点字符,再提交一次,.git 变成20M了… 我曾一直以为它有什么神奇的办法可以记录任意类型文件的修改量,没想到它只是整个拷贝… 并且所有版本信息都存储在.git中,分支,提交节点什么的只是存储索引,因此git能够很快地创建和切换分支,我认为 2022-04-02 笔记 #git #版本控制
Atcoder Beginner 245 G G - Foreign Friends题意:给出一个带边权的无向图,每个点有一个颜色,其中还有若干个特殊点。现在要求输出:每个点前往一个颜色与自己不同的特殊点的最短距离 解法:首先不考虑颜色,这个题就是一个魔改的dij,初始将所有特殊点加入队列跑一遍即可。 然后我们考虑颜色,可以将颜色按照二进制位拆开,枚举每一位,将所有在这一位上为0的特殊点加入队列跑一遍dij,并且更新在这一位上为1的点的答案。 2022-03-31 题解 #题解 #Atcoder
Codeforces Round 779 div.2 D2F D2. 388535 (Hard Version)题意:给出两个数 $l,r$ 和一个数字集合 $a$,有某个 $x$,使得 $[l,r]$ 范围内的这些数分别异或上 $x$ 之后,结果恰好能组成序列 $a$。要求找到一个合法的 $x$,保证有解。 对于每一位去考虑:如果在某一个二进制位上,两边集合0和1的个数不相等,比如 $l…r$ 中共有3个0,2个1;序列 $a$ 中共有2个0,3个1,那么 2022-03-29 题解 #codeforces #题解
Educational Codeforces Round 117 D. For Gamers. By Gamers.题意:玩家有 $C$ 块钱,可以从酒馆中招募随从,每个随从有攻击力 $d_i$,生命 $h_i$,花费 $c_i$ 块钱。接下来有若干轮战斗,每轮战斗有一个敌人,攻击力 $D_j$,生命 $H_j$。每轮相互独立(钱也独立),玩家可以招募若干个相同随从来和怪物战斗,但要求己方没有随从会死亡。问每一轮战斗需要花费至少多少金币 战斗不是回合制的,双方连 2022-03-23 题解 #codeforces #题解
Codeforces Round 774 div.2 DEF D. Weight the Tree题意:给定一棵树,每个节点有一权重 $w_i$,若一个节点的权值等于其相邻点的权值之和,则这个节点是好的。现在你可以为每个,使得好的点数量最多,在这基础上,还要使得总权值最小,输出赋值方案。 首先想到,除了 $n=2$ 的情况,相邻两个点不可能都是好的 对于不好的点,肯定让它为1($w_i\ge1$),那么好的点的权值一定等于其度数,我们要选上一些不相 2022-03-05 题解 #codeforces #题解
Codeforces Round 773 div.2 F F. Two Arrays题意:给出 $n$ 个数组,每个数组都有 $m$ 个不同元素,有权值 $w_i$,我们称两个不包含相同元素的数组是匹配的,要求匹配的数组对当中, $w_i+w_j$ 的最小值($n\le10^5,m\le5,a_i\le10^9$) 奇技淫巧: 哈希,我们可以把 $w$ 映射到一个很小的范围上去(比如1000以内),可能会产生冲突,但要导致最终结果出错,当前仅当作为答案选 2022-02-23 题解 #codeforces #题解
Codeforces Round 772 div.2 A-F A. Min Or Sum题意:有一个数组 $a$,你可以进行任意次操作:取两个数 $a_i,a_j$,将这两个数分别改为 $x,y$,要求 $a_i|a_j=x|y$ 问可能得到数组总和最小值。 我们显然可以把二进制中每一位上多余的部分全部删光,只留一个,答案即所有数或起来 ll n, m; void solve(){ cin >> n; ll a 2022-02-20 题解 #codeforces #题解
Codeforces Round 770 div.2 EF E. Fair Share题意:有 $n$ 组物品,第 $i$ 组有 $m_i$ 个,每个物品有一个编号,保证每种物品出现偶数次,每组物品有偶数个,要求将所有物品划分为两组,使得一组中有每种物品各一半,每组物品各一半。 首先将问题抽象出来,组别和物品类别其实没有什么区别,都是物品的属性; 建图:左边点表示组别,右边点表示类别,$i$ 组中包含物品 $j$,则连边 $i,j$ 因为保证了物品出现偶 2022-02-06 题解 #codeforces #题解