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 服务器运行在用户侧，负责和共享磁盘通信，该设计要求用户是可信的。该系统使用粗粒度的锁定，一个文件对应一个锁，所以不适用于经常并发写入相同文件的负载。论文的性能测试我没有太多时间看，总结时也忽略了一些我认为不是很重要的细节。

Rectangle Cutting

题目

输入两个整数 \(a\) 和 \(b\)，表示矩形 \(a\times b\)，判断是否能将矩形切割一次再拼接得到不同的矩形，切割线要求平行于某条边且得到的矩形边长为整数。

数据范围：\(1\leq a,b\leq 10^{9}\)。

思路

以下讨论总是假设 \(a\leq b\)：

• 首先我们总是应该对半切，如果不对半切，并且想要拼接得到矩形，那么只能切割更长的边 \(b\)，得到 \(a\times a\) 和 \(a\times(b-a)\)，但是不论怎么拼接都和原矩形相同。
• 如果 \(a\) 是偶数，可以总是对半切 \(a\)，然后拼接得到不同的矩形 \(\frac{a}{2}\times 2b\)。
• 如果 \(a\) 是奇数，\(b\) 必须是偶数，否则无法对半切。此时只能对半切 \(b\)，拼接得到矩形 \(2a\times\frac{b}{2}\)，当 \(a\neq\frac{b}{2}\) 时，得到的矩形和原矩形不同。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13

public static void solve() {
    int a = io.nextInt(), b = io.nextInt();
    if (a > b) {
        int t = a;
        a = b;
        b = t;
    }
    if (a % 2 == 0 || b % 2 == 0 && b != 2 * a) {
        io.println("Yes");
    } else {
        io.println("No");
    }
}

Equalize

题目

输入长度为 \(n\) 的数组 \(a\)，可以选择一个 \([1,n]\) 的任意排列 \(p\)，执行 \(a_{i}=a_{i}+p_{i}\) 操作。输出执行操作之后，能够得到的数组 \(a\) 中相同元素最大出现次数的最大值。

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

思路

将数组加上任意排列，肯定是更小的数对应更大的数，才能使相同元素的最大出现次数最大化。我们可以将数组 \(a\) 排序同时去重，之所以去重是因为相同元素加上排列之后必定不相同，然后将排列看作固定的递减数组。只要数组 \(a\) 中的两个数的差值小于 \(n\)，那么这两个数之间的元素必定可以在操作之后变成相同的元素。问题就转化为求区间的最大长度，同时最大值和最小值的差值小于 \(n\)，可以使用滑动窗口求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public static void solve() {
    int n = io.nextInt();
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < n; i++) {
        set.add(io.nextInt());
    }

    int m = set.size(), idx = 0;
    int[] a = new int[m];
    for (var x : set) {
        a[idx++] = x;
    }

    int ans = 1;
    for (int i = 0, j = 1; j < m; j++) {
        while (a[j] - a[i] >= n) {
            i++;
        }
        ans = Math.max(ans, j - i + 1);
    }
    io.println(ans);
}

Physical Education Lesson

题目

输入两个整数 \(n\) 和 \(x\)，求 \(k\) 的个数，使得对于编号为 \(1\) 到 \(k\) 的位置，满足第 \(n\) 个位置的编号为 \(x\)。第 \(n\) 个位置是按往返来计算的，例如 \(1,2,\dots,k-1,k,k-1,\dots,2,1\)，第 \(1\) 和 \(1+2k-2\) 个位置的编号都为 \(1\)。当 \(k>1\) 时，编号循环的周期就是 \(2k-2\)。题目限制 \(k>1\)。

数据范围：\(1\leq x<n\leq 10^{9}\)。

思路

\(k\) 必须满足 \(k\geq x\)，同时 \((2k-2)\cdot t+x=n\) 或 \((2k-2)\cdot t+k+k-x=n\)，变形得到 \(n-x=2\cdot(k-1)\cdot t\) 或 \(n+x-2=2\cdot(k-1)\cdot(t+1)\)。求 \(k\) 的个数，可以首先求出 \(\frac{n-x}{2}\) 和 \(\frac{n+x-2}{2}\) 的约数，约数加一就是满足等式的 \(k\) 值，最后限制 \(k\geq x\)，得到答案。其实也可以不使用集合去重，只需要特判 \(x=1\) 和 \(k=x\) 的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static void solve() {
    int n = io.nextInt(), x = io.nextInt();
    Set<Integer> set = new HashSet<>();
    calc(n - x, x, set);
    calc(n + x - 2, x, set);
    io.println(set.size());
}

private static void calc(int x, int y, Set<Integer> set) {
    if (x % 2 != 0) {
        return;
    }
    x /= 2;
    for (int i = 1; i <= x / i; i++) {
        if (x % i == 0) {
            if (i + 1 >= y) {
                set.add(i + 1);
            }
            if (x / i != i && x / i + 1 >= y) {
                set.add(x / i + 1);
            }
        }
    }
}

Lonely Mountain Dungeons

题目

输入三个整数 \(n,b,x\)，以及长度为 \(n\) 的数组 \(c\)。有 \(n\) 种生物，每种生物的数量为 \(c_{i}\)。你需要将所有生物分为 \(k\) 组，位于不同组的每对同种生物会使总分增加 \(b\)，同时总分会减少 \((k-1)\cdot x\)。输出能够得到的最大分数。

数据范围：\(1\leq n\leq 2\cdot 10^{5}\)，\(1\leq b\leq 10^{6}\)，\(0\leq x\leq 10^{9}\)，\(1\leq c_{i}\leq 2\cdot 10^{5}\)，\(\sum_{i=1}^{n}c_{i}\leq 2\cdot 10^{5}\)。

思路

首先需要知道，对于某种生物 \(i\) 和固定的 \(k\)，将 \(c_{i}\) 尽量平均分配是最优的，不过我也不知道该怎么证明。当 \(k>c_{i}\) 时，得分总是为 \(C_{c_{i}}^{2}\cdot y^{2}\)。当 \(k\leq c_{i}\) 时，就需要将 \(c_{i}\) 分为，\(c_{i}\bmod k\) 组包含 \(y=\lceil\frac{c_{i}}{k}\rceil\) 个该种生物，\(k-c_{i}\bmod k\) 组包含 \(y^{\prime}=\lfloor\frac{c_{i}}{k}\rfloor\) 个该种生物。得分为：

根据以上讨论，很容想到暴力枚举组数 \(k\)，然后内层循环计算该组数下的最大得分，总时间复杂度为 \(O(\max(c_{i})\cdot n)\)。由于题目限制 \(\sum_{i=1}^{n}c_{i}\leq 2\cdot 10^{5}\)，我们可以预处理得到所有 \(c_{i}\) 在组数为 \([1,c_{i}]\) 下的最大得分之和，从而可以将暴力枚举的内循环优化为 \(O(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

public static void solve() {
    int n = io.nextInt(), b = io.nextInt(), x = io.nextInt();

    int m = 0;
    int[] c = new int[n];
    for (int i = 0; i < n; i++) {
        c[i] = io.nextInt();
        m = Math.max(m, c[i]);
    }

    long[] f = new long[m + 1];
    long[] g = new long[m + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= c[i]; j++) {
            f[j] += calc(c[i], j);
        }
        g[c[i]] += calc(c[i], c[i]);
    }

    long ans = 0L;
    for (int i = 1; i <= m; i++) {
        ans = Math.max(ans, (f[i] + g[i - 1]) * b - (long) (i - 1) * x);
        g[i] += g[i - 1];
    }
    io.println(ans);
}

private static long calc(int n, int k) {
    int a = n / k, b = n % k;
    long res = (long) (k - b) * (k - b - 1) / 2 * a * a;
    res += (long) b * (b - 1) / 2 * (a + 1) * (a + 1);
    res += (long) (k - b) * b * a * (a + 1);
    return res;
}