WyOJ 面向的主要用户是谁？

首先是 wfyz 的同学，WyOJ 的性质首先是校内的 OJ。

其次，是水平高的，还是水平低的？

目前为止 WyOJ 的主要用户是水平尚可的初二到高二同学，主要的用处是来打模拟赛。虽然说理论上也有补题的作用，但是补的人不是很多。

高水平的同学会上类似 hba 或者现在的 LCA 那里去集训。所以 WyOJ 应该面向低到中等偏上水平的同学。

这部分同学的特点是什么？大部分的算法已经学习完成，但是有缺陷，有短板。WyOJ 应该能给他们提供一个平台，让他们可以快速认清自己的短板，快速补齐。

这需要什么？首先需要让他们知道自己有短板、短板在哪里。其次需要让他们知道怎么补，怎么做题，做哪些题。

这其实很重要。我在役时间只有一年。前大半年我基本上都是在学算法，到第二年的四五月份左右，NOIP 级的算法我早就掌握完了，还学了一堆屁用没有的 ds。

直到六七月模拟赛开始多起来，我才逐渐意识到我的比赛成绩与水平非常之低。七八月我去了 mx 集训，在那里我可以说打了一百万场模拟赛，但是回来之后似乎提升并没有想象的那么多。

我观察到这似乎是一个非常共同的问题。

总结一下这个问题是什么呢：

• 只接受过集训，针对性的训练比较少，害怕打模拟赛

• 智力在线，算法点满了，但不均衡

• 通过模拟赛意识到自己有大问题，但是靠自己不太清楚怎么补，或者是就算找到了题单，也做不下去

比如说，我早就认识到我的贪心是个大问题，我找了一堆贪心的题单，包括 CF 的 ABCD 这种难度的题目去训练。

但是问题在哪里：做不出来的题目还是做不出来，能做出来的题目本来就能做出来。训练效果为零。

最终我的 NOIP 在贪心上撞死了。我想，如果我在役时把贪心给补好，也许结果会很不一样。

但我已经退役很久了。我希望能让以后的同学们不再受类似的问题困扰。

所以说，怎么办？

WyOJ 应该提供一个专题训练的功能。

具体就是用大模型。

互联网的优点就是大量的数据，这也是他的缺点，我们要做的就是选出我们要的那些数据来。

我想要的数据是优质的、有中文题面、带题解的题目。我能想到的是洛谷爬的 Codeforces、AtCoder 的题目。理由如下：

• 有中文题面，好做

• 质量有一定保证

• 有题解，虽然数量参差不齐但是可以选择题解数量多的

CF 提供了一点 API，但是似乎没有提供读取题面的 API，看来他不怎么希望能让别人爬他的题面。At 的 API 似乎也差不多。

用洛谷的好处是我已经会了，WyOJ Shojo 可以打个样。Shojo 这个名字太二了，换成 Maid 还好点儿。

然后我们可以用大模型去阅读这些题解，得到对这个题的一个大概认识。

我还没有认真学好深度学习，虽然整了本书，但只看到 CNN，离着 LLM 还远。

然后通过一些类似 IOI 赛制的比赛来测试每个人的能力，再不断测试出每个人各项能力的大致分数区间，随后针对性推荐题目。

这是个推荐网络，推荐网络里头似乎有很多有意思的算法，深度学习里头也有很多有意思的算法。

这个草稿还相当简略，但是想法已经成型了。

我非常期待这套系统能早日成功，帮助像曾经的我那样的同学们能够获得更好的分数。

E

观察数据范围，容易想到二分答案。

那么问题转化为如何统计 $1 \sim k$ 中的美丽数的数量。

考虑 $1 \sim k$ 中有多少个数能被 $p$ 整除，答案显然是 $\lfloor k/p \rfloor$。

考虑 $1 \sim k$ 中有多少个数能被 $p$ 和 $q$ 整除，答案是 $\lfloor k/p \rfloor + \lfloor k/q \rfloor$ 吗？

不对，因为这样的话，能同时被 $p$ 和 $q$ 整除的数会被算两次。所以要减去能同时被 $p$ 和 $q$ 整除的数，也就是减去 $\lfloor k / \text{lcm}(p,q)\rfloor$。

考虑 $1 \sim k$ 中有多少个数能被 $p$ 或 $q$ 整除，那么就是再减去能被 $p$ 和 $q$ 同时整除的数。

所以 $1 \sim k$ 中美丽数的数量就是 $\lfloor k / p \rfloor + \lfloor k / q \rfloor - 2\lfloor k/\text{lcm}(p,q)\rfloor$。

这样我们就可以直接二分得到最后的答案。

#include <iostream>
#define int long long
using namespace std;

int check (int p, int n, int m, int g)
{
    return p / n + p / m - p / g * 2;
}

int gcd (int a, int b)
{
    if (!b) return a;
    return gcd (b, a % b);
}

signed main (void)
{
    int t;


    cin.tie(0)->sync_with_stdio (false);
    cin >> t;
    while (t--) {
        int n, m, k;

        cin >> n >> m >> k;
        int g = n / gcd (n, m) * m;
        int l = 1, r = 1e18, mid, ans = -1;
        while (l <= r) {
            mid = (l + r) / 2;
            if (check (mid, n, m, g) < k) l = mid + 1;
            else r = (ans = mid) - 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

F

考虑这其实和背包问题很像，只是本题有多个“价值”。

然而价值都很小（最大为 $6$），那么我们可以直接把它放到我们的 DP 状态里。

所以最终的状态就是：$f_{iabcdef}$，表示考虑了前 $i$ 种学习计划，每种科目的得分分别为 $a, b, c, d, e, f$。

其实还有更简单的写法：把 $abcdef$ 压到同一个整数里，也就是用一个六进制数来作为状态。

转移和背包问题是一样的。

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, K, P;
    std::cin >> N >> P;
    K = 6;

    std::vector<int> pw(K + 1);
    pw[0] = 1;
    for (int i = 1; i <= K; i++) {
        pw[i] = pw[i - 1] * (P + 1);
    }

    std::vector dp(pw[K], -1LL);
    dp[0] = 0;

    for (int i = 0; i < N; i++) {
        int C;

        std::vector<int> A(K);
        for (int j = 0; j < K; j++) {
            std::cin >> A[j];
        }
        std::cin >> C;

        for (int s = pw[K] - 1; s >= 0; s--) {
            int t = 0;
            for (int j = 0; j < K; j++) {
                int a = s / pw[j] % (P + 1);
                int na = std::min(P, a + A[j]);
                t += na * pw[j];
            }
            if (dp[s] != -1 && (dp[t] == -1 || dp[t] > dp[s] + C)) {
                dp[t] = dp[s] + C;
            }
        }
    }
    std::cout << dp.back() << "\n";

    return 0;
}

参赛选手须知

本比赛使用 IOI 赛制，2025 年 12 月 7 日星期日 14:30 开始，时长三小时，17:30 结束。

赛时可以实时提交测评并查看结果。最终分数取决于最后一次没有编译错误的代码，而不是最高分。

不保证终榜分数等于赛时分数。

一切有关题意或测评，但不包含题目的解法、本人解法的正误等问题，可以向监考老师提出。

一切试图干扰正常评测的行为，将会被取消成绩。包括但不限于：

• 提交无意义的占用时间程序，比如 while (true);

• 频繁提交不能通过编译的程序。禁止将测评平台当作编译器。频繁提交编译错误的代码，干扰他人正常评测的，给予警告。

• 频繁提交相同程序。同一份代码，没有监考人员允许，不要提交多次。

• 频繁提交只有参数不同的程序，比如模拟退火等随机化算法。禁止通过多次提交测试参数来试图获得分数。

• 试图通过获得测试数据来得分的程序（虽然这是不可能的）。

• 其它任何严重干扰正常评测的行为。

选手可以在自己机器上利用大样例随意测试，没有限制。

赛时严禁任意形式的讨论。一切讨论被视作作弊，取消成绩。

如题。可以点击进入用户主页，或者是在用户博客首页点击“关于我”来查看。

可以在博客系统中创建新博客，随后在勋章管理中的自定义页面中展示。

潍坊一中机房残党，不定期维护 WyOJ

目前主要兴趣：虚拟化与容器、深度学习、计算机网络与路由、MBV 和 Fayzz

以往的部分兴趣：计算机组成、操作系统、x86 和 RISC-V、UNIX 与 UNIX 网络编程、计算机图形学

GNU 忠实信徒。GPLv3 忠实用户。

以往完成与未完成的项目：

• WyOJ
• vcc 与 vccd
• evx、xnix 与 cunix
• spearl 与 tripl

如题！

大家可以注意到的是，WyOJ 已经有了一个崭新且漂亮的博客系统。

同时，我把关注列表里的大部分人的博客搬运到了 OJ 上。

众所周知，由于洛谷的特殊情况，洛谷博客现在不太方便。

推荐大家以后使用 WyOJ 的博客系统！

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-31 23:37:49

多项式基本中的基本就是著名的 FFT。这个东西一个简单的（也是我现在只会的）用途是做多项式的乘法。

如果能做到两个过程 —— 即给定 $n$ 次多项式，求其在 $n$ 个不同点上的取值；给定 $n$ 个点表示某多项式的某些取值，还原出这个多项式 —— 我们就能快速进行多项式乘法：因为只需要把第一个过程得到的 $n$ 个点上的取值乘起来，然后还原，就好了。

DFT 就是解决这个东西的。我还分不清它和 FFT 的区别，暂且就这么叫着。

首先考虑怎么做第一步。

给定了多项式 $f(x) = \sum\limits_{i=0}^n a_ix$，要求其在 $n$ 个固定点上的取值。

设 $f_0(x)$ 表示这个多项式的偶数项取出来后得到的多项式（次数减半），$f_1(x)$ 表示相应的次数为奇数的。那么 $f(x) = f_0(x^2) + xf_1(x^2)$。这样分治下去，好像很对，但是啥用也没有，因为我们只是知道这两个子多项式在 $n/2$ 个点上的取值，无法解决现在的问题。

考虑：$f(-x) = f_0(x^2) - xf_1(x^2)$。很有启发性啊！这样，递归到 $f_0$ 和 $f_1$ 后，就可以 $O(n)$ 得到 $n$ 个点的取值了。

但是，相反数只有一对，肯定不能按来按去一直用。这个时候考虑把视角放到复数。设 $\omega_n^k = \exp (2\pi k\text{i} / n)$，那么有 $(\omega_n^k)^2 = \omega_{n/2}^k$。这个构造性确实很强，因为递归到子问题时，底标恰好也减半。同时，有 $\omega_n^{k+n/2} = -\omega_n^k$，因此恰好可以把它代入到原式里头。

得到：$f(\omega_n^k) = f_0(\omega_{n/2}^k) + \omega_n^k f_1(\omega_{n/2}^k)$

与：$f(\omega_n^{k+n/2}) = f_0(\omega_{n/2}^k) - \omega_n^k f_1(\omega_{n/2}^k)$。

就可以了。复杂度是线性单对数。

然后是第二步，怎么还原回去呢？经过我还没看的代数推导，只需要把 $f_1$ 前面的系数指数变成负的，最后把所有东西除以一个 $n$，就好了。

待补充：递归转迭代，IFFT 的证明，还有 NTT。

补充：递归转迭代，观察一下就好了。NTT，把 $\omega$ 的定义换一下就好了。IFFT 的证明，还要补。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-08 22:33:12

我们应该怎么维护这些集合？

如果简单的维护每个集合包含哪些数，能快速询问对称差吗？好像很难。

可不可以，考虑在值域上维护？

在值域上维护，用什么数据结构呢？维护什么信息呢？

我们设 $q_{ij}$ 表示第 $i$ 个集合中 $j$ 是否存在，为 $0$ 或 $1$。

那么，$w$ 不在 $x$ 与 $y$ 集合的对称差中，当且仅当 $q_{xw} = q_{yw}$。

相等。想起来什么东西了吗？

哈希。

发现，我们并不需要知道对称差中全部的元素。

因为我们只需要知道最大的，同时，我们又在值域上操作，所以……

想到用什么数据结构了吗？

如提示中所言。

我们用一颗值域线段树来维护一个集合，并在线段树上维护区间的哈希值。

操作一：加入一个数。也就是线段树单点修改某点为一。

操作二：查询对称差的最大值。

我们并不需要知道对称差里头的所有数。

我们想知道的是最大的 $w$，满足 $q_{xw} \ne q_{yw}$。

由于我们维护了区间的哈希值，那么这个问题可以用线段树二分解决。

只需要在每个节点，判断两棵树的右儿子是否相等。相等就往左儿子走，否则往右儿子走，直到走到叶子。

于是本题做完了。时空复杂度都是 $O(n\log V)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-03 18:56:06

这个循环右移相当不常规吧，所以也很难用常规的状态去描述它。一般的状态没法描述循环右移导致的改变。

我们考虑类似 $f_{ij}$ 的状态，表示匹配到 $s$ 前 $i$ 个字符，$t$ 的前 $j$ 个，所需要的最少的操作数量。

首先有朴素的转移 $f_{i-1j-1} + 1$，当 $s_i = t_j$。

然后，我们可以不让 $i$ 和 $j$ 匹配，而是把 $i$ 塞到前头和某个位置匹配，即 $f_{i-1j} + 1$。

同时，对应着“往前塞”的转移，我们可以也必须有一个“往后放”的转移。不这样的化，往前塞的转移是转移不到 $f_{00}$ 的。这条转移是 $f_{ij} = f_{ij-1}$。

我们想一想这个为啥是正确的。也就是：每一个往前塞的转移，是否都对应前面一个往后放的转移。

这是必须的。因为我们只能从 $(0, 0)$ 出发转移，且只有第一种转移是 $x, y$ 同时加一的；往前塞的转移，会让 $y$ 相对 $x$ 往前移动一步，往后放的转移会让 $y$ 相对 $x$ 往后走一步。如果不是两两对应，还能是什么呢？

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-03 19:41:38

本来不想打 ABC，unr 看了题，很快啊，一眼序列分治！刚好这几天写了一车序列分治板子，于是就整活写了。

题意是：对于所有子区间，求它的区间和模 $P$ 的加和。只对区间和取模，答案不取模。

首先有简单性质：对于两个小于 $P$ 的数，加起来也小于 $2P$。换句话说，把两个模后的数加起来，再取模，最多就减少一个 $P$。

考虑序列分治，那么区间和由在中点左边的后缀和和中点右边的前缀和组成。不妨把所有在中点右边的前缀和存起来，放到 vector 里并排序，然后枚举左端点确定后缀和。

由于刚才提到的性质，那么后缀和和前缀和凑成的区间和，要么已经小于 $P$，不再需要取模，要么最多只需要取模一次，也就是减掉一个 $P$。我们二分出第一个需要减去 $P$ 的位置，其左边的直接加起来，右边的加起来，然后减去右边的数量个 $P$。

复杂度 $O(n\log^2n)$。

p.s. 序列分治写起来比树状数组顺手，因此抢了个自己榜上首 A。整活成功。

submission