隐藏
「bsoj5406」ZY的数列2 - 构造+数学+抽屉原理 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bsoj5406」ZY的数列2 - 构造+数学+抽屉原理

题目大意

    ZY一向热衷于出一些水题,例如“两个数列”。但是ZY却因为这道题被同学们狠狠的骂了一顿。委屈的ZY决定再出一道水题,以证明他是个菜鸡。
    ZY有一个长度为$2n$的整数数列,每一项的绝对值$\left|a_i\right|\le n$,且满足所有数的和$a_1+a_2+a_3+\cdots+a_{2n}=1$。现在ZY想知道是否能从中取出若干个数,使得它们的和等于$0$。然后,ZY就被难住了,这个问题就交给你来解决了。


题目分析

考场居然骗了$80$分,有搞头有搞头
搜索好像能拿$70$分。
输出$-1$可以拿$0$分(原因参考证明部分)。

挺不错的一道思维题,据说是从自招题改编的。
题目的每一个条件都是有用的。

考虑,若原数列存在$0$或$1$,直接输出$0$或除了$1$剩下的数即可,否则:

  1. 随便选一个数放进数组。
  2. 若当前所选数之和为$0$或$1$,找到答案。
  3. 若当前所选数之和$\lt0$,选一个正数加入数组。
  4. 若当前所选数之和$\gt1$,选一个负数加入数组。
  5. 在Hash表中查询当前所选数和是否出现过,若出现过则找到答案。
  6. 将当前所选数和加入Hash表,返回第$2$步。

时间复杂度$O(n)$。

至于证明:
若始终没有出现答案,则当前数之和$\in[-n,0)\bigcup(1,n]$。
而这样的数只有$2n-1$个,而总共有$2n$个数。
根据抽屉原理,必定有两个数相同,因此用这个方法一定能够找到答案。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=100005;

int n,posi[maxn],nega[maxn],pos_posi,pos_nega,cnt_posi,cnt_nega,sum=0,M1[maxn<<1],M2[maxn<<1];

int main() {
n=Get_Int()<<1;
for(int i=1; i<=n; i++) {
int x=Get_Int();
if(x==0) {
puts("1\n0");
return 0;
}
if(x>0)posi[++cnt_posi]=x;
else nega[++cnt_nega]=x;
}
sum+=posi[++pos_posi];
while(true) {
if(sum<0)sum+=posi[++pos_posi];
if(sum>1)sum+=nega[++pos_nega];
if(sum==0) {
printf("%d\n",pos_posi+pos_nega);
for(int i=1; i<=pos_posi; i++)printf("%d ",posi[i]);
for(int i=1; i<=pos_nega; i++)printf("%d ",nega[i]);
return 0;
}
if(sum==1) {
printf("%d\n",cnt_posi+cnt_nega-pos_posi-pos_nega);
for(int i=pos_posi+1; i<=cnt_posi; i++)printf("%d ",posi[i]);
for(int i=pos_nega+1; i<=cnt_nega; i++)printf("%d ",nega[i]);
return 0;
}
if(M1[sum+n]) {
printf("%d\n",pos_posi+pos_nega-M1[sum+n]-M2[sum+n]);
for(int i=M1[sum+n]+1; i<=pos_posi; i++)printf("%d ",posi[i]);
for(int i=M2[sum+n]+1; i<=pos_nega; i++)printf("%d ",nega[i]);
return 0;
}
M1[sum+n]=pos_posi,M2[sum+n]=pos_nega;
}
return 0;
}
姥爷们赏瓶冰阔落吧~