Logo ryp的博客

博客

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)$ 的空间复杂度。

评论

zrl123456
原来 T1 40pts+70pts=100pts
ryp
其实这篇题解不是 ryp 写的。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。