比赛链接：[牛客竞赛]第 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取 […]

比赛传送门：Dashboard - Codeforces Round #824 (Div. 2) - Codeforces A. Working Week（数学） 给定一个数字N，选择三个点进行封锁，必须封锁最后一个点，不能封锁第一个点，且任意两个封锁的点不能连续（中间必须有没被封锁的点），于是这三个封锁的点会将整个序列划分为三块，每块都有一个长度（没被封锁的点的个数），求这三个长度的最小差值的最 […]

在做矩形面积并之前需要了解线段树，不了解线段树的需要先对线段树的各种操作比较熟练后，方可学习扫描线。 线段树资料： 线段树 - OI Wiki (oi-wiki.org) 线段树详解 - Xenny - 博客园 (cnblogs.com) 好，现在你学会了线段树，接着往下看吧。 扫描线 现在我们用扫描线来求多个矩形组成的一个大图形的面积。 我们先假设有一条从下往上扫描的线（当然你从左往右也一样，后 […]

题目传送门：3695 -- Rectangles (poj.org) 题目大意 / Problem 给定若干个矩形（N <= 20），求某几个矩形的面积之和。 分析 / Analyse 因为矩形比较少，可以状态压缩来表示矩形是否被选中，先计算出所有的可能情况的交集，再用容斥原理来计算最终的面积（并集）。容斥原理中如果元素个数为奇数个就加，偶数个就减，这个可以通过状态中1的个数来判定。 复杂度 […]

题目链接：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 […]