- 博客(128)
- 收藏
- 关注
RSS订阅
原创 观察者模式
定义“观察者模式”是一个坑很多的模式。要实现一个简单的观察者模式可能并不困难，但如果想要实现好一个没有 bug、功能完善的观察者模式，或许也不容易，这其中有许多值得注意的地方。本文将通过一个布告板的例子1，首先用最直观的方式实现，分析代码实现中可能存在的问题，引出并应用观察者模式，以达到“优美”地解决案例的目的，在读者对观察者模式有一定了解之后，提出关于观察者模式的一些小知识点，以及不同场景下应用该模式需要注意的地方，最终介绍观察者模式的实际应用。案例现在已经有一个能获取实际气象数据（温度、湿度、
2020-12-15 00:17:07
248
原创 迪杰斯特拉 & 堆优化
单源最短路该博客的单源最短路算法要解决的就是在一个没有负权边的图上，找出所有点与源点 sss 的最短路径，这样一个问题。这里介绍迪杰斯特拉 O(n2)O(n2)O(n^2) 解法与堆优化 O(mlogm)O(mlogm)O(m\log m) 解法，其中 nnn 为图上节点数量，mmm 为图上边的数量。 不介绍也不推荐玄学复杂度的 spfaspfaspfa 解法。朴素写法思路：贪心...
2018-02-22 02:14:29
9781
6
原创 组合博弈问题：从 dfs 到 SG 函数
定义只有两个玩家轮流进行游戏；游戏规则对游戏双方是平等的；游戏能在有限的步骤内达到其中一方胜/败的局面，没有平局；双方都采取最优策略，面对相同的状态，对于游戏双方的必胜/必败态是确定的。必胜态与必败态首先，存在一个状态，使得先手为必胜态或者必败态，再根据以下两点，就可以确定所有状态的必胜/败态。如果一个状态的后继状态中，存在一个必败态，则该状态为必胜态；如果一个状
2018-01-16 00:14:23
471
原创 欧拉函数相关数论
欧拉函数 欧拉函数ϕ(n)\phi(n) 的百度百科定义是：“对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目(ϕ(1)=1)(\phi(1)=1)。”不如将小于改成小于等于，倒是省去ϕ(1)\phi(1) 的特例。关于欧拉函数的证明，不多赘述。本文侧重于欧拉函数在编程竞赛中的应用，这里只将其中三个知识点提出来（其他公式皆可由这三个公式推导得出）： 1.ϕ(1)=1\phi(1)=
2017-08-07 00:59:52
608
原创 从快速幂到dp 优化：矩阵快速幂
幂运算 nn 个aa 相加我们当然不会写成一个循环，nn 个aa 相乘我们自然要用幂运算。幂运算裸题题目链接 L1-012. 计算指数解法 用上cmath 头文件中的pow() 函数即可，由于本题数据范围极小，所以根本不会出现什么精度问题。过题代码#include #include using namespace std;int
2017-07-14 21:05:06
2569
原创 C++ 实现BigInteger 类
本文提供可复用 C++ BigInteger 类的声明与实现，读者可直接复制使用或从 Github 上获取代码，笔者希望能提供“像使用基本数据类型一样方便”的高精度整数类
2017-07-01 22:32:43
9906
2
原创 浅谈数据压缩算法
压缩算法（Compaction Algorithm）指的是数据压缩的算法，主要包括压缩和还原（解压缩）的两个步骤。其实就是在不改变原有文件属性的前提下，降低文件字节空间和占用空间的一种算法。
2023-09-16 07:14:55
324
原创 数学位运算板子
这些函数都可以在函数名末尾添加 l 或 ll（如）来使参数类型变为 (unsignedlong或 (unsignedlong long（返回值仍然是int类型）。
2023-09-14 02:20:29
125
原创 Codeforces Round #532 (Div. 2)
Contests 链接：Codeforces Round #532 (Div. 2)A. Roman and Browser题意RomanRomanRoman 最开始打开了 nnn 个网页，所有网页要么是个测试网页，要么是一个社交网页，现在他打算每隔 kkk 个网页就关闭一个网页，要使得这两种网页的差的绝对值最大，求最大值。输入第一行为两个整数 n,k (2≤k&...
2019-01-16 20:58:55
1062
原创 Educational Codeforces Round 58
Contests 链接：Educational Codeforces Round 58 A. Minimum Integer题意输出不在范围 [l,r][l,r][l,r] 内的最小的正整数 xxx，要求 xxx 是 ddd 的整数倍。输入第一行为一个整数 q (1≤q≤500)q~(1\leq q\leq500)q (1≤q≤500)，接下去有 qqq 行，第...
2019-01-15 20:24:43
575
原创 Codeforces Round #531 (Div. 3)
Contests 链接：Codeforces Round #531 (Div. 3)过题数：5排名：176/9160A. Integer Sequence Dividing题意给定一个整数 nnn，将 [1,n][1,n][1,n] 以内所有的整数分到两个集合 AAA 和 BBB 中，每个整数只能被分到一个集合，要求两个集合中所有数字的和的差的绝对值最小，即：∣sumA−sumB∣|s...
2019-01-10 16:27:41
594
原创 Codeforces 985C Liebig's Barrels（贪心）
题目链接：Liebig’s Barrels题意 总共有 m=n×km=n×km=n\times k 个木板，第 iii 个木板的长度为 aiaia_i，要用这 mmm 个木板做成 nnn 个桶，每个桶由 kkk 个木板组成，每个桶的容积由构成这个桶的最短木板决定，要求所有的桶的容积差距不能超过 lll，问所有桶的最大容积和。输入 第一行为 333 个整数 n,k,l&...
2018-08-20 09:36:24
359
原创 Codeforces 985B Switches and Lamps（预处理）
题目链接：Switches and Lamps题意 有 nnn 个开关和 mmm 盏灯，每个开关可以控制几个灯，这些开关只能将所控制的灯变亮，问能否从中去掉一个开关，仍能使得所有灯都亮起来。输入 第一行为两个整数 n,m (1≤n,m≤2000)n,m (1≤n,m≤2000)n,m~(1\leq n,m\leq2000)，接下去为 nnn 行长度...
2018-08-20 09:34:52
291
原创 Codeforces 985A Chess Placing（暴力）
题目链接：Chess Placing题意 有一个 1×n1×n1\times n 的棋盘，nnn 为偶数，棋盘上的颜色是黑白相间的，在棋盘上放 n2n2\frac{n}{2} 个棋子，要求用最少的步数，使得所有棋子在的格子的颜色是一样的，每一步可以将任意一个棋子往左或者往右移动一位，棋子移动不能越过其他棋子。输入 第一行为一个整数 n (2≤n≤100)n&...
2018-08-20 09:33:14
290
原创 Educational Codeforces Round 44
Contests 链接：Educational Codeforces Round 44 过题数：3 排名：833/10094A. Chess Placing题意 有一个 1×n1×n1\times n 的棋盘，nnn 为偶数，棋盘上的颜色是黑白相间的，在棋盘上放 n2n2\frac{n}{2} 个棋子，要求用最少的步数，使得所有棋子在的格子的颜色是一样的，每一步可以将任意一...
2018-08-20 09:31:15
268
原创 Codeforces 1023E Down or Right（贪心）
题目链接：Down or Right题意 这是一道交互题，有一个 n×nn×nn\times n 的网格，其中有一些网格是可以行走的，而有一些是无法行走的，在可以行走的网格中，下一步只能往右或下两个方向移动到下一格可以行走的网格中，但是我们并不知道这个网格哪些格子是可以行走的那些无法行走。BobBobBob 要从 (1,1)(1,1)(1,1) 点走到 (n,n)(n,n)(n,n) ...
2018-08-18 21:33:07
331
原创 Codeforces 1023D Array Restoration（线段树）
题目链接：Array Restoration题意 有一个长度为 nnn 的序列，可以对这 nnn 个序列进行 qqq 次操作，第 iii 次操作选择一个区间 [li,ri][li,ri][l_i,r_i]，将这个区间内的所有数字用 iii 替换，每个位置上的数字至少被一个区间覆盖，最后将这个序列中的某几个数字改为 000。现在题目给出最终的序列，问是否存在合法的 qqq 次操作，能够得...
2018-08-18 21:18:23
479
原创 Codeforces 1023C Bracket Subsequence（瞎搞）
题目链接：Bracket Subsequence题意 给定一个长度为 nnn 的合法括号序列，其中的左右括号能完全匹配，要求从中找到一个长度为 kkk 的合法括号子序列。输入 第一行为两个整数 n,k (2≤k≤n≤2×105)n,k (2≤k≤n≤2×105)n,k~(2\leq k\leq n\leq2\times10^5)，其中 nnn 和 ...
2018-08-18 21:14:44
328
原创 Codeforces 1023B Pair of Toys（瞎搞）
题目链接：Pair of Toys题意 有 nnn 个玩具，第 iii 个玩具的价格为 iii，问有多少对玩具 (a,b) (a≠b)(a,b) (a≠b)(a,b)~(a\neq b)，它们的价值和等于 kkk，其中 (a,b)(a,b)(a,b) 和 (b,a)(b,a)(b,a) 被认为是相同的玩具对。输入 输入只包含两个整数 n,k&nbs...
2018-08-18 21:12:54
398
原创 Codeforces 1023A Single Wildcard Pattern Matching（瞎搞）
题目链接：Single Wildcard Pattern Matching题意 给定两个字符串 sss 和 ttt，长度分别为 nnn 和 mmm，sss 串中最多含有一个 * 通配符，通配符可以用任意字符串（也可能为空）替换，问能否将其中的通配符用某个字符串替换后，使 sss 与 ttt 串相等。输入 第一行为两个整数 n,m (1≤n,m≤2×105)n...
2018-08-18 21:10:30
259
原创 Codeforces Round #504 (Div. 1 + Div. 2)
Contests 链接：Codeforces Round #504 (Div. 1 + Div. 2) 过题数：3 排名：1013/7459A. Single Wildcard Pattern Matching题意 给定两个字符串 sss 和 ttt，长度分别为 nnn 和 mmm，sss 串中最多含有一个 * 通配符，通配符可以用任意字符串（也可能为空）替换，问能否将其中...
2018-08-18 21:08:15
576
原创 Codeforces 979D Kuro and GCD and XOR and SUM（字典树）
题目链接：Kuro and GCD and XOR and SUM题意 初始有一个空的集合，有 qqq 次操作，每次操作有两种选择： 给定 uiuiu_i，表示将 uiuiu_i 加入到集合中； 给定 xi,ki,sixi,ki,six_i,k_i,s_i，从集合中找到一个整数 vvv，要求 vvv 满足条件 ki|gcd(xi,v),xi+v≤siki|gcd(x...
2018-08-17 10:57:03
246
原创 Codeforces 979C Kuro and Walking Route（dfs）
题目链接：Kuro and Walking Route题意 在一棵 nnn 个节点的树上，(u,v) (u≠v)(u,v) (u≠v)(u,v)~(u\neq v) 表示从节点 uuu 到节点 vvv 的一条路径，其中 (u,v)(u,v)(u,v) 与 (v,u)(v,u)(v,u) 被认为是不同的路径，问有多少条路径不会先经过节点 xxx 再经过节点 yyy。...
2018-08-17 10:55:29
368
原创 Codeforces 979B Treasure Hunt（贪心）
题目链接：Treasure Hunt题意 KuroKuroKuro、ShiroShiroShiro 和 KatieKatieKatie 三人都有一个长度相同的字符串，每个字符串都只包含小写字母和大写字母，三个人都有 nnn 次对自己的字符串进行操作的机会，每次操作可以选择一个字符并将这个字符修改成另一个字符。一个字符串的价值定义为这个字符串中所有子串出现的最大次数，他们三人经过 n...
2018-08-17 10:53:50
345
原创 Codeforces 979A Pizza, Pizza, Pizza（瞎搞）
题目链接：Pizza, Pizza, Pizza!!!题意 用最少的线将一个圆平分成 n+1n+1n+1 块。输入 输入只包含一个整数 n (0≤n≤1018)n (0≤n≤1018)n~(0\leq n\leq10^{18})。输出 输出需要的线的数量。样例 输入 3 输出 2...
2018-08-17 10:52:03
238
原创 Codeforces Round #482 (Div. 2)
Contests 链接：Codeforces Round #482 (Div. 2) 过题数：2 排名：843/10089A. Pizza, Pizza, Pizza!!!题意 用最少的线将一个圆平分成 n+1n+1n+1 块。输入 输入只包含一个整数 n (0≤n≤1018)n (0≤n≤1018)n~(0\leq n\leq10^{...
2018-08-17 10:49:25
1083
原创 HDU 6357 Hills And Valleys（思维 动态规划）
题目链接：Hills And Valleys题意 给定一个长度为 nnn 的序列，可以选择序列上的一个区间 [l,r] (1≤l≤r≤n)[l,r] (1≤l≤r≤n)[l,r]~(1\leq l\leq r\leq n)，将这个区间上的所有数字翻转，求进行一次操作后能够得到最长非递减子序列的长度。输入 第一行为一个整数 T (1≤T≤1...
2018-08-16 21:35:05
554
原创 HDU 6356 Glad You Came（ST 表）
题目链接：Glad You Came题意 有一个长度为 nnn 的序列，序列中每个数字的初始值都为 000，接下来对这个序列进行 mmm 次操作，每次操作将区间 [li,ri][li,ri][l_i,r_i] 之间的所有数字 aiaia_i，都更新为 max(ai,vi)max(ai,vi)\max(a_i,v_i)，输出 mmm 次操作后 ⨁ni−1i×ai⨁i−1ni×ai\big...
2018-08-16 21:33:21
240
原创 HDU 6354 Everything Has Changed（计算几何）
题目链接：Everything Has Changed题意 在平面直角坐标系内有一个圆心在原点，半径为 RRR 的初始圆，以及 mmm 个圆心在 (xi,yi)(xi,yi)(x_i,y_i)，半径为 ririr_i 的圆，这 mmm 个圆两两互不相交且不会包含整个初始圆，这 mmm 个小圆将对初始圆进行切割，问最终初始圆的周长。输入 第一行为一个整数 T ...
2018-08-16 21:31:31
269
原创 HDU 6351 Beautiful Now（预处理）
B. Beautiful Now题意 给定一个没有前导零的整数 nnn，其十进制表示为 (x1x2⋯xm)10(x1x2⋯xm)10(x_1x_2\cdots x_m)_{10}，即 n=∑mi=110m−ixin=∑i=1m10m−ixin=\sum_{i=1}^m10^{m-i}x_i，可以对这个整数进行 kkk 次操作，每次操作选择两个整数 i,j (1≤i≤j≤m...
2018-08-16 21:29:17
198
原创 2018 多校第五场部分题解
链接：2018 Multi-University Training Contest 5 过题数：1 排名：470/704B. Beautiful Now题意 给定一个没有前导零的整数 nnn，其十进制表示为 (x1x2⋯xm)10(x1x2⋯xm)10(x_1x_2\cdots x_m)_{10}，即 n=∑mi=110m−ixin=∑i=1m10m−ixin=\sum_{...
2018-08-16 21:27:45
374
原创 Codeforces 980C Posterized（贪心）
题目链接：Posterized题意 给出 nnn 个整数和一个阈值 kkk，所有整数都在 [0,255][0,255][0,255] 的范围内，要求将所有整数分到一个不阈值大于 kkk 的区间内，并从这个阈值内选出一个数字代表这个阈值中的所有数字，[0,255][0,255][0,255] 内每个整数都只能属于一个阈值，问将 nnn 个整数都用所属阈值的代表数字替换后，字典序最小的结果...
2018-08-16 09:56:51
278
原创 Codeforces 980B Marlin（构造）
题目链接：Marlin题意 在一个 4×n4×n4\times n（nnn 为奇数）的网格中，需要设置 kkk 个障碍，这 kkk 个障碍不能设置在网格的边界上，要求从 (1,1)(1,1)(1,1) 到达 (4,n)(4,n)(4,n) 的最短路径数量等于从 (4,1)(4,1)(4,1) 到 (1,n)(1,n)(1,n) 的最短路径数量，两个方格之间的路径长度为 111，当且仅当...
2018-08-16 09:55:03
282
原创 Codeforces 980A Links and Pearls（瞎搞）
题目链接：Links and Pearls题意 给定一个只包含 - 和 o 的字符串，- 表示项链上的链，o 表示项链上的珍珠，将字符串首尾相连表示一条项链，每次操作可以将任意位置的链或珍珠拆下，插入到另一个位置上，问进行任意多次操作后，能否使得项链上任意两个相邻的珍珠之间的链的数量相等。输入 输入为一个字符串 s (3≤|s|≤100)s (3≤...
2018-08-16 09:53:22
195
原创 Codeforces Round #480 (Div. 2)
Contests 链接：Codeforces Round #480 (Div. 2) 过题数：3 排名：804/9913A. Links and Pearls题意 给定一个只包含 - 和 o 的字符串，- 表示项链上的链，o 表示项链上的珍珠，将字符串首尾相连表示一条项链，每次操作可以将任意位置的链或珍珠拆下，插入到另一个位置上，问进行任意多次操作后，能否使得项链上任意两个...
2018-08-16 09:51:12
961
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人