Java 中的 Protected 修饰符

概述

  • protected 方法的调用是否合法（编译是否通过），关键是要看 调用者所在的类与被调用的 protected 方法所在的类是否在相同的包下，若相同，则合法；否则，不合法。
  • 在子类内部，任何情况下都可以访问父类的 protected 方法

栗子

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
// pacakge p1;
public class Father1 {
    protected void f() {}
}

// package p1;
public class Son1 extends Father1 {}

// package p2;
public class Son2 extends Father1 {}

// package p1;
public class Test1 {
    public static void main(String[] args) {
        Son1 son1 = new Son1();
        son1.f();       // Compile OK.

        Son2 son2 = new Son2();
        son2.f();       // Compile OK.
    }
}

// package p2;
public class Test2 {
    public static void main(String[] args) {
        Son1 son1 = new Son1();
        son1.f();       // Compile Error.

        Son2 son2 = new Son2();
        son2.f();       // Compile Error.
    }
}

更有趣的栗子

### $\text{栗}_1$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
// package p1;
public class MyObject1_2 {}

// package p1;
public class Test1_2 {
    public static void main(String[] args) {
        MyObject1_2 myObject1_2 = new MyObject1_2();
        myObject12.clone();     // Compile Error.
        
        Test1_2 test1_2 = new Test1_2();
        test1_2.clone();        // Compile OK.
    }
}
这里 `myObject1_2.clone` 是继承自 `Object` 的 `protected` 方法，虽然 `Test1_2` 也是 `Object` 的子类，但是 `Test1_2` 和 `MyObject1_2` 并不存在直接的继承关系，并且由于 `Object` 和 `Test1_2` 不在同一个包中，因此编译不通过。 而由于 `Test1_2` 继承自 `Object`，因此可在 `Test1_2` 内部任意调用从 `Object` 继承来的 `protected` 方法。

more >>

概率论基础（1）

期望

  • 设离散型随机变量 $X$ 的分布律为： $\displaystyle P\lbrace X=x_k\rbrace = p_k,\hskip 1em k=1,2,\cdots$。若级数 $\displaystyle \sum_{k=1}^\infty x_kp_k$ 绝对收敛，则称级数 $\displaystyle \sum_{k=1}^\infty x_kp_k$ 为变量 $X$ 的数学期望，记为 $E(X)$，即 $\displaystyle E(X)=\sum_{k=1}^\infty x_kp_k$
  • 设连续性随机变量 $X$ 的概率密度为： $f(x)$。若积分 $\displaystyle \int_{-\infty}^{+\infty} xf(x)dx$ 绝对收敛，则称积分 $\displaystyle \int_{-\infty}^{+\infty} xf(x)dx$ 的值为随机变量 $X$ 的数学期望，记为 $E(X)$

定理

设 $Y$ 是随机变量 $X$ 的连续函数：$Y=g(X)$

  • 如果 $X$ 是离散型随机变量，它的分布律为 $P\lbrace X=x_k\rbrace = p_k,\hskip 1em k=1,2,\cdots$；若 $\displaystyle \sum_{k=1}^{\infty} g(x_k)p_k$ 绝对收敛，则有

more >>

线性代数基础之矩阵(1)

【定义1】 由 $m\times n$ 个数 $a_{ij}(i=1,2,\cdots,m;j=1,2,\cdots,n)$ 有序地排成 $m$ 行 $n$ 列的数表
\begin{align}
\left(\begin{matrix}
a_{11} & a_{12} & \cdots & a_{1n} \
a_{21} & a_{22} & \cdots & a_{2n} \
\vdots & \vdots & & \vdots \
a_{m1} & a_{m2} & \cdots & a_{mn} \
\end{matrix}\right)
\end{align} 称为一个 $m$ 行 $n$ 列的矩阵，简记为 $(a_{ij})_{m\times n}$

  • 如果两个矩阵有相同的行数和列数，则称他们是 同型的
  • 如果两个同型矩阵 $\mathbf{A}=(a_{ij}){m\times n}$、$\mathbf{B}=(b{ij}){m\times n}$ 的对应元素相同，即
    $$ a    {ij} = b_{ij}, \hskip 2em i=1,2,\cdots,m; \hskip .5em j=1,2,\cdots, n$$
    则称矩阵 $\mathbf{A}$ 和 $\mathbf{B}$ 相等，记作 $\mathbf{A}=\mathbf{B}$

more >>

线性代数基础之行列式

逆序数

【定义1】 $n$ 级排列 $i_1i_2\cdots i_n$ 的逆序数记为 $\tau(i_1i_2\cdots i_n)$。
比如，$\tau(123)=0$，而 $\tau(321)=3$，因为 32,31,21 是逆序，共 3 对。

  • 若 $\tau(i_1i_2\cdots i_n) \equiv 0\mod 2$ 则称为 偶排列；否则称为 奇排列

【定理1】 若互换排列 $i_1i_2\cdots i_n$ 中两个数 $i_x$ 和 $i_y$ 的位置（不妨假设 $x<y$），则
$$\tau(i_1i_2\cdots i_x\cdots i_y\cdots i_n) \not\equiv \tau(i_1i_2\cdots i_y\cdots i_x\cdots i_n) \mod 2 \tag{1}$$

  • 当 $y=x+1$ 时，也就是相邻两个数进行对换，由于和其它数的相对顺序没有发生改变；此时 定理1 成立
  • 当 $y=x+k$ （其中 $k>1$ 且 $k \in Z^+$）时，可以理解成：
  • $i_y$ 先和 $i_{y-1}$ 交换，随之和 $i_{y-2}$ 交换，直到和 $i_{x}$ 交换，此时 $i_y$ 一共发生了 $y-x$ 次交换，且 $i_x$ 位于交换前 $i_{x+1}$ 的位置
  • 然后 $i_x$ 和 $i_{x+1}$ 交换，直到和 $i_{y-1}$ 交换，一共交换了 $y-1-x$ 次

不难发现这样交换的结果和直接让 $i_x$ 和 $i_y$ 交换是一样的，相当于进行了 $(y-x)+(y-1-x)=2\times(y-x)-1$ 次相邻交换，而每次相邻交换 $\tau$ 的奇偶性都会发生改变（前述已经证明），故等价于 $(2\times(y-x)-1)\mod 2$ 次相邻交换
综上，即可证明 定理1

more >>

初识 Ubuntu

安装 Ubuntu 双系统

  • 在 Windows 下分出硬盘空间，我分了 60G
  • 下载 Ubuntu 镜像软件
  • 下载 ultralSO 并将下载的 Ubuntu 镜像软件制作成 U 盘启动盘
  • 安装 Ubuntu （在出现机器 logo 的时候按下 F12， 选择 USG HDD 启动）；设置分区：
    • 逻辑分区，200M，起始，Ext4 日志文件系统， /boot；（引导分区；200 M 足够）
    • 逻辑分区，4000M，起始，交换空间；（交换分区；一般不大于物理内存）
    • 逻辑分区，35000M，起始，Ext4 日志文件系统，/；（系统分区）
    • 逻辑分区，剩下的空闲空间，起始，Ext4 日志文件系统，/home；（用户分区；存放个人文档）
  • 使用 EasyBSD 创建启动系统
  • 参考链接*

more >>

前端学习之 css(1)

边框

  • border-radius
    圆角边框效果
    • 语法
      1
      2
      3
      border-radius: 5px; /* 四个角的半径均为 5px 的圆角 */
      border-radius: 5px 7px; /* 左上角和右下角半径为 5px；右上角和左下角半径为 7px*/
      border-radius: 5px 4px 3px 7px; /*依次为 左上角、右上角、右下角、左下角*/
      使用 border-radius 时，需要给边框设置宽度和高度
    • 效果
      可以使用 border-radius 画实心圆，只要满足：height=width, border-radius=$\frac{1}{2} \times $width。

more >>

组合游戏基础之 SG 函数和 SG 定理

NP 状态描述

  • 无法进行任何移动的局面为 P-position
  • 可以移动到 P-position 的局面为 N-position
  • 任意移动都到达 N-position 的局面为 P-position

Nim 游戏

Nim 游戏是组合游戏中的经典游戏，描述如下：
有 $n$ 堆石子，第 $i$ 堆有 $x_i$ 颗石子。$A$、$B$ 两人轮流取石子，每次仅能选择一堆不为空的石子进行操作：取走至少一颗石子。不能操作的人输。

关于 Nim 游戏有一个著名的结论：当且仅当 $x_1\oplus x_2\oplus\cdots\oplus x_n=0$ 时，先手获胜；否则后手胜。
证明很简单，当 $X=x_1\oplus x_2\oplus\cdots\oplus x_n\neq 0$ 时，设 $X$ 的二进制最高位为 $k$，那么一定存在一个 $x_i$ 其第 $k$ 位为 1。我们只需要从第 $i$ 堆石子中取走 $X\oplus x_i$ 个（显然，$X\oplus x_i < x_i$，所以此操作是有效的），那么新的游戏状态下：$x_1\oplus x_2\oplus\cdots(x_i\oplus X)\oplus x_n=X\oplus X=0$。
事实上，这也是构造 Nim 游戏方案的方法。

more >>

网络流专题

实现

由于网络流问题难点在于建模，实现网络流的代码几乎可以不变，为此，特将下文中将会多次使用到的代码给罗列出来。

ISAP

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
namespace ISAP {/*{{{*/
    static const int MAXN = 10000+10;
    static const int INF = 0x3f3f3f3f;

    struct edge {
        int from, to, cap, flow;
        edge(int from=0, int to=0, int cap=0, int flow=0):
            from(from), to(to), cap(cap), flow(flow) {}
    };
 
    int s, t, n;
    int cnt[MAXN];
    int cur[MAXN];
    int path[MAXN];
    int dist[MAXN];
    std:: vector<edge> edges;
    std:: vector<int> G[MAXN];
    std:: queue<int> Q;
 
    void addedge(int from, int to, int cap) {
        int siz = edges.size();
        edges.push_back(edge(from, to, cap, 0));
        edges.push_back(edge(to, from, 0, 0));
        G[from].push_back(siz);
        G[to].push_back(siz+1);
    }
    
    void BFS() {
        memset(dist, 0x3f, sizeof dist);
        Q.push(t);
        dist[t] = 0;
 
        while( !Q.empty() ) {
            int o = Q.front(); Q.pop();
            for(int i=0; i < G[o].size(); ++i) {
                edge& e = edges[G[o][i]];
                if( dist[e.to] == INF && e.cap == 0 ) {
                    dist[e.to] = dist[o] + 1;
                    Q.push(e.to);
                }
            }
        }
    }

    int augment() {
        int mif = INF; 
        for(int o=t; o != s;) {
            edge& e = edges[path[o]];
            mif = std:: min(mif, e.cap-e.flow);
            o = e.from;
        }
        for(int o=t; o != s;) {
            edges[path[o]].flow += mif;
            edges[path[o]^1].flow -= mif;
            o = edges[path[o]].from;
        }
        return mif;
    }

    int maxflow() {
        BFS();
        memset(cur, 0, sizeof cur);
        memset(cnt, 0, sizeof cnt);
        for(int i=0; i < n; ++i) 
            if( dist[i] < n ) ++cnt[dist[i]];

        int ans = 0;
        for(int o=s; dist[o] < n; ) {
            if( o == t ) ans += augment(), o = s;
            bool ok = false;
            for(int i=cur[o]; i < G[o].size(); ++i) {
                edge& e = edges[G[o][i]];
                if( e.cap > e.flow && dist[o] == dist[e.to]+1 ) {
                    ok = true;
                    cur[o] = i;
                    path[e.to] = G[o][i];
                    o = e.to;
                    break;
                }
            }
            if( !ok ) {
                int d = n-1;
                for(int i=0; i < G[o].size(); ++i) {
                    edge& e = edges[G[o][i]];
                    if( e.cap > e.flow ) d = std:: min(d, dist[e.to]);
                }
                if( --cnt[dist[o]] == 0 ) break;
                ++cnt[dist[o] = d+1];
                cur[o] = 0;
                if( o != s ) o = edges[path[o]].from;
            }
        }
        return ans;
    }

    void solve();
    void solve(int);
    void solve(int, int);
    void solve(int, int, int);
};/*}}}*/

Dinic

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
namespace Dinic {/*{{{*/
    struct edge {
        int from, to, cap, flow;
        edge(int from=0, int to=0, int cap=0, int flow=0):
            from(from), to(to), cap(cap), flow(flow) {}
    };

    int s, t;
    int cur[MAXN];
    int dist[MAXN];
    std:: queue<int> Q;
    std:: vector<edge> edges;
    std:: vector<int> G[MAXN];

    void addedge(int from, int to, int cap) {
        int siz = edges.size();
        edges.push_back(edge(from, to, cap, 0));
        edges.push_back(edge(to, from, 0, 0));
        G[from].push_back(siz);
        G[to].push_back(siz+1);
    }

    bool BFS() {
        memset(dist, -1, sizeof dist);

        Q.push(s);
        dist[s] = 0;

        while( !Q.empty() ) {
            int o = Q.front(); Q.pop();
            for(int i=0; i < G[o].size(); ++i) {
                edge& e = edges[G[o][i]];
                if( dist[e.to] != -1 || e.cap <= e.flow ) continue;
                dist[e.to] = dist[o]+1;
                Q.push(e.to);
            }
        }

        return dist[t] != -1;
    }

    int DFS(int o, int minflow) {
        if( o == t || minflow == 0 ) return minflow;
        int flow = 0;
        for(int& i=cur[o]; i < G[o].size(); ++i) {
            edge& e = edges[G[o][i]];
            if( dist[e.to] == dist[o]+1 ) {
                int f = DFS(e.to, std:: min(minflow, e.cap-e.flow));
                if( f <= 0 ) continue;
                e.flow += f;
                edges[G[o][i]^1].flow -= f;
                flow += f;
                minflow -= f;
                if( minflow == 0 ) break;
            }
        }
        return flow;
    }

    int maxflow() {
        int ans = 0;
        while( BFS() ) {
            memset(cur, 0, sizeof cur);
            ans += DFS(s, INF);
        }
        return ans;
    }

    void solve();
    void solve(int);
    void solve(int, int);
    void solve(int, int, int);
};/*}}}*/

MCMF

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
84
85
namespace MCMF {/*{{{*/
    const int MAXN = 10000+10;
    const int INF = 0x3f3f3f3f;

    struct edge {
        int from, to, cap, flow, cost;
        edge(int from=0, int to=0, int cap=0, int flow=0, int cost=0):
            from(from), to(to), cap(cap), flow(flow), cost(cost) {}
    }; 

    int s, t;
    int cost, flow;
    int path[MAXN];
    int dist[MAXN];
    std:: vector<edge> edges;
    std:: vector<int> G[MAXN];

    void init(int source=0, int converge=1, int N=MAXN) {
        s = source; 
        t = converge;
        cost = 0;
        flow = 0;
        edges.clear();
        for(int i=0; i < N; ++i) G[i].clear();
    }

    void addedge(int from, int to, int cap, int cost) {
        int siz = edges.size();
        edges.push_back(edge(from, to, cap, 0, cost));
        edges.push_back(edge(to, from, 0, 0, -cost));
        G[from].push_back(siz);
        G[to].push_back(siz+1);
    }

    bool SPFA() {
        static std:: queue<int> Q;
        static bool inq[MAXN];

        memset(dist, 0x3f, sizeof dist);
        Q.push(s);
        inq[s] = true;
        dist[s] = 0;
 
        while( !Q.empty() ) {
            int o = Q.front(); Q.pop();
            for(int i=0; i < G[o].size(); ++i) {
                edge& e = edges[G[o][i]];
                if( e.cap > e.flow && dist[e.to] > dist[o]+e.cost ) {
                    dist[e.to] = dist[o] + e.cost;
                    path[e.to] = G[o][i];
                    if( inq[e.to] ) continue;
                    inq[e.to] = true;
                    Q.push(e.to);
                }
            }
            inq[o] = false;
        }
 
        return dist[t] != INF;
    }

    std:: pair<int, int> mincostmaxflow() {
        while( SPFA() ) {
            int mif = INF;
            for(int o=t; o != s;) {
                edge& e = edges[path[o]];
                mif = std:: min(mif, e.cap-e.flow);
                o = e.from;
            }
            for(int o = t; o != s;) {
                edges[path[o]].flow += mif;
                edges[path[o]^1].flow -= mif;
                o = edges[path[o]].from;
            }
            flow += mif;
            cost += mif*dist[t];
        }
        return std:: make_pair(flow, cost);
    }

    void solve();
    void solve(int);
    void solve(int, int);
    void solve(int, int, int);
};/*}}}*/

read

1
2
3
4
5
6
7
8
9
10
inline int read() {/*{{{*/
    bool positive = true;
    char c = getchar();
    int s = 0;
    for(; c < '0' || c > '9'; c=getchar())
        if( c == '-' ) positive = false;
    for(; c >= '0' && c <= '9'; c=getchar())
        s = s*10 + c-'0';
    return positive? s: -s;
}/*}}}*/

more >>

网络流基础之最大权闭合图

概念

对于有向图 $G=(V,E)$，其中 $V$ 为 $G$ 的点集，$E$ 为 $G$ 的边集。

  • 割集: 一个 $s$–$t$ 割 $[S,T]$ 是 $V$ 的一种划分，使得 $s\in S$、$t\in T$
  • 最小割: 一个 $s$–$t$ 割的容量是 $\displaystyle c(S,T) = \sum_{(\mu,\nu) \in (S\times T)\bigcap E} c(\mu,\nu)$；容量最小的割集称为最小割
  • 简单割：若一个 $s$–$t$ 割满足割中的每条边都只与源点 $s$ 或汇点 $t$ 相连，则称该割为简单割
  • 闭合图：若点集 $V’ \in V$ 是一个闭合图，那么对于 $\forall \left< \mu, \nu\right > \in E$，若 $\mu \in V’$ 则必有 $\nu \in V’$
  • 最大权闭合图： 一个点权和最大的闭合图

more >>

2016 多校第 2 场

1004 Differencia

题目链接

题目描述

有两个序列：$\displaystyle \big\lbrace a_1, a_2, \cdots, a_n \big\rbrace$，$\displaystyle \big\lbrace b_1, b_2, \cdots, b_n \big\rbrace$
有两种操作：

  • $+lr~x$ 将所有的 $a_i(l \leqslant i\leqslant r)$ 置为 $x$
  • $?lr$ 询问 $l\leqslant i\leqslant r$ 中有多少个 $i$ 满足 $a_i \geqslant b_i$

数据范围：$1\leqslant n\leqslant 10^5$，$3\times 10^6$ 次询问，强制在线。

more >>