回分類題庫
z027: 愛玩的普遜
關鍵字: npsc 2017模擬試題

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 2 Times / 2 Users | Submit : 5 Times / 2 Users | Accepted rate : 100%
題目加入時間 : 2018-10-04 12:01

Content: 简体中文

普遜最喜歡數字了,⼀堆數字照⼀定順序接起來的「數列」當然更讓他喜歡了。但是,傳說中最美麗的數列:「對稱數列」更是普遜追求的極致!我們稱⼀個⾮空數列(項數⼤於零)< ai >ni=1為「對稱數列」,若是對於所有的k1n都滿⾜ ak = an+1k

現在普遜的好友,史冬咪,送給普遜⼀個「數列」來做為⽣⽇禮物。普遜為了表達對史冬 咪的感謝,決定把這個「數列」經過數次操作變成⼀個「對稱數列」!所有操作都必須是「加⼊」操作,也就是在數列的某個位置加⼊⼀個正整數,加⼊後,其後⽅的所有數字都會往後⾯順移。舉例來說,< 1,2,3,4 >可以經由⼀次「加⼊」操作變成< 1,2,5,3,4 >< 1,2,3,4,514 >< 1126,1,2,3,4 >,但是沒辦法變成< 1,2,4,3 >< 1,2,5,4 >< 1,2,4 >。不難發現,能夠經由數次「加⼊」操作變成的「對稱數列」其實不只⼀個,於是普遜打算讓它變成最「好」的⼀個「對稱數列」。 我們⽐較兩個數列好壞的⽅法如下:

若兩個數列的項數不⼀樣多,那麼項數⽐較⼩的數列⽐較好。
若前項⽐較無法完成⽐較,則看兩個數列的第⼀項(即a1),第⼀項⽐較⼩的數列⽐較 好。
• 若前項⽐較無法完成⽐較,則看兩個數列的第⼆項(如果存在的話),第⼆項⽐較⼩的數 列⽐較好。
• 若前項⽐較無法完成⽐較,則看兩個數列的第三項(如果存在的話),第三項⽐較⼩的數 列⽐較好。
• 以此類推⽐較下去,直到完成⽐較為⽌。(可以發現如果到結束都無法⽐較出好壞關係, 表⽰兩個數列確實相等。)

現在給你史冬咪送給普遜的數列,請你求出普遜能藉由數次「加⼊」操作可以得到最「好」 的「對稱數列」。 為了避免輸出過⼤,令計算出所求的數列為< bi >mi=1,請輸出(b1+1)(b2+2)⊕···(bi+i )⊕···(bm + m),其中⊕為位元互斥或(BitwiseXOR),即為C/C++中的運算⼦“′′

例如,範例測試資料第⼆筆,所求的數列為 < 1,2,3,2,1 >,上述需輸出的值即為 (1 + 1)(2 + 2)(3 + 3)(2 + 4)(1 + 5) = 0;另外,
範例測試資料第⼀筆中,所求的數列為 < 4,1,5,1,4 >,可以⽤同樣⽅法計算出輸出應為 2

Input:

測試資料共包含 2 ⾏。 第⼀⾏包含⼀個正整數 n,表⽰史冬咪送給普遜的數列的項數。

第⼆⾏包含 n 個正整數,依序史冬咪送給普遜的數列的第⼀項到第 n 項。

• 1  n 2000 
 1  史冬咪送給普遜的數列的每⼀項  2000

Output:

輸出⼀⾏,包含⼀個整數,即為題⽬中所要求的值。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
5 1 4

Sample Output :

2

Hint :

Author :

npsc 2017模擬試題 (管理員:Chang)

  Solve it!   Status Forum