题目链接：GCD XOR - UVA 12716 - Virtual Judge (vjudge.net) 最近在看紫书的时候看到这道题，但是感觉紫书上写的有点云里雾里，对于一些“不难发现”的不等式解释不够详细，这里做一下解释。 题目大意 / Problem 给定一个正整数N，问有多少对正整数（A，B）使得\(gcd(a, b) = a\oplus b\)，且有\(1 \le B \le A \l […]

在pta可以补题。 题目大意 / Problem 给定一个不降序列，每次可以中间的元素（除了第一个和最后一个元素）进行一次操作： 先选择一个点删除，然后选一个点设置为任意的值。 过程中需要保证序列一直是不降的，序列的权值是所有相邻的元素的差的平方和（第一个和最后一个不相邻）。 问k次修改可以使得权值最大为多少。 思路 / Thought 发现修改点和删除点是一样的。比如在一个长度为9的序列中，可以 […]

比赛传送门：Dashboard - Codeforces Round #822 (Div. 2) - Codeforces A. Select Three Sticks 枚举所有点，选择一个点作为基准，计算所有点与基准的差的绝对值，取最小的三个相加，再从所有结果中取小就可以了。时间复杂度\(O(t*n^2*logn)\) B. Bright, Nice, Brilliant 这个构造太简单就不说了 […]

题目传送门：P1521 求逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路 / Thought 用dp[i]j[j]表示选取[1, i]的数组，且有j个逆序对的排列方案数。 dp[i]可以从dp[i - 1]转移过来，假设现在的数字是i，那么对于dp[i - 1]的所有状态，i可以插入到i个位置中去，如果插入到第1个位置，那么逆序对会增加i - 1个，如果插入第2个位 […]

为了熟悉各类算法原理，在这里整理一下一些需要经常练习的算法。 扩展欧几里得ex_gcd（求解ax + by = gcd(a, b) (mod p)） P1082 [NOIP2012 提高组] 同余方程 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) P1516 青蛙的约会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Problem - 2669 (hdu.e […]

题目传送门：第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（上海） D Strange_Fractions（解方程，数论） 解方程，设\(t = \frac{b}{a}\)，将方程两边同时乘\(t\)可以得到\(qt^2 - pt + q = 0\)，通过小学二年级学的一元二次方程求根公式可知：当\(p^2 - 4q^2 \ge 0\)时方程有解。由求根公式可以得到\(t = \frac […]

可以在PTA补题。 题目大意 / Problem 给定两个字符串s和t，求一个s的子串s'使得s'和t的最大公共子串长度不超过1，问s'的最大长度。 子串可以不连续。 思路 / Thought 先把字符转换成[0, 25]的数字方便处理。 根据题意判断应该是个DP。由于是一个和位置和字符有关的dp，状态可以设为\(dp[i][j]\)，表示到s的第i个位置为止，最后一个敏感字符（定义为存在于t中的 […]

题目链接：The 2022 ICPC Asia Regionals Online Contest (I) (pintia.cn) 在PTA可以补题。 题意 / Problem 给定一个长度为N的01串，有Q次询问。 对于一个01串，每次可以代价为0的删除任意一个1以及和它相邻的两个数字，或者代价为1的将某个0翻转为1。 注意这个01串是环形的，也就是头尾相连，比如100也可以代价为0的进行一次删除 […]

题目传送门：P3386 【模板】二分图最大匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路 / Thought 关于二分图的最大匹配，参考以下文章： 算法学习笔记(5)：匈牙利算法 - 知乎 (zhihu.com) 最大匹配的思路可以这么理解：dfs(x)函数是用于判断x能否在另一边占到坑位，如果能那就占着，如果已经有人了就看能不能让这人去别的地方，如果可以就占着，否则 […]

使用试除法得到质因数的复杂度是\(O(\sqrt{n})\)，如果数字较大比如\(10^{18}\)就束手无策了。 在上一篇文章有写到Miller Rabin可以在\(O(klog^{2}{n})\)的复杂度下判断一个数字是不是素数，这次要介绍的Pollard Rho（普拉德柔）算法就是结合Miller Rabin的快速素性检验来进行的一个复杂度大约为\(O(n^{\frac{1}{4}})\)来 […]