Fracture_Dream-CSDN博客

很好的一道“签到题”，想了两个小时一分没有，破防了。考场上想到了定义dpij0/1表示处理完前i个数，当前数为j，是否被修改的方案数，然而不会去重，遂开摆。所以为了的统计方案数，我们增加一种状态dpij2表示当前位既有可能被修改，又有可能未被修改的方案数，请注意这种状态与其它两种状态并不存在所谓的，一定的情况就只能属于01，可能的情况就只能属于2。当然为了方便些，下文中dpij0/1/2，分别表示表示处理完前i个数，当前位为j，未被修改(0。

2024-10-09 22:21:10 892 2

原创 Day44【欧拉回路】

欧拉回路典中典trick。不难想到把白边拆成2条，那么对于某个连通块，其最多会走一次回路，那就是欧拉回路（如果有两个回路显然可以合并在一起），所以对每个联通块分别判定其所有点的度数是否为偶数即可。用并查集易维护，注意如果初始全为白就不操作。

2024-10-08 23:45:41 925

原创 Day47【最小生成树】

所以我们先跑一边生成树，把白边先全加进去，再把黑边加进去，此时加入的黑边就是必须加的，然而这样有一个思维小漏洞，必须加入的黑边组成的集合不是唯一的，但我们任选其中一个集合是对的，为什么？这些边的出现情况，如果还不出现，那么就意味着，接下来无论怎么修改，这些边肯定不会出现，置为极小值也同理对应着最坏情况，如果这些边还出现了，那么无论接下来怎么修改。没试过，但正确率应该感人，为什么，因为图可能不连通，又是为什么，考虑一个问题：有些黑边是必须加的，换个意思说，不加这些黑边图联通不了！

2024-10-08 21:58:18 905

原创あHit Your Heartあ语录

你喜欢吃草莓，你会毫不犹豫的买下它，如果你不喜欢吃香蕉，但考虑到香蕉助消化，你还是会买它。所以，喜欢是单纯的，不喜欢，才会权衡利弊，在你犹豫的一瞬间，其实已经做出了选择。> 人生就是一列开往坟墓的列车，路途上会有很多站，很难有人自始至终陪你走完，当陪着你的人要下车时，即使不舍也要心存感激，然后挥手道别。而是你明白，你和这个人真的没有以后了，以后，他给过你的没有给过你的，都要给另一个人了，而你，连眼红都没有资格。> 如果真的有反方向的钟，我希望回到刚遇见你的时候，因为那个时候，我连你叫什么都不感兴趣。

2024-08-06 16:28:46 215

原创珠海行 ʕ̯•͡˔•̯᷅ʔ

集训一期的最后一天，上午疯狂擤鼻涕，甚至把同桌的一包纸用完了。下午果不其然开始发烧，遂请假，有点担心明天的旅行。晚上情况好转，起来追了会番，玩了会王者。追完一部番后脑袋开始晕，赶紧上床睡觉。（危。

2024-08-06 14:56:40 856

原创「PKUSC2018 星际穿越」Solution

有注释的部分应该很好理解，瓶颈在于框出的两行代码，网上大多数题解这一部分都没有写明白。注意，在上述推导过程中，我们并未考虑从起点往右跳的贡献，这一部分会在后文详细阐述。因此，我们只需要考虑起点往右跳的情况，就可以保证递推的重要性，因此。最开始往右跳的贡献，所以我们要强制选择一个点，那么为什么选择了。在任意最优情形下，只有起点可能往右跳，其他点一定只会向左跳。，所以考虑了也无所谓），发现这样初始化代入上述例子也是对的。，因此一定尽可能往右跳，才能最小化步数。的做法可得，我们没有考虑往右跳的情况。

2024-05-10 00:25:25 992

原创「Dasha and Photos」Solution

给定一个n×m的方格，每个格子里有一个小写英文字母。现在你有k个n×m的方格，这些方格都是给定方格的基础上将左上角为aibi，右下角为cidi的矩形区域的方格中的字母替换成字符ei。定义两个方格的距离为所有格子中字母在Ascll码的差累和。你要找到k个方格中的一个方格，满足它到其他k−1个矩阵的距离之和最小，并输出这个最小值。

2024-05-08 00:09:20 1076

原创「Differences」Solution

给定一个长度为n的字符串，从中选出一个子串，使得字串中出现次数最多的字母与出现次数最少（不能为0）的字母的出现次数相差最大，请求出这个最大值。

2024-05-03 09:55:20 949

原创「Pudding Monsters」Solution

给定一个n×n的棋盘，其中有n个棋子，每行每列恰好有一个棋子。对于所有的1≤k≤n，求有多少个k×k的子棋盘中恰好有k个棋子，输出其总和。n≤3×105。

2024-05-01 23:58:41 2290 1

原创「Transmitting Levels」Solution

给定一个n个元素的环形数组aq次查询，每次给定一个k，将数组划分为若干个连续段，使得每一段的和都不超过k，最小化连续段个数。

2024-05-01 19:56:16 67

原创「Nastya Hasn‘t Written a Legend」Solution

给定长为n的数组a，长为n−1的数组k。试支持以下2+ i x，表示ai←aix，然后重复以下过程：若ai1aiki，则ai1←aikii←i1，否则结束本次操作。s l r，输出il∑rai。

2024-05-01 09:41:06 946

原创「Destiny」Solution

给定n个元素，q次询问。每次给出三个参数lrk，询问区间lr内是否存在出现次数严格大于kr−l1的数。如果有，输出最小的那个数，否则输出−1。

2024-04-30 21:38:32 486

原创「Bear and Bowling 4」Solution

给一个长度为n的序列a，选取一个连续子序列axax1axk−1使得∑i1ki⋅axi−1最大。

2024-04-30 19:45:46 639

原创「Imbalance Value of a Tree」Solution

给定一颗n个节点的树，每个点有一个点权ai。定义Ixy表示x到y的路径上最大点权与最小点权的差值。求出∑i1n∑jinIij。1≤nai≤106。

2024-04-28 23:22:00 1187

原创「Good Subarrays」Solution

我们定义一个数组b是好的当且仅当所有的bi≥i。现在给你q次操作，每次操作有两个数p和x，求出把ap赋值成x后a数组好的子序列的个数，每次。

2024-04-28 22:08:18 775

原创「Two permutations」Solution

给定两个长度为n的排列ab，以及q次询问，每次询问给定l1r1l2r2，求出有多少个数x满足x∈aii∈l1r1且x∈bii∈l2r2，强制在线。

2024-04-20 23:21:10 260

原创「High Cry」Solution

给定长度为n的数组n，求出有多少个区间满足区间或大于区间最大值。n≤2×105。

2024-04-19 23:28:34 971

原创「ケーキの貼り合わせ (Cake 3)」Solution

你要从n个蛋糕中选择m个，每个蛋糕有vc两个属性，令你选择的蛋糕编号为k1到kmi1∑mvki−i1∑m∣cki−cki1∣注意km1k1。

2024-04-17 00:03:25 951

原创「Boring Queries」Solution

给定一个长度为n的序列a以及q次询问。每次询问包含2个整数lr，你需要求出区间lr的最小公倍数对1097取模的结果。询问强制在线。对于每次读入的xy，你需要进行以下操作得到lrlxlastmodn1rylastmodn1last为上次查询的答案。特别地，如果l比r大，交换lr。

2024-04-12 23:51:08 460 1

原创「Positions in Permutations」Solution

给定nm，对于一个长度为n的排列pFpi1∑n∣pi−i∣1求有多少个排列满足Fpm，答案对1097取模。1≤m≤n≤103。

2024-04-11 00:29:26 997 1

原创「Lucky Array」Solution

定义幸运数为只包含4和7这两个数字的数。例如477444都是幸运数字，但516467不是。给定长度为n的数组，进行m个操作。add l r dlrdcount l rlr保证所有数操作前后都不超过104。请你编一个程序来执行这些操作。

2024-04-09 23:56:44 581

原创「Sasha and Array」Solution

在本题中，我们用fi来表示第i个斐波那契数（f1f21fifi−1fi−2i≥3。给定一个n个数的序列a。有mal∼arxil∑rfaimod10971≤nm≤1051≤ai≤109。

2024-04-08 23:55:47 926

原创「Phoenix and Berries」Solution

有n个盒子，每个盒子里有ai个红球和bi个蓝球。现有无数个可以装k不必用完所有小球，问最多能装满多少个容器。

2024-04-08 21:39:05 1160

原创「Bombs」Solution

给定两个长度为n的排列ab，对于一个初始为空的集合进行以下操作：对于每个i，将ai加入集合，若visi1，将此时集合中的最大值删除。现对于每一个i，求出∀j∈1i−1visj1的情况下，进行一次操作后集合中的最大值。

2024-04-07 00:32:28 944

原创「Fibonacci Additions」Solution

给定两个长度为n序列ab，以及模数MOD。试支持以下操作：给定lr，对于∀i∈lrai←aifl−i1，其中f为斐波那契数列（f1f21进行q次操作，每次对a或者b进行操作，回答每次操作后a与b数组在模意义下是否相等。

2024-04-05 23:57:59 800 1

原创「快速傅里叶变换」总结

作为 NOI 大纲里的十级算法，FFT拥有着逼格十分高的名称，也十分令人头疼？（雾cki0∑kaibk−iFFT的核心思想在于：将一个多项式转化成点值表示法，再由点值表示法推出原多项式。

2024-03-26 22:11:31 1062

原创「终末之诗」

终末之诗......

2024-03-26 16:11:44 451

原创 Solution -「ABC 217」EFG

将所有的插入操作先存进一个临时序列。在遇到排序操作时再处理这些序列里的元素。具体来说就是直接丢进优先队列。

2024-03-26 16:01:44 733

原创【差分约束系统】总结

是求解多个不等式的合法解的算法，因以两变量之差与一常量关系的形式出现，故称作差分约束。数学形式表示如下：该算法旨在对于以上 n 个未知数，m 个不等式的不等式组求解。

2024-03-26 15:53:09 2296

原创【魔力树】题解

【代码】【魔力树】题解。

2024-03-26 15:51:09 118

原创【二次扫描与换根】总结

在一棵无根树上需要以多个节点为根求解答案，可以运用。具体操作是通过实现一次自底向上的深度优先搜索和一次自顶向下的深度优先搜索来计算“换根”后的解。

2024-03-26 15:48:56 873

原创【初等数论】阶断性总结(未完结)

数论是信息竞赛中一重大分支，其主要研究整数环的整除理论及同余理论，此外它也包括了连分数理论和少许不定方程的问题。

2022-10-13 13:11:02 361

原创【Genotype（基因串）& 玩具取名】题解

Genotype 是一个独特的基因串

2022-10-13 13:06:37 292

原创图论入门（完结）

- 图的基本概念（已更）- 图的存储结构（邻接矩阵、邻接表、链式前向星）（已更）- 图的遍历（深度优先、广度优先）（已更）- 一笔画问题（欧拉回路，已更）- 哈密顿路问题（已更）- 最短路径（已更）- 最小生成树(已更)

2022-10-12 14:01:46 13474 7

原创论一个算法【哈希】

通过一种计算方式，将每个值映射到一个唯一对应的键值。并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为哈希表，这一映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址

2022-10-12 13:58:48 364 1

原创【牛牛的跳跳棋】dp解法

当棋子位于第 i 个格子时，它的下一步可以移动到[𝑖 − 𝑝𝑖, 𝑖 + 𝑝𝑖]范围内的任意一个格子，每次可以使得一个格子的弹力系数𝑝𝑖 + 1，请输出最小操作次数，以及操作序列。

2022-10-12 13:42:36 534 2

cqbzliuhongyi的博客

原创 Day49 【强联通分量】

原创 Day48【NOIP模拟赛13】