a019: WC2011 2.拼点游戏
標籤 :
通過比率 : 84% (16 人 / 19 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-02-27 10:27

內容

小W 和小Y 都很喜歡玩一種“拼點遊戲”。遊戲中兩個人分別通過某種操作產生一個數作為自己的“點數”,點數大的一方獲勝。 “拼點遊戲”的規則如下:
1、遊戲開始時,給定一個包含$n$個元素的正整數序列$U=(u_1,u_2,...,u_n)$。
2、定義$U$的一個下標序列$I=(i_1,i_2,\dots,i_m)$是滿足$1 \leq i_1 < i_2 < \dots < i_m \leq n$的一個整數序列($m$可以為0,即序列可以為空),並且其對應$U$的子序列為$V=(u_{i_1},u_{i_2},\dots,u_{i_m})$。
3、定義下標序列I=(i_1,i_2,...,i_m)對應的點數D(I)為
$D(I) = \sum_{p=1}^m u_{i_p} * (-1)^p$
4、進行遊戲時兩人分別選擇一個下標序列,誰選擇的下標序列對應的點數$D(I)$大,誰就獲勝。
然而在每次遊戲中,小W 總是能準確無誤的算出點數最大的最優下標序列。
為了讓遊戲更加具有競技性,他們制定了下列額外規則:
Ex1. 小W 可以選擇一個非空區間$[l,r]$,並將$u_l,u_l+1,\dots,u_r$同時增加一個整數$c$,產生的新序列將取代原序列$U$。
Ex2. 當他們對於當前的$U$序列進行一次“拼點遊戲”時,允許小Y 在小W選出最優下標序列$I_W=(i_1,i_2,\dots,i_m)$之後,對$I_W$進行任意次修改操作。每次修改操作規則如下:
(1)任意選擇一個正整數$k$滿足$2k+1 \leq m$,以及兩個非負整數$z1, z2$滿足$i_{2k}+z_1<i_{2k+1}-z_2$;
(2)將$i_{2k}$修改為$i_{2k}+z_1$,將$i_{2k+1}$修改為$i_{2k+1}-z_2$。
若小W選出的下標序列$I_W$經過小Y 若干次修改操作之後所對應的點數小於等於0,則小Y 獲勝。
現在給出小W 所進行的Ex1 操作的信息,請你對於每一次“拼點遊戲”,幫助他們計算:
a)小W 一開始所能選出的最優下標序列對應的點數是多少?
b)小Y 最少需要進行幾次修改操作才能獲勝?即使得$D(I_W) \leq 0$。

輸入說明

輸入文件的第一行包含一個正整數$T$,表示測試數據的組數。接下來為$T$組數據。
每一組數據的第一行包含兩個整數$n$和$q$,分別表示$U$中的元素個數和事件個數。
接下來的一行,包含$n$個用一個空格隔開的正整數,第$i$個整數為初始的序列中第$i$個元素$u_i$。
接下來$q$行,每行代表一個事件(按事件發生順序輸入)。每行的第一個數非0 即1,表示這個事件的類型。
若為0 :在0 之後還有三個整數$l$,$r$和$c$(這四個數之間均有一個空格),
表示小W 將$u_l,u_l+1,\dots,u_r$增加$c$;
若為1 :表示兩人進行了一次“拼點遊戲”,你需要輸出相應的結果。
輸入數據保證序列$U$中的所有元素總是正整數。

輸出說明

輸出文件對於每一組測試數據,依次對每一次“拼點遊戲”輸出一行包含兩個由一個空格隔開的整數$D_\mathrm{max}$和$X$,其中$D_\mathrm{max}$為對於當前序列$U$,小W 所能選出的最優下標序列所對應的點數;
$X$表示小Y 最少需要進行幾次修改操作才能獲勝。如果小Y 不論多少次操作都無法獲勝,則輸出-1。
數據保證最優下標序列總是唯一的。

範例輸入
2
5 9
9 10 7 6 8
1
0 4 5 2
0 3 5 4
1
0 2 5 -2
0 3 5 -3
0 4 5 -2
0 5 5 -4
1
4 3
2 4 3 5
1
0 3 3 3
1
範例輸出
3 1
5 -1
0 0
4 -1
4 -1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 3.0s , <1K
公開 測資點#1 (10%): 3.0s , <1M
公開 測資點#2 (10%): 3.0s , <1M
公開 測資點#3 (10%): 3.0s , <1M
公開 測資點#4 (10%): 3.0s , <10M
公開 測資點#5 (10%): 3.0s , <10M
公開 測資點#6 (20%): 3.0s , <10M
公開 測資點#7 (20%): 3.0s , <10M
公開 測資點#8 (0%): 1.0s , <10M
公開 測資點#9 (0%): 1.0s , <10M
提示 :

【評分標準】(原題含有部分分,但本題現暫時採用非部分分評測)
一個測試點包含多組測試數據,對於該測試點:
如果所有的$D_\mathrm{max}$均正確但某個$X$不正確,則可以得到3 分;
如果所有的$X$均正確但某個$D_\mathrm{max}$不正確,則可以得到7 分;
如果所有回答均正確,則可以得到10 分。

【樣例說明】
輸入數據包含兩組測試數據。
在第一組測試數據中:
第一次“拼點遊戲”時,最優下標序列為(1,2,4,5),小Y 只需要進行一次修改操作:選擇$k=1$,以及非負整數$z_1=1, z_2=0$ 。這樣經過修改操作之後下標序列將變為(1,3,4,5),小Y 獲勝。
第三次“拼點遊戲”時,序列U 為(9,8,6,5,3),小W 所選擇的最優下標序列為空序列,所產生的點數為0。在這種情況下,小Y 無法進行任何修改操作(也無需進行任何修改操作),此時小Y 已經直接獲勝。

【數據規模】
對於10%的數據滿足$n, q \leq 13$;
對於30%的數據滿足$n, q \leq 1000$;
對於另外20%的數據滿足$T=1$ 且$n \leq 40000$;
對於100%的數據滿足$T \leq 3$ 且$n, q \leq 10^5$,同時初始序列$U$滿足 $0 < u_i < 2^{31}$, $\left| c \right| < 10^5$。
【時限】3s

本題題目敘述已修正。
經查,第6測資點和第7測資點有誤,已刪除並重測。
——2017/2/27

標籤:
出處:
WC2011第二题 [編輯:
liouzhou_101 (王启圣)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」