队列►Kafka

Kafka-Docker

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

ACM►学习笔记►DP

凸四边形不等式优化dp

理论篇

决策单调性

对于一类一维$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$的值关于该偏序关系单调，则称该函数具有区间包含单调性。

Read More

ACM►刷题实战►比赛

第44届ICPC亚洲赛区银川站

比赛链接

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]);
    }
}
ACM►学习笔记►数学

数论分块

分块

已知某函数$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$的前缀和。

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

Read More

ACM►学习笔记►数学

反演

莫比乌斯反演

狄利克雷卷积

$$
\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
$$

ACM►学习笔记►数学

生成函数与形式幂级数

前言

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

前置知识

代数系统，群论

环

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

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

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

  • $\circ$对$+$有分配率，即$a\circ(b+c)=a\circ b+a\circ c$

Read More

ACM►刷题实战►比赛

2020牛客暑期多校训练营第七场

比赛链接

https://ac.nowcoder.com/acm/contest/16151?&headNav=www

D. Fake News

题意

输入一个数$n$，问你$\begin{aligned}\sum_{i=1}^n i^2\end{aligned}$ 是不是一个完全平方数。

数据范围

$10^6$组输入

$n\lt 10^{15}$

题解

前缀和为$\frac{n\cdot(n+1)\cdot(2n+1)}{6}$, 由于$n$，$n+1$，$2n+1$两两互质，所以他们排除掉$2$和$3$这两个因子以后是完全平方数。直接验证这个就可以了。

H. Dividing

题意

  • (1,k)合法
  • 如果(n,k)合法，则(n+k,k)合法
  • 如果(n,k)合法，则(nk,k)合法

输入$N$,$K$, 问你有多少组$1\le n\le N,1\le k\le K$合法。

题解

显然每个$k$都是独立的。

考虑n的k进制，很容易发现第一句话说的是$1$合法，第二句话说的是合法的数加上$10$合法，第三句话说的是合法的数左移一位合法。

所以很容易发现，只要最低位为0或者1，就是合法的。

然后就是一个分块的模版题了。计算$\begin{aligned}\sum_{i=1}^K \sum_{j=1}^N [j\mod i\le 1]\end{aligned}$

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
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int mod = 1e9 + 7;

// [0,n] sum n/i
ll cal(ll k, ll n) {
    ll ans = 0, pos;
    // i=1, min(n,k)
    for (ll i = 1; i <= min(n, k); i = pos + 1) {
        pos = n / (n / i);
        pos = min(pos, min(n , k));
        //doing something
        ans += (pos - (i - 1)) * (n / i);
        ans %= mod;
    }
    // i=min(n,k)+1 , k
    return ans;
}

ll cal2(ll k, ll n) {
    if(k == 1) {
        return 0;
    }
    ll ans = 0, pos;

    for (ll i = 2; i <= min(n - 1, k); i = pos + 1) {
        pos = (n - 1) / ((n - 1) / i);
        pos = min(pos, min(n - 1, k));
        //doing something
        ans += (pos - (i - 1)) * ((n - 1) / i);
        ans %= mod;
    }
    ans += k-1;
    return ans % mod;
}

int main() {
    ll n, k;
    scanf("%lld %lld", &n, &k);
   // cout << cal(k, n) << " " << cal2(k, n) << endl;
    ll ans = (cal(k, n) + cal2(k, n));
    printf("%lld", ans % mod);
}


B. Mask Allocation

题意

给你$n\times m$个口罩，你可以对口罩进行分组，要求分组后可以在不拆开组的情况下，分配给n个医院。每个医院m个口罩，也可以分配给m个医院，每个医院n个口罩。

数据范围

$100$组输入

$1\le n,m \le 10^4$

题解

不妨考虑$n<m$, 那么我们直接分出n个n，那么后面剩余$n\times m-n\times n$个口罩，要求可以分成$m-n$个n，以及n个$m-n$，注意到出现了子问题。所以递归解决。

ACM►学习笔记►数学

杜教筛

公式

$$
g(1)\sum_{i=1}^nf(i)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)
$$

使用

很多时候我们会碰到求积性函数前缀和的情况，由于积性函数的前缀和不一定依然是积性函数，所以我们需要使用一些技巧。

比如给你一个积性函数$f(x)$, 现在要求你计算$\begin{aligned}\sum_{i=1}^n f(x)\end{aligned}$。

Read More