专栏文章

2025 年 10 月 20 日 J 组 CJ 模拟赛总结 & 题解

GGeorgeDeng
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjzjsr
此快照首次捕获于
2025/12/02 03:39
3 个月前
此快照最后确认于
2025/12/02 03:39
3 个月前
查看原文
原：24 年集训第十一场。
ABCD总分
分数100100101030303030170170
评价特别简单，不评价思路很容易想，但是我为什么没有想到啊结论题倍增好题rk.rk. 1616
很难，但也没有那么难。
补题链接。

A：卡片

题意简述

有 nn 个 11，nn 个 22，nn 个 33，从中选出若干张卡片，使得综合为 dd。求方案数。

正解思路

我们可以枚举使用 ii 张 33，jj 张 22。如果 d−3i−2j∈[1,n]d-3i-2j \in \left [ 1,n\right ]，那么这就是一个合法的方案，答案 +1+1。

赛时

简单题，直接切了。

B：分组

题意简述

有一个长度为 nn 的数组 aa，每次找到最大值，把 [max⁡(1,i−k),min⁡(n,i+k)]\left [ \max(1,i-k),\min(n,i+k) \right] 里面的数取出来。令这是第 ii 个被取出来的段，如果 ii 是奇数，把一段全部编号为 11，否则编号为 22。最后求所有的编号。

正解思路

看到区间删除，很容易想到用链表维护这整个东西。每次最大值，可以用一个 pair，它的 first 存原来的值，second 存下标。我们用一个优先队列存这个玩意。如果当前这个地方的答案非零，直接 continue。然后，我们暴力往两边跳 kk 步，直到是最左边或最右边为止（或者跳完 kk 步了）。然后，使用链表 把这个区间内所有点赋值为当前的编号。由于每个点只会被访问一次，所以时间复杂度 O(nlog⁡n)O(n\log n)，瓶颈在于优先队列。

赛时

只写了 k=0k=0 的部分分，想正解没有想到用链表，甚至想到树状数组去了。

AC 代码：

CPP
#include <iostream>
#include <cstdio>
#include <queue>
#include <utility>
#include <algorithm>
#define endl '\n'
using namespace std;

struct node{
    int prv,nxt;
}lb[6000005];//链表
int ans[6000005];
int n,m;
pair<int,int> aa[6000005];//卡常
queue<pair<int,int>  > q;//正常的有限队列，但是因为aa排过序了，所以直接用普通队列就行
signed main()
{
    freopen("team.in","r",stdin);
    freopen("team.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        lb[i].prv = i-1;
        lb[i].nxt = i+1;
        int a;
        cin>>a;
        aa[i] = {a,i};
    }
    sort(aa+1,aa+1+n,greater<pair<int,int>  >()  );
    for(int i = 1;i<=n;i++){
        q.push(aa[i]);
    }
    lb[n].nxt = 0;
    lb[0].nxt = 1;
    int now = 1;
    #define top front
    while(!q.empty()){
        pair<int,int> f = q.top();
        q.pop();
        if(ans[f.second]) continue;//如果这个地方被找过了
        int l = f.second,r = f.second;
        for(int i = 1;i<=m&&lb[l].prv!=0;i++){//暴力向左找
            l = lb[l].prv;
        }
        for(int i = 1;i<=m&&lb[r].nxt!=0;i++){//暴力向右找
            r = lb[r].nxt;
        }
        // cout<<l<<' '<<r<<' '<<f.second<<endl;
        for(int i = l;i<=r;i = lb[i].nxt){//染色
            ans[i] = now;
            if(lb[i].nxt==0) break;
        }
        // for(int i = l;i<=r;i++){
        //     ans[i] = now;
        //     // lb[i].nxt = lb[i].prv = 0;
        // }
        now = 3-now;
        lb[lb[l].prv].nxt = lb[r].nxt;
        lb[lb[r].nxt].prv = lb[l].prv;//删除
        while(!q.empty()&&ans[q.top().second]) q.pop();//把已经染色的点删掉，卡常
        // cout<<"lb[]:"<<endl;
        // for(int j = 1;j<=n;j++){
        //     cout<<lb[j].prv<<' '<<lb[j].nxt<<endl;
        // }
        // cout<<endl;
        // nxt[pre[l]]=nxt[r];
        // pre[nxt[r]]=pre[l];
        // while(!q.empty()&&vis[q.top().second])q.pop();
    }
    for(int i = 1;i<=n;i++){
        cout<<ans[i];
    }
    return 0;
}

C：活动

题意简述

有 nn 个线段，每个线段的左端点是 lil_i，右端点是 rir_i（其实是给你 lil_i 和 mm，ri=li+m−1r_i=l_i+m-1）。你最多可以移动一个线段到任意位置。求怎么移动才能使得仅被一个线段覆盖的地方尽量多。输出这个值。

正解思路

我们先定义一个函数：
f(i,j,k)=max⁡(0,m−max⁡(0,ri−lj+1)−max⁡(0,rj−lk+1))f(i,j,k)=\max(0,m-\max(0,r_i-l_j+1)-\max(0,r_j-l_k+1))
不难看出，这就是求第 jj 个线段不被 ii 和 kk 这两个线段覆盖的长度。
先求出不进行操作的答案，设这个答案为 nownow，显然：
now=∑i=1nf(i−1,i,i+1)now=\sum_{i=1}^n f(i-1,i,i+1)
当然要特殊处理一下 nn 这里。可以直接把 ln+1=rn+1=rn+1l_{n+1}=r_{n+1}=r_n+1。
然后，我们枚举移动的是 ii 这条线段。显然，我们可以把这个线段移动到很远的地方，使得这 mm 个地方都不会有其他线段挡住。那么，原来这个线段对 nownow 做出的贡献都需要减掉，再加上移除这个线段之后剩下的线段新对答案增加了哪些贡献。用数学式子表达，答案就是
max⁡i=2n{now+m−f(i−2,i−1,i)−f(i−1,i,i+1)−f(i,i+1,i+2)+f(i−2,i−1,i+1)+f(i−1,i+1,i+2)}\max_{i=2}^n\left \{ now+m-f(i-2,i-1,i)-f(i-1,i,i+1)-f(i,i+1,i+2)+f(i-2,i-1,i+1)+f(i-1,i+1,i+2)\right \}
时间复杂度线性。

赛时

没推出这个式子，导致只能拿 O(nm)O(nm) 的 3030 分。以后需要多尝试，不能只拿暴力分。

AC 代码：

CPP
#include <iostream>
#include <cstdio>
#include <utility>
#include <algorithm>
#define int long long
#define endl '\n'
using namespace std;

int n,m;
pair<int,int> t[200005];
int f(int i,int j,int k){
    if(j<1||j>n) return 0;
    return max(0ll,m-max(0ll,t[i].second-t[j].first+1)-max(0ll,t[j].second-t[k].first+1));
}
signed main()
{
    freopen("activity.in","r",stdin);
    freopen("activity.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>t[i].first;
        t[i].second = t[i].first+m-1;
    }
    sort(t+1,t+1+n);
    int now = 0;
    t[n+1].first = t[n+1].second = t[n].second+1;
    for(int i = 1;i<=n;i++){
        // now+=max(0ll,m-max(0ll,t[i-1].second-t[i].first+1)-max(0ll,t[i].second-t[i+1].first+1));
        now+=f(i-1,i,i+1);
        // cout<<i<<' '<<now<<endl;
    }//求now
    // cout<<now<<endl;
    int ans = now;
    for(int i = 2;i<=n;i++){
        ans = max(ans,now+m-f(i-2,i-1,i)-f(i-1,i,i+1)-f(i,i+1,i+2)+f(i-2,i-1,i+1)+f(i-1,i+1,i+2));
        // ans = max(ans,m+now-f(i-1,i,i+1)+f(i-2,i-1,i+1));
        // ans = max(ans,m+now-max(0ll,m-max(0ll,t[i-1].second-t[i].first+1)-max(0ll,t[i].second-t[i+1].first+1))+max(0ll,m-max(0ll,t[i-2].second-t[i-1].first+1)-max(0ll,t[i-1].second-t[i+1].first+1)));
    }//求最终答案
    cout<<ans;
    return 0;
}

D：卡牌游戏

题意简述

有一个长度为 nn 的数组 aa。每次从给定的 ll 到 rr 跳跃。如果当前的值是 aia_i，且后面有一个地方 jj，使得 ai=aja_i=a_j，那么可以直接传送到那里的后一个地方，且不花费任何代价，否则花费 11 的代价，往右移动一格。如果有多处满足，只能传送到最近的一个。求最小代价。TT 组数据，对于每组数据，qq 组查询 ll 和 rr。

正解思路

我们先算出对于 ii 它能够传送到哪里，设这个地方为 nxtinxt_i。定义 fi,jf_{i,j} 表示从 ii 开始 仅通过传送 跳 2j2^{j} 能跳到的地方。如果 nxtinxt_i 有意义，fi,0=nxtif_{i,0}=nxt_i，否则 fi,0=n+1f_{i,0}=n+1。
通过倍增的思想，我们很容易得到
fi,j=ffi,j−1+1,j−1f_{i,j}=f_{f_{i,j-1}+1,j-1}
然后对于每次询问，如果能跳，我们必定跳，具体跳多少可以通过倍增解决，注意：跳完之后还需要 +1+1 到下一格。否则，答案 +1+1，往后跳一格。
时间复杂度 O(T⋅qlog⁡n)O(T\cdot q \log n)，瓶颈在于倍增。

赛时

打了个暴力走人，没想到 8080 分就是在正解上面不用倍增用暴力跳就行。

AC 代码

CPP
#include <iostream>
#include <cstdio>
#include <map>
// #define int long long
#define endl '\n'
using namespace std;
namespace IO{
    char buff[1<<21],*p1=buff,*p2=buff;
    char getch(){
        return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;
    }
    template<typename T>
    void read(T &x){
        char ch=getch();int fl=1;x=0;
        while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}
        while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getch();}
        x*=fl;
    }
    template<typename T,typename ...Args>
    void read(T &x,Args& ...args){
        read(x);read(args...);
    }
    char obuf[1<<21],*p3=obuf;
    void putch(char ch){
        if(p3-obuf<(1<<21))*p3++=ch;
        else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;
    }
    void pc(const char *s){
    	while(*s)putch(*s),s++;
    }
    char ch[100];
    template<typename T>
    void write(T x){
        if(!x)return putch('0');
        if(x<0)putch('-'),x*=-1;
        int top=0;
        while(x)ch[++top]=x%10+48,x/=10;
        while(top)putch(ch[top]),top--;
    }
    template<typename T,typename ...Args>
    void write(T x,Args ...args){
        write(x),putch(' '),write(args...);
    }
    void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;//上面联考同款快读快写
int lst[15];
int nxt[500005];
int n;
int a[500005];
int f[35][500005];//把小的一位放前面，卡常
int lg[500005];
signed main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int _;
    // cin>>_;
    read(_);
    for(int i = 2;i<=(int)(5e5);i++){
        lg[i] = lg[i>>1]+1;
    }
    while(_--){
        // cin>>n;
        read(n);
        for(int i = 1;i<=13;i++) lst[i] = 0;
        for(int j = 0;j<=lg[n];j++){
            for(int i = 1;i<=n;i++){
            	f[j][i] = n+1;//初始化
            }
        }
        for(int i = 1;i<=n;i++){
            // cin>>a[i];
            read(a[i]);
            nxt[i] = 0;
        }
        for(int i = n;i;i--){
            nxt[i] = lst[a[i]];
            // mp[a[i]] = i;
            lst[a[i]] = i;
            if(nxt[i]!=0){
                f[0][i] = nxt[i];
            }
//                cout<<"f["<<i<<"][0]="<<f[i][0]<<endl;
        }
        for(int j = 1;j<=lg[n];j++){
            for(int i = 1;i+(1<<j)-1<=n;i++){//倍增转移
                if(f[j-1][i]<n)
                    f[j][i] = f[j-1][f[j-1][i]+1];
//                cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<endl;
            }
        }
//        return 0;
        int q;
        // cin>>q;
        read(q);
        while(q--){
            int l,r;
            // cin>>l>>r;
            read(l,r);
            int ans = 0;
            while(l<=r){
                if(f[0][l]>r){
                    ans++;
                    l++;
                }else{
                    for(int i = lg[n];i>=0;i--){//找能够跳多少
                        if(f[i][l]<=r){
//                        	return 0;
                            l = f[i][l]+1;
                            break;
                        }
                    }
                }
                // if(nxt[l]!=0&&nxt[l]<=r){
                //     l = nxt[l]+1;
                // }else l++,ans++;
            }
            // cout<<ans<<endl;
            write(ans);
            putch('\n');
        }
    }
    flush();
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...