杭电多校春季联赛-热身赛

以下按难度顺序。

临渊羡鱼

Description

给定数轴上若干个点，求可以完整包含所有点的最小区间长度。

Solution

自然是最左端的点和最右端的点的距离。

Code

void solve() {
    cin>>n; int mx=0, mn=LLONG_MAX;
    for(int i=1; i<=n; i++) {
        int t; cin>>t;
        mx=max(mx, t);
        mn=min(mn, t);
    }
    cout<<mx-mn+1<<'\n';
}

最大三段和

Description

给定一个数组，从中选出三个不连续的非空子段，同时要求第二个子段长度为 。求最大的三段和。

Solution

枚举第二个子段，对于前后缀，贪心的选取，即：分别维护前后缀和，出现负数就舍去，该过程不断保留最大值。注意要求子段非空，可能出现全为负数情况，则还须维护单点最大值。

Code

void solve() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
    }
    int st=0, mx=0; 
    mf[0]=LLONG_MIN;
    mg[n+1]=LLONG_MIN;
    for(int i=1; i<=n; i++) {
        st+=a[i];
        if(st<0) st=0;
        mx=max(mx, st);
        mf[i]=max(mf[i-1], a[i]);
        if(mf[i]>0) f[i]=mx;
        else f[i]=mf[i];
    }
    st=0; mx=0;
    for(int i=n; i>=1; i--) {
        st+=a[i];
        if(st<0) st=0;
        mx=max(mx, st);
        mg[i]=max(mg[i+1], a[i]);
        if(mg[i]>0) g[i]=mx;
        else g[i]=mg[i];
    }
    int __=LLONG_MIN;
    for(int i=3; i<=n-2; i++) {
        __=max(__, f[i-2]+a[i]+g[i+2]);
    }
    cout<<__<<'\n';
}

最大的公约数

Description

给定整数 ， 将其拆分成两个大小不等的正整数 和 ，求 的最大值。

Solution

考虑 ，令 ，，则 ，所以问题转化为求 最小值，稍加分析可得该值为 第一个大于 因子。

Code

void solve() {
    cin>>n;
    //div4d别追我了
    vector<int> ir;
    for(int i=1; i*i<=n; i++) {
        if(n%i==0) {
            ir.push_back(i);
            ir.push_back(n/i);
        }
    }
    sort(ir.begin(), ir.end());
    for(auto &ele: ir) {
        if(ele>2) {
            cout<<n/ele<<'\n'; return;
        }
    }
}

杂草蔓延

Description

给定一个 大小的网格场地，初始场地无杂草。从某时刻开始你可以指定操场任意位置格子出现杂草，询问最终能使得操场长满杂草的初始杂草格子数量最小值。

杂草蔓延规则：每天都会有未长杂草的格子被杂草蔓延，当且仅当其与至少两个已经生长杂草的格子相邻（四联通）。

Solution

神秘构造题，不会证明，就这样吧。

注意到在蔓延规则下斜着的杂草利用率更高，钦定短边为 ，则我们可以使用 块杂草沿 对角线铺设，最终效果为该正方形杂草覆盖完全。

然后再考虑余下的 ，注意到对于 ，只需每两列安排一个杂草即可。

Code

void solve() {
    cin>>n>>m;
    if(n<m) swap(n, m);
    if(n==m) cout<<n<<'\n';
    else cout<<m+(n-m+1)/2<<'\n';
}

雪蜜冰城柠檬茶的神秘成分魔法

Description

给定初始正整数序列与三种操作：

• ：将目前序列中所有 替换为
• ：在序列末尾添加一个
• ：将目前序列中所有 删除

Solution

很明显注意到倒着处理会很正确。

记录一个数组，表示当前元素指向的元素。初始时所有元素指向自己。替换即将 指向元素替换为 指向元素。删除即为指向 。最终输出所有不为 的元素即可。

但是很关键的一个点是，这个东西不是树形结构！不是树形结构！不是树形结构！

换句话说这个类似于快照，当前指向什么就是什么，而不存在链式的向上查找。不要写类似dsu的路径压缩之类的，不然会变得不幸。

Code

void solve() {
    cin>>n; 
    for(int i=1; i<=n; i++) cin>>a[i];
    cin>>m;
    stack<array<int, 3>> q;
    for(int i=1; i<=m; i++) {
        int op; cin>>op;
        if(op==1) {
            int x, y; cin>>x>>y;
            q.push({1, x, y});
        }
        else {
            int x; cin>>x;
            q.push({op, x, -1});
        }
    }
    stack<int> add;
    for(int i=0; i<=10000004; i++) fa[i]=i;
    while(!q.empty()) {
        auto [op, x, y]=q.top(); q.pop();
        if(op==1) {
            fa[x]=fa[y];
        }
        else if(op==2) {
            if(fa[x]) add.push(fa[x]);
        }
        else {
            fa[x]=0;
        }
    }
    for(int i=1; i<=n; i++) {
        if(fa[a[i]]) cout<<fa[a[i]]<<' ';
    }
    while(!add.empty()) cout<<add.top()<<' ', add.pop();
    cout<<'\n';
}

收买时间

Description

给定一个 大小的网格，以及一个初始金钱。

每个格子有一个属性 ，意味着只有当时间达到 时刻时才能通过该格子。保证 与 的 均为0。

有两种移动方式：

1. 你可以在相邻的格子间自由移动，包括上下左右四个方向。这种移动不消耗时间，也不花费金钱。然而你不能去不可通行的格子和网格之外。
2. 网格中共有 个单向传送门，每个传送门具有三个属性：起点、终点、需要消耗的金钱。同样的，这种移动不消耗时间，也不能去不可通行的格子。

你的目标是从起点 尽可能早地到达终点 ，同时总花费不超过初始金钱。

Solution

二分答案+ 。只有当当前格子的 小于等于当前钦定的时间时，才认为有连边。

其实因为每个点能连点边数非常有限，所以写这种直接的 复杂度不会太大。然而如果不二分，写点带 的东西就会 ，神秘卡常题，很神奇吧。

Code

int n, m, money, k, t[_], ha[_];
vector<pair<int, int>> pro[_];
bool check(int mm) {
    for(int i=401*1+1; i<=401*n+m; i++) ha[i]=-1;
    queue<pair<int, int>> q; q.push({401*1+1, money}); ha[401*1+1]=money;
    while(!q.empty()) {
        auto [pos, tm]=q.front(); q.pop();
        if(ha[pos]>tm) continue;//快照
        int x=pos/401, y=pos%401;
        for(int i=0; i<4; i++) {
            int tx=x+dx[i], ty=y+dy[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m) {
                if(t[401*tx+ty]<=mm) {
                    if(tx==n&&ty==m) {
                        return 1;
                    }
                    if(ha[401*tx+ty]<tm) {
                        ha[401*tx+ty]=tm;
                        q.push({401*tx+ty, tm});
                    }
                }
            }
        }
        for(auto &[aim, cost]: pro[pos]) {
            if(t[aim]<=mm) {
                if(tm>=cost) {
                    if(aim==401*n+m) {
                        return 1;
                    }
                    if(ha[aim]<tm-cost) {
                        ha[aim]=tm-cost;
                        q.push({aim, tm-cost});
                    }
                }
            }
        }
    }
    return 0;
}
void ff(int l, int r) {
    if(l+1>=r) {
        cout<<r<<'\n'; return;
    }
    int mid=l+r>>1;
    if(check(mid)) ff(l, mid);
    else ff(mid, r);
}
void solve() {
    cin>>n>>m>>money>>k;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>t[401*i+j];
            pro[401*i+j].clear();
        }
    }
    for(int i=1; i<=k; i++) {
        int x, y, p, q, w;
        cin>>x>>y>>p>>q>>w;
        pro[401*x+y].push_back({401*p+q, w});
    }
    ff(-1, 1e9);
}

小z的开箱

Description

一条环形道路，每个节点有一个幸运宝石与其幸运值(1~10)。小z有一颗幸运宝石，初始幸运值为0。

小z可以任意选择起点与方向一直前行(不可回头)，直到回到初始位置，小z可以自由选择是否吸收路上的幸运宝石中的幸运值。

然而小z的幸运宝石只能保存质数的幸运值。

也就是说，当小z每吸收一颗幸运宝石，他手中的宝石的幸运值为小于等于手中宝石和吸收宝石幸运值之和的最大质数，若不存在则为0。

小z希望最后得到的宝石幸运值最大，请你告诉他最大的幸运值是多少。

Solution

首先对于任意起点与任意方向，我们可以分两个方向拆环为链，然后处理两个链上的问题。

这题有个非常非常关键的注意，就是注意到这个每个宝石的幸运值非常小啊！

然后发动一下注意力，就是如果有两个连续的质数之间的差值比10还要大那么后面的质数都完全不可能达到了！然后发现能达到的质数数量非常有限，只有30个。

然后就是愉快的 了。 数组的含义为，达到第 个质数所需要的最晚的起点。

最后直接枚举找到那个能达到的最大质数即可。

Code

void solve() {
    cin>>n; 
    for(int i=1; i<=n; i++) {
        cin>>a[i]; a[i+n]=a[i];
    }
    for(int i=1; i<=2*n; i++) b[i]=a[2*n-i+1];
    for(int i=0; i<=icnt; i++) f[i]=g[i]=0;
    for(int i=1; i<=2*n; i++) {
        for(int j=icnt; j>=0; j--) {
            //这个倒序很关键啊，类似01背包的东西，否则会污染本轮数据
            if(i-f[j]+1<=n) {
                int t=ir[j]+a[i], k=j;
                while(t>=ir[k+1]) ++k;
                f[k]=max(f[k], f[j]);
            }
            if(ir[j]<=a[i]) f[j]=i;

            if(i-g[j]+1<=n) {
                int t=ir[j]+b[i], k=j;
                while(t>=ir[k+1]) ++k;
                g[k]=max(g[k], g[j]);
            }
            if(ir[j]<=b[i]) g[j]=i;
        }
    }
    int __=0;
    for(int i=0; i<=icnt; i++) {
        if(f[i]||g[i]) __=i;
    }
    cout<<ir[__]<<'\n';
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    // solve();
    for(int i=2; i<=2000; i++) {
        if(!vis[i]) {
            if(i-ir[icnt]>10) break;
            ir[++icnt]=i;
            for(int j=i; j<=2000; j+=i) vis[j]=1;
        }
    }
    ir[0]=0; ir[icnt+1]=LLONG_MAX;
    // cout<<icnt<<' '<<ir[icnt]<<'\n';
    int T; cin>>T; while(T--) solve();
    return 0;
} //"日拱一卒，功不唐捐。"

时空碎片收集者

Description

在一个包含 个节点的单向路径上移动，每个节点有权值 。在每个节点 可执行三种操作：

1. 普通收集：获得 ，移动至 。
2. 时空回溯：获得 ，移动至 。副作用：强制令后续 个节点的权值变为 ，且效果持续期间无法再次触发“回溯”。
3. 时空跳跃：获得区间 的所有节点权值（无视减半副作用），直接移动至 。

其中走到大于 的节点视作离开。

现在从节点 出发，求离开时能得到的权值总和的最大值。

Solution

因为一直都没有认真学 ，所以这题也是没有想出来怎么写。看了大佬的代码学习了一下，感慨 的精髓其实就是状态设计。

我们定义 为，到达 且之后的 个节点需要半价处理的状态时，完成当前轮决策后的最大收益。

其实实现过程中也有很多要点，目前还不够熟练，该加训算法竞赛进阶指南动态规划篇了。

Code

void solve() {
    cin>>n>>k>>m;
    for(int i=1; i<=n; i++) {
        cin>>a[i]; pr[i]=pr[i-1]+a[i];
    }
    for(int i=0; i<=n; i++) {
        for(int j=0; j<=k; j++) f[i][j]=0;
    }
    //采用forward DP，也就是说用当前值更新后面的值
    //状态设计统一为，到达该状态且完成决策后的最大收益
    for(int i=0; i<n; i++) {
        //直接拿
        for(int j=0; j<=k; j++) {
            f[i+1][max(0LL, j-1)]=max(f[i+1][max(0LL, j-1)], f[i][j]+(j?a[i+1]/2:a[i+1]));
        }
        //回溯
        f[i+1][k]=max(f[i+1][k], f[i][0]+2*a[i+1]);
        //跳跃
        for(int j=0; j<=k; j++) {
            int pos=min(n, i+m+1);
            f[pos][max(0LL, j-m-1)]=max(f[pos][max(0LL, j-m-1)], f[i][j]+pr[pos]-pr[i]);
        }
    }
    int __=0;
    for(int i=0; i<=k; i++) {
        __=max(__, f[n][i]);
    }
    cout<<__<<'\n';
}

云遥栈｜“日拱一卒，功不唐捐。”