学步园

题意： 有一排数，有的明示它的值，有的则隐藏（以-1表示）。现在给出他们所有相邻三个的和（头尾两个位置只包含两个数的和），有500次询问，问某个位置上的可能最大值是多少。

解法： 容易知道我们可以把从左到右数第三个数的值求出，类推我们能够知道所有位置是3的倍数的值，再类推我们能够知道所有从右往左数位置是3的倍数的值。所以当n%3!=2时，我们能够知道每三个数中的两个的值，剩下的一个可以直接求出。而当n%3==2时，我们就只能算出所有3的倍数位置的值，但是因为有的值是之前已经明示过的，因此只要有任意一个明示的值位置%3!=0，那么就有两个已知值是连续的，而我们知道连续三个数的和，因此可以推出所有的值。

还有一种情况，没有任何两个连续数已知，那么就是这样：xxoxxoxxoxx，o表示能确定的值，x表示未知数。于是我们把已知的三连续数和减去已知的数，处理成相邻两个未知数的和的形式，那么就会得到（n-n/3-1）个二元一次方程。不妨把方程写成下面这种形式：

x2 = y1 - x1

x3 = y2 - x2

x4 = y3 - x3

x5 = y4 - x4

x6 = y5 - x5

.

.

.

xn = yn - xn-1

再不妨把所有未知数x用x1替代

x2 = y1 - x1

x3 = y2 - y1 + x1

x4 = y3 - y2 + y1 - x1

x5 = y4 - y3 + y2 - y1 + x1

x6 = y5 - y4 + y3 - y2 + y1 - x1

.

.

.

xn = delta (+-) x1  >= 0

把所有方程写成如上一行所示的形式，题目的条件是不存在负数且小于10000，那么就变成关于x1的一些不等式，借此算出x1的上界和下界，从而根据每个未知数与x1的关系来求出他们的最大值，并且保证了每一个等式和不等式的合法性。

最后一步逗逼了4.5个小时，纪念一下。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 101000;
const int INF = 0x3f3f3f3f;
int n,ok,pos;
int a[MAXN];
int s[MAXN];
int min_lim,max_lim;
int delta[MAXN];
void Soul() {
    min_lim = 0;
    max_lim = 10000;
    for (int i = 3; i <= n; i += 3) {
        s[i-1] -= a[i];
        s[i] -= a[i];
        s[i+1] -= a[i];
    }
    for (int i = 2; i <= n; i ++) {
        if (i%3 == 1) {
            delta[i] = s[i-1] - delta[i-2];
            min_lim = max(min_lim, -delta[i]);
        }
        else if (i%3 == 2) {
            delta[i] = s[i] - delta[i-1];
            max_lim = min(max_lim, delta[i]);
        }
    }
    for (int i = 1; i <= n; i ++) {
        if (i%3 == 1) 
            a[i] = delta[i] + max_lim;
        else if (i%3 == 2)
            a[i] = delta[i] - min_lim;
    }
}
void work() {
    int temp = s[1];
    for (int i = 3; i <= n; i += 3) {
        a[i] = s[i-1] - temp;
        temp = s[i+1] - a[i];
    }
    temp = s[n];
    for (int i = n-2; i >= 1; i -= 3) {
        a[i] = s[i+1] - temp;
        temp = s[i-1] - a[i];
    }
    if (n%3 != 2) {
        for (int i = 1; i <= n; i ++) if (a[i] != -1) {
            s[i-1] -= a[i];
            s[i] -= a[i];
            s[i+1] -= a[i];
        }
        for (int i = 1; i <= n; i ++) if (a[i] == -1)
            a[i] = s[i];
        return ;
    }
    if (ok) {
        if (pos % 3 == 1) {
            for (int i = pos+1; i <= n; i ++) a[i] = s[i-1] - a[i-1] - a[i-2];
            for (int i = pos-1; i >= 1; i --) a[i] = s[i+1] - a[i+1] - a[i+2];
        } else {
            for (int i = pos-1; i >= 1; i --) a[i] = s[i+1] - a[i+1] - a[i+2];
            for (int i = pos+1; i <= n; i ++) a[i] = s[i-1] - a[i-1] - a[i-2];
        }
        return ;
    }
    Soul();
}
int main() {
    while (~scanf("%d", &n)) {
        memset(a, 0, sizeof(a));
        memset(s, 0, sizeof(s));
        memset(delta, 0, sizeof(delta));
        ok = 0;
        for (int i = 1; i <= n; i ++) {
            scanf("%d", &a[i]);
            if (!ok && a[i] != -1 && i%3 != 0) ok = 1, pos = i;
        }
        for (int i = 1; i <= n; i ++)
            scanf("%d", &s[i]);
        work();
        int nq;
        scanf("%d", &nq);
        while (nq --) {
            int d;
            scanf("%d", &d);
            d ++;
            printf("%d\n", a[d]);
        }
    }
    return 0;
}