Logo ryp的博客

博客

标签
暂无

WyOJ 账号激活方法

2025-08-28 21:27:56 By ryp

为了减少完全以刷号为意义的小号出现,并且将线上可能出现的不恰当行为言论与线下相关联,我们决定 任何账号都必须绑定到 QQ 以进行活动

具体方法:

  • 加入 QQ 群 1061173220,口令是 wyojyydsrypnb

  • 在群中发消息 /bind XXX,其中 XXX 是你的用户名

  • WyOJ Musume,也就是 WyOJ 的机器人,会回应你的消息。

  • 根据 WyOJ Musume 的指示来完成操作,绑定成功后,你的账号便可用。

注意:

每个账号只能绑定一个 QQ,但一个 QQ 可以绑定最多三个账号。

若某个账号决定被封禁,其对应的 QQ 会被封禁,对应 QQ 下的所有账号也会被封禁。

已把所有疑似僵尸号 Rating 清零

2025-08-27 13:47:45 By ryp

所有没有任何提交记录的号的 Rating 都已被清零。

没有封号。误操作的联系 2681243014 解封。

2025.8.22 题解

2025-08-22 16:51:12 By ryp

书记的纸牌游戏 1

$\text{Subtask 1(40pts)}$

递推,比正解还麻烦,略。

$\text{Subtask 2(60pts)}$

超级笨蛋博弈论,找规律。

考虑倒推,剩 $1$ 到 $m$ 张是先手有必胜策略,$m+1$ 是后手有必胜策略。

继续,考虑 $m+2$ 到 $2m+1$,先手方可以将纸牌数控制为 $m+1$,使得对方从 $m+1$ 开始取,进而自己有必胜策略;若 $2m+2$,则不论如何取,剩下纸牌在 $[m+2,2m+1]$ 范围内,后手有必胜策略。

归纳可知,若初始纸牌数 $n$ 为 $m+1$ 的倍数,后手有必胜策略,否则先手有必胜策略。

购物计划

$\text{Subtask 1(10pts)}$

$n\le 10$,乱搞点暴搜之类的东西大概就可以过的吧(其实我也不知道有什么具体的办法)。


$\text{Subtask 2(50pts)}$

$n\le 10^3$,是不加优化的 DP 做法。

问题的一个难解决的地方就在于分组的实质是选数并建立集合,而不是选取某一段。但要使每个集合中的最大值减最小值(集合即每一组,值即体积,下同)尽可能小,每个集合的元素就一定是排序后的数中某连续的一段,于是直接按物品体积进行排序,这样就可以把集合问题转化为分段问题了。

设 $f_i$ 表示将前 $i$ 个物品进行分组的最小“不整齐程度”,起初 $f_0=0$,有如下转移:

$$f_i=\begin{cases}v_i-v_1 & 1\le i< 2k \\\min \limits_{j=0}^{i-k}(f_j+v_i-v_{j+1}) & 2k\le i\le n \end{cases}$$

对于 $2k\le i\le n$ 的情况,枚举每个 $j$,取最小的 $f_j-v_{j+1}$ 进行转移,$f_n$ 即为最终答案。

转移次数 $O(n)$,转移复杂度 $O(n)$,总的时间复杂度为 $O(n^2)$。


$\text{Subtask 3(40pts)}$

考虑对上述 $O(n^2)$ 的做法进行优化。

复杂度高的原因出在每次取 $\min \limits_{j=0}^{i-k}(f_j-v_{j+1})$ 时需要 $O(n)$ 枚举 $j$,而实际上 $\left [0,i-k \right ]$ 是一个左端静止且右边递增的区间,因此可以直接用一个变量维护这个最值(甚至不需要写单调队列)。

现在,转移次数 $O(n)$,转移复杂度 $O(1)$,DP 的时间复杂度为 $O(n)$,由于排序是 $O(n \log n)$ 的,故总的时间复杂度为 $O(n \log n)$,可以通过此题。


代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e6+5;
const ll inf=1e18;
int n,k;
ll v[N],f[N],mini;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    sort(v+1,v+1+n);
    for(int i=1;i<=n;i++)
    {
        if(i<k*2)f[i]=v[i]-v[1];
        else
        {
            mini=min(mini,f[i-k]-v[i-k+1]);
            f[i]=v[i]+mini;
        }
    }
    printf("%lld",f[n]);
    return 0;
}

烟花大会

$\text{Subtask 1(30pts)}$


$O(n^2)$ 求出任意两点之间的边权(即时间,下同),直接从 $1$ 跑最短路。


$\text{Subtask 2(70pts)}$


考虑边权与坐标的关系,若从一点 $i$ 走到 $j$ 的时间是 $|x_i-x_j|$,且存在另一点 $k$ 满足 $x_k$ 在 $x_i,x_j$ 之间,那么边 $(i,j)$ 可被边 $(i,k),(k,j)$ 代替,也即经过 $k$ 不会使时间更长,这是因为:

$$\begin{aligned} dis_{i,j} &= |x_i-x_j| \\ &= |x_i-x_k| + |x_k-x_j| \\ &\ge \min \left\{ |x_i-x_k|,|y_i-y_k| \right\} + \min \left\{ |x_k-x_j|,|y_k-y_j| \right\} \\ &= dis_{i,k} +dis_{k,j} \end{aligned}$$

纵坐标同理。

对此推广,我们得到结论:对所有点按横坐标排序,相邻点连边,然后纵坐标做相同处理,然后跑最短路即可。边数是 $O(n)$ 的,可以通过此题。


代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+5;
const ll inf=1e18;

int n;
struct node
{
    int num;
    ll x,y;
}dot[N];
bool cmp1(node a,node b)
{
    return a.x<b.x;
}
bool cmp2(node a,node b)
{
    return a.y<b.y;
}

struct edge
{
    int v;
    ll w;
};
vector<edge>e[N];
priority_queue<pair<ll,int> >q;
ll d[N];
bool vis[N];

void dijkstra()
{
    for(int i=1;i<=n;i++)d[i]=inf;
    d[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int u0=q.top().second;
        q.pop();
        if(vis[u0])continue;
        vis[u0]=1;
        for(int i=0;i<e[u0].size();i++)
        {
            int v0=e[u0][i].v,w0=e[u0][i].w;
            if(d[u0]+w0<d[v0])
            {
                d[v0]=d[u0]+w0;
                q.push(make_pair(-d[v0],v0));
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        dot[i].num=i;
        scanf("%lld%lld",&dot[i].x,&dot[i].y);
    }

    sort(dot+1,dot+1+n,cmp1);
    for(int i=1;i<n;i++)
    {
        int u0=dot[i].num,v0=dot[i+1].num,
        w0=dot[i+1].x-dot[i].x;
        e[u0].push_back({v0,w0});
        e[v0].push_back({u0,w0});
    }

    sort(dot+1,dot+1+n,cmp2);
    for(int i=1;i<n;i++)
    {
        int u0=dot[i].num,v0=dot[i+1].num,
        w0=dot[i+1].y-dot[i].y;
        e[u0].push_back({v0,w0});
        e[v0].push_back({u0,w0});
    }

    dijkstra();
    printf("%lld",d[n]);
    return 0;
}

告白气球

$\text{Subtask 1(10pts)}$

$O(n^3)$ 超级大暴力,略。

$\text{Subtask 2(5pts)}$

容易知道均衡区间不存在,答案全是 $0$。

$\text{Subtask 3(15pts)}$

建 $ST$ 表维护区间 $min$ 和 $\max$,$O(1)$ 判断一个区间是否合法,时间复杂度 $O(n^2)$。

$\text{Subtask 4(35pts)}$

这一档区分出常数太大的 $\log$ 以及一些神秘复杂度,像根号、$\log^2$ 之类的,放到下面讲。

$\text{Subtask 5(35pts)}$

我们考虑位置 $i$ 成为一个均衡区间的左端点需要满足的限制(右端点同理):

  1. 右边有比 $v_i$ 大的数;
  2. 右边有比 $v_i$ 大的数。

也就是说,$i$ 符合条件需要右端点 $j$ 足够大。

我们做四次单调栈分别预处理出每个 $v_i$ 的左侧和右侧第一个大于或小于 $v_i$ 的数的位置(不存在则用 $0$ 或 $n+1$ 补充)。左侧的两个位置取 $\min$,记为 $L_i$;右侧取 $\max$,记为 $R_i$。

那么 $[i,j]$ 是均衡区间的充要条件是,$j>R_i$ 且 $L_j>i$。

因此,将所有 $(j,L_j)$ 视为平面上的点,$i$ 的答案即平面上符合上述条件的点的个数,离线下来用树状数组做二位数点即可。注意要离散化。

这个做法有 $O(n\log n)$ 的时间复杂度和 $O(n)$ 的空间复杂度。

目录下重复文件自动转成符号链接。仅 Linux

2025-08-20 18:48:34 By ryp
import os
import hashlib

def hash (path, method=hashlib.md5):
    h = method ()
    with open (path, 'rb') as f:
        while b := f.read (8192):
            h.update (b)
    return h.hexdigest ()

q = dict ()
for root, _, k in os.walk ('.'):
    for d in k:
        i = root + '/' + d
        print (i)
        h = hash (i)
        print (h)
        if h in q:
            print (f'{i} (Cached from {q[h]})')
            os.system (f'ln -sf {q[h]} {i}')
        else:
            print (f'{i} (Uncached)')
            q[h] = i

比赛公告

2025-08-20 13:46:16 By ryp

T4 的数据有误,已经修好。

WyOJ 添加了伟大无敌正确胜利的 UB 检测器!

2025-08-17 23:33:10 By ryp

经过我一晚的奋战,WyOJ 已经成功加入了一个 UB 检测器!

截图

具体使用,只需要把语言选为 C++17ubsan,然后重新提交!非常简单也非常好用!!!!!!

然后,点击 Runtime Error 的数据点,可以看到 output 区域包含了具体 UB 信息

具体的实现是,我把 C++17ubsan 语言的 stderr 输出到了输出文件,于是 output 就会包含原先 stderr 的内容。

如果你的 stderr 内容过多,可能导致 UB 信息被挤掉看不到。 这时可以 #define stderr stdout,然后重新提交。

原先 AC 的点会变成 WA

使用检测器后的代码常数会变大不少,所以可能导致 TLE。

比赛期间看不到 output,所以本功能也自然在赛时无用。

同时,Special Judge 和 Hack 功能也已经修好!

Splay 详解

2025-08-01 11:53:12 By ryp

整理了一些关于 Splay 的资料,一个简洁美丽而高效的数据结构。

Splay 是最简洁的平衡树之一,支持维护区间信息。相比线段树,其可以动态地删点、加点,更加灵活;相比分块,其复杂度是均摊对数,更加高效。

在形态变化时,Splay 并不通过维护一系列性质来保证树高,而是通过伸展保证均摊复杂度。这让它少了常见平衡树的繁杂分讨,但常数也要大不少。

形态及操作

Splay 首先是一棵二叉搜索树,由许多节点组成。我们在每个节点维护父亲的左右儿子指针,以及键值。如有需要,还可以维护它子树内的信息,如它的子树大小。维护子树大小,可以实现快速查询第 k 大或者某数排名。

Splay 的核心操作是伸展(splay)。伸展某个节点 $x$,意味着将 $x$ 节点提升到根,同时更新所维护的子树信息。原来的根在伸展后成为某个普通内部节点。伸展操作的均摊复杂度是对数。

如果能够实现伸展操作,就可以方便地进行许多操作:

  • 插入。插入与普通二叉树的插入相同,按照二叉树的遍历方法找到某个叶子节点,将新值插入到该叶子的儿子下。不同的是,在插入某个点后,为了保证复杂度正确,我们要将这个节点伸展到根。

  • 删除。首先将这个节点伸展到根,然后将其与其儿子断开。这时原树分裂成两个子树,考虑合并它们。找到左子树的最大值,由二叉树的性质,这个数一定小于右子树的最小值。因此,我们将 $y$ 伸展到根。这时 $y$ 的右儿子一定空,于是将右子树拼到其右儿子上即可。

  • 查找某个数。按照二叉树的查找方法,一直找到这个数,或者某个叶子。将最后找到的节点伸展到根。

  • 查询排名。首先查找这个数,伸展到根。然后小于其的数数量就是现在根左子树的大小。如果待查询的值不存在,还要考虑根是否小于这个数。

  • 查询第 $k$ 大。和二叉树相同。从根节点开始遍历。如果当前节点 $x$ 左子树的大小,也就是小于 $x$ 的数字数量,大于等于 $k$,要找的节点在左子树;如果等于 $k - 1$,那么就是当前节点 $x$;否则,在右子树,并且 $k$ 减去左子树加上当前点大小。

  • 查询前驱。伸展到根,然后找左子树的最大值,也就是一直向右走。如果查询的值不存在,特判根是否小于待查值。

  • 查询后继。与查询前驱同。

  • 查询区间。设待查询区间为 $[l, r]$,我们将 $l - 1$ 旋到根,$r + 1$ 旋到根的右儿子,那么根的右儿子的左儿子,其上的信息就是 $[l, r]$ 的信息。

伸展

旋转

现在,我们只需要有效地实现伸展操作,就可完成所需的一切操作。

考虑怎么将某个节点高度提升一。我们称这个操作为旋转。

考虑怎么将 $2$ 提升到 $4$ 的位置。

那样,$4$ 该放到哪里?可以接到 $2$ 的右儿子上。$2$ 的右儿子放到哪里?放到 $4$ 的左儿子上,因为 $4$ 原来的左儿子是 $2$,现在已经空。其他子树不变。因此,变的只有 $2$ 和 $4$。

单旋与双旋

伸展操作能不能直接一直向上旋转呢?可以,但复杂度错误。

为了改善复杂度,我们需要引入双旋。

双旋是指,在伸展过程中,如果出现 $x$ 与 $x$ 的父亲同向,不能简单地旋转两次 $x$,而是要先旋转其父亲,再旋转 $x$。

我们如果想要将 $6$ 伸展到根,是不是需要双旋?答案是肯定的,因为 $4$ 和 $6$ 都是其父亲的右儿子,属于同向。如果是伸展 $3$,就不需要了。按照双旋的过程,我们先旋转 $4$,再旋转 $6$。也就是,先变成:

后旋转 $6$

光看上图,可能感觉双旋和单旋没有什么区别,但实际上在复杂度分析时,使用双旋可以保证某个性质,进而保证复杂度正确。

总之,我们已经知道了怎样以正确的复杂度将 $x$ 伸展到根。有关 Splay 的基本操作,就介绍完毕了。

附一份常数和美观程度都不错的实现

复杂度

势能分析简介

我们发现,Splay 的复杂度来源于两部分,一部分是遍历,另一部分是伸展。让最终遍历到节点马上被伸展到根,就可以把复杂度都算在伸展里,进而只需证明伸展的复杂度。

我们采用势能分析。势能分析是指,引入某个势能函数 $\Phi(D)$,描述某时数据结构的状态。

设每次操作的代价是 $c_i$,每次操作后数据结构为 $D_i$。要证 $\sum c_i$ 有某上界。如果 $\Phi(D_n) - \Phi(D_0) = O(F(n))$,$\Phi(D_n) - \Phi (D_0) + \sum c_i = \sum (c_i + \phi(D_i) - \phi(D_{i - 1})) = O(G(n))$,显然 $\sum c_i = O(F(n) + G(n))$。

这样有什么好处?我们考虑,Splay 等数据结构复杂度分析的难处,在于我们只知道 $c_i$ 的一个很松的上界,而不好直接分析 $\sum c_i$。实际上,某个大的 $c_i$ 对数据结构的影响也是大的,会导致后续的操作 $c_i$ 更小;换句话说,不会出现所有 $c_i$ 都取到上界的情况。

引入势能函数后,每个很大的 $c_i$,可以用一个很小的 $\Phi(D_i) - \Phi(D_{i-1})$ 来平衡。因而可以更方便地放缩,并得到上界。

具体分析

我们设某个节点的势能函数为 $\phi(x) = \log \lvert x\rvert$($\log$ 均以二为底;$\lvert x\rvert$ 表示 $x$ 的子树大小),$\Phi(D) = \sum \phi(x)$。显然的,$0\le \Phi(D) \lt n\log n$,并且 $\Phi(D_n) - \Phi(D_0) = O(n\log n)$。我们要证明每次伸展操作的均摊复杂度是对数。

伸展的分解

根据上面对 Splay 的介绍,我们可以将伸展分为三种具体操作。设 $x$ 为待伸展的节点,$y$ 为 $x$ 的父亲,$z$ 为 $y$ 的父亲。

  • zig,即一次单旋,在 $y$ 为根时候发生。直接旋转 $x$,其深度减少一。发现这种旋转最多发生一次。

  • zig-zig,即一次双旋,在 $y$ 和 $x$ 同向时发生。先旋转 $y$,后旋转 $x$。$x$ 深度减少二。

  • zig-zag,即两次对 $x$ 的单选,在 $x$ 和 $y$ 不同向时发生。$x$ 深度减少二。

伸展的过程是数次 zig-zig 与 zig-zag 的组合,加上可能存在的一次 zig。

zig 的分析

旋转的复杂度为 $O(1)$,势能的变化量为

$\phi(x') + \phi(y') - \phi(x) - \phi(y) = \phi(y') - \phi(x) \le \phi(x') - \phi(x)$

因此摊还代价是 $O(1) + \phi (x') - \phi (x)$。

zig-zig 的分析

摊还代价是

$$ \begin{aligned} & c \\ =& 1 + \phi(x') + \phi(y') + \phi(z') - \phi(x) - \phi(y) - \phi(z) \\ =& 1 + \phi(y') + \phi(z') - \phi(x) - \phi(y) \\ \end{aligned} $$

考虑怎么把 $1$ 去掉,因为如果引入 $1$,就会导致最终复杂度与旋转次数有关。

有:

$$ \begin{aligned} 2\phi(x') - \phi(x) - \phi(z') = \log (\dfrac{\lvert x'\rvert^2}{\lvert x\rvert\lvert z'\rvert}) \ge 1 \end{aligned} $$

这是因为 $\lvert x'\rvert \ge \lvert x\rvert+\lvert z'\rvert$。注意到不双旋时,此不等式不满足。这也是为什么双旋才能保证复杂度。

用这个不等式代换常数 $1$,得到

$$ \begin{aligned} & c \\ \le& 2\phi(x') - \phi(x) - \phi(z') + \phi(y') + \phi(z') - \phi(x) - \phi(y) \\ \le& 2\phi(x') - 2\phi(x) + \phi(y') - \phi(y) \\ \le& 3\phi(x') - 3\phi(x) \\ =& O(\phi(x') - \phi(x)) \end{aligned} $$

成功将常数消去,同时和前面的 $\phi(x') - \phi(x)$ 保持了一致。

zig-zag 的分析

类似的,我们有不等式:$2\phi(x') - \phi(y') - \phi(z') = \log (\dfrac{\lvert x'\rvert^2}{\lvert y'\rvert\lvert z'\rvert})\ge 1$

$$ \begin{aligned} & c \\ &= 1 + \phi(x') + \phi(y') + \phi(z') - \phi(x) - \phi(y) - \phi(z) \\ &= 1 + \phi(y') + \phi(z') - \phi(x) - \phi(y) \\ &\le 2\phi(x') - \phi(y') - \phi(z') + \phi(y') + \phi(z') - \phi(x) - \phi(y) \\ &\le 2\phi(x') - 2\phi(x) - \phi(y) \\ &\le 2\phi(x') - 2\phi(x) \\ &= O(\phi(x') - \phi(x)) \end{aligned} $$

综合

分析得到,zig 的摊还代价为 $O(1 + \phi(x') - \phi(x))$,而这种旋转最多一次;其他的两种旋转,摊还代价都是 $O(\phi(x') - \phi(x))$。这样,伸展的总代价就是 $O(\log \lvert x'\rvert - \log \lvert x\rvert + 1) = O(\log n)$。我们成功证明了伸展的复杂度是摊还对数,由此知道 Splay 的复杂度是正确的。

跳表

2025-07-24 14:59:31 By ryp

跳表实际上是一个多层链表,每一层链表都有序。从下到上(层数从小到大),链表逐渐变小。一个元素位于第 $k$ 层的概率是 $p^k$,实践中一般会限制层数。

因此 $n$ 个元素的跳表的第 $k$ 层链表的大小期望是 $np^k$,呈指数级下降。这保证复杂度正确。

对于实践,我们对每一个节点,维护它的值以及它在每一层的链表指针 nxt[]

接下来考虑操作。

最基本的操作是在跳表中查找一个节点。由于每一层链表有序,并且越高层节点越少,我们可以从最高层开始遍历。由于在高层的节点一定也在低层,并且每一层链表都具有单调性,所以这个算法正确。

考虑复杂度。显然的,如果证明了搜索的复杂度正确,跳表的其他一系列操作复杂度都正确。

注意到,搜索某个节点,实际上就是从 rank $1$ 走到 rank $k$ 的过程。与朴素链表不同的是,跳表允许不连续地从 $1$ 走到 $k$,这就是它节省的复杂度。

有一个比较简单的感性证明。考虑在第 $k$ 层,rank $i$ 走到 $rank j$ 的期望代价是 $(j - i) p^k$(二项分布),这个代价随着层数增加而减小。

严格证明可以看 OI Wiki,但是我觉得我这个感性就比较够了。

然后考虑更多的操作。考虑插入一个节点。我们需要决定把这个节点到前多少层,这可以随出来。我们找到这些层上这个节点的前驱,就可以按照链表的方法,把它插入到跳表中。删除一个节点同样简单,前驱后继也很基本。

第 $k$ 大和查排名不出所料地需要维护信息。

维护啥?如果能维护出每个节点的 $rank$,那就跟玩一样了。虽然我们显然办不到,但是我们可以维护每一层上相邻两个节点之间的实际距离,也就是排名差。

这个玩意儿是很好维护的。插入的时候我们将后继的排名差加一,删除的时候减一即可。于是我们做完了。

好吧,这个东西好像不那么好维护,但是我现在不太感兴趣了。我打算用 Rust 写一个类似 Redis 的内存数据库,主要是为了练习 Rust。

一个简单的渲染到 PPM 的渲染器

2025-07-10 16:08:05 By ryp

之前写了个渲染到 PPM 的最基本的渲染器,画了条贝塞尔曲线,但是非常简陋:

  • 只有 2D
  • 明显的锯齿
  • 渲染架构太简陋

第一个问题我以后再解决。至于锯齿,我觉得可以写一个 MSAA。渲染架构,就加一个包围盒。

我最开始想的是,维护所有包围盒,然后渲染时候用类似二维差分的东西做,后来发现这个东西差分掉之后很不自然,精度大概也有点问题。所以我决定做在线渲染,也就是接收到每一个图元的同时即时渲染出片段颜色。

但是之后咋办?二维遍历图元和像素点太慢,但是前缀和精度要爆。

哦我脑瘫了,只能这么做。而且这个也不能前缀和,因为矩形内部颜色又不一样。

发现图形学有很多神秘参数需要调。

【比赛通知】0621 模拟赛 须知

2025-06-21 13:42:01 By ryp
  1. 赛时只测样例,因此只要没有编译错误,都是满分。

  2. 赛后由老师点击重测来进行实际测试

  3. 第五、第六题是实际的第三、第四题,原第三、第四题是实际的第五、第六题

共 28 篇博客