fa_555's Blog文章归档标签分类关于友链
2020 Jan Records
|动态
字数总计: 3.7k|阅读时长: 17 分钟

菜鸡 fa_555 会把一些动态简要地记在这里。主要还是留给自己以后看的。

所有代码不保证包括无关紧要的部分

非 OI

一月的前半段一直在准备期末考试。期末考得很烂。

15 号来了 qbxt。

CF325D Reclamation

problem

给定一个 $N \times M$ 的环形网格图（圆柱的侧面）。

按顺序给出 $K$ 次操作，第 $i$ 次操作会选中一个格子 $(x_i, y_i)$。如果把这个格子变成障碍后，圆柱的顶面和底面依然相连通，那么把这个格变成障碍。

solution

考虑环形，把网格横向复制。用并查集维护。如果两部分中对应的点在同一个集合中，则操作不能执行。

由于 DSU 需要支持撤销，路径压缩失去了正确性。为了保证复杂度正确，按秩合并是必须的。

code

由于太长时间没写代码，sb fa_555 这题写挂了好多地方。

  • 按秩合并，集合大小要初始化！

  • std::bitset 的两维不要开反！

这份代码也是抄的 cf 上外国友人的

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
/* struct IO { ... } cin, cout; */

constexpr int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

std::bitset<6003> vis[3003];
// bitset 两维大小开反真是草了（
int N, M, K, ans, top, U[19], V[19];

namespace DSU {
// 这个 DSU 需要支持撤销，不能路径压缩！
// 为了复杂度正确，需要按秩合并
int fa[18000003], siz[18000003];

int find(int u); // 无路径压缩

void merge(int u, int v) {
  u = find(u), v = find(v);
  if (u == v) return;
  if (siz[u] > siz[v]) std::swap(u, v);
  fa[u] = v, siz[v] += siz[u];
  U[++top] = u, V[top] = v;
}
} // DSU
using namespace DSU;

int pos(int x, int y) {
  return (M * (x - 1) << 1) + y;
}

void mark(int x, int y) {
  vis[x].set(y);
  for (int k = 0, p = pos(x, y), nx, ny; k < 8; ++k) {
    nx = x + dx[k], ny = y + dy[k];
    if (nx < 1 || nx > N) continue;
    if (ny < 1) ny = M << 1;
    if (ny > M << 1) ny = 1;
    if (vis[nx][ny]) merge(p, pos(nx, ny));
  }
}

int main() {
  cin >> N >> M >> K;
  for (int i = 1; i <= N * M << 1; ++i)
    fa[i] = i, siz[i] = 1; // 初始化！
  for (int x, y; K; --K) {
    top = 0;
    cin >> x >> y;
    mark(x, y), mark(x, y + M);
    if (find(pos(x, y)) == find(pos(x, y + M))) {
      vis[x].reset(y), vis[x].reset(y + M);
      do {
        siz[V[top]] -= siz[U[top]];
        fa[U[top]] = U[top];
      } while (--top);
    } else ++ans;
  }
  printf("%d", ans);
  return 0;
}

P1456 Monkey King

用来唤醒记忆的左偏树例题。

problem

有 $N$ 只猴子，初始时他们两两不认识，且第 $i$ 只猴子有 $a_i$ 的战斗力。有 $M$ 个事件会发生，在第 $i$ 个事件中，$x_i, y_i$ 两只猴子会各自叫上他们认识的猴子里战斗力最高的打一架。一架之后，两只战斗里最高的猴子的战斗力会各减小一半（向下取整）并互相认识 不打不相识嘛。认识关系具有传递性。

solution

支持找爹、查询最大值、修改和合并，一看就是左偏树！

code

直接看代码吧。好好看看板子和修改的操作。

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
/* struct IO { ... } cin, cout; */

using iarrN = int[100003];

int N, M;

namespace DSU {
iarrN fa;

int find(int u); // 有路径压缩
} // DSU
using namespace DSU;

namespace LTT {
iarrN ls, rs, dis, s;

int merge(int p, int q) {
  if (!p || !q) return p + q;
  if (s[p] < s[q])
    std::swap(p, q);
  rs[p] = merge(rs[p], q);
  fa[rs[p]] = p;
  if (dis[ls[p]] < dis[rs[p]])
    std::swap(ls[p], rs[p]);
  dis[p] = dis[rs[p]] + 1;
  return p;
}

void reduce(int p) {
  // reduce the value of $p by half
  s[p] >>= 1;
  int t = merge(ls[p], rs[p]);
  ls[p] = rs[p] = dis[p] = 0;
  fa[t] = fa[p] = merge(t, p);
}
} // LTT
using namespace LTT;

int main() {
  while (scanf("%d", &N) != EOF) {
    for (int i = 1; i <= N; ++i) {
      ls[i] = rs[i] = dis[i] = 0;
      fa[i] = i;
      cin >> s[i];
    }
    cin >> M;
    for (int u, v; M; --M) {
      cin >> u >> v;
      u = find(u), v = find(v);
      if (u == v) {
        cout << '-' << '1' << '\n';
        continue;
      }
      reduce(u), reduce(v);
      fa[fa[u]] = fa[fa[v]] = merge(fa[u], fa[v]);
      cout << s[find(u)] << '\n';
    }
  }
  cout.flush();
  return 0;
}

UVA11419 SAM I AM

由于 UVa 在国内网络环境速度过于难受，链接用了谷

problem

$N \times M$ 的网格图，$K$ 个点 $(x_i, y_i)$ 中有障碍。一颗炮弹可以摧毁一整行/一整列的障碍。求至少几颗炮弹可以摧毁所有的障碍。

solution

二分图裸题，不过我只想写网络流。对于点 $(x, y)$，连边 $(S, x_L, 1), (x_L, y_R, \mathrm{inf}), (y_R, T, 1)$，答案即为最小点覆盖（最大流）。

难的是输出方案。我们发现，对于 左侧所有入边满流的点 与 与左侧不满流的点相连的右侧的点 需要计入答案。

code

用了题解的一个小 trick：只建需要的边。此外，memset 和 memcpy 直接算了内存大小，不建议像我一样 << 2，至少也要 * sizeof(int)。

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
/* struct IO { ... } cin; */

using iarrN = int[2013];

constexpr int inf = 0x3f3f3f3f;

std::bitset<2013> ex, vis;
int N, M, K, S, T, tot;
iarrN cur, dep, head;

struct Edge {
  int nxt, to, w;
} e[6000003];

void _aE(int u, int v, int w);
void addEdge(int u, int v, int w);

void init() {
  tot = 1, S = 0, T = N + M + 1;
  ex.reset(), vis.reset();
  memset(head, 0, (N + M + 2) << 2);

  for (int i = 1, x, y; i <= K; ++i) {
    cin >> x >> y;
    addEdge(x, y + N, inf);
    if (!ex[x]) addEdge(S, x, 1), ex.set(x);
    if (!ex[y + N]) addEdge(y + N, T, 1), ex.set(y + N);
  }
}

/* dinic: returns maxflow */

void mark(int u) { // dfs
  vis.set(u);
  for (int i = head[u]; i; i = e[i].nxt)
    if (e[i].w && !vis[e[i].to])
      mark(e[i].to);
}

int main() {
  while (cin >> N >> M >> K, N) {
    init();
    std::cout << dinic(S, T);
    mark(S);

    for (int i = 1; i <= N; ++i)
      if (ex[i] && !vis[i])
        std::cout << " r" << i;
    for (int i = N + 1; i <= N + M; ++i)
      if (ex[i] && vis[i])
        std::cout << " c" << i - N;
    std::cout << '\n';
  }
  return 0;
}

[FJOI2007]轮状病毒

做道应景的题

solution (Luogu @WJiannan)

抄了题解还没看懂/kk，复读一遍吧。

考虑把先不管中心点，然后把外围的 $n$ 个点拆环成链，暂时强制第一个点不能和最后一个点连边。

于是方案数就类似一个整数拆分，将外围的点分成若干个联通块，

即设 $f_i$ 为当前已经分配了前 $i$ 个点的方案数，$f_i = \sum_{j=1}^{i} f_{i-j} \times j$（因为每加入一个联通块，中心点都可以向其中的任意一个点连边）。

但是我们还需要考虑上第一个点与最后一个点连边的情况，发现，如果分配第一个联通块大小为 $x$，那么我们可以把这张图逆时针旋转，则总共有 $x$ 种不同的方案。

于是答案的计算方式就等于

高精度视为 $O(1)$，总复杂度 $O(n^2)$。

code

高精度写得奇丑无比，不放了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* struct BigInteger { ... } f[103]; */

int N;

int main() {
  std::cin >> N;
  f[0] = 1;
  for (int j = 1; j <= N; ++j)
    f[j] = f[j] + f[0] * (j * j);
  for (int i = 1; i < N; ++i)
    for (int j = 1; i + j <= N; ++j)
      f[i + j] = f[i + j] + f[i] * j;
  std::cout << f[N];
  return 0;
}

[APIO2012]派遣

solution (Luogu @amazingOZR)

自己没想出来。贴一下抄的题解，顺便修一下格式。

明显领导关系形成一棵树，则答案为 $ans = max \{L_u \times k \}$，其中 $k$ 代表以 $u$ 为根的子树中选出的节点数个数（设这些节点为 $v_1, v_2, \cdots, v_k$）且有 $\sum_{i = 1}^{k} C_{v_i} \leq M$。

所以以每个节点建一个大根堆，维护薪水值。初始时若自己满足条件就选自己，否则不选。从叶子节点往上推，对于每个节点，将它与它的儿子节点合并。如果当前的选择费用超出了 $M$，就弹出堆里最大的，一直到不超过 $M$ 为止。动态维护当前选择的节点数 num 和选择费用 sum 即可。

总复杂度 $O(n \log n)$（不大会证 /wq）。

code

学会做法，代码倒是挺简单，也是抄的题解。不过自己去了去糟粕。

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
/* struct IO { ... } cin; */

using iarrN = int[100003];

int N, M, tot;
iarrN head, L;
long long ans;

struct Edge {
  int nxt, to;
} e[100003];

void addEdge(int u, int v);

namespace LTT {
iarrN rt, ls, rs, dis, s, cnt, sum;

int merge(int p, int q) {
  if (!p || !q) return p + q;
  if (s[p] < s[q]) std::swap(p, q);
  rs[p] = merge(rs[p], q);
  if (dis[ls[p]] < dis[rs[p]])
    std::swap(ls[p], rs[p]);
  dis[p] = dis[rs[p]] + 1;
  return p;
}
} // LTT
using namespace LTT;

int main() {
  cin >> N >> M;
  for (int i = 1, u; i <= N; ++i) {
    cin >> u >> s[i] >> L[i];
    addEdge(u, i);
  }
  for (int i, u = N, v; u; --u) {
    rt[u] = u, cnt[u] = 1;
    sum[u] = s[u];
    for (i = head[u]; i; i = e[i].nxt) {
      rt[u] = merge(rt[u], rt[v = e[i].to]);
      sum[u] += sum[v], cnt[u] += cnt[v];
      while (sum[u] > M) {
        sum[u] -= s[rt[u]], --cnt[u];
        rt[u] = merge(ls[rt[u]], rs[rt[u]]);
      }
    }
    ans = std::max(ans, 1ll * L[u] * cnt[u]);
  }
  printf("%lld", ans);
  return 0;
}

[JSOI2010]满汉全席

2-SAT 模板题。

solution

把每种材料拆成两个点。

每组的两个限制都是或的形式：如果不满足其中一个限制，则必须满足另外一个限制。

最后检验一下每种材料的两个点是否不在同一个 SCC 内（合法）。

总复杂度 $O(Tn)$，$T$ 为数据组数。

code

主要看看 tarjan。

把每种材料 i 拆成两个点：i << 1 代表 i 的满式做法，i << 1 | 1 代表 i 的汉式做法，最终结点的值域为 [2, N << 1 | 1]。

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
/* struct IO { ... } cin; */

void dmin(int &m, int n) {
  if (n < m) m = n;
}

using iarr2N = int[203];

std::bitset<203> vis;
int T, N, M, tot, top, dft, cntSCC;
iarr2N head, s, dfn, low, bel;

struct Edge {
  int nxt, to;
} e[2003];

void addEdge(int u, int v);

void init() {
  cntSCC = tot = dft = 0;
  memset(dfn, 0, sizeof dfn);
  memset(head, 0, sizeof head);

  cin >> N >> M;
  char u_, v_;
  for (int u, v; M; --M) {
    // 这个建图可以看一下嗷
    cin >> u_ >> u >> v_ >> v;
    u <<= 1, v <<= 1;
    addEdge(u | (u_ == 'm'), v | (v_ == 'h'));
    addEdge(v | (v_ == 'm'), u | (u_ == 'h'));
  }
}

void tarjan(int u);

int main() {
  for (cin >> T; T; --T) {
    bool f = 0;
    init();
    for (int i = 2; i <= (N << 1 | 1); ++i)
      if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= N; ++i)
      if (bel[i << 1] == bel[i << 1 | 1]) {
        f = 1;
        break;
      }
    std::cout << (f ? "BAD" : "GOOD") << '\n';
  }
  return 0;
}

POJ2976 Dropping tests

01 分数规划模板题。

没届到这个算法跟名字有什么关系，甚至也没届到这是个什么算法（

problem

给出 $n$ 组 $a, b$，选出其中 $n - k$ 组，使得 $\frac{\sum a}{\sum b}$ 最大。

solution

题目要求 $\frac{\sum a}{\sum b} \ge x$，即 $\sum (a - x b) \ge 0$ 中 $x$ 的最大值。

二分 $x$，把 $a_i - x b_i$ 排序，判断最大的 $n - k$ 的和是否大于等于 0 即可。

总复杂度 $O(n \log r)$，$r$ 为答案值域大小。

代码过丑，不放了。

P1642 规划

01 分数规划模板题。

problem

$N$ 个结点的树，每个结点 $i$ 有两个值 $a_i, b_i$，删去其中 $K$ 个结点，使得剩余结点的 $\frac{\sum a_i}{\sum b_i}$ 最大。

solution

首先把删除 $K$ 个点转化为留下 $N - K$ 个点，那它长得就跟个 01 分数规划似的。考虑二分这个最大值，可以通过一次树形 dp check。

设 f[u][i] 为以 u 为根的子树中有一个包含 u 且 siz = i 的连通块时的最大值。那么转移方程为

实现起来有些细节要注意。

code

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
/* struct IO { ... } cin; */

using iarrN = int[103];

constexpr double eps = 1e-4, inf = 1e9;

int N, K, tot;
iarrN head, siz, a, b;
double t[103], f[103][103];

struct Edge {
  int nxt, to;
} e[203];

void addEdge(int u, int v);

void dfs(int u, int fa) {
  f[u][0] = 0, siz[u] = 1;
  for (int i = head[u], v; i; i = e[i].nxt) {
    if ((v = e[i].to) == fa) continue;
    dfs(v, u);
    siz[u] += siz[v];
    for (int j = std::min(siz[u], K); j; --j)
      for (int k = 0; k <= std::min(siz[v], j); ++k)
        f[u][j] = std::max(f[u][j], f[u][j - k] + f[v][k]);
  }
  for (int i = std::min(siz[u], K); i; --i)
    f[u][i] = f[u][i - 1] + t[u];
}

bool check(double mid) {
  for (int i = 1; i <= N; ++i) {
    t[i] = a[i] - mid * b[i];
    for (int j = 1; j <= K; ++j)
      f[i][j] = -inf;
  }
  dfs(1, 0);
  for (int i = 1; i <= N; ++i)
    if (f[i][K] > -eps) return 1;
  return 0;
}

int main() {
  cin >> N >> K;
  K = N - K;
  for (int i = 1; i <= N; ++i)
    cin >> a[i];
  for (int i = 1; i <= N; ++i)
    cin >> b[i];
  for (int i = 1, u, v; i < N; ++i) {
    cin >> u >> v;
    addEdge(u, v), addEdge(v, u);
  }

  double l = 0, r = 10000;
  for (double mid; r - l > eps; ) {
    mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
  }
  
  printf("%.1lf", r);
  return 0;
}

P3709 大爷的字符串题

这个题充分考察了大家的语文水平

可以发现这个乱七八糟的题面，本质是每次从区间中取出一个严格上升的序列，然后问最少取几次

由于是严格上升，所以只和相同的数个数有关，即要用区间出现次数最大的那个数出现次数那么多次

从上句话可以看出这出题人语文没救

即要求区间众数

我觉得也就 lxl 这样的人才能写出这么难读的题面和题解，所以我不在这放题面了，你复习的时候自己读去。

solution

题面翻译成人话：给出一个序列，选定若干个区间，每次从中取出一个单调增序列，求最少几次取完。

加粗部分可以转化为：求该区间的众数的出现次数，即区间内所有数出现次数的最大值。

这样这个题就没啥难度了。

code

放一放 add 和 del 函数的部分。可读性很低。

1
2
3
4
5
6
7
8
9
10
11
void add(int p) {
  --t[cnt[z[p]]];
  if (cnt[z[p]] == now) ++now;
  ++t[++cnt[z[p]]];
}

void del(int p) {
  if (!--t[cnt[z[p]]] && cnt[z[p]] == now) --now;
  ++t[--cnt[z[p]]];
}

[HNOI2009]最小圈

题意真难读。

solution

要求求图中所有环上边权的平均值的最小值，即求 $\min\{ \frac{\sum_{i = 1}^{k} w_i}k\}$，其中 $k$ 为环的边数。

设 $\mathrm{ans}$ 为这个最小值。则 $\sum_{i = 1}^k (w_i - \mathrm{ans}) = 0$。二分这个最小值，判断新图有无负环即可。

[SCOI2014]方伯伯运椰子

没看懂，你个懒熊回来复习的时候记得补上

一月结束了。

文章作者: fa_555
文章链接: https://blog.fa555.tech/2020/2020-Jan-Records/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 fa_555's Blog！