題意：一個數(shù)列，給出這個數(shù)列中的某些位置的數(shù)，給出所有相鄰的三個數(shù)字的和，數(shù)列頭和尾處給出相鄰兩個數(shù)字的和。有若干次詢問，每次問某一位置的數(shù)字的最大值。

分析：設(shè)數(shù)列為a1～an。首先通過相鄰三個數(shù)字的和我們可以求出a3,a6,a9……是多少。a3=sum(a1,a2,a3)-sum(a1,a2)。a6=sum(a4,a5,a6)-sum(a3,a4,a5)。后面依次類推。

推到了數(shù)列的最右面，如果恰好知道了an或者a(n-1)中的一個，那么可以通過sum(an,a(n-1))減去它來求得另一個。

這個題還有個性質(zhì)就是，只要知道數(shù)列中連續(xù)的兩位就可以通過不斷向兩側(cè)延伸的方法得到整個數(shù)列。因為任意相鄰三個的和都知道，知道其中兩個數(shù)自然可以得到第三個。

所以我們?nèi)绻懒俗詈髢晌粍t一定可以知道整個數(shù)列。同樣如果根據(jù)已知的數(shù)列中的數(shù)和推出的數(shù)能得知兩個已知的相鄰的數(shù)的話，也可推出整個數(shù)列。

唯一一種無法確定該數(shù)列的情況就是我們，沒有推出最后的兩個數(shù)（即n%3==2的情況），且數(shù)列中已知給出的數(shù)也沒有提供任何推出信息以外的信息。

這時我們就獲得了一個不確定的數(shù)列，將數(shù)列中的數(shù)字ai按照i%3結(jié)果的不同分成三組，得0則已知。

得1的數(shù)之間互相是同增同減的，因為他們互相之間的差是一樣的。a1-a4=sum(a1,a2,a3)-sum(a2,a3,a4)。得2的同理。所以這些同增同減的數(shù)字會同時取得最大值或最小值。

得1和得2的之間是此消彼漲的，因為他們互相之間的和是一樣的。a1+a2=sum(a1,a2) ? ?a2+a4=sum(a2,a3,a4)-a3 ? ?a4+a5=sum(a3,a4,a5)-a3 所以得1的取得最小值則得2的取得最大值，反之亦然。

在符合了這些和與差的條件之后，唯一會導(dǎo)致數(shù)列不合法的情況就是出現(xiàn)負數(shù)。我們只需要先對得1的隨意娶個值，并推出整個數(shù)列后，根據(jù)最小數(shù)值調(diào)整所有得1的取值，使最小的那個數(shù)恰好為0。

這樣就可以使得1的取最小值，即讓得2的取得最大值。

同理可以求得得1的最大值。

存儲好各種最大值之后按題目中的詢問輸出即可。計算最大值需要O(n)，每次詢問需要O(1)，共m次詢問，總復(fù)雜度為O(n + m)。

#include <cstring> #include <algorithm> #include <cstdio> using namespace std;#define MAX_NUM 100005int array[MAX_NUM], array1[MAX_NUM], array2[MAX_NUM]; int sum[MAX_NUM]; int num; int query_num; bool filled;void cal_left(int pos, int array[]) {for (int i = pos - 2; i > 0; i--)array[i] = sum[i + 1] - array[i + 1] - array[i + 2]; }void cal_right(int pos, int array[]) {for (int i = pos + 2; i <= num; i++)array[i] = sum[i - 1] - array[i - 1] - array[i - 2]; }void input() {int pos = -1;for (int i = 1; i <= num; i++){scanf("%d", &array[i]);if (i % 3 != 0 && array[i] != -1)pos = i;}for (int i = 1; i <= num; i++)scanf("%d", &sum[i]);array[0] = 0;for (int i = 3; i <= num; i += 3)array[i] = sum[i - 1] - (sum[i - 2] - array[i - 3]);if (num % 3 == 2 && pos == -1)return;filled = true;if (array[num] != -1)array[num - 1] = sum[num] - array[num];if (array[num - 1] != -1)array[num] = sum[num] - array[num - 1];if (array[num] != -1)cal_left(num, array);array[num + 1] = 0;if (pos != -1){if (array[pos - 1] != -1)pos--;cal_left(pos + 1, array);cal_right(pos, array);} }void work() {scanf("%d", &query_num);for (int i = 0; i < query_num; i++){int a;scanf("%d", &a);a++;if (filled){printf("%d\n", array[a]);continue;}if (a % 3 == 1)printf("%d\n", array1[a]);else if (a % 3 == 2)printf("%d\n", array2[a]);elseprintf("%d\n", array[a]);} }void make2() {memcpy(array2, array, sizeof(array2));array2[1] = 0;array2[2] = sum[1] - array2[1];cal_right(1, array2);array2[1] -= *min_element(array2 + 1, array2 + num + 1);array2[2] = sum[1] - array2[1];cal_right(1, array2); }void make1() {memcpy(array1, array, sizeof(array1));array1[num] = 0;array1[num - 1] = sum[num] - array1[num];cal_left(num, array1);array1[num] -= *min_element(array1 + 1, array1 + num + 1);array1[num - 1] = sum[num] - array1[num];cal_left(num, array1); }int main() {while (scanf("%d", &num) != EOF){filled = false;input();if (!filled){make2();make1();}work();}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/rainydays/p/3334641.html

總結(jié)

以上是生活随笔為你收集整理的2013 ACM/ICPC 长沙网络赛J题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。