🔖 算法图论二分图学习笔记

Term

点覆盖 (vertex covering)

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

边覆盖 (edge covering)

  • 边覆盖： 一个边集，满足所有顶点都是集合中至少一条边的一个端点

🔖 acmSplay解题报告专题训练

题目

hihoCoder/1329

题目链接： hihoCoder/1329 平衡树 Splay

基础题。

hihocoder-1329.cpp  | 166 lines.
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
#include <bits/stdc++.h>


typedef long long LL;


struct node {
  int key;
  int siz;
  node* lson;
  node* rson;


  int cmp(int x) {
    int cnt = lson->siz + 1;
    if (x == cnt) return -1;
    return x < cnt ? 0 : 1;
  }
  void maintain() {
    siz = lson->siz + 1 + rson->siz;
  }
};


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


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


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


inline void zag(root& o) {
  root k = o->rson;
  o->rson = k->lson;
  k->lson = o;
  o = k;
}
inline void zig(root& o) {
  root 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) {
  int d = o->cmp(k);
  if (d == 1) k -= o->lson->siz + 1;
  if (d != -1) {
    root& p = d ? o->rson : o->lson;
    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->rson = right;
  left->maintain();
  return left;
}


inline int rank(root o, int key) {
  if (o == null) return 0;
  if (key == o->key) return o->lson->siz;
  if (key < o->key) return rank(o->lson, key);
  return o->lson->siz + 1 + rank(o->rson, key);
}


inline void insert(root& o, int id) {
  int k = rank(o, id);
  root left, right;
  root middle = newnode(id);
  split(o, k, left, right);
  o = merge(merge(left, middle), right);
}


inline void remove(root& o, int id1, int id2) {
  int k1 = rank(o, id1);
  int k2 = rank(o, id2 + 1);
  if (k1 >= k2) return;


  root left, middle, right;
  split(o, k1, left, right);
  split(right, k2 - k1, middle, right);
  o = merge(left, right);
}


inline int query(root& o, int key) {
  if (o == null) return 0;
  if (key < o->key) return query(o->lson, key);
  return std::max(o->key, query(o->rson, key));
}


root rt;
void Init() {
  null = new node();
  null->key = 0;
  null->siz = 0;
  null->lson = NULL;
  null->rson = NULL;


  nodetop = nodepool;
  rt = newnode(0);
  rt->rson = newnode(1000000001);
}


int N, arg1, arg2, arg3;
char cmd[20];
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;
}


int main() {
  Init();
  N = read();
  for (int i = 1; i <= N; ++i) {
    scanf("%s", cmd);
    arg1 = std::min(std::max(read(), 1), 1000000000);
    if (cmd[0] == 'D') arg2 = std::min(std::max(read(), 1), 1000000000);


    switch (cmd[0]) {
    case 'I':
      insert(rt, arg1);
      break;
    case 'Q':
      printf("%lld\n", query(rt, arg1));
      break;
    case 'D':
      remove(rt, arg1, arg2);
      break;
    }
  }
  return 0;
}

🔖 acmAho-Corasick 自动机矩阵快速幂动态规划解题报告

问题简述

有 N 个由小写字母构成的单词。一个串的权值为这个串中每个单词出现的次数的总和（单词可部分重叠）。求一个长度为 L 串的最大权值。

数据范围：N 个单词长度总和不超过 100，1⩽L⩽1015.

样例输入：

1
2
3
4
3 15
agva
agvagva
gvagva

🔖 编译原理语法制导翻译计算机

前言

设计一个文法，匹配合法的计算式，并返回正确计算式的结果。

一些定义：

  • 语法制导定义（Syntax-directed definitions, SDD）
  • 语法制导翻译方案（Syntax-directed Translation Schema, SDT）

其它一些编译原理相关的前置知识可以参考：

🔖 编译原理语法分析计算机

FIRST

FIRST(X)

  • 如果 X 是一个终结符号，那么 FIRST(X)=X

  • 如果 X→ε 是一个产生式，那么 ε∈FIRST(X)

  • 如果 X 是一个非终结符号，且

🔖 acm递推状态压缩动态规划字典树解题报告

1002 K 个连通块

题目链接

题目简析

假入 N 个点依次为：V={A0,A1,⋯,AN−1}. 不难想到状态压缩。令 dp(k,s) 表示点集 Vs={Ai|⌊s2i⌋≡1mod2}

🔖 math数论原根

什么是原根

  • 原根的定义

    对于正整数 N，如果正整数 g 满足 gcd(g,N)=1 且 {g0,g1,⋯,gφ(N)−1} 两两模 N 不同余，则称 g 为 N 的一个原根。

    由于 gcd(A,B)=1 ⇔ gcd(AmodB,B)=1

© 2017-2025 光和尘有花满渚、有酒盈瓯