[构造] Codeforces 618F Wunder Fund Round 2016 F. Double Knapsack_给你两个可重集 a, ba,b,a, ba,b 的元素个数都为 nn-程序员宅基地

技术标签：构造

给定两个大小为n的可重集A, B ，两个数集中的元素均为[1, n]的整数。
现在要求在两个数集中各找出一个非空子集(子集也为可重集) ，满足两个集合中元素的和相等。
n<=10^6

加限制使得选的为两个连续的段。
不妨设SA<=SB，记SA的前缀和为SA(0),SA(1),SA(2),…, SB的前缀和为SB(0),SB(1),SB(2),…
对于每个SA(i)，找到最大的SB(j)满足SA(i)>=SB(j)，这样可以得到n+1个SA(i)-SB(j)，然而每个都是在0到n-1之间。
所以至少有两个是一样的。
于是SA(i)-SB(j)=SA(p)-SB(q)，即SA(i)-SA(p)=SB(j)-SB(q)。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> abcd;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

const int N=1000005;

int n,a[N],b[N];
ll sa[N],sb[N];
int match[N];
int pos[N];

inline void print(int l,int r){
  if (l>r) swap(l,r);
  printf("%d\n",r-l);
  for (int i=l+1;i<=r;i++)
    printf("%d ",i);
  printf("\n");
}

int main(){
  int flag=0;
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  read(n);
  for (int i=1;i<=n;i++) read(a[i]),sa[i]=sa[i-1]+a[i];
  for (int i=1;i<=n;i++) read(b[i]),sb[i]=sb[i-1]+b[i];
  if (sa[n]>sb[n]){
    flag=1;
    for (int i=1;i<=n;i++) swap(a[i],b[i]),swap(sa[i],sb[i]);
  }
  sort(sb,sb+n+1);
  for (int i=0;i<n;i++) pos[i]=-1;
  for (int i=0;i<=n;i++){
    int it=upper_bound(sb,sb+n+1,sa[i])-sb-1;
    match[i]=it;
    if (~pos[sa[i]-sb[it]]){
      int t=pos[sa[i]-sb[it]];
      if (!flag)
    print(t,i),print(match[t],match[i]);
      else
    print(match[t],match[i]),print(t,i);    
      return 0;
    }
    else
      pos[sa[i]-sb[it]]=i;
  }
  return 0;
}

本文链接：https://blog.csdn.net/u014609452/article/details/69642208

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

css限制文字行数且超出部分显示省略号_前端文本文字行数限制-程序员宅基地

文章浏览阅读2.8k次。实现方法：display: -webkit-box;-webkit-box-orient: vertical;-webkit-line-clamp: 3;overflow: hidden;适用范围：因使用了WebKit的CSS扩展属性，该方法适用于WebKit浏览器及移动端；注：-webkit-line-clamp用来限制在一个块元素显示的文本的行数。为了实现该效果..._前端文本文字行数限制

【STM32学习笔记】I2C 读写 EEPROM 实验_i2c_mode_i2c-程序员宅基地

文章浏览阅读2k次，点赞5次，收藏24次。【STM32学习笔记】目录I2C 初始化结构体详解 /* I2C 初始化结构体 */ typedef struct { uint32_t I2C_ClockSpeed; // 设置SCL 时钟频率，此值要低于400000 uint16_t I2C_Mode; // 指定工作模式，可选 I2C 模式及 SMBUS 模式 uint16_t I2C_DutyCycle; // 指定时钟占空比，可选 low/high = 2_i2c_mode_i2c

react-native报错解决方法 in next release empty section headers will be rendered_rn in this release you can use 'enableemptysection-程序员宅基地

文章浏览阅读1.6k次。错误截图解决方法在ListView下加个 enableEmptySections = {true} 就可以解决了_rn in this release you can use 'enableemptysections' flag to render empty se

html 字体大小em,px，em，rem该选择哪个？css相对字体大小的详细介绍-程序员宅基地

文章浏览阅读474次。网页设计中最大的混淆之一是由font-size属性引起的。最常用的字体大小是像素(px)，em和rem。首先，我们将重点关注字体大小属性。在CSS中，可以使用多个单元(例如像素，em和rem)，这通常会导致设计人员额外头痛。在本文中，我们将详细介绍这些单位的用法和任何误解。PX单位最常见和最受欢迎的单位是像素(px)。大多数人开始使用像素(px)单元，因为它使您可以完全控制文本大小。如果未指定字体..._字号 em

PYTHON RSA 使用私钥加密公钥解密独家解决方案_typeerror: this is not a private key-程序员宅基地

文章浏览阅读4.6k次，点赞3次，收藏15次。PYTHON解决RSA私钥加密公钥解密的方法。_typeerror: this is not a private key

Qt实现一个简单的编译器（软件生成器）_qt能直接生成程序吗-程序员宅基地

文章浏览阅读2.1k次。Qt实现一个简单的编译器（软件生成器）本文章只记录如何用Qt实现一个简单编译器，即点击本软件中的按钮便可在另一目录中生成一个新的软件（与本软件不冲突）。文章目录Qt实现一个简单的编译器（软件生成器）前言一、命令行执行Qt程序1.使用Qt for Desktop MinGW 7.3.0 64-bit1.先指定项目目录2.生成makefile文件3.编译程序4.为生成的exe文件生成所依赖的dll5.双击.exe文件，验证结果2.直接使用CMD执行程序1.将刚才找到的qtenv2.bat复制到目录下_qt能直接生成程序吗

随便推点

安装完python找不到应用程序错误,找不到uwsgi错误python应用程序-程序员宅基地

文章浏览阅读632次。I've configured my nginx server with uwsgi and python and when I try to run my python application by hitting the url in my browser, the browser returns the message, uwsgi error python application not ..._pid: 82711|app: -1|req: -1/1] 113.87.83.237 () {38 vars in 697 bytes} [tue d

泛函_9 。′,≥′1′粥輦∫, 年, 凸∫i、 ”∴,, ,,}11y,′′-程序员宅基地

文章浏览阅读238次。最速降线由能量守恒得mgy=12mv2mgy=\frac{1}{2}mv^2mgy=21mv2，即v=2gyv=\sqrt{2gy}v=2gy 设点A到点P的弧长为s，则dsdt=v\frac{ds}{dt}=vdtds=v，因此：dt=ds2gy=12gy[1+y′2]dxdt=\frac{ds}{\sqrt{2gy}}=\sqrt{\frac{1}{2gy}[1+{y}'^2]}dxdt=2gyds=2gy1[1+y′2]dx其中y′=dydxy'=\frac{dy}{dx}y_9 。′,≥′1′粥輦∫, 年, 凸∫i、 ”∴,, ,,}11y,′′

html 使用 js 脚本调用$(document).ready(function()报错 Uncaught ReferenceError: $ is not defined_$(document).ready(function() is not defined-程序员宅基地

文章浏览阅读3k次，点赞2次，收藏3次。添加的脚本使用了jquery语法，需要引用jquery调用在线的jquery<script src="http://code.jquery.com/jquery-latest.js"></script>_$(document).ready(function() is not defined