Believe it

相信不屈不挠的努力,相信战胜死亡的年轻

运行源码

我们将运行1.13.0版本的Flink,其scala环境为2.12

Step1. 获取学习项目

1
git clone https://github.com/fightinggg/flink-src-study.git --recursive

在这个项目中,笔者把flink源码作为了一个git submodule放置于文件夹flink中,用来临时查看,当然我个人不建议看这些代码。

然后就可以直接运行了

阅读全文 »

容器与开发语言

容器

随着云计算领域的兴起,容器这个词出现了,但是什么是容器?

容器英文名Container,是基于Linux Namespace以及Cgroups技术实现的具备隔离特性的一组进程

OK,他是一组具备隔离特性的进程

虚拟机

虚拟机是使用Hypervisor技术提供的虚拟化硬件的操作系统。

OK,虚拟机是一个操作系统。

阅读全文 »

Install Kafka

step 1. launch zookeeper in background

1
2
3
4
5
docker run -d \
-p 2181:2181 \
--name zookeeper \
-m 100M --memory-swap 100M --cpus 0.1 \
zookeeper

step 2. launch kafka

1
2
3
4
5
6
7
8
9
10
docker run -it --rm \
--link zookeeper:zookeeper \
--name=kafka \
-p 9092:9092 \
-m 200M --memory-swap=1024M \
1144560553/kafka:test \
bin/kafka-server-start.sh config/server.properties \
--override zookeeper.connect=zookeeper:2181 \
--override listeners=PLAINTEXT://0.0.0.0:9092 \
--override advertised.listeners=PLAINTEXT://localhost:9092

Project In Github

https://github.com/fightinggg/kafka-docker

Project In Dockerhub

使用Github Packages Repository

这里主要介绍Github packages搭建私服,这种方案上传和下载都需要使用token

步骤1

访问地址 ,点击Generate new token 创建新的token,选择权限 write:packages

image-2021-05-22 17.39.54.125
阅读全文 »

理论篇

决策单调性

对于一类一维\(dp\),若有转移\(dp[i]=min/max(dp[j]+w(i,j)) 0<j<i\),并假定\(pri[i]\)为到\(dp[i]\)的最优转移\(j\),如果\(pri[i]\)关于\(i\)单调,那么我们称该\(dp\)具有决策单调性。

对于一类二维\(dp\),如果有转移$dp[i][j]=min/max(dp[i][k]+dp[k+1][j]+w(i,j)) i<=k<j \(并假定\)pro[i][j]\(为到\)dp[i][j]\(的最优转移\)k\(,如果\)pri[i][j]\(关于\)i\(单调,且关于\)j\(单调,那么我们称该\)dp$具有决策单调性。

四边形不等式

对于二元数论函数,\(w(i,j)\),若满足\(a\le b\le c\le d\)恒有 \(w(a,d)+w(b,c) \ge w(a,c)+w(b,d)\)则该二元函数满足四边形不等式

他的充要条件是: 若\(a\lt b\) 恒有\(w(a,b)+w(a+1,b+1) \ge w(a,b+1)+w(a+1,b)\)

可以理解为,交叉小于包含

区间包含单调性

对于二元数论函数,\(i<j\)\(w(i,j)\) 我们将参数看做区间,定义区间的包含为偏序关系, 若\(w\)的值关于该偏序关系单调,则称该函数具有区间包含单调性。

阅读全文 »

比赛链接

https://www.jisuanke.com/contest/20844

B. So Easy

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> v1;
const int bit = 30;
const int maxn = 1e5 + 5;

v1 tree[maxn], kdisSon[maxn];
int value[maxn], stk[maxn];
unsigned long long dp[maxn], ans[maxn];
int state[maxn][4];

void dfs1(int cur, int k, int dep) {
stk[dep] = cur;
if (dep - k >= 0) {
kdisSon[stk[dep - k]].push_back(cur);
}
for (int son:tree[cur]) {
dfs1(son, k, dep + 1);
}
}


void dfs2(int cur, int j, int k) {
for (int t = 0; t < 4; t++) {
state[cur][t] = 0;
}
for (int son:tree[cur]) {
dfs2(son, j, k);

for (int kson:kdisSon[son]) {
int msk1 = (value[kson] & (1 << j)) >> j;
int msk2 = (value[kson] & (1 << k)) >> k;
int t = msk1 << 1 | msk2;
state[cur][t]--;
}
for (int t = 0; t < 4; t++) {
state[cur][t] += state[son][t];
}
}
int msk1 = (value[cur] & (1 << j)) >> j;
int msk2 = (value[cur] & (1 << k)) >> k;
int t = msk1 << 1 | msk2;
state[cur][t]++;
dp[cur] = 0;
for (int t = 0; t <= 1; t++) {
ll add = 1ll * state[cur][t ^ 3] * state[cur][t];
add <<= j + k;
dp[cur] += add;
}
}

int main() {
int n, k;
scanf("%d%d", &n, &k);

for (int i = 1; i <= n; i++) {
scanf("%d", &value[i]);
}
for (int i = 2; i <= n; i++) {
int fa;
scanf("%d", &fa);
tree[fa].push_back(i);
}

dfs1(1, k, 0);
for (int i = 0; i < bit; i++) {
dfs2(1, i, i);
for (int cur = 1; cur <= n; cur++) {
ans[cur] += dp[cur];
}
for (int j = i + 1; j < bit; j++) {
dfs2(1, i, j);
for (int cur = 1; cur <= n; cur++) {
ans[cur] += dp[cur] * 2;
}
}
}
for (int i = 1; i <= n; i++) {
printf("%llu\n", ans[i]);
}
}

分块

已知某函数\(f(x)\)对于\(x\in[l,r]\),有\(f(x)\)关于\(x\)单调,且\(f(x)\)值域远小于\(x\)的定义域。

现在要你求\(\sum_{x=1}^n g(x,f(x))\)

那么我们就可以根据\(f(x)\)\(g\)进行分块,在这一块中,始终有常数\(y=f(x)\),然后对\(h(x)=g(x,y)\)统计\(x\)的前缀和。

最终我们就能很快的计算答案。

阅读全文 »

莫比乌斯反演

狄利克雷卷积

\[ \begin{aligned} f(n)\circ g(n)=\sum_{d|n} f(d)\cdot g(\frac{n}{d}) \end{aligned} \]

莫比乌斯函数

\[ f(n)= \begin{cases} 1 &n=1 \\(-1)^k &n=p_1\cdot p_2\cdot \cdot \cdot p_k \\0 &p^k|n , k>1 \end{cases} \]

反演

\(F(n)=\sum_{d|n} f(d)\)

\(f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\)

二项式反演

\[ f_n = \sum_{i=0}^n (-1)^i {n \choose i} g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^i {n \choose i} f_i \]

前言

关于生成函数有很多概念模糊的地方,比如生成函数的乘法是怎么定义的,比如乘法可以换序吗?比如为什么可以把多项式变成对数函数?为什么又可以使用泰勒展开?

前置知识

代数系统,群论

环是一个具有两个二元运算的代数系统。环\(\lt R,+,\circ\gt\)满足

  • \(\lt R,+\gt\)构成交换群, 即\(+\)满足封闭性、结合律、单位元、逆元、交换律

  • \(\lt R,\circ\gt\)构成半群, 即\(\cdot\)满足封闭性、结合律、单位元

  • \(\circ\)\(+\)有分配率,即\(a\circ(b+c)=a\circ b+a\circ c\)

阅读全文 »