Yang's Website

This is Yang’s Website.

Mining Bitcoin with pencil and paper: 0.67 hashes per day

http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html

This article introduces the process how mining works in Bitcoin, which requires miners to find a hash smaller than a specific value. The author also shows the process calculating SHA-256, one of the hash functions, using pen and paper.

ViaBTC Rises: How A mysterious Miner Could Decide Bitcoin’s Future

https://www.coindesk.com/viabtc-mystery-miner-bitcoin-scaling-future

This article introduces a bitcoin mining pool in China called ViaBTC became to support Bitcoin Unlimited instead of Bitcoin Core. There are two ways that are possible to scale the bitcoin block size: Segregated Witness and Bitcoin Unlimited. Segregated Witness is a planned technical fix that would make bitcoin’s block size about 1.8 times larger than original size, while Bitcoin Unlimited allows miners and individual node operator to choose a block size that they prefer instead of limited block size. Either side has its supporters and have continued arguing.

The Antbleed Backdoor

https://www.coindesk.com/antbleed-bitcoins-newest-new-controversy-explained

This article introduces a mining chip vulnerability, which some are calling a “backdoor”, that could potentially be used to remotely shut off bitcoin mining machines. The public fears that someone could exploit the vulnerability to switch off bitcoin mining equipment in bulk and involving mining chip manufacturer Bitmain has been controversial.

Ethereum Whitepaper

https://github.com/ethereum/wiki/wiki/%5B中文%5D-以太坊白皮书

This article first introduces the history of bitcoin and its general principle. Then it states the advantages of implementing some specific functions on ethereum beyond those on bitcoin such as script. It also enumerates other applications of ethereum in practice.

Time stamped chatlogs: Why Jihan and Jiang want to block segwit at all cost

https://medium.com/bitcoinfoundation/verified-chatlogs-why-jihan-and-jiang-want-to-block-segwit-at-all-cost-bbf068c5ce0f

This article shows chatlogs between Chinese miners and a Litecoin developer discussing activating Segwit on Litecoin. Jihan, one of the Chinese miners, supported to activate the Segwit with a hard fork, while Xinxi, a LTC developer, argued that it should be activated with soft ford instead.

题目

John 有一个计数器，记录从某次越狱开始每天距离上次奶牛越狱的天数（越狱当天为0）。当他打算统计时，计数器上某些天数被涂掉了（用 -1 表示）。给出总天数 N 和每天记录的天数，返回 N 天中奶牛越狱次数可能的最小值和最大值，若记录的天数有矛盾的地方，返回 -1

思路

根据题目，第一天的数字一定为 0。将记录计数的数组复制一份，原数组用于参考数据，并在新数组上进行更改。从后往前遍历原数组，每当发现一个不为 -1 的元素 m，在新数组中将该元素前 m 个元素更改为相应的降序数字，过程中若发现矛盾，返回 -1。遍历完成后，新数组中 0 的数量即为越狱次数的最小值，0 与 -1 的总数量为最大值

复杂度分析

由于只需要遍历一次数组，时间复杂度为 O(n)，且 N 最大为 100，不会超时

题目

有 n 头牛站在不同的位置，每头牛只能传球给离自己最近的牛（如果有多头牛距离相同传给左边的），求需要多少球能让所有奶牛都传一次球。

思路

假设让每头奶牛都传一次球，并记录每头奶牛收到球的数量；如果有奶牛收到球的数量为 0，或有两头奶牛相互传球且不会有新的球进来，则需要球的数量加一。

复杂度分析

排序数组的复杂度为n logn，过程中需要遍历两次数组，复杂度都为 O(n)，奶牛数量最大为 100，所以不会超时

题目

Famer John 和 Bessie 猜拳。在 $n$ 次猜拳中 ($1 ≤ n ≤ 100000$)，Bessie 只会变一次手势，给出 Farmer John 每次出的手势，求 Bessie 能赢的最大次数

思路

将 FJ 每次出的手势装进一个 prefix 数组中，数组的每个元素是当前 FJ 出过三个手势分别的次数。遍历装 FJ 手势的数组，计算每次 Bessie 赢的次数，并求出最大值

复杂度

创建一个 prefix 数组的复杂度为 $O(n)$，遍历数组的复杂度为 $O(n)$，利用 prefix 计算赢的次数的复杂度为 $O(1)$，总复杂度为 $O(n)$，$n$ 最大为 100000，不会超时

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

def win(a, b, i):
	global gestures, prefix

	count = 0
	count += prefix[i][a] + prefix[-1][b] - prefix[i][b]
	return count

lines = open('hps.in').read().strip().split('\n')
n = int(lines[0])
gestures = lines[1:]
prefix = []
for i in range(n):
	if i == 0:
		if gestures[i] == 'H': prefix.append((1,0,0))
		elif gestures[i] == 'P': prefix.append((0, 1, 0))
		else: prefix.append((0,0,1))
	else:
		h = prefix[i - 1][0]
		p = prefix[i - 1][1]
		s = prefix[i - 1][2]
		if gestures[i] == 'H': prefix.append((h + 1, p, s))
		elif gestures[i] == 'P': prefix.append((h, p + 1, s))
		else: prefix.append((h, p, s + 1))
# print(gestures, prefix)

max_count = 0
for i in range(n):
	count = max(win(0, 1, i), win(0, 2, i), win(1, 0, i), win(1, 2, i), win(2, 0, i), win(2, 1, i))
	max_count = max(max_count, count)
	
print(max_count)
file = open('hps.out', 'w')
file.write(str(max_count))
file.close()

题目

一个 log 由日期（第 i 天），奶牛名字和产奶量变化三部分组成。所有奶牛第 0 天的产奶量都为 7，给出 n 个 log (1 <= n <= 100)，返回这 n 个 log 中产奶量最多的奶牛一共变化的次数

思路

先将日期和对应的奶牛排序，再遍历排序后的数组，记录每次产奶量最多的奶牛，并与上次做比较，如果不一样则变化量加一

复杂度分析

排序 n 个元素的复杂度为 O(n logn)，遍历长度为 n 的数组的复杂度为 O(n)，n 最大为 100，不会超时

题目

给出 N 个草垛的坐标以及能用的奶牛数量 K，要求得出只用 K 只奶牛能炸完所有草垛的奶牛最小爆炸半径。

思路

由于爆炸半径大于等于最小爆炸半径就一定能炸完所有草垛，小于就一定炸不完，所以可以用二分查找法来找到最小半径。

复杂度分析

在 n 个元素中用二分查找法找到某个元素的复杂度为O(logn)，每次选择一个元素后检查是否合法的复杂度为 O(n)，因此整个二分法的复杂度为O(n logn)。K 的范围是 1 - 10，草垛数量的范围是1 - 50000，时间复杂度最大约为 10 log50000，因此不会超时

题目

一共有 $n$ 头奶牛，每头奶牛站在不同的位置 $(x, y)$，并拥有一个广播半径为 $p$ 的对讲机（每只奶牛的 $p$ 不一定相同）。求从某只奶牛开始能联系到最多的奶牛数是多少（单向）

思路

将奶牛坐标装进一个数组中，将每只奶牛的 $p$ 装进另一个 $index$ 都一一对应的数组。遍历装坐标的数组，利用递归计算当前奶牛能联系到的所有奶牛数，并得出最大值

复杂度分析

遍历长度为 $n$ 数组的复杂度为 $O(n)$，其中每个元素递归最坏的复杂度也为 $O(n)$，总复杂度为 $O(n^2)$。$n$ 最大为 200，不会超时

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

def distance(p1, p2):
	return ((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2) ** 0.5
	
def neighbors(pos):
	global poses, powers
	
	result = set()
	for i in range(len(poses)):
		if i == pos: continue
		if distance(poses[pos], poses[i]) <= powers[pos]: result.add(i)
	return result

def process(pos):
	global poses, visited
	
	visited.add(pos)
	neighbor_pos = neighbors(pos)
	#print(neighbor_pos)
	if len(neighbor_pos) == 0: return
	for neighbor in neighbor_pos:
		if neighbor not in visited: process(neighbor)

lines = open('moocast.in').read().strip().split('\n')
n = int(lines[0])
poses = []
powers = []

for i in range(1, n + 1):
	line = list(map(int, lines[i].split(' ')))
	pos = (line[0], line[1])
	power = line[2]
	poses.append(pos)
	powers.append(power)

max_size = 0
for i in range(len(poses)):
	visited = set()
	process(i)
	max_size = max(len(visited), max_size)

print(max_size)
file = open('moocast.out', 'w')
file.write(str(max_size))
file.close()

题目

给出 N 个城市（1 ≤ N ≤ 200000），每个城市有自己的名字和长度为两个字母的代号（可能会重复）。若两个城市是一对 special pair ，则这两个城市的名称的前两个字母都是对方的代号。找出这 N 个城市中有多少对 special pair

思路

将城市的前两个字母和代号分别装进一个长度为 2 的元组的两个房间，并将每个这样的元组装进 hashmap 中，其中每个元组作为 key，出现的次数作为 value。遍历 hashmap，将当前的元组的前后两格互换，若 hashmap 中有与新元组相同的 key，则 count 加上当前的 valve 与新 value 的积

复杂度分析

遍历 hashmap 的复杂度为 O(N)，在 hashmap 中查找 key 的复杂度为 O(1)，总复杂度为 O(N)。N 最大为 200000，不会超时

题目

给出一个长度为 N 的数列和 M 个范围（1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000），分别求出数列中有多少个数在范围内。

思路

先将数列排序，用二分法分别找出数列中对应数字的 index，再用上界的 index 减下界的 index

复杂度分析

排序的复杂度为 N logN，对 M 个范围分别用二分法的复杂度为 M logN，总复杂度最大为 10^5 log(10^5)，不会超时