题意：n个学生，每个学生手里有非负数个糖果，每个学生可能告诉你他有多少个糖果，也可能不告诉你，但是他一定会告诉你他及与他相邻的2个学生的糖果的数量和（端的2人，其余的3人），m个询问，每个询问问一个学生最多能拥有多少糖果（3 ≤ n ≤100000，1 ≤ m ≤100，学生编号从0开始）。
题目链接：http://acm.zju.edu.cn/changsha/showProblem.do?problemId=31
——>>今晚长沙网络赛的J题，比赛4个半小时，一直TLE与WA，又是赛后才AC。。。
师兄提供吾思路：
当n % 3 ！= 2时，所有学生拥有的糖果数是确定的；
当n % 3 == 2时，设a[n-1] = x，则
a[n-4] = x + b[n-3] - b[n-2];
a[n-7] = x + b[n-3] - b[n-2] + b[n-6] - b[n-5];
...
a[1] = x + b[n-3] - b[n-2] + b[n-6] - b[n-5] + ... + b[2] - b[3];
因为a[i] >= 0，所以相应的，有：
x >= b[n-2] - b[n-3];
x >= b[n-2] - b[n-3] + b[n-5] - b[n-6];
...
x >= b[n-2] - b[n-3] + b[n-5] - b[n-6] + ... + b[3] - b[2];
这里可以确定x的下界L。
另外，
a[n-2] = -x + b[n-1];
b[n-5] = -x + b[n-1] + b[n-4] - b[n-3];
...
b[0] = -x + b[n-1] + b[n-4] - b[n-3] + ... + b[1] - b[2];
因为a[i] >= 0，所以相应的，有：
x <= b[n-1];
x <= b[n-1] + b[n-4] - b[n-3];
...
x <= b[n-1] + b[n-4] - b[n-3] + ... + b[1] - b[2];
这里可以确定x的上界R。
对应每个查询的c，
如果a[c] != -1，当然返回它的确定值，否则，
若c % 3 == 0，则a[i] = b[n-1] + _xsum[c] - L;
若c % 3 == 1，则a[i] = R + xsum[c];
若c % 3 == 2，此时一定是确定的。
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 100000 + 10;
const int INF = 0x3f3f3f3f;int a[maxn]; //输入的a数组
int b[maxn]; //输入的和数组
int xsum[maxn]; //n % 3 == 2时将数表示成x + B时存B
int _xsum[maxn]; //n % 3 == 2时将数表示成 -x + a[n-1] + B时存B
int n; //n个数void getAll(int x, int y){ //已知[x, y]内的所有数，求得[0, n-1]整个区间所有数for(int i = x-1; i >= 0; i--){if(i) a[i] = b[i+1] - a[i+1] - a[i+2];else a[i] = b[i] - a[i+1];}for(int i = y+1; i < n; i++){if(i != n-1) a[i] = b[i-1] - a[i-1] - a[i-2];else a[i] = b[i] - a[i-1];}
}void init(){ //根据已知数推出可以确定的数a[2] = b[1] - b[0]; //顺数第3个数a[n-3] = b[n-2] - b[n-1]; //倒数第3个数for(int i = 0; i < n; i++){ //间隔为3，往右更新a[]if(a[i] != -1 && i+3 < n) a[i+3] = a[i] + b[i+2] - b[i+1];}for(int i = n-1; i >= 0; i--){ //间隔为3，往左更新a[]if(a[i] != -1 && i-3 >= 0) a[i-3] = a[i] - b[i-1] + b[i-2];}for(int i = 0; i+1 < n; i++){ //看是否已知连续的两个数if(a[i] != -1 && a[i+1] != -1){getAll(i, i+1);break;}}for(int i = 0; i+2 < n; i++){ //看是否已知两个数且其中间恰好夹一个数且该数未知if(a[i] != -1 && a[i+1] == -1 && a[i+2] != -1){a[i+1] = b[i+1] - a[i] - a[i+2];getAll(i, i+2);break;}}
}int main()
{int m, c;while(scanf("%d", &n) == 1){memset(xsum, 0x3f, sizeof(xsum));memset(_xsum, 0x3f, sizeof(_xsum));for(int i=0; i<n; i++) scanf("%d", &a[i]);for(int i=0; i<n; i++) scanf("%d", &b[i]);init();int L = 0, R = INF; //当n % 3 == 2时设a[n-1] = x, L为x的下界，R为x的上界if(n % 3 == 2){xsum[n-1] = _xsum[n-2] = 0; //最后的两个未知数的右部for(int i = n-4; i-1 >= 0; i -= 3){xsum[i] = xsum[i+3] + b[i+1] - b[i+2];L = max(L, -xsum[i]);_xsum[i-1] = _xsum[i+2] + b[i] - b[i+1];R = min(R, _xsum[i-1] + b[n-1]);}}scanf("%d", &m);while(m--){scanf("%d", &c);if(a[c] != -1) printf("%d\n", a[c]);else{if(c % 3 == 0) printf("%d\n", b[n-1] + _xsum[c] - L);else printf("%d\n", R + xsum[c]);}}}return 0;
}
