題目 2271:
藍(lán)橋杯2016年第七屆真題-壓縮變換
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 589 解決: 75
題目描述
小明最近在研究壓縮算法。
他知道,壓縮的時(shí)候如果能夠使得數(shù)值很小,就能通過(guò)熵編碼得到較高的壓縮比。
然而,要使數(shù)值很小是一個(gè)挑戰(zhàn)。
最近,小明需要壓縮一些正整數(shù)的序列,這些序列的特點(diǎn)是,后面出現(xiàn)的數(shù)字很大可能是剛出現(xiàn)過(guò)不久的數(shù)字。對(duì)于這種特殊的序列,小明準(zhǔn)備對(duì)序列做一個(gè)變換來(lái)減小數(shù)字的值。
變換的過(guò)程如下:
從左到右枚舉序列,每枚舉到一個(gè)數(shù)字,如果這個(gè)數(shù)字沒有出現(xiàn)過(guò),剛將數(shù)字變換成它的相反數(shù),如果數(shù)字出現(xiàn)過(guò),則看它在原序列中最后的一次出現(xiàn)后面(且在當(dāng)前數(shù)前面)出現(xiàn)了幾種數(shù)字,用這個(gè)種類數(shù)替換原來(lái)的數(shù)字。
比如,序列(a1, a2, a3, a4, a5)=(1, 2, 2, 1, 2)在變換過(guò)程為:
a1: 1未出現(xiàn)過(guò),所以a1變?yōu)?1;
a2: 2未出現(xiàn)過(guò),所以a2變?yōu)?2;
a3: 2出現(xiàn)過(guò),最后一次為原序列的a2,在a2后、a3前有0種數(shù)字,所以a3變?yōu)?;
a4: 1出現(xiàn)過(guò),最后一次為原序列的a1,在a1后、a4前有1種數(shù)字,所以a4變?yōu)?;
a5: 2出現(xiàn)過(guò),最后一次為原序列的a3,在a3后、a5前有1種數(shù)字,所以a5變?yōu)?。
現(xiàn)在,給出原序列,請(qǐng)問(wèn),按這種變換規(guī)則變換后的序列是什么。
輸入格式
輸入第一行包含一個(gè)整數(shù)n,表示序列的長(zhǎng)度。
第二行包含n個(gè)正整數(shù),表示輸入序列。
對(duì)于30%的數(shù)據(jù),n<=1000;
對(duì)于50%的數(shù)據(jù),n<=30000;
對(duì)于100%的數(shù)據(jù),1 <=n<=100000,1<=ai<=10^9
輸出格式
輸出一行,包含n個(gè)數(shù),表示變換后的序列。
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程,包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程,提供視頻講解以及配套習(xí)題,還有老師答疑,
點(diǎn)擊這里了解課程詳情
標(biāo)簽