文档章节

【CF618F】Double Knapsack(构造)

o
 osc_kfnbvkb9
发布于 2019/03/21 22:20
字数 473
阅读 13
收藏 0

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

【CF618F】Double Knapsack(构造)

题面

洛谷 Codeforces

题解

很妙的一道题。 发现找两个数集很不爽,我们强制加强限制,我们来找两个区间,使得他们的区间和相等。 把区间和转为前缀和的形式,现在问题变成了,给定两个单增的数列$A,B$,不妨令$A_n<B_n$找到$l1,r1,l2,r2$,满足$A_{r1}-A_{l1}=B_{r2}-B_{l2}$,换一下就是$B_{l2}-A_{l1}=B_{r2}-A_{r1}$。 那么对于$A$数列的每个$i\le [0,n]$我们都一定可以在$B$数量中找到一个最小的$j$使得$0\le B_j-A_i<n$,证明就是因为每个元素都小于$n$。 那么这样子一共会产生$n+1$个差,根据鸽巢原理,必定有两个差相等,那么等价于我们构造出了一组答案。 这题最妙的地方就是在于本来限制相当宽松,我们强制加强了限制,反而能够更容易的得到解了。

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define MAX 1000100
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,a[MAX],b[MAX],fl;ll A[MAX],B[MAX];
void Output(int l1,int r1,int l2,int r2)
{
	if(fl)swap(l1,l2),swap(r1,r2);
	printf("%d\n",r1-l1);for(int i=l1+1;i<=r1;++i)printf("%d ",i);puts("");
	printf("%d\n",r2-l2);for(int i=l2+1;i<=r2;++i)printf("%d ",i);puts("");
	exit(0);
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)A[i]=A[i-1]+read();
	for(int i=1;i<=n;++i)B[i]=B[i-1]+read();
	if(A[n]>B[n])swap(A,B),fl=1;
	for(int i=0;i<n;++i)a[i]=-1;
	for(int i=0,j=0;i<=n;++i)
	{
		while(B[j]<A[i])++j;
		int d=B[j]-A[i];
		if(~a[d])Output(a[d],i,b[d],j);
		a[d]=i;b[d]=j;
	}
	puts("-1");
	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
浅入浅出Android(003):使用TextView类构造文本控件

基础: TextView是无法供编辑的。 当我们新建一个项目MyTextView时候,默认的布局(/res/layout/activity_main.xml)中已经有了一个TextView: <TextView 运行效果如下: 修改其文本内容...

樂天
2014/03/22
664
1
【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
libqt4json

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

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

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

匿名
2013/04/02
4.1K
0
理解Swift中Optional类型-有和无的哲学

原文连接:http://blog.barat.cc/ios/understanding-swift-optional/ nil的遗憾 当某个变量或表达式没有任何内容时,在Objective-C中可以使用来表示。在Objective-C中是一个「野孩子」,voi...

巴拉迪维
2015/11/19
1.8K
9

没有更多内容

加载失败,请刷新页面

加载更多

Trends期刊8月中国论文合辑

作为Cell Press细胞出版社旗下的权威综述月刊,Trends系列旨在为科学家们提供具有权威性且易于理解的科研趋势。其16本Trends期刊涵盖生命科学和化学的不同领域。 为了让大家对于Trends期刊有...

科研菌
昨天
0
0
C语言哈希表uthash的使用方法详解(附下载链接)

工科生一枚,热衷于底层技术开发,有强烈的好奇心,感兴趣内容包括单片机,嵌入式Linux,Uboot等,欢迎学习交流! 爱好跑步,打篮球,睡觉。 欢迎加我QQ1500836631(备注CSDN),一起学习交流...

osc_h7zc4umy
17分钟前
7
0
CGB2004-京淘项目Day08

1.实现图片回显 1.1准备虚拟路径 1.1.1 编辑image.properties 说明:在jt-manager中创建image.properties文件,在其中编辑关于图片配置的所有信息. 1.1.2 编辑FileServiceImpl 说明:实现虚拟路...

osc_gp8avabl
18分钟前
5
0
C++核心准则​E.28:避免基于全局状态的错误处理(例如errno)

蜀葵 E.28: Avoid error handling based on global state (e.g. errno) E.28:避免基于全局状态的错误处理(例如errno) Reason(原因) Global state is hard to manage and it is easy to for......

面向对象思考
今天
6
0
网易2020校招笔试- 大数据开发工程师(正式批)

目录 一、翻倍 方法一:暴力 方法二:递归 二、跳柱子 方法一:暴力,寻找能到达的最高柱子,方便我下次跳 方法二:动态规划dp 三、人数统计 方法:哈希表 四、积木 方法 如果你从本文中学习...

osc_8kei32r9
20分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部