文档章节

[codeforces 618 F] Double Knapsack (抽屉原理)

o
 osc_v22siqak
发布于 2018/08/25 21:32
字数 673
阅读 9
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

题目链接:http://codeforces.com/contest/618/problem/F

题目:

题目大意:

有两个大小为 N 的可重集 A, B, 每个元素都在 1 到 N 之间. 分别找出 A 和 B 的一个子集, 使得这两个子集元素之和相等.

分别输出集合A和集合B的子集的个数以及子集中元素在原集合中的位置

N ≤ $10^6$

题解:

首先我们证明一个结论,存在一组方案,满足两个子集在A中和在B中都是连续的一段

把两个集合看成两个数组,分别计算出前缀和sa,sb

对于每个i(0<=i<=n),我们j为满足0<=sa[i]-sb[j]<=n-1的最大的j,设d[i]=sa[i]-sb[j],可以发现j的单调递增的

我们发现d数组一共有n+1个元素(包括i=0,sa[i]=0的情况),并且我们又发现d[i]的取值只有n个。那么根据抽屉原理,至少有两个d数组中的元素是相等的

于是我们有sa[i']-sb[j']=sa[i]-sb[j](i'>i)

移项之后得到sa[i']-sa[i]=sb[j']-sb[j]

这个时候我们就知道在A数组中i+1~i'这一段元素之和与B数组中j+1~j'这一段元素之和相等

证毕

其实上面的证明过程就是我们本题的做法,我们用two pointers处理出d数组,然后判断当前的d值在之前是否出现过,这个时候我们就得到了答案

值得注意的是,我们需要sa[n]<=sb[n],因为若是sa[n]>sb[n]可能出现对于i=n找不到一个j满足上述条件

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int N=1e6+15;
int n,cnt1,cnt2,st1,st2,ed1,ed2;
int sa[N],sb[N],vis[N],p[N];
inline int read()
{
    char ch=getchar();
    int s=0,f=1;
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*f;
}
void solve(int a[],int b[])
{
    memset(vis,-1,sizeof(vis));
    int j=0;
    for (int i=0;i<=n;i++)
    {
        while (a[i]-b[j]>=n) j++;
        int d=a[i]-b[j];
        if (vis[d]!=-1)
        {
            cnt1=i-vis[d];
            st1=vis[d]+1;ed1=i;
            cnt2=j-p[vis[d]];
            st2=p[vis[d]]+1;ed2=j;
            break;
        }
        vis[d]=i;p[i]=j;
    }
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++) sa[i]=sa[i-1]+read();
    for (int i=1;i<=n;i++) sb[i]=sb[i-1]+read();
    if (sa[n]<=sb[n])
    {
        solve(sa,sb);
    }
    else 
    {
        solve(sb,sa);swap(cnt1,cnt2);swap(st1,st2);swap(ed1,ed2);    
    }
    printf("%d\n",cnt1);
    for (int i=st1;i<=ed1;i++) printf("%d ",i);
    printf("\n");
    printf("%d\n",cnt2);
    for (int i=st2;i<=ed2;i++) printf("%d ",i);
    printf("\n");
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【opencv】图形的绘制

1.矩形图像的绘制: 原函数:void cvRectangle(CvArr* img, CvPoint pt1, CvPoint pt2, CvScalar color, int thickness=1, int line_type=8,int shift=0) img就是需要绘制的图像 pt1 and pt......

其实我是兔子
2014/10/08
1.2K
1
beego API开发以及自动化文档

beego API开发以及自动化文档 beego1.3版本已经在上个星期发布了,但是还是有很多人不了解如何来进行开发,也是在一步一步的测试中开发,期间QQ群里面很多人都问我如何开发,我的业余时间实在...

astaxie
2014/06/25
2.7W
22
libqt4json

libqt4jon 是一个使用 Qt QVariant 对象的 JSON 序列化和反序列化库。可系列化原生类型如 integer, double, QString, lists, maps, and QObject recursively. 只序列化通过 QObject Q_PROPER...

匿名
2013/03/29
386
0
Java™ 编译器--Janino

Janino是一个超级小但又超级快的Java™ 编译器. 它不仅能像javac工具那样讲一组源文件编译成字节码文件,还可以对一些Java表达式,代码块,类中的文本(class body)或者内存中源文件进行编译,...

匿名
2013/04/02
4.1K
0
HHPanningTableViewCell

HHPanningTableViewCell是一个UITableViewCell实现“刷卡显示”抽屉视图。这种观点通常包含应用到当前行的操作按钮。此行为被看作在数量iOS应用程序。据我所知,当时的想法是首创的罗兰Brich...

匿名
2012/10/24
441
0

没有更多内容

加载失败,请刷新页面

加载更多

大数据研发学习之路--Hadoop集群搭建

阅读编译文档 准备一个hadoop源码包,我选择的hadoop版本是:hadoop-2.7.7-src.tar.gz,在hadoop-2.7.7的源码 包的根目录下有一个文档叫做BUILDING.txt,这其中说明了编译hadoop所需要的一些...

DSJ-shitou
50分钟前
8
0
OSChina 周五乱弹 —— 特么是别的公司派来的特洛伊木马吧?

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 小小编辑推荐:《我会守在这里》- 毛不易 《我会守在这里》- 毛不易 手机党少年们想听歌,请使劲儿戳(这里) @FalconChen :股市连跪了五天,...

小小编辑
51分钟前
59
2
如何在find中排除目录。命令 - How to exclude a directory in find . command

问题: I'm trying to run a find command for all JavaScript files, but how do I exclude a specific directory? 我正在尝试为所有JavaScript文件运行find命令,但是如何排除特定目录? ......

法国红酒甜
今天
73
0
《Java8实战》笔记(02):通过行为参数传递代码

本文源码 应对不断变化的需求 通过筛选苹果阐述通过行为参数传递代码 初试牛刀:筛选绿苹果 public static List<Apple> filterGreenApples(List<Apple> inventory){List<Apple> result = ......

巨輪
今天
19
0
JeeSite 4 架构特点、安全方面、为什么好、工匠精神、不忘初心

1、底层架构 以 Spring Boot 2 为基础,Maven 多项目依赖,模块分项目,松耦合,方便模块升级、增减模块。 模块化的数据库自动升级程序,当模块升级代码需要更新数据库时,自动执行对应版本 ...

ThinkGem
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部