zoj 2013长沙网络赛 Candies

本文从WordPress迁移而来, 查看全部WordPress迁移文章

目前的提交地址:http://acm.zju.edu.cn/changsha/showProblem.do?problemCode=J

思维题,乱搞题

题意:给n个非负数,下标从0到n-1标号,如果x[i]=-1表示不知道它的值是多少,否则的话,则代表它的值。下面再给出n个数组,s[i]表示x[i-1],x[i],x[i+1]的和,对于头尾两个元素,s[0] = x[0] + x[1]; s[n-1] = x[n-1] + x[n-2];

给出m个询问,每次询问第id位的那个数字,最大可能值是多少,每个询问是独立的,即只要满足当前这个询问,令其最大,而不是结合所有询问来考虑

这题看完,数据很大,时限很小,没什么思路,但是把式子列出来,就能发现这个问题的性质

1
2
3
4
5
6
7
x[0]+x[1]=s[0]
x[0]+x[1]+x[2]=s[1]
x[1]+x[2]+x[3]=s[2]
x[2]+x[3]+x[4]=s[3]
x[3]+x[4]+x[5]=s[4]
x[4]+x[5]+x[6]=s[5]
x[5]+x[6]=s[6]

把这些式子两两相减

1
2
3
4
5
6
x[2]=s[1]-s[0]
x[0]-x[4]=s[1]-s[2]
x[1]-x[4]=s[2]-s[3]
x[2]-x[5]=s[3]-s[4]
x[3]-x[6]=s[4]-s[5]
x[4]=s[5]-s[6]

所以我们知道,一开始

  1. x[2]的值是可以算出来的,x[2] = s[1]-s[0];
  2. x[n-3]的值也是可以算出来的,x[n-3] = s[n-2] - s[n-1];
  3. x[i]-x[i+3] = s[i+1]-s[i+2],如果知道了x[i]就可以知道x[i+3],知道了x[i+3]就可以知道x[i]

    由3可知

    1. 知道了x[0],可知x[4],可知x[7],x[10]…………..(或者说知道了其中的一个,其他都知道)
    2. 知道了x[1],可知x[5],可知x[8],x[11]…………..(或者说知道了其中的一个,其他都知道)
    3. 知道了x[2],可知x[6],可知x[9],x[12]…………..(或者说知道了其中的一个,其他都知道)
      所以我们把整个序列分成了3个部分,”0”系列,”1”系列,”2”系列,一个系列里面的元素知道了,整个系列的其他元素都被唯一确定。

      而x[2]是可以算出来的,所以整个”2”系列在一开始就能被唯一确定。

  4. s[0] = x[0] + x[1]; 如果x[0]知道了x[1]也能知道,x[1]知道了x[0]也能知道
  5. 结合3,4点就可知,如果知道了”0”系列里面的一个元素,那么整个”0”系列唯一确定,即x[0]被唯一确定,接着x[1]也被唯一确定,然后整个”1”系列也被唯一确定。同理,”1”可知,”0”系列也一定可知

结合以上的,我们可以对这个序列做一个初始化的填数操作

  1. 先计算出x[2],和x[n-3],然后根据序列中,已知的元素,再唯一确定其他的元素(看看已知的元素在哪个系列里面,然后就可以唯一确定它们所在的那个系列)
  2. 检查一下”0”系列是否被填满了,是的话,就可以唯一确定”1”系列。或者检查一下”1”系列是否被填满,是的话,就可以唯一确定”0”系列。这时候可以发现,要么整个序列都被唯一确定了,要么只有”2”系列被唯一确定

这个性质其实说明了一个问题,这个序列是很容易被唯一确定的

因为别忘了一开始x[n-3]是能被计算出来的,x[n-3]属于哪个系列呢?只要x[n-3]是属于”0”或”1”系列的,那仅凭x[2],x[n-3]就能唯一确定整个序列,也就是说 n % 3 != 2 的话,整个序列能被唯一确定(即使一开始全部都是-1)。就算 n % 3 == 2的话,只要序列中一些元素是一开始就给出了,那么要唯一确定整个序列也是有很高的概率的。

初始化结束后,开始查询,对于查询x[id],首先看x[id]是否被填好了,填好的话直接输出
没有确定的话,就要去查询。

其实没有被确定的话,说明x[id]一定是属于”0”或”1”系列的,并且”0”和”1”系列都为-1,这时候只需要枚举x[0],x[1]即可,枚举了x[0]就能唯一确定整个序列了。但是注意一个问题,不能二分枚举。

因为在一个系列内部,元素之间是有单调性的,即如果x[id]属于”0”系列,x[0]越大x[id]越大,但是x[0]的大小却会影响整个序列的正确性,在整个序列而言,没有单调性

对于所有查询,理论复杂度是O(m 10000 n),但是这个问题,在大多数情况下,被唯一查询,查询都是O(1)的,只有一部分情况才需要用到暴力去查询,所以跑出来的时候还是比较乐观的

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,x[N],s[N],a[N];

void init(){
x[2] = s[1] - s[0];
x[n-3] = s[n-2] - s[n-1];
for(int k = 0; k < 3; k++){
int id = -1;
for(int i = k; i < n; i += 3)
if(x[i] != -1){
id = i; break;
}
if(id == -1) continue;
for(int i = id - 3; i >= 0; i -= 3)
x[i] = x[i+3] + (s[i+1] - s[i+2]);
for(int i = id + 3; i < n; i += 3)
x[i] = x[i-3] - (s[i-2] - s[i-1]);
}
if(x[0] != -1 && x[1] != -1) return ;
if(x[0] == -1 && x[1] == -1) return ;
for(int i = 0; i < n; i += 3){
if(i+1 >= n){
x[i] = s[i] - x[i-1]; break;
}
if(x[i] == -1){
x[i] = s[i+1] - x[i+1] - x[i+2];
}
else{
x[i+1] = s[i+1] - x[i] - x[i+2];
}
}
}


bool check(int m,int id,int val){
a[0+m] = val; a[1-m] = s[0] - val;
for(int i = 3; i < n; i += 3){
if(i == n-1){
a[i] = s[i] - x[i-1];
if(a[i] < 0) return false;
continue;
}
a[i] = a[i-3] - (s[i-2] - s[i-1]);
a[i+1] = a[i-2] - (s[i-1] - s[i]);
if(a[i] < 0) return false;
if(a[i+1] < 0) return false;
if(a[i] + a[i+1] != s[i+1]-x[i+2]) return false;
}
return true;
}

int solve(int index){
int val = s[0];
while(val >= 0){ //暴力枚举x[0]或x[1]
if(check(index%3,index,val))
return a[index];
val--;
}
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0; i < n; i++)
scanf("%d",&x[i]);
for(int i = 0; i < n; i++)
scanf("%d",&s[i]);
init(); //先把原始序列中能填的数都填完
//for(int i = 0 ; i < n; i++)
// printf("%d ",x[i]);
//puts("");
int q;
scanf("%d",&q);
while(q--){
int index;
scanf("%d",&index);
if(x[index] != -1){ //已经填好的数直接输出
printf("%d\n",x[index]);
continue;
}
int res = solve(index);
printf("%d\n",res);
}
}
return 0;
}