2301_81692739的博客

原创 2024 吉林 CCPC

这里可以用小顶堆或者栈，如果后续出现一个较大的值，就将所有小于a[ i ].se的弹出去，按照 y 进行排序，由于数据范围比较小，可以直接枚举找到小球接下来。先暴力用第一个点和所有点，计算斜率。将 k ,x , y 带入，如果b值相同，说明在同一条直线上。判断每一条平行线上，点的x坐标。由于直接求斜率会有误差，可以两边同乘 （x1-x2）看到连通块第一想到的就是并查集，但实际上用不到。每次将后面大于当前的点，加入并查集，并弹出。，这样保证每次都可以用最小值来连接。分别排序，进行两次就可以过。

原创 欧几里得 ---＞ 裴蜀定理 ---＞ 拓展欧几里得

费马小定理求逆元，模数需要是质数。扩展欧几里得求逆元只需 a 与 m 互质。对 b 取模，可以看作 **+b y ** (y为负值)题目：判断 ax+by =c 的解。：对于任意整数 (a, b)

原创 2025 吉林CCPC

赛时：6道A题不可惜，因为赛后WA了好几发才A.今天的题目比较简单，大家过题数差不多，同样凡过的题都没有WA。

原创 PTA练习题

主要考察字符串函数的运用，当然也可以自己暴力写。multimap 没法下标索引，用insert。先用一个短的字符串替换，输出时再替换为长的。

原创 2025 河北ICPC( D. 金泰园（二分）-- C.年少的誓约(公式转化))

赛时C、D题没写出来，太可惜了。虽然目前只过了7道题，不过也还可以。今天是CCPC训练赛第一天，我们队稳扎稳打，凡是过的题，都没有WA就是慢了一点，但目前不构成影响。希望明天训练赛，大脑在线。今天D题竟然没看出二分！！！每次的二分都意料之外，虽然现在看来不过如此，没A也是事实。

原创 博弈论（巴什、nim、......SG打表）

SG函数（Sprague-Grundy Function）是博弈论中解决公平组合游戏（Impartial Combinatorial Games，简称ICG）的重要工具。定义SG函数的参数是游戏的状态，返回值是一个非负整数。公式：$sg(x)=mex({sg(y)∣y是x的后继状态}) $其中，mex（Minimum EXcludant）表示从集合中排除的最小非负整数。例如，mex{0, 1, 2} = 3。后继状态后继状态是指从当前状态通过合法操作能够到达的所有状态。性质1。

原创 G-组合数的奇偶——河南省第十六届ICPC大学生程序设计竞赛（区间子集数）

本文讨论了如何利用卢卡斯定理判断组合数的奇偶性，并在此基础上解决给定区间内数字子集数量的问题。文章提出了两种方法：数位动态规划（数位dp）和减去不符合条件的子集。数位dp通过遍历二进制位，选择或不选择每一位来累加子集数量，确保只计算区间内的值。第二种方法则通过计算每个数字的子集总数，再减去小于区间下限的子集数量，得到最终结果。两种方法的核心目标都是求解区间内数字的子集数量，第二种方法更易于理解。

原创 2023年河南CCPC（ABCEFHK）

个人赛3.5h 赛时过了3道，补题7道。还有一道大模拟没补。2024年CCPC，赛时也是过了3道，补题六道。

原创 Acwing 998. 起床困难综合症(bitset,dp)

设定两个串，一个p1全置1，一个p0全置0.分别进行操作，看某一位是否可以置一。由于sum<m , 所以优先考虑 p0,选择p1时，只需要保证sum<m。由题目易知，每一位都是独立，互不影响的。我们只需要知道，某一位怎样才能变成1.用 bitset 比较便捷。

原创 Codeforces Round 1015, Div. 1 + Div. 2

f (b) 是 mex(b) 的最小可能值，所以最多进行m次操作，视作 进行 m 次。设n 放在位置 x ,则 max(a[x-1],a[x])=n，应满足 n%x=x-1。​ n / (m+1) ，所以 f (b) 最大为 n / (m+1)-对于所有 2≤i≤n ，满足 max(pi−1,pi)mod。​ 每个数字最多删除m 次，要想留下来，至少存在 m+1 个。每次删除 k 个 ，删除m 次，最后剩下 n-m * k。进行排列， f (b)最大为 n - m * k。

原创 数三角形 （公式推导，平方和公式）

“满纸荒唐言，一把辛酸泪。都云作者痴，谁解其中味”

原创 我的创作纪念日

这一年的博客见证了我的ACM之路，我的青春里也有这样充实幸福的两年。 “今年花胜去年红”

原创 Codeforces Round 1014 (Div. 2)

又是掉分的一场。

原创 Codeforces Round 1011 (Div. 2)

一共有n个盘子，第 i 个盘子在 i 分钟才出现。每个盘子里有 k 个寿司，需要 k 分钟吃完，美味值为。

原创 Educational Codeforces 176 (Div. 2) —— D. Equalization（最小代价dp）

这个性质表明，多次取整和除以 C 的幂次方的操作可以合并为一次操作。

原创 Codeforces Round 1012 (Div. 2) 3.23

根据“0/1”,分别从“zhuo”“p”小顶堆中取出位置，同时用map标记去重。题意很好懂，每一行每一列从左往右，从下往上都是非递增，也就是0需要在前面。每次先找到距离每张桌子最近的点，将其存在"zhuo"小顶堆里。刚开始太草率了，只开了个两重循环，感觉不对劲，果然wa了。数据类型为“tuple”,分别存放: 距离，x , y。注意：只能从走廊穿过，肯定不能踩着桌子过！将这张桌上的每个点全存放在“p”小顶堆里。到达桌子的右上角需要：x+y+2。开两重循环，将可能到达的位置用。其他三个位置需要：x+y。

原创 Codeforces Round 1009 (Div. 3) C(位掩码)

行文至此，不得不提一下zx的至理名言。 “异或是不进位加法”这就是位屏蔽的神奇。注意：运算符的优先级。

原创 计数组合型dp（四种小球盒子问题总结）

本篇将结合两个题目从dp入手来解决：n个相同的小球放进k个相同的盒子，有几种分法同时总结四种小球盒子问题。如此，忍痛言，无复憾矣。 悟已往之不谏，知来者之可追。实迷途之未远，觉今是而昨非。

原创 整除分块 (+例题变形K-取模 2022年天梯赛（GPLT）上海理工大学校内选拔赛)

利用除法的性质，将问题分解为若干个块，每个块内的值相同，从而减少计算量。整除分块在解决一些数学问题时非常有效，特别是当问题涉及到大量除法操作时，它可以大大减少计算时间。

原创 线性dp(数字三角形，LIS,LCS，LCIS)

为了提高效率，我们可以在遍历 j 的过程中维护一个最大值 mx，表示在当前 i 的情况下，所有 f [i-1] [k] 的最大值，其中 k < j 且 B[k] < A[i]。既然两个数组都是1-n的全排列，那么可以用一个新的数组c存放b[i]在数组a中的位置，只有c中递增的子序列才可构成a,b的公共子序列。包含a[i] 的子集，将这个子集继续划分,依据是子序列的倒数第二个元素在b[]中是哪个数（也就是由谁递推而来）不包含a [i]的子集，最大值是f[i-1] [j]首先判断公共子序列中是否包含a[i]

原创 D-小柒分糖果_牛客练习赛135（组合数，阶乘，逆元）

这道题也算是给之前的一个交代，去思考”岗位分配“那道题，整理组合数的几种求解方法，这些并不是徒劳。不过还是忘记了”逆元之间的计算推导“，这次没能用上，至于当时的理解思考，也已忘记了。

原创 Educational Codeforces Round 175 (C.二分 D.树形结构、dp)

上一层的总和递推下一层，所以要分层计算，用二维vector类型v，存放每一层的节点。层数如何得知呢？用数组d来计算d[i]=d[f[i]]+1。想知道每一层所有节点的序列数，就用sum不断清零、累加。

原创 卢卡斯定理判断组合数奇偶（Codeforces Round 1006 (Div. 3)——F）

为什么提到“奇偶”“对2取摸”“杨辉三角”“卢卡斯定理”？​ 根据三角形定义，易知：此三角形正是杨辉三角对2取模

原创 第 26 场 蓝桥月赛 2025.2.22

第一次打，题目并不难，算法涉及少，思维偏多。不太习惯题目描述的风格。这次wa太多了，过题速度也慢。

原创 2025.2.2牛客周赛 Round 79 IOI

这次简单+题量少，全补完了，似乎从来没有过。其实就补了最后一题，也很简单，E虽然没过，但是思路是对的。

原创 求组合数（递推法、乘法逆元、卢卡斯定理、分解质因数）

递推法，了解杨辉三角、二项式、组合数之间的联系 。数据较大，运用乘法逆元+快速幂。卢卡斯定理，n,m比较大，p比较小， 分解+乘法逆元求组合数法。

原创 9.12-13 codeforces Div 2

这两天Div 2,都只补了2题。昨天又有一种不知道怎么打比赛，怎么做题，无从下手

原创 9.11 codeforces Div 2

比如（15，9），可以变成（15，18），此时他们的差值为3而不是6。这样太武断了，且没有说服力很强的论证，看起来就不像答案。此时为（14-6=8），这样并不是最优的，（11-4=7才是）。​ 我的整体思路没错，计算一个C,数组对C取模，将结果围成一个圈，两种转圈方法，取最小的。整数 a 、 b 和 c ，使得 gcd(a,b)=gcd(b,c)=gcd(a,c)=1。审题不清，刚开始以为下标在某范围内，进行±，但平常也用不上算法，后来开始写。，进行+1或-1.每操作后，输出最大值。

原创 P1045 麦森数

输入n,求出2p−1位数和500个尾数。

原创 背包习题

原创 Stack(习题)

原创 萌新联赛 2024第（六）场：郑州大学 8.21

原创 约瑟夫环问题（模板题，递推，树状数组，双端队列）

约瑟夫问题，接下来分两类问题讲解：求**最后活下的人，出局顺序**。其中皆有**数学递推公式做法**。 对于出局顺序还加了 **双端队列，树状数组**做法，时间复杂度更低。最后还有编号从1开始，与从0开始的不同之处。

原创 图片合集+-+

文章目录线段树8.23线段树8.23

原创 Codeforces Round 967 (Div. 2) 8.20

这次题目看似复杂，混淆罢了。

原创 并查集（模板+例题）

将物品价值从大到小排序，先给他安排时间，安排好，将。

原创 8.14 萌新：第五场 信息工程大学 树状数组，ST表

链接：https://ac.nowcoder.com/acm/contest/88527/D来源：牛客网Alice 有 n 个数，她可以对这 n 个数执行以下两种操作：​ 1. 将区间 [L,R] 上的所有数加上 d。

原创 背包九讲（灵魂版）

多重背包单调队列优化、有依赖的背包问题不明白？dp思想模模糊糊？快进来学习吧

原创 Codeforces Round 965 (Div. 2) 8.10

看题得认真，不能迷糊，不然太费时间。

原创 洛谷 外星密码 正确代码

这就是一个递归分治，我不会这样写，所以记录一下。还有一个原因，前人代码好多已经过不了了，会TLE,RE。我猜测是因为19年的一个题解是这样，好多人照着敲。现在我们给你外星人发送的密码，请你对其进行解压缩。，类似于后面这种压缩之后再压缩的称为二重压缩。while外面的return，也是不能缺，用简单样例。输入一行，一个字符串，表示外星人发送的密码。输出一行，一个字符串，表示解压缩后的结果。