首页 > 其他分享 >CF1239E 题解

CF1239E 题解

时间:2023-08-08 22:25:19浏览次数:62  
标签:25 right min int 题解 sum CF1239E --

CF1239E

给定 \(2n\) 个数,将其重排成 \(2\times n\) 的矩阵,最小化:从 \((1,1)\) 走到 \((2,n)\),只可向右下走的所有方案中,途径所有数的和的最大值。\(n\le 25,|V|\le 5\times 10^4\)。


考场上有个 \(n\le 10\) 的包,分值高达 \(40\)。注意到 \(\binom{20}{10} \approx 10^5\) 可枚举,考虑确定第一行选取元素集合 \(a\) 和第二行 \(b\) 之后,如何将其排列。

这是个典,见此。令 \(s=a_1+\sum b_i\),即在第 \(1\) 列向下走的情况,答案就是

\[s+\max_{k=1}^{n-1}\{\sum_{i=1}^k a_{i+1}-b_i\} \]

也就是对 \(a_{i+1}-b_i\) 的前缀和取 \(\max\)。我们要令这个东西最小,那显然是 \(a\) 从小到大排,\(b\) 从大到小排。看大样例就盯出来了。

官方题解给的是这个图。\(a_{i+1}-b_i\) 是单调递增的。那么答案就是

\[\max\left(a_{\min}+\sum b_i,b_{\min}+\sum a_i\right) \]

回到原问题,将给出的长为 \(2n\) 的数组 \(r\) 排序,现在要把它划分成 \(a\) 和 \(b\) 并最小化上式。

首先不妨 \(a_{\min}\le b_{\min}\)。那么有结论,\(a_{\min}=r_1,b_{\min}=r_2\)。证明就是把它们替换成 \(r_k(k\ge 3)\) 然后发现答案更劣。

注意到

\[\left(a_{\min}+\sum b_i\right)+\left(b_{\min}+\sum a_i\right)=S=r_1+r_2+\sum r_i \]

为定值,让两者尽量靠近 \(\frac S2\) 即可。也就是

\[\sum_{i=2}^n a_i\sim \lceil \left(r_1+r_2+\sum r_i\right)\div 2\rceil-r_1-r_2 \]

变成背包问题:在 \(r_{3,\cdots,2n}\) 中选出 \(n-1\) 个数,使其加和尽量靠近上述值 \(v\),并记录方案。


令 \(f_{i,s,c}:\) 考虑到 \(r_i\),加和为 \(s\),选中了 \(c\) 个数,是否可行。朴素转移的时空均为 \(\Theta(n^3|V|)\)(这里的 \(s\) 是 \(\Theta(n|V|)\) 级别的)。

for(int i=3;i<=(n<<1);++i) for(int s=W-1;s>=a[i];--s) for(int c=n-1;c;--c)
    if(f[s-a[i]][c-1]) f[s][c]=1,l[s][c]=i,nxt[i][s][c]=l[s-a[i]][c-1];//f运用了滚动数组,l和nxt记录方案

考虑优化空间(记录方案)。一眼滚动数组,把 \(i\) 那一维扔了。但是有问题,对于一对 \((s,c)\),满足 \(f_{i,s,c}=1\) 的 \(i\) 不止一个,直接滚动数组会导致永远记录最后一个 \(i\),0/1 背包变成完全背包。

所以只在 \(f_{i,s,c}\) 第一次变成 \(1\) 的时候记录方案:

for(int i=3;i<=(n<<1);++i) for(int s=W-1;s>=a[i];--s) for(int c=n-1;c;--c)
	if(!f[s][c]) if(f[s-a[i]][c-1]) f[s][c]=1,l[s][c]=i,nxt[s][c]=l[s-a[i]][c-1];

空间复杂度 \(O(n^2|V|)\)。调整一下,从记录下标变成记录值:

for(int i=3;i<=(n<<1);++i) for(int s=W-1;s>=a[i];--s) for(int c=n-1;c;--c)
	if(!f[s][c]) if(f[s-a[i]][c-1]) f[s][c]=1,l[s][c]=a[i];

再考虑优化时间。调整下标顺序,然后注意到 \(f_{i,c}\) 是一个 0/1 数组,可以拿 bitset 搞。错位或通过左移实现。求新增的位就是异或一下。时间变成 \(O(\frac{n^3|V|}w)\),且这个 \(w\) 比 \(n\) 还大。

bitset<W> f[25],tf;
for(int i=3;i<=(n<<1);++i) for(int c=n-1;c;--c){
	tf=f[c];f[c]|=(f[c-1]<<a[i]);tf^=f[c];
	for(int x=tf._Find_first();x!=W;x=tf._Find_next(x)) l[x][c]=a[i];
}

完整代码:

#include <cstdio>
#include <bitset>
#include <algorithm>
 
using namespace std;
 
const int W=50000*25+5;
 
int a[55],l[W][25],t[W>>4],stk[55],tp;
 
bitset<W> f[25],tf;
 
int main()
{
    int n,s=0;scanf("%d",&n);
    for(int i=1;i<=(n<<1);++i) scanf("%d",a+i),s+=a[i],++t[a[i]];
    sort(a+1,a+(n<<1)+1);int am=a[1],bm=a[2];--t[am];--t[bm];
    s=((s+am+bm+1)>>1)-am-bm;f[0][0]=1;
    for(int i=3;i<=(n<<1);++i) for(int c=n-1;c;--c){
        tf=f[c];f[c]|=(f[c-1]<<a[i]);tf^=f[c];
        for(int x=tf._Find_first();x!=W;x=tf._Find_next(x)) l[x][c]=a[i];
    }
    for(int d=0;;++d) if(f[n-1][s-d]||f[n-1][s+d]){
        int x,su,c=n-1;
        f[c][s-d]?(x=l[s-d][c],su=s-d):(x=l[s+d][c],su=s+d);
        while(c) stk[++tp]=x,--t[x],x=l[su-=x][--c];
        break;
    }
    printf("%d ",am);while(tp) printf("%d ",stk[tp--]);
    puts("");for(int i=50000;~i;--i) while(t[i]--) printf("%d ",i);
    printf("%d",bm);
}

标签:25,right,min,int,题解,sum,CF1239E,--
From: https://www.cnblogs.com/vanspace/p/CF1239E.html

相关文章

  • 2023年 8月7日普及组南外集训题解
    A国家集训队题解注意数据已经是有序的,我还搞了个排序,我是智障所以只需要将第5个人到第16个人的成绩都预设成300,再把前4个人的成绩都预设成0,再看有没有人能超过第4个人就行了ac代码#include<iostream>usingnamespacestd;constintN=20;inta[N],ans=4;intmain(......
  • 2023年百度之星程序设计竞赛初赛1题解
    每次出题都出其不意---->群友蓝桥国三ac一道题根据官方的视频题解整理依据难度的划分第五题:促销糖果 分析:从答案出发想吃K个糖果,必定有k个糖纸,考虑换购,则有一张糖纸是不可以换的(因为你必须至少要买一颗糖果)则换购的数量为(k-1)/减去换购的糖果则是买的糖果packageLi2209;i......
  • CodeForces CF1846G 题解
    CodeForcesCF1846G题解CodeForces题目链接洛谷题目链接标准答案是状压之后,转化成Dijkstra算法跑最短路。我这里提供一个不一样的思路。题意简述主人公得了病,有部分类型的症状。所有类型症状共有\(n\)种,用长为\(n\)的01串表示是否有那种症状。共有\(m\)种药,吃......
  • 【BZOJ 3364】Distance Queries 距离咨询 题解
    原题简化题意:有一棵\(n\)个点的树,\(q\)组询问,每次询问回答两点间的距离。令\(dis[i][j]\)表示\(i\)到\(j\)的距离,根节点为\(rt\),则有\(dis[i][j]=dis[rt][i]+dis[rt][j]-2×dis[rt][lca(i,j)]\),按照题意打即可。#include<bits/stdc++.h>usingnamespacestd;#d......
  • Edge Drop传输缓慢的问题解决
    首先在移动端上传一张图片1.图片上传失败上传失败就没得救,网络真的不好,或者微软的服务器暂时被迫挂了。2.图片上传成功网页就会弹出消息......
  • RTSP流媒体服务器LntonNVR(源码版)视频平台通过级联到上级云服务器但视频无法播放的问题
    在经过多次的测试后,官方发布的版本可以正常级联。在实际使用过程中,有用户反馈LntonNVR通过国标GB28181协议级联到上级云服务器平台后,出现了上级平台无法播放的问题,需要我们技术人员协助进行排查。从上图我们可以看出,用户的云服务器平台显示是正常的,但是实际点击播放却存在一些问题......
  • 国标GB28181视频平台LntonGBS(源码版)国标平台大量通道接入后,创建角色接口不响应的问题
    国标GB28181协议视频平台LntonGBS是基于国标GB28181协议的视频云服务平台,支持多路设备同时接入,并对多平台、多终端分发出RTSP、RTMP、FLV、HLS、WebRTC等格式的视频流。平台可提供视频监控直播、云端录像、云存储、检索回放、智能告警、语音对讲、平台级联等功能,在视频能力上,GB2818......
  • 国标GB28181视频平台LntonGBS(源码版)国标视频平台内存错误导致崩溃的问题解决方案
    LntonGBS国标视频云服务通过支持国标GB28181协议,实现了设备接入、实时监控直播、录像、语音对讲、云存储、告警、级联等功能。同时,它还支持将接入的视频流以多种格式(包括RTSP、RTMP、FLV、HLS、WebRTC)进行全终端、全平台分发,实现了无插件播放在Web浏览器、手机浏览器、微信端、PC客......
  • Make Equal 题解
    MakeEqual题目大意给出\(n\)个数字\(a_1,a_2,a_3,......,a_n\),每次操作可以给其中一个数加上\(2\)的非负整数次幂。求最少的操作次数,使得这\(n\)个数相等。思路模拟赛看到这道题然后直接打的暴力拿了40分。暴力思路就是你需要找到一个大于等于\(a_{max}\)的\(m\)......
  • 「JSOI2008」最小生成树计数 题解报告
    简要题意现在给出了一个简单无向加权图。你希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。输出方案数对\(31011\)取模。SOLUTION这个题求最小生成树的方案所以我们从最小生成树入手(根据kruskal的思路)我们......