二分图

概念

点覆盖 (vertex covering)

  • 点覆盖： 一个点集，满足所有边都至少有一个端点在集合中
  • 极小点覆盖： 本身是一个点覆盖，但任意一个真子集都不是点覆盖
  • 最小点覆盖： 点数最少的点覆盖
  • 点覆盖数： 最小点覆盖的点数

边覆盖 (edge covering)

  • 边覆盖： 一个边集，满足所有顶点都是集合中至少一条边的一个端点
  • 极小边覆盖： 本身是一个边覆盖，但任意一个真子集都不是边覆盖
  • 最小边覆盖： 边数最少的边覆盖
  • 边覆盖数： 最小边覆盖的边数

more >>

伸展树专题

题目

UVa/11922 Permutation Transformer
基础题。

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>/*{{{*/
using namespace std;

struct node {
    int key;
    int siz;
    bool flip;
    node* lson;
    node* rson;
    node(int key=0): key(key), siz(0), flip(0), lson(NULL), rson(NULL) {}
    int cmp(int key) {
        int cnt = lson->siz + 1;
        if( key == cnt ) return -1;
        return key < cnt? 0: 1;
    }
    void pushdown() {
        if( !flip ) return;
        lson->flip ^= 1;
        rson->flip ^= 1;
        swap(lson, rson);
        flip = false;
    }
    void maintain() { siz = lson->siz + 1 + rson->siz; }
};

typedef node* root;
typedef pair<node*, node*> droot;
const int MAX_NODES = 100000+10;
node* null = new node();

node nodepool[MAX_NODES];
node* nodetop;

inline node* newnode(int key=0) {
    nodetop->key = key;
    nodetop->siz = 1;
    nodetop->flip = false;
    nodetop->lson = null;
    nodetop->rson = null;
    return nodetop++;
}

inline void zag(root& o) {
    node* k = o->rson;
    o->rson = k->lson;
    k->lson = o;
    o = k;
}
inline void zig(root& o) {
    node* k = o->lson;
    o->lson = k->rson;
    k->rson = o;
    o = k;
}
inline void rotate(root& o, int d) { 
    d? zig(o): zag(o);
    d? o->rson->maintain(): o->lson->maintain();
    o->maintain();
}

inline void splay(root& o, int k) {
    o->pushdown();
    int d = o->cmp(k);
    if( d == 1 ) k -= o->lson->siz + 1;
    if( d != -1 ) {
        root& p = d? o->rson: o->lson;
        p->pushdown();
        int d2 = p->cmp(k);
        if( d2 == 1 ) k -= p->lson->siz + 1;
        if( d2 != -1 ) {
            splay((d2? p->rson: p->lson), k);
            if( d == d2 ) rotate(o, d^1);
            else rotate(p, d);
        }
        rotate(o, d^1);
    }
}

inline void split(root o, int k, root& left, root& right) {
    splay(o, k);
    left = o;
    right = o->rson;
    o->rson = null;
    o->maintain();
}

inline root merge(root left, root right) {
    splay(left, left->siz);
    left->pushdown();
    left->rson = right;
    left->maintain();
    return left;
}

inline void build(root& o, int lft, int rht) {
    int mid = (lft+rht) >> 1;
    o = newnode(mid);
    if( lft < mid ) build(o->lson, lft, mid-1);
    if( mid < rht ) build(o->rson, mid+1, rht);
    o->maintain();
}

inline void print(root& o) {
    if( o == null ) return;
    o->pushdown();
    if( o->lson != null ) print(o->lson);
    if( o->key ) printf("%d\n", o->key);
    if( o->rson != null ) print(o->rson);
}

root rt;
inline void init(int N) {
    nodetop = nodepool;
    build(rt, 0, N);
}

int main()
{
    int N, Q;
    while( scanf("%d%d", &N, &Q) == 2 ) {
        init(N);
        while( Q-- ) {
            int lft, rht;
            root o, left, middle, right;
            scanf("%d%d", &lft, &rht);
            split(rt, lft, left, o);
            split(o, rht-lft+1, middle, right);
            middle->flip ^= 1;
            rt=merge(merge(left, right), middle);
        }
        print(rt);
    }
    return 0;
}/*}}}*/

UVa/11996 Jewel Magic
用 hash 求 LCP，仅需用 splay 维护 hash 值即可。考虑到用反转操作，每个节点需要维护正反两个 hash 值。

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <bits/stdc++.h>/*{{{*/
using namespace std;

typedef unsigned long long ULL;
const int MAXN = 400000+10;
const int hashkey = 137;

ULL xp[MAXN];

struct node {
    int key;
    int siz;
    ULL val;
    ULL reval;
    bool flip;
    node* lson;
    node* rson;
    
    int cmp(int x) {
        int cnt = lson->siz + 1;
        if( x == cnt ) return -1;
        return x < cnt? 0: 1;
    }
    void reverse() {
        flip ^= 1;
        swap(lson, rson);
        swap(val, reval);
    }
    void pushdown() {
        if( !flip ) return;
        lson->reverse();
        rson->reverse();
        flip = false;
    }
    void maintain() {
        siz = lson->siz + 1 + rson->siz;
        val = lson->val + key*xp[lson->siz] + rson->val*xp[lson->siz+1];
        reval = rson->reval + key*xp[rson->siz] + lson->reval*xp[rson->siz+1];
    }
};

typedef node* root;
typedef pair<node*, node*> droot;
const int MAX_NODES = 400000+10;

node* null;
node* nodetop;
node nodepool[MAX_NODES];

inline root newnode(int key=0) {
    nodetop->key = key;
    nodetop->siz = 1;
    nodetop->val = 0;
    nodetop->reval = 0;
    nodetop->flip = false;
    nodetop->lson = null;
    nodetop->rson = null;
    return nodetop++;
}

inline void zag(root& rt) {
    root k = rt->rson;
    rt->rson = k->lson;
    k->lson = rt;
    rt = k;
}
inline void zig(root& rt) {
    root k = rt->lson;
    rt->lson = k->rson;
    k->rson = rt;
    rt = k;
}
inline void rotate(root& rt, int d) {
    d? zig(rt): zag(rt);
    d? rt->rson->maintain(): rt->lson->maintain();
    rt->maintain();
}

inline void splay(root& rt, int k) {
    rt->pushdown();
    int d = rt->cmp(k);
    if( d == 1 ) k -= rt->lson->siz+1;
    if( d != -1 ) {
        root& pt = d? rt->rson: rt->lson;
        pt->pushdown();
        int d2 = pt->cmp(k);
        if( d2 == 1 ) k -= pt->lson->siz+1;
        if( d2 != -1 ) {
            splay((d2? pt->rson: pt->lson), k);
            if( d == d2 ) rotate(rt, d^1);
            else rotate(pt, d);
        }
        rotate(rt, d^1);
    }
}

inline void split(root rt, int k, root& left, root& right) {
    splay(rt, k);
    left = rt;
    right = rt->rson;
    rt->rson = null;
    rt->maintain();
}

inline root merge(root left, root right) {
    splay(left, left->siz);
    left->rson = right;
    left->maintain();
    return left;
}

/* insert at (k+1)th position. */
inline void insert(root& rt, int k, int key) {
    root left, right;
    root middle = newnode(key);
    split(rt, k, left, right);
    rt = merge(merge(left, middle), right);
}

/* remove at (k+1)th position. */
inline void remove(root& rt, int k) {
    root left, middle, right;
    split(rt, k, left, right);
    split(right, 1, middle, right);
    rt = merge(left, right);
}

/* modify [lft+1, rht+1]. */
inline void update(root& rt, int lft, int rht) {
    splay(rt, lft);
    splay(rt->rson, rht-lft+2);
    rt->rson->lson->reverse(); /* update rt->rson->lson, rt->rson, rt */
    rt->rson->maintain();
    rt->maintain();
}

inline int query(root& rt, int p1, int p2) {
    int lft = 0, rht = rt->siz - p2;
    while( lft < rht ) {
        int mid = (lft+rht) >> 1;
        splay(rt, p1);
        splay(rt->rson, mid+1);
        ULL val1 = rt->rson->lson->val;
        splay(rt, p2);
        splay(rt->rson, mid+1);
        ULL val2 = rt->rson->lson->val;
        if( val1 == val2 ) lft = mid+1;
        else rht = mid;
    }
    return lft-1;
}

root rt;
char s[MAXN];
int N, Q, op, arg1, arg2;

inline void build(root& rt, int lft, int rht) {
    int mid = (lft+rht) >> 1;
    rt = newnode(s[mid]-'0');
    if( lft < mid ) build(rt->lson, lft, mid-1);
    if( mid < rht ) build(rt->rson, mid+1, rht);
    rt->maintain();
}

inline void Init() {
    nodetop = nodepool;
    scanf("%s", s+1);
    s[0] = s[N+1] = '0';
    build(rt, 0, N+1);
}

inline int read() {
    char c = getchar();
    int s = 0;
    for(; c < '0' || c > '9'; c=getchar());
    for(; c >= '0' && c <= '9'; c=getchar())
        s = s*10 + c-'0';
    return s;
}

int main()
{ 
    null = new node();
    memset(null, 0, sizeof(node));
    xp[0] = 1;
    for(int i=1; i < MAXN; ++i)
        xp[i] = xp[i-1] * hashkey;

    while( scanf("%d%d", &N, &Q) == 2 ) {
        Init();
        while( Q-- ) {
            op = read();
            arg1 = read();
            if( op != 2 ) arg2 = read();
            switch( op ) {
                case 1: insert(rt, arg1+1, arg2); break;
                case 2: remove(rt, arg1); break;
                case 3: update(rt, arg1, arg2); break;
                case 4: printf("%d\n", query(rt, arg1, arg2)); break;
            }
        }
    } 
    return 0;
}/*}}}*/

more >>

语法分析

FIRST

计算方法

$FIRST(X)$

  • 如果 $X$ 是一个终结符号，那么 $FIRST(X) = X$
  • 如果 $X \rightarrow \varepsilon$ 是一个产生式，那么 $\varepsilon \in FIRST(X)$
  • 如果 $X$ 是一个非终结符号，且 $X \rightarrow Y_1Y_2\cdots Y_k$ 是一个产生式：
    • $FIRST(Y_1) \in FIRST(X)$
    • 对于 $1 \leqslant t \leqslant k$，如果 $\varepsilon \in FIRST(Y_s)$, $1\leqslant s < t$ 成立，则 $FIRST(Y_t) \in FRIST(X)$。

more >>

百度之星 2016 解题报告

1002 K 个连通块

题目链接

题目简析

假入 $N$ 个点依次为：$\displaystyle V=\left\lbrace A_0,A_1,\cdots,A_{N-1} \right\rbrace$。
不难想到状态压缩。
令 $dp[k][s]$ 表示点集 $\displaystyle V_s=\big\lbrace A_i ~~ \big| ~~\left\lfloor \frac{s}{2^i} \right\rfloor \equiv 1\hskip -1em\mod 2 \text{（即 $s&2^i=1$）} \big\rbrace$ 恰好构成 $k$ 个连通块的方案数。
要注意的是，点对 $\displaystyle \big\lbrace (u,v) ~~ \big| ~~ u \in V, v\in V_s \big\rbrace$ 之间的连边都要抹去，因为 $V_s$ 中的点首先要和不在 $V_s$ 中的断开“联系”，才能得到独立的 $k$ 连通块，这样才能正确递推。

more >>

python 字符串操作

python 字符串可由 单引号' 或 双引号" 括起来，二者无区别；引号可用 反斜杠\ 转义
在引号前加一个 r 可以使得引号中的字符保留原义

1
2
3
4
5
>>> print('\some\name')
\some
ame
>>> print(r'\some\name')
\some\name

字符串运算符

more >>

数论基础之原根

什么是原根

对于正整数 $N$，如果正整数 $g$ 满足 $\gcd(g,N)=1$ 且 $\big\lbrace g^0,g^1,\cdots,g^{\varphi(N)-1}\big\rbrace$ 两两模 $N$ 不同余，则称 $g$ 为 $N$ 的一个原根。

由于：$\displaystyle \gcd(A,B)=1 \Leftrightarrow \gcd(A\hskip -1em\mod B,B)=1$。
所以，$\big\lbrace g^0,g^1,\cdots,g^{\varphi(N)-1}\big\rbrace$ 构成 $N$ 的一个既约剩余系。

阶

如果正整数 $X$ 和 $N$ 互质，且 $r$ 为使得 $\displaystyle X^r\equiv 1\hskip -1em\mod N$ 的最小正整数，
则称 $r$ 为 $X$ 模 $N$ 的阶，记做 $\displaystyle \delta_N(X)=r$。

所以，原根的定义也可以描述为：$X$ 是模 $N$ 的一个原根的充要条件为 $\varphi(N)=\delta_N(X)$。

more >>

数论基础之欧拉函数

今天学习一些欧拉函数的性质，以及重要的数论欧拉定理，当 $a$ 和 $N$ 互质时，有：
$$ a^{\phi(N)} \equiv 1\hskip -.6em \mod N$$
以及今天主要讨论的广义欧拉定理，当 $a$ 和 $N$ 不互质时，有：
$$
a^b \equiv
\left\lbrace\begin{aligned}
&a^b \hskip -.6em\mod N, & 0\leqslant b < \varphi(N) \
&a^{\big(b\hskip -.6em\mod \varphi(N)\big) + \varphi(N)} \hskip -.6em \mod N, &b \geqslant \varphi(N)
\end{aligned}\right.
$$

more >>