Sasha and the Drawing

题目

输入整数 \(n\) 表示 \(n\times n\) 的正方形网格，网格总共有 \(4n-2\) 条对角线，输出最小的着色单元格数量，使得至少有 \(k\) 个对角线上存在着色的单元格。

数据范围：\(2\leq n\leq 10^{8}\)，\(1\leq k\leq 4n-2\)。

思路

最好情况下，对 \(1\) 个单元格着色，可以贡献 \(2\) 个对角线，最多有 \(2n-2\) 个单元格满足该条件，例如选择着色第一行的 \(n\) 个单元格和最后一行的中间 \(n-2\) 个单元格。剩下 \(2\) 个单元格，每着色 \(1\) 个可以贡献 \(1\) 个对角线。

代码

1
2
3
4
5
6
7
8

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    if (k <= 4 * n - 4) {
        io.println((k + 1) / 2);
    } else {
        io.println(2 * n - 2 + (k - (4 * n - 4)));
    }
}

Sasha and the Casino

题目

输入三个整数 \(k,x,a\)，表示有一个游戏每次可以选择下注 \(y\) 个硬币（\(y\leq a\)），如果赢了将获得 \(y\cdot k\) 个硬币，输了不会获得任何硬币，游戏最多连续输 \(x\) 次。输出初始有 \(a\) 个硬币时，是否存在某个方案能够获取无限数量的硬币。

数据范围：\(2\leq k\leq 30\)，\(1\leq x\leq 100\)，\(1\leq a\leq 10^{9}\)。

思路

首先，前 \(x\) 次游戏都下注 \(1\) 个硬币，最后下注 \(a-x\) 个硬币不是最优策略，因为可能会提前赢，如果赢的时候增量为负，将会输得很惨。所以对于第 \(i\) 次下注（\(1\leq i\leq x+1\)），下注大小 \(y_{i}\) 需要满足赢得游戏时 \(y_{i}\times (k-1)>\sum_{j=1}^{i-1}y_{j}\)。

代码

1
2
3
4
5
6
7
8

public static void solve() {
    int k = io.nextInt(), x = io.nextInt(), a = io.nextInt();
    int sum = 0;
    for (int i = 0; i <= x && sum <= a; i++) {
        sum += sum / (k - 1) + 1;
    }
    io.println(sum <= a ? "YES" : "NO");
}

Sasha and a Walk in the City

题目

输入一棵树，包含 \(n\) 个节点和 \(n-1\) 条边，输出存在多少个集合，使得任意简单路径都不会包含超过两个在集合中的节点，答案对 \(998244353\) 取模。

数据范围：\(2\leq n\leq 3\cdot 10^{5}\)，\(1\leq u_{i},v_{i}\leq n\)，\(u_{i}\neq v_{i}\)。

思路

假设节点 \(1\) 是树的根节点，定义 \(dp_{v}\) 表示以 \(v\) 为根的子树的非空集合个数，集合满足不存在一对节点，其中一个是另一个的祖先。假设节点 \(u_{1},u_{2},\dots,u_{k}\) 是节点 \(v\) 的子节点，则有 \(dp_{v}=\prod_{i=1}^{k}(dp_{u_{i}}+1)\)，当所有子树的集合为空时，表示只选择节点 \(v\)。最后答案为 \(\sum_{i=1}^{n}dp_{i}+1\)，可以通过以下分类讨论得到：

• 不存在祖先关系的集合个数为 \(dp_{1}+1\)，其中 \(dp_{1}\) 表示不存在祖先关系的非空集合个数，\(1\) 表示集合为空的情况。
• 存在祖先关系的集合个数为 \(\sum_{i=2}^{n}dp_{i}\)，因为对于每个节点 \(v\) 作为祖先，有 \(\sum_{i=1}^{k}dp_{u_{i}}\) 个集合存在祖先关系。

代码

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

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt();
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < n - 1; i++) {
        int u = io.nextInt() - 1, v = io.nextInt() - 1;
        g[u].add(v);
        g[v].add(u);
    }

    long[] dp = new long[n];
    dfs(0, -1, g, dp);

    long ans = 1L;
    for (long x : dp) {
        ans = (ans + x) % MOD;
    }
    io.println(ans);
}

private static void dfs(int x, int fa, List<Integer>[] g, long[] dp) {
    dp[x] = 1;
    for (int y : g[x]) {
        if (y != fa) {
            dfs(y, x, g, dp);
            dp[x] = dp[x] * (dp[y] + 1) % MOD;
        }
    }
}

Sasha and the Wedding Binary Search Tree

题目

输入两个整数 \(n\) 和 \(c\)，表示一颗二叉搜索树，以及节点值的取值范围为 \([1,c]\)。然后输入 \(n\) 行 \(l_{i},r_{i},v_{i}\) 值，表示节点 \(i\) 的左右子节点和该节点的值。如果 \(l_{i}<0\) 或 \(r_{i}<0\)，则表示没有对应的子节点。如果 \(val_{i}<0\)，则表示不知道该节点的值是多少。输出可能的二叉搜索树个数，答案对 \(998244353\) 取模。

数据范围：\(2\leq n\leq 5\cdot 10^{5}\)，\(1\leq c\leq 10^{9}\)。

思路

首先进行中序遍历，将所有值添加到一个列表，那么可以求出每段连续负数值的方案数，将所有段的方案数相乘就是答案。对于每一段可以知道其上下限，假设段的长度为 \(m\)，取值范围为 \([lo,hi]\)，则可能的取值数量为 \(k=hi-lo+1\)。那么方案数就是将 \(m\) 个球放入 \(k\) 个盒子的方案数，盒子可以为空，公式为 \(C_{m+k-1}^{k-1}=C_{m+k-1}^{m}\)，可以参考上一场比赛的最后一题。

需要注意的是，\(k\) 的取值范围很大，我们使用等号右边的公式计算方案数，可以只循环 \(m\) 次。由于答案需要取模，循环中取模之后的值可能无法被整除，所以必须计算模乘法逆元。以及下面的代码会栈溢出，但是改写为 C++ 就不会，只能说 Java 占用的栈空间比较大么，但是也有其他人使用 Java 通过测试，真不知道为什么我的就不行。

代码

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

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt(), c = io.nextInt();
    int[] val = new int[n];
    int[][] g = new int[n][2];
    for (int i = 0; i < n; i++) {
        int l = io.nextInt() - 1, r = io.nextInt() - 1;
        val[i] = io.nextInt();
        g[i][0] = l;
        g[i][1] = r;
    }

    List<Integer> aux = new ArrayList<>();
    dfs(0, g, val, aux);
    aux.add(c);

    long ans = 1L;
    int lo = 1, cnt = 0;
    for (int x : aux) {
        if (x < 0) {
            cnt++;
            continue;
        }
        if (cnt > 0) {
            ans = ans * calc(lo, x, cnt) % MOD;
            cnt = 0;
        }
        lo = x;
    }
    io.println(ans);
}

private static void dfs(int x, int[][] g, int[] val, List<Integer> aux) {
    if (x < 0) {
        return;
    }
    dfs(g[x][0], g, val, aux);
    aux.add(val[x]);
    dfs(g[x][1], g, val, aux);
}

private static long calc(int lo, int hi, int cnt) {
    long res = 1L;
    int len = hi - lo + 1;
    for (int i = cnt + len - 1, j = 1; j <= cnt; i--, j++) {
        res = res * i % MOD * pow(j, MOD - 2) % MOD;
    }
    return res;
}

private static long pow(long x, long n) {
    long res = 1L;
    for (; n != 0; x = x * x % MOD, n >>= 1) {
        if ((n & 1) == 1) {
            res = res * x % MOD;
        }
    }
    return res;
}

ABC 都是简单模拟题。D 题很经典，利用哈希表求同余的下标对数。E 题需要观察到答案只和元素的位数有关。F 题给出元素的偏序，判断是否存在全序，可以将顺序建模成有向图，然后使用拓扑排序判断是否存在环。G 题需要观察到如下性质，1 和 2 的数量不能相差超过一，3 和 4 放置的方案数相互独立，计算组合数的方式类似将 m 个球放入 n 个可以为空的盒子，公式为 \(C_{n+m-1}^{n-1}=C_{n+m-1}^{m}\)，可以看看灵神的视频。

阅读论文 Frangipani，参考 FAQ，note。

概述

Frangipani 是一个分布式文件系统，由 Petal 分布式存储服务和多个 Frangipani 服务器组成，Frangipani 服务器共享 Petal 提供的单个虚拟磁盘抽象，同时使用分布式锁保证缓存一致性。

实现

预写日志

每个 Frangipani 服务器都会使用预写日志记录系统元数据的变化（不记录文件数据），只有当日志持久化到 Petal 之后，才能修改系统的元数据。日志首先会按顺序存放在服务器内存的循环缓冲区中，然后定期刷新到 Petal。使用日志记录元数据的变化，可以避免服务器故障时元数据的部分更新导致文件系统结构被破坏（产生不一致），从而可以避免运行 fsck 一致性检查程序，实现快速恢复。

日志由若干大小为 512 字节的日志块组成，每个日志块都有一个单调递增的序列号。论文表示序列号作用是在故障恢复时检测日志的末尾，即使磁盘乱序写入数据。元数据由若干大小为 512 字节的元数据块组成，每个元数据块都有一个单调递增的版本号。日志块也会包含其所修改元数据块的版本号，只有日志块中的版本号大于元数据块的版本号时，才能应用日志。从而可以避免服务器故障恢复时，旧日志覆盖新版本的元数据，以及重复应用已经应用的日志。512 字节的日志块和元数据块实际上对应一个扇区，扇区的读写保证是原子的。

PS：论文提到元数据块被释放然后重用于文件数据导致版本号消失的问题，然后说明限制释放的元数据块仅被新的元数据块重用可以解决该问题。此处所说的元数据块应该是指扇区，所有才会释放和重用，也就是说版本号实际上是和元数据块所在的扇区绑定，而和元数据是什么无关。而且，之所以版本号消失会有问题，是因为日志块记录的是所修改元数据块的扇区位置。这种设计有点奇怪，日志块以及版本号不和修改的元数据关联，而是和扇区关联。

分布式锁

锁服务使用 Paxos 进行容错，为文件系统提供读写锁。当锁服务检测到冲突的锁请求时，会要求当前锁的持有者释放或降级锁，以消除冲突。读写锁允许 Frangipani 服务器从磁盘获取数据并将其缓存。在释放读写锁前，服务器会使缓存无效，从而保证缓存一致性。在释放或降级写锁前，服务器必须将脏数据写入磁盘（包括文件数据）。磁盘被划分为若干逻辑段，每个段都有一个锁，每个日志、文件、目录和符号链接都是一个段。每个文件使用一个锁，适合很少并发写的工作负载，其他负载可能需要使用更细粒度的锁。

锁具有粘性，也就是说 Frangipani 服务器获取锁之后不会主动释放，除非锁服务要求其释放。当挂载 Frangipani 文件系统时，Frangipani 服务器会调用 clerk 模块，该模块会连接到锁服务，获取租约并且在本地打开一个锁表。当文件系统被卸载时，clerk 会关闭锁表。clerk 和锁服务使用异步消息进行通信，有四种消息类型：request、grant、revoke 和 release。

故障处理

当 Frangipani 服务器的租约由于没有续约而过期时，锁服务会认为该服务器故障，此时需要一种机制来释放故障服务器持有的锁。锁服务会在另一个 Frangipani 服务器上启动恢复进程，新服务器会获取租约和故障服务器日志的锁，然后按顺序应用未执行的日志，最后释放（release）所有锁以及释放（free）日志。如果是由于网络分区故障而没有续约，租约过期的 Frangipani 服务器会主动丢弃其所有锁和缓存数据。如果缓存中存在脏数据，则服务器会向用户程序报告错误，将问题交给用户处理。

如果租约在服务器向 Petal 发送写入请求之后到达之前过期，则会产生问题，因为此时锁可能已经被授予故障恢复服务器。论文提到可以为每个写入请求添加过期时间戳，如果请求到达 Petal 的时间戳大于请求中的时间戳，则拒绝该请求。或者将锁服务和 Petal 集成，服务器为写入请求添加租约标识符，然后 Petal 可以判断租约是否过期。

问题

Q：日志序列号的作用有点奇怪，为什么磁盘要乱序写入数据？

Q：日志只会记录元数据，那么有可能只执行元数据更改，而丢失文件数据？

A：该语义符合标准的本地 Unix 文件系统，崩溃之前的写入可能会丢失。应用程序可以使用 fsync 系统调用，强制将数据立即刷新到磁盘。

总结

预写日志存储在 Petal 提供的共享虚拟磁盘上，使得任何服务器都可以使用故障服务器的日志进行恢复。多个日志使得恢复过程变得复杂，需要使用版本号机制避免异常。分布式锁保证服务器之间的缓存一致性。Frangipani 服务器运行在用户侧，负责和共享磁盘通信，该设计要求用户是可信的。该系统使用粗粒度的锁定，一个文件对应一个锁，所以不适用于经常并发写入相同文件的负载。论文的性能测试我没有太多时间看，总结时也忽略了一些我认为不是很重要的细节。