Sep 17, 2021
数字逻辑设计 - 总结
1.Duality - can only be used in statement proof, not in simplification. Here are some interesting equations about boolean algebra:Distributive:$$
x + y · z = (x + y) · (x + z)
$$Absorption:$$
······
Sep 14, 2021
NOTES ON MAKING M.U.S.I.C!
artist namerys<rys in Polish means lynx in English and that's my favorite animal! LOLand it sounds like r-ee-th actually.current daw:）Cakewalk by Bandlabmy lovely（and some of which expensive ······
Aug 19, 2021
牛客网 10662D Fight against involution 题解
题目描述MianKing chose a course in this semester. There are $n$ students in this course, and everyone needs to write a final paper. Let $w_i$ denote the word count of the i-th student's final paper ······
Aug 19, 2021
牛客网 10662C Stone Game 题解
题目大意有 $n$ 堆石子，每堆最多有 $3$ 个石子，现在要把所有石子合并。假设要合并数量为 $a,b$ 的两个堆，则代价为 $$(a \text{ mod } 3)(b \text{ mod } 3)$$ 求最小代价。题解把所有石子数看成模 $3$ 意义下的数，每合成三的倍数可看做“消除为零”，首先把 $3$ 的跟其他的合并，即不产生影响，又没有代价，之后把 $1,2$ 的配对合 ······
Aug 18, 2021
牛客网 9925I Sky Garden 题解
题解定义 $A[i]$ 表示第 $i$ 层上某一点到该层点距离的和， $B[i]$ 表示第 $i$ 层上某一点到该层即内部所有层的点的距离和，维护这两个数组统计答案，每层的答案贡献为：$$
mA_i + 2m\left(B_{i-1} + 2m(i - 1)\right)
$$代码// https://ac.nowcoder.com/acm/contest/9925/I
#inclu ······
Aug 18, 2021
牛客网 10272L Let's Play Curling 题解
题解手画样例后发现最优的 $c$ 一定取在 $b$ 的任意两点之间的中点处，此时这个区间框起来的 $a$ 的个数即可以用了来更新最大值，得到答案，注意要在左右分别加一个 $0, +\infty$ ，因为在两边只有一个端点的情况也要考虑。代码使用离散化快速得到区间内 $a$ 的个数。代码// https://ac.nowcoder.com/acm/contest/10272/L
#in ······
Aug 17, 2021
牛客网 10272K Co-prime Permutation 题解
题解构造答案：$k,1,2,3,\cdots,k-1,k+1,\cdots,n$.代码// https://ac.nowcoder.com/acm/contest/10272/K
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#in ······
Aug 17, 2021
牛客网 10272F Fireworks 题解
题解我们假设做了 $x$ 个时成功出现至少一个为事件 $A$，则该事件的概率为 $\displaystyle P(A)=1-(1-p)^x$，期望时间为 $\displaystyle E(A)=\frac{nx+m}{P(A)}$，这个期望是单峰函数，三分出最小值即为答案。代码// https://ac.nowcoder.com/acm/contest/10272/F
#includ ······
Aug 16, 2021
牛客网 10272E Evil Coordinate 题解
题目大意给定二维平面的一个“陷阱”的坐标，给定一串上下左右的移动序列，问是否存在一组重排给定序列后的走法不经过陷阱。（序列长度 $\leq 10^5$，坐标的绝对值 $\leq 10^9$ ）题解由于不能经过的点只有一个，一个结论是一定存在一个每次的每个方向走到头的方案，所以只需要对方向进行排列然后判断。代码// https://ac.nowcoder.com/acm/contest ······
Aug 16, 2021
牛客网 9925M Gitignore 题解
题目大意给一个文件目录结构，要求某些文件可以“被忽略”，如果有一个目录下的所有文件都可以被“忽略”，则只需要对这个目录打一个标记，否则需要给下面的文件或目录打标记，问最少打几个标记就可以满足要求。题解每一个目录或文件看成文件树上的一个节点，每个节点有一个标记，$0$ 表示可以忽略， $1$表示不能忽略，两次 dfs 得到每个点最终的忽略情况，如果有一个点可以忽略，则更新答案并直接返回 ······
Aug 15, 2021
牛客网 9925G Fibonacci 题解
题目描述In mathematics, the Fibonacci numbers, commonly denoted as $f_n$, is a sequence such that each number is the sum of the two preceding numbers, starting with $1$ and $1$. That is, $f_1 = 1, ······
Aug 15, 2021
牛客网 9925D Walker 题解
题目描述As a world-famous traveler, Prof. Pang's research interest is to travel as many places as possible in his life.We have a segment $[0,n]$ and $n\leq 10^4$. There are two travelers on it. The ······
Aug 14, 2021
牛客网 9925C Sum of Log 题解
代码// https://ac.nowcoder.com/acm/contest/9925/C
// from https://www.cnblogs.com/lipoicyclic/p/14718739.html
#include <cstdio>
#include <cctype>
#include <algorithm>
#include & ······
Aug 14, 2021
牛客网 9925B Mine Sweeper II 题解
题解一个结论是，一个扫雷图的原图和反图的数字和相同，所以不存在不合法的答案，答案是 $A$ 的原图或反图，统计一下不一样的位置判断是输出原图还是反图。代码// https://ac.nowcoder.com/acm/contest/9925/B
#include <cstdio>
#include <cctype>
#include <algorithm ······
Aug 13, 2021
计蒜客 42545 The Answer to the Ultimate Question of Life, The Universe, and Everything 题解
题目大意给定整数 $x\,\,(0\leq x\leq 200)$，求整数 $a,b,c\in[-5000,5000]$ 满足：（若不存在则输出 impossible）$$
a^3+b^3+c^3=x
$$解题思路首先常规思路，对 $a,b$ 进行枚举，我们会发现 $a,b,c$ 全部是负数的情况不合法，合法的情况分别是：三个全为正两正一负一正两负所以在枚举的时候可以先 ······
Aug 12, 2021
UVALive 7614 Recursive sequence 题解
题解利用矩阵转移每次递推，初始向量为 $v=(a_2,a_1,2^4,2^3,2^2,2,1)$，每次转移时的向量为 $(a_n,a_{n-1},n^4,n^3,n^2,n,1)$，转移矩阵见代码中的 $M[7][7]$，矩阵乘法用快速幂来计算。代码// https://vjudge.net/problem/UVALive-7614
#include <cstdio>
# ······
Aug 11, 2021
洛谷P2051 AHOI2009 中国象棋 题解
题解首先我们发现，每行每列至多只能放两个棋子。我们定义 $\text{dp}[i][j][k]$ 表示考虑前 $i$ 行，其中的所有 $m$ 列中有 $j$ 列放了一个棋子， $k$ 列放了两个，之后讨论当前行放 $0,1,2$ 个时对应上一行的情况分类讨论进行转移。代码// https://www.luogu.com.cn/problem/P2051
#include <cs ······
Aug 10, 2021
洛谷 P2518 HAOI2010 计数 题解
题解题目的意思是给出一序列数 $n=n_1n_2\cdots$，问所有重排各位的数码得到的新数中比 $n$ 小的有多少。我们从高到低考虑，当放的数 $0\leq b<a[i]$时，后边可以随意放，都满足“小于”这个条件，此时合法的情况是，如果能放数码 $k$，会给答案贡献 $\displaystyle\binom{\text{cnt}[k]}{i-1}$ ，由于是分步，要乘完再 ······
Aug 10, 2021
HDU 5965 扫雷 题解
题目大意有一个 $3\times n$ 的扫雷区域，中间一行没有雷，并且会给出周围 $8$ 个位置的雷的个数（和扫雷游戏规则一致），问合法的雷的放置方案一共有多少？题解我们设给出的雷的情况是 $a_n$，我们假设第 $i$ 个位置（竖着看）放的雷有 $b_i(0\leq b_i\leq 2)$ 个，则如果第一列的情况确定，则后边的每一个地方的情况就已经确定下来了，所以我们枚举第一列的 ······
Aug 9, 2021
洛谷 P2602 ZJOI2010 数字计数 题解
题解定义 $\text{dp}[i][j][k]$ 表示长度为 $i$ ，且最高位为 $j$ 的所有数中出现 $k$ 的次数。首先预处理出该辅助数组，用来构造答案。代码// https://www.luogu.com.cn/problem/P2602
#include <cstdio>
#include <cctype>
#include <algori ······
Aug 9, 2021
Codeforces 176B Word Cut 题解
题目链接： Codeforces 176B Word Cut题目大意给两个字符串 $s$，$e$ $(\text{len} \leq 1000)$，和数字 $k$ $(k\leq 10^5)$， 定义一次操作为：从当前字符串中任取一个间隔拆开字符串并交换左右部分得到新字符串，问从 $s\to e$ 且恰好操作了 $k$ 次的不同方案数。题解我们把字符串复制一份放到后面接上，设为 $t ······
Aug 8, 2021
UVALive 7678 JiLi Number 题解
题解首先打表，发现在 $1111111110$ 之后会一直跑不出来新的数，可以猜一下之后可能没有满足条件的数，于是把这 $83$ 个数打出来，每次查表即可。代码// https://vjudge.net/problem/UVALive-7678
#include <cstdio>
#include <cctype>
#include <algorithm ······
Aug 7, 2021
计蒜客 42580 Bob's Problem 题解
题解由于题意为仅要求最终连通，故所以黑边一定可以全要，之后加从大到小加白边即可：先加白边保证连通，在此基础上如果还能加再多加一些白边也可以。代码// https://nanti.jisuanke.com/t/42580
#include <cstdio>
#include <cctype>
#include <algorithm>
#include ······
Aug 5, 2021
计蒜客 42582 Eating Plan 题解
题解我们首先进入 www.factordb.com 对这个奇怪的模数尝试进行分解，得到：$$
998857459 = 461 \times 773 \times 2803
$$由于阶乘是从 $1$ 一直乘到 $n$，所以输入的阶乘中 $\leq 2803$ 的数阶乘模 $998857459$ 后全部都是 $0$，所以剩下的不是零的位置最多 $2082$ 个，我们于是可以离散化，之后暴 ······
Aug 4, 2021
Codeforces gym 101611D. Decoding of Varints 题解
题解阅读理解题，讲的是把一个大数转换成一种类似 $2^7$ 进制的编码规则，直接看题目中给的样例可以很快理解：$$
\begin{aligned}
260 =(b_0-128)\cdot 2^0+b_1\cdot 2^1 \\
=(132-128)\cdot 2^0+2\cdot 2^1
\end{aligned}
$$即除了最高的一位 $b_i< 128$ ，其他位均为 $\ ······
Aug 4, 2021
CodeForces 670C Cinema 题解
题目链接： CodeForces 670C CinemaAuthor: 第7组 2021.4.19题目概述有$n$ 个人，各自会说一种语言，他们去看电影，每个电影$q_i$有音频语言$a_i$和字幕语言$s_i$，如果一个人能听懂，则非常开心,如果只能看懂字幕则不是非常开心但也能凑合，如果两个都不懂，他会非常愤怒。现在要找一个电影，可以让非常开心的人最多，如果有多个方案，要求不是 ······
Aug 3, 2021
计蒜客 42578 And and Pair 题解
题解定义 $\text{dp}[k][i_1][j_1]$ 表示从低位到高位（二进制下从右往左）考虑到第了 $k$ 位，且数字 $i$ 的该位为 $i_1$，数字 $j$ 的该位为 $j_1$，的方案数。转移时，由题目要求，当 $n$ 该位为 $0$ 时， $i$ 该位必须为 $0$（此举也可以保证考虑的到的 $i\leq n$），否则 $i$ 的该位放 $1,0$ 均可。由于 $i ······
Aug 3, 2021
计蒜客 42577 A Funny Bipartite Graph 题解
题解从 $1$ 开始往后搜索，每次取匹配左边的点，若当前枚举到的左边的点合法（即不与之前的已选点的出现产生冲突），则选上该点，每次选上这个点后，题目中给的与其不能共存的点都要把标记 $+1$，该直接连的点出度 $+1$ 并更新答案。在搜索中可以剪枝：若当前没有已知最优解优，则返回。代码// https://nanti.jisuanke.com/t/42577
#include < ······
Aug 2, 2021
Luogu P3387【模板】缩点
tarjan 算法讲解https://zhuanlan.zhihu.com/p/101923309tarjan 可以做什么无向图的割点和桥无向图双连通分量有向图强连通分量若从图中删除节点 $x$ 以及所有与 $x$ 关联的边之后，图将被分成两个或两个以上的不相连的子图，那么称 $x$ 为图的割点。若从图中删除边 $e$ 之后，图将分裂成两个不相连的子图，那么称 $e$ 为图的桥或割边 ······
Aug 2, 2021
Luogu P3128 USACO15DEC Max Flow P 题解
题解定义 $\text{fa}[i][j]$ 表示从 $i$ 向上 $2^j$ 位置的父亲节点是哪一个，利用这个倍增可以迅速得到 $\text{LCA}(u,v)$ ，定义 $\text{d}[i]$ 表示从根节点到当前节点路径上所有点 $+\text{d}[i]$ 这个差分标记，每次树上的连续加可以写作：$$text{d}[u]++\text{d}[v]++\text{d}[tex ······
Aug 1, 2021
Codeforces gym 101611H. Hilarious Cooking 题解
题目大意给定 $T$，询问是否存在数列 $t_i$ 满足：$|t_i - t_{i + 1}| \leq 1\,\,(i=1,\cdots n-1)$$t_i\geq 0$$\displaystyle \sum_{i=1}^{n}t_i=T$题解把问题转化为寻找可行的范围 $[L,R]$，判断是否 $T\in [L,R]$，由于题目中的限制，可以得到所有关键点之间的中间最大和最小状态 ······
Aug 1, 2021
Codeforces gym 101611A. Walk of Three Advertising Strategy 题解
题解我们可以把递推式子简化为：$$
\begin{aligned}
b_{i+1}=b_i+&\min{\{b_i,\frac{n-b_i}{2}\}+x_i}\\
&\sum_{i=1}^{n}x_i\leq k
\end{aligned}
$$我们想象这个过程，可以分为两步：先是一个类似二倍的增加，在接近 $n$ 时变为由剩余部分进行限制，每次类似把剩下的一半填满 ······
Jul 31, 2021
Codeforces gym 102860I. Walk of Three 题解
题解注意到，题目中仅需要走三步，要求是不可以走重复的路以及不可以回到 $1$，由于步数很小，我们直接计算方案数：首先我们把和 $1$ 相邻的点标记出来，之后遍历所有的点，统计其周围有多少个和 $1$ 直接相连的点，假设对 $i$ 来说是 $\text{cnt}[i]$，则后两步可以看做从某一个入边进来，之后选一个不一样的再出去，刚好为 $3$ 步：即$$
\text{cnt}[i]\ ······
Jul 30, 2021
Codeforces gym 102920E. Imprecise Computer 题解
题解我们首先来看如果 $x,x+1$ 被错误地判断为 $x>x+1$ 时会发生什么。假设是第 $1$ 次实验，此时 $r_1(x)\to r_1(x)+1, r_1(x+1)\to r_1(x+1)-1$，会产生一正一负的影响，考虑第 $2$ 次实验时同理。我们每次考虑数对 $(x,x+1)$，根据给出的 $D_i$，我们知道了当前的差分 $|r_1(x)-r_2(x)|$，根 ······
Jul 30, 2021
Codeforces gym 102823G. Greatest Common Divisor 题解
题目大意给 $n$ 个数，每次可以给所有数加 $1$ ，问最少需要多少次可以让所有数的 $\text{gcd}(a_i)>1$，若不存在则输出 $-1$.题解有关最大公约数的性质：原数组的 $\text{gcd}$ 和差分后的数组的 $\text{gcd}$ 相等，于是我们把原输入数组差分，所以每次全部加一可以转化为只在差分数组 $d[1]$ 上加，我们取 $\_g=\text ······
Jul 29, 2021
Codeforces gym 102920C. Dessert Café 题解
题目大意求一棵树上的“好点”，满足：到某个“公寓区” $A$ 的距离比其他任何点小（除了公寓和它本身）到另一个“公寓区” $B$ 的距离比刚才的那个“公寓” $A$ 到 $B$ 的距离更小题解我们假设 $P$ 是“好点”，并取出公寓点 $A$ 和 $B$，我们考虑树上该两点的连线，可以发现我们任取一个不在该路径上的点都不满足条件 1，由于条件 2 的限制，正好就是这个连线上的点满足条 ······
Jul 29, 2021
HDU 6237 A Simple Stone Game 题解
题目大意有 $n$ 堆石子，每次可以任意从其中一个移动到另一个上，算作一次操作。结束状态是对于当前所有石子堆个数，存在一个公因子 $x$ 且 $x>1$，问可能的最少步数。题解我们先去考虑一下最终状态会是什么样子，设最终每一个石子堆个数变为 $c[i]$，存在 $x>1$ 使得 $x\mid c[i]$ 对任意 $i$ 成立，我么就会有：$$
x\mid c[1]+c[2 ······
Jul 28, 2021
HDU 5963 朋友 题解
题解手画了一下样例，会发现奇数次操作则女生赢，偶数次操作则男生赢，我们考虑以 $u$ 为根节点，引出了一些连向子树的边 $s_1,\cdots, s_p$，我们从整体考虑，如果这个边是 $1$，则我们一定要在该子树里进行奇数次操作， 边为 $0$ 时同理，这样我们就可以得到总共需要的操作的奇偶性，也就是得到了答案。代码// https://acm.hdu.edu.cn/showpro ······
Jul 27, 2021
HDU 5968 异或密码 题解
题目大意给定一个序列，计算所有合法区间的异或值，每次询问给出 $x$ ，问异或值距离 $x$ 最近的连续区间长度是多少，若长度不唯一输出最长的。题解预处理出异或和，利用异或的性质可以快速得到任意区间的异或和，最后枚举得到答案。代码// https://acm.hdu.edu.cn/showproblem.php?pid=5968
#include <cstdio>
#in ······
Jul 27, 2021
HDU 5969 最大的位或 题解
题目大意给定 $l, r$ ，求所有 $l\leq a\leq b\leq r$ 的最大 $a\,|\,b$ 异或值。题解我们按二进制逐位考虑，在前缀的部分我们发现，如果上下界该位相等，则没有选择的余地（利用数位 $\text{trie}$ 树表示比较好理解，转化为一个二进制下的字典树），假设我们扫描到了第一个上下界该位不等的地方，之后一定会在字典树上取连续的一些叶子节点，由于异或只 ······
Jul 26, 2021
HDU 6231 K-th Number 题解
题目大意给定一个数组 $a$，枚举每一个子区间，写出子区间的第 $k$ 大数，放到数组 $b$ 中，求 $b$ 中的第 $m$ 大数。题解由于最终答案一定在 $a$ 里，所以我们只需要取 $a$ 中的元素判断。我们把 $a$ 中元素排序加去重，之后二分下标，每当二分到 $a[mid]$，我们就把原数组中 $\geq a[mid]$ 的置为 $1$ ，否则置为 $0$。则我们使用双指针 ······
Jul 25, 2021
HDU 5912 Fraction 题解
题目大意模拟一个连分数的计算。题解从后往前，设当前存的分数为 $\displaystyle\frac{B}{A}$，则更新后的分数为 $\displaystyle\frac{A\cdot b_i}{B+A\cdot a_i}$，一路递推即可。代码// https://vjudge.net/problem/HDU-5912
#include <cstdio>
#includ ······
Jul 25, 2021
HDU 5934 Bomb 题解
题目大意有 $n$ 个炸弹， 每个点燃需要一定代价，每个炸弹有位置和爆炸半径，每次爆炸可以把周围在爆炸半径的炸弹引爆，并以此类推。求让所有炸弹全部爆炸的最小代价。题解我们对于炸弹 $u$ 和 $v$，若 $\rho(u,v)\leq \text{radis}(u)$，则连一条有向边 $u\to v$。我们用 $\text{tarjan}$ 得出图的强连通分量，把每个强连通分量缩成一个 ······
Jul 24, 2021
HDU 5938 Four Operations 题解
题目大意给一串数，要求拆成 $5$ 个数 $a,b,c,d,e$，求可能的最大的 $\displaystyle a+b-\frac{c\times d}{e}$.题解首先打了一个暴力搜素，复杂度算了算 $\displaystyle\binom{19}{4}$ 加常数有些悬，由于计算的数非常大，还开了 __int128，结果果然 TLE。后来发现，由于拆出来的全是正数，所以 $\di ······
Jul 24, 2021
HDU 5935 Car 题解
题目大意给定位移轴上的 $n$个点，一个人从 $x=0$ 原点出发，给定的位移轴上的点到达的时间未知，但一定是整数时刻，Ruins 的速度是一个不降的实数曲线，问最短经过多少时间可以走完。题解由于时间要短，所以速度要尽可能大，我们考虑速度最快的最后，由于每两个给定位置经过的时间差最小只能是 $1$（要求在整时刻上），于是我们贪心地把最后的速度 $\displaystyle v=\fr ······
Jul 23, 2021
HDU 5933 ArcSoft's Office Rearrangement 题解
题目大意给 $n$ 个石子堆，要求可以任意把某一堆分成两半，或把两个堆合并，问最少需要多少次操作使石子堆变成每堆相等的 $k$ 堆。题解模拟，我们想象最终状态，每个石子堆都是由相邻的两边的原始石子堆拆分与合并而成，于是我们从左到右模拟这个过程即可，代码实现要注意很多细节（WA了无数次）。代码//https://acm.hdu.edu.cn/showproblem.php?pid=59 ······
Jul 22, 2021
HDU 6235 Permutation 题解
题目大意输出一个 $n$ 的排列，要求 $p_i\equiv 0\,(\text{mod } |p_i-p_{i-2}|)$，对 $i=3,4,\cdots$ 成立。题解我们发现，如果 $|p_i - p_{i-2}|$ 如果可以为 $1$，即隔一个的位置差的绝对值为 $1$，则一定满足条件。我们从 $1$ 开始依次逐个递增一个向后放，从 $n$ 开始递减向后放，就可以满足上面的要求 ······
Jul 21, 2021
Codeforces gym 102823J. Stone Game 题解
题目大意Alice 和 Bob 取石子，每一回合只能从某一堆上取一个，并且任何时候相邻两堆石子个数不能相同，不能再取得人失败。Alice 先手，问二人谁必胜？题解我们来想最终极限不能取的状态应该是什么样子的。例如有一个部分最初为 $2,3,5,7,8$，我们发现取法是把这样的上升序列取成连续序列，比如刚才的部分最终的状态一定是 $0,1,2,3,4$（从左边的小的石子堆取，取完之后 ······
Jul 21, 2021
Codeforces gym 102823H. Hamming Distance 题解
题目大意定义汉明距离为两个等长字符串间不同字符的个数和，给定两个字符串，求字典序最小的到这两个字符串汉明距离相同的字符串。题解我们设给定两个字符串为 $a$ 和 $b$ ，构造的字符串为 $c$，若在第 $i$ 位 $a,b$ 的字符相等，则 $c$ 放字符 $'a'$ 一定是最优解（考虑从前往后依次放字符）。若不相等，则当我们 ······
Jul 20, 2021
Codeforces gym 102823D. Bits Reverse 题解
题目大意给两个数，求使得两个数经过若干次操作后相等的最小次数，每次操作可以把一个数的相邻三位翻转。题解只考虑把 $x$ 变成 $y$，逐位考虑两个数的每一位，若不相等，设该位置为 $i$ ，则去依次看 $x$ 的 $i+2,i+4,\cdots$ 位，取第一个和 $y$ 相等的即为最优取法，然后逐一交换（原题目中的操作可以等价看成隔位交换）。代码// https://codeforc ······