ryp的博客

博客

PSS Round - 09.10（Easy Version）比赛须知

2025-09-10 13:34:16 By ryp

题目顺序是：

T1 T2 T3 T4 T5

368 369 370 365 364

阅读全文

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 下的所有账号也会被封禁。

阅读全文

书记的纸牌游戏 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$ 成为一个均衡区间的左端点需要满足的限制（右端点同理）：

右边有比 $v_i$ 大的数；
右边有比 $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)$ 的空间复杂度。

阅读全文

ryp的博客

博客

PSS Round - 09.10（Easy Version）比赛须知

WyOJ Musume 代码

新博客

WyOJ 账号激活方法

2025.8.22 题解

书记的纸牌游戏 1

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

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

购物计划

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

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

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

代码

烟花大会

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

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

代码

告白气球

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

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

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

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

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