快要比赛了，要抓紧时间力！ 1.拓展欧几里得exgcd 用于求ax+by=c的解，当c = k * gcd(a, b)时有解。 解集为\(x = x_0 + k * (b / d), y = y_0 - k * (a / d)\)，其中d为gcd(a, b)。 不难发现，x的最小正整数解一定是mod(b / d)意义下的，所以一般对方程的解法是先将x扩大c / d倍，再模上b / d即可。 模板题 […]

首先明确欧拉格式和龙格库塔算法是用来干啥的，他们都用来解决同一个问题： 求解常微分方程 本文所作的的各种概念均有简化，可能与学术界不同，尽可能简单的理解。 常微分方程一般长这样： 可见y的导数由x和y共同表示。 现在我们的任务是求出y函数，或者说能够通过y0得到许多个y函数上的点y1, y2, y3 ... yn，从而可以用插值等方法构造出y的多项式来，总是就是要能够得到y的信息。 朴素欧拉格式（ […]

题目链接：最长的 X - Problem - Daimayuan Online Judge ETOJ：P1003 - 最长的1 - ETOJ (eriktse.com) 有两种做法，第一种是二分。 解法一：二分 先将给定的序列转换成01串，其中'.'换成0，'X'换成1。 再给01串求一个前缀和记录0的个数，现在开始枚举右端点，然后二分得到左端点。 不难发现左端点应该尽可能原理右端点且区间[l, […]

题目链接：Problem - D - Codeforces 给定一个长度N，和一个取值范围M，现在要我们构造长度为[1, N]，元素大小为[1, M]的数组，使得其被删除的方法大于1种，问构造方案数有多少。 删除方法定义为：对于数组中任意一个元素ai，如果gcd(ai, i) == 1，那么这个元素就可以被删除，删除之后，右边的所有元素向左移动，长度减1。 现在我们考虑任意一个数组，一定存在至少一 […]

比赛传送门：第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（沈阳） G - The Witchwood（签到） 选出最大的K个数字求和即可。 F - Kobolds and Catacombs（排序 + Hash） 给定一个序列，将其划分为若干份，将每一份分别排序后，可以使得整体序列非降序，问怎样划分使得份数最多。 读入a序列，再将b序列作为a序列排序后的序列，从前往后遍历，如果某个区间 […]

题目传送门：最大异或和 - Problem - Daimayuan Online Judge 分析 不难发现用可以先预处理出异或前缀和，然后一段区间[l, r]的异或和可以用prefix[r] ^ prefix[l - 1]来表示。 现在问题就转化为对于一个r，在[1, r]的区间内找到一个l（当l == r说明区间内只有一个点），使得prefix[r]^prefix[l - 1]最大，那么l - […]

题目传送门：Nearest Opposite Parity - Problem - Daimayuan Online Judge 每个点出发可以往左走也可以往右走，注意可能会形成环，所以拓扑是不行的，可以用记忆化搜索。 默认dp[i]为0，这是一个不可能出现的结果，我们记作为“没更新过”的状态，如果dp[i] = -1说明更新过且到不了，如果为正整数说明是能到达终点的最小步数，这里一定要将res设 […]

比赛传送门：第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京） 题解按照难度从小到大排序。 K.K Co-prime Permutation（构造 + 签到） ，给定一个排列大小N和一个数字K要求构造一个有K个值与下标的最大公因数为1的排列。 比如样例5, 3，构造如下的排列： val 1 4 5 2 3 idx 1 2 3 4 5 样例 我看可以看到其中下标为1, 3, 5的三对二 […]

比赛传送门：Dashboard - The 2021 CCPC Weihai Onsite - Codeforces A. Goodbye, Ziyin!（签到 + 树） 签到题。 给定一颗无根树（没有指定根的，意味着任何一点都可以为根），问有多少个点作为根可以使得整棵树为一颗二叉树。 对于签到的树题，一般都不需要建树，只需要记录度数。我们想一下二叉树的特征：根的度数\(\le 2\)，其余点的度 […]

比赛链接：[牛客竞赛]第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海） G.Fibonacci（规律 + 组合数学） 在经典的斐波那契数列（1, 1, 2, 3, 5, 8...）中，给出一个N求出满足以下条件的(f(i), f(j))二元组个数： \(1 \le i < j \le N\)且\(f(i) * f(j) % 2 == 0\)。 分析一下，斐波那契数列如果对2取 […]