'LeetCode: 172. 阶乘后的零'
原题链接(英文):https://leetcode.com/problems/factorial-trailing-zeroes/description/原题链接(中文):https://leetcode-cn.com/problems/factorial-trailing-zeroes/description/
如果将一个正整数因式分解,那么其末尾的 $0$ 必然可以分解为 $2\times 5$。也就是说,因子中每一对 $2$ 和 $5$ 就对应着末尾的一个 $0$,因为 $2$ 肯定比 $5$ 多。综上,所以我们只要统计因子中有多少个 $5$ 就是结果了。根据算术基本定理中性质(5):$n!$ 的素因子分解中的素数 $p$ 的幂为 $[\frac{n}{p}]+[\frac{n}{p^2}]+[\frac{n}{p^3}]+\cdots$我们把 $p=5$ 代入,计算出结果即为所求。
12345678910111213int trailingZeroes(int n){ int count_zeros = 0; long long p = 5; ...
'LeetCode: 98. 验证二叉搜索树'
原题链接(英文):https://leetcode.com/problems/validate-binary-search-tree/原题链接(中文):https://leetcode-cn.com/problems/validate-binary-search-tree/
这个题主要有两种解法:一、利用二叉搜索树的性质:中序遍历序列严格单调递增。二、递归法逐一判断每个结点(子树)是否满足二叉搜索树的特征。方法一:
我们只需要对此二叉树进行一次中序遍历,查看其中序遍历序列是否是严格单调递增的即可。
我们并不需要将这个树的中序遍历序列记录下来,也可能不需要遍历完整棵树。当我们遍历到某结点时,只需要比较一下看看这个结点的值是否大于上一个遍历的结点的值。因此我们只需要记录上一个遍历的结点的值 $inorder\_last\_val$,并每当遍历过一个结点后,更新该值。如果遍历到某个结点时,发现当前结点的值比 $inorder\_last\_val$ 小,说明这不是一个二叉搜索树,直接中断遍历并返回 $false$;如果遍历完整棵树都没有出现这种情况,那么这就是一个二叉搜索树,返回 $true ...
SSR 科学上网方法
1. 购买 VPSVPS 选择谁家的都可以,例如搬瓦工和 Vultr,我使用的是 Vultr 的。系统建议选择 Debian,因为本文后面要使用的脚本在 Debian 上支持一键配置谷歌 BBR 加速。本篇文章重点在于配置 SSR,就不在购买 VPS 这里多码字了。
注意,并不是所有的 IP 地址都可行的,我们在开始配置 SSR 之前,要确保我们 VPS 的 22 号端口为开放状态。如果 22 号端口是关闭的,那么我们就要摧毁并重建 VPS,直到获得一个 22 号端口为开放的 IP 地址。你可以用命令行的方式来判断某个端口是否打开,也可以使用一些网站工具来帮助你。这里分享几个可以进行端口扫描的网站:1. https://www.yougetsignal.com/tools/open-ports/2. http://coolaf.com/tool/port3. http://tool.chinaz.com/update.html
2. 下载并执行脚本2.1. 使用SSH连接VPSMacOS 使用终端,输入 ssh root@xxx.xxx.xxx.xxx,后面是你的 IP 地址,再输入 ...
HDU-3555 Bomb (数位DP)
描述传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3555
给你一个数 N,问在从 1 ~ N 的数中有多少个数包含 “49”,其中 4 和 9 必须是连续的。例如 1 ~ 500中,有 49, 149, 249, 349, 449, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499 一共 15 个数包含 “49”,所以答案是 15。
思路题目范围已经到了 long long 的边界了,暴力肯定不可行。然后这个题看起来就是数位DP的简单题 😂。只要在dfs()函数中记录下上一个数是不是 4 就可以了,然后将算好的值存在 dp 数组中,记忆化搜索,这样便可以算出有多少个数不包含 “49”,再做一下减法就是答案了。唯一要注意的也就是这个题的范围了。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <iostream>#include < ...
HDU-2089 不要62 (数位DP)
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2089
题目大意:告诉你一个范围 n ~ m,例如 200 ~ 3000, 问你在这个范围内,不包含 62 ,也不包含 4 的数有多少个。例如 1062、1620、401 等都是不满足要求的,因为存在 62 或者 4,但像 1602 是可以的,因为不存在 62(要求必须连续)。
解题思路:数位DP简单题,对于 62,我们在 dfs() 函数中用一个参数来表示前一个位是否是 6,当前一位是 6 并且当前位是 2,就跳过不要了;对于 4,因为就一个数,所以也不用去记忆化,直接遇到就跳过就行,最后统计数目。
通过代码:123456789101112131415161718192021222324252627282930313233343536373839404142#include <iostream>#include <cstdio>#include <cstring>#define MAX 10using namespace std;int a[MAX];in ...
POJ-2352 Stars (树状数组)
描述传送门:http://poj.org/problem?id=2352
在笛卡尔坐标系上,有很多的猩猩,对于某一只猩猩,它的等级等于位置在它左下方的猩猩的数目。换句话说,设一个猩猩的坐标为 $(x_0,y_0)$,那它的等级就是所有坐标为 $(x,y)$ 的猩猩的数目,其中 $x\leqslant x_0, y\leqslant y_0$ 。一共有 $N$ 只猩猩,问你从等级 $0$ 到 $N-1$,各有多少只猩猩。
思路考虑用树状数组求解,首先将坐标排序,按纵坐标从小到大,纵坐标相同时横坐标从小到大。虽然本题已经排好了,但我们仍然有必要知道为何要这样排,下面解释。
我们按照排列好的顺序依次计算,就能保证当计算到某一只猩猩的时候,满足计算它等级条件的所有猩猩都已经提前计算完了,假设这只猩猩坐标是 $(x_0,y_0)$,那它的等级就是 $Sum(x_0)$,然后再将这只猩猩也加入到树状数组当中,即 $Modify(x_0)$。我们只需要在计算等级的时候记录一下就可以了。
另外这题设置了一个小坑,我们知道树状数组和线段树这类数据结构在计算的时候,下标是必须从 1 开始的。在本题中, ...
Lost Cows(暴力/线段树)
描述传送门:POJ 2182 - Lost Cows
有一些奶牛,从 $1$ 到 $N$ 编号,现在这些奶牛站成一行,但是没有按顺序,我们只知道一个条件:对于某一只奶牛,站在它前面并且编号比它小的奶牛的数量。要求计算出每只奶牛的编号。
思路根据题意,我们考虑最后一只奶牛(设为 $N$),我们知道站在它前面的并且编号比它小的奶牛的数目(设为 $Pre[N]$ ),因为所有的其他奶牛已经都在它前面了,所以 $Pre[N]$ 也就是所有奶牛中编号比它小的数目,那么这最后一只奶牛,编号就是 $Pre[N]+1$ 。
然后从后往前推,第 $N-1$ 只奶牛,站在它前面的编号比它小的奶牛数目是 $Pre[N-1]$ ,因为我们是从后往前推的,那么站在这第 $N-1$ 只奶牛后面的,编号肯定都已经确定了,那么从编号 $1$ 开始往后查找,第 $Pre[N-1]+1$ 个没有被确定的编号,就是它的编号。以此类推,直到所有奶牛的编号都确定下来。
因为题目数据范围较小,只有 $8000$, $O(n^2)$ 的暴力算法就可以过了,但是秉着学习的态度,还是用线段树解了一发,万一遇到数据很大的类似题目呢~!
...
Apple Tree(DFS序+树状数组)
传送门: POJ 3321 - Apple Tree
题目大意:给你一棵树(不是二叉树,多少个枝干都有可能),树的形式以结点关系描述的形式给出,比如给你 $u$ 和 $v$,表示编号为 $v$ 的结点是编号为 $u$ 的结点的子结点。每个结点上有一个苹果,有两个操作 C 和 Q :操作 C :告诉你一个结点,如果这个结点当前有苹果,那就把它摘下来,如果没有,那这个结点就长出一个苹果。操作 Q :同样是告诉你一个结点,问你以这个结点为根的子树上一共有多少个苹果。
解题思路:
遇到这类有频繁的单点修改和区间查询操作的题目,一般首先想到的都是树状数组或者线段树来解,这个题目也没例外。
对于这个题,给出的是结点的关系,那么我们就可以用 DFS序 得到这个树的遍历序列,我们知道,DFS序有一个特殊的性质,就是一个结点的子树一定是在一个连续的区间内的,比如题目样例里面的数据,DFS序为 “122331”,对于以结点 1 为根的子树,每一个结点的进入与离开时间,全都在结点 1 的进入时间和离开时间之间。
我们用树状数组来维护DFS序列,对于操作 C ,我们只要把DFS序列中这个结点的进入和离开的序列 ...
想要的 GitHub ID 被注册了怎么办?
作为一名计算机专业的学生,加入 GitHub 已经有一段时间了。
我想很多人和我一样,想要某一个 id 却苦于已被注册,比如我想要的,就是我姓名的全拼 id “gukaifeng”。
因为我的全拼 id 被注册了,所以只能用其他的,但换来换去,也始终没能有一个称心的 id。
我本想去联系我的名字全拼 id 的持有人,但是到了那个主页后看到的画面是这样子的:
这直接断了我想联系这个人的念头。。。
气愤!占着 XXX ( GitHub id ) 不 XXX ( 干正事 ) !
…
后来无意间听说,GitHub 其实是有闲置 id 的处理方案的,允许用户去申请的。
惊了个呆!这简直就是为我量身定制的啊!
于是开始 Google 方案,花了 1 个小时,并没有找到什么有卵用的东西。。。
想了想,也许可以尝试下 Contact GitHub 的呀!说做就做!当然了结果是成功啦,不然也不会有这篇博客了,下面记录下过程,给有同样想法的小伙伴借鉴。
1. 要先确认下,这个方法也是有前提条件的,就是你想要的这个 id 虽被注册了,但是处于一个长期闲置的状态,就像我上面发的图的那样。如果你想要的 id ...
Trailing Zeroes (III)(算术基本定理+二分查找)
传送门:LightOJ 1138 - Trailing Zeroes (III)
题目大意:
给你一个数 $Q$,问你,阶乘结果末尾有 $Q$ 个 $0$ 的数,最小是多少。
$1\leqslant Q\leqslant 1e8$
解题思路:
我们先来考虑如何计算一个正整数的阶乘结果末尾 $0$ 的个数。
如果将一个正整数因式分解,那么其末尾的 $0$ 必然可以分解为 $2\times 5$,也就是说,因子中每一对 $2$ 和 $5$ 就对应着末尾的一个 $0$,因为 $2$ 肯定比 $5$ 多,所以我们只要统计因子中有多少个 $5$ 就是结果了。根据算术基本定理中,性质(5):$n!$ 的素因子分解中的素数 $p$ 的幂为 $[\frac{n}{p}]+[\frac{n}{p^2}]+[\frac{n}{p^3}]+\cdots$我们把 $p=5$ 代入,计算出结果即为所求。代码如下:
12345678910int trailingZeroes(int n) { int cnt = 0; long long p = 5; while (n / p) ...