2013-04-14 09:29:39Morris
[NPSC][BIT] a641. B. 蚯蚓疊積木
內容 ：
還記得老蚯的那些寶物嗎？隨著蚯蚓們挖到的寶物越來越多，蚯蚓的公用倉庫越疊越高，老蚯發現自己竟愛上了疊東西。為了滿足自己疊東西的欲望，老蚯從寶物堆中找出了許多大小不一的積木，不停的疊來疊去。
然
而，在疊了七七四十九年後，單純的疊積木再也無法滿足老蚯了。為了讓疊積木變得更有趣，老蚯決定出個考題考考自己：依照某個順序每次拿起一個積木，一一決
定是否將這個積木疊到積木塔上，並使得最後積木塔上疊的積木最多。當然，為了要疊出一個穩固的積木塔，任何一個積木都只能疊在一個比他自己大的積木上。
幸運，也不幸的，因為老蚯天生對積木的直覺，這個問題在老蚯嘗試玩了三次以後就變得簡單無聊。所以老蚯決定問問自己一個更有挑戰性的問題：有哪些積木如果被規定了不准疊到積木塔上，會使得能疊到積木塔上的最多積木數量減少？
輸入說明
：
輸入檔的第一行有一個正整數T (T<=6000)，表示接下來總共有幾筆測試資料。
每組測試資料的第一行的開頭有一個正整數N (1<=N<=200000) 代表蚯蚓打算依序拿起N 個積木，同一行接著有N 個整數Si (1<=Si<=N)，代表那N 個積木的大小，所有積木的大小都是不同的。我們保證有99% 的測試資料N<=1000 。
輸出說明
：
為了輸出方便，我們先定義一個雜湊函數hash，能夠將一個長度為size 的整數序列轉換成一個整數。
int hash(int numbers[], int size){
int value = 0, i;
for(i = 0; i < size; i++){
value ^= (numbers[i] + i + 1);
}
return value;
}
對於每一筆測試資料，請輸出中間用一個空白分隔的兩個整數A,B。A 代表有幾個積木若被規定不准放到積木塔上，會使得能疊到積木塔上的最多積木數量減少。B代表將那A 個積木的索引值(依據輸入順序從1 開始編號到N) 從小排到大後雜湊的結果。
範例輸入 ：
3 6 6 5 4 3 2 1 6 1 2 4 3 5 6 6 2 3 5 4 6 1
範例輸出 ：
0 0 4 4 3 14
提示
：
出處
：
NPSC 2012 高中組決賽
(管理：xavier13540)
題目要求最長遞增子序列，而哪些剃除掉後，會使得最長遞增子序列。
意即將所有最長遞增子序列列出後，該數值出現在所有最長遞增子序列的所有相同位置。
利用 BIT 可以找到遞增序列。
if (A[i] < A[j]) dp[j] = max(dp[j], dp[i]+1);
等價在 [0, A[j]-1] 中查找最大值，利用掃描線的做法。
最後會得到 ____L____O____R____
O是該元素所在位置，L是 可以接到 O 的最大 LIS，R是從 O開始的最大 LIS。
只要 L.length+R.length+1 == all.LIS 就是在 LIS 中，
記錄該元素所在的位置，最後再掃描在位置是不是唯一。
#include <stdio.h>
#include <string.h>
#define max(x,y) ((x)>(y)?(x):(y))
void modify(int idx, int l, int val, int T[]) {
while(idx <= l) {
T[idx] = max(T[idx], val);
idx += idx&(-idx);
}
}
int query(int idx, int T[]) {
int r = 0;
while(idx) {
r = max(r, T[idx]);
idx -= idx&(-idx);
}
return r;
}
int l[200005], r[200005], bit[200005];
int A[200005], pos[200005];
int main() {
int t, n, i, x, y;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(i = n-1; i >= 0; i--) {
scanf("%d", &A[i]);
bit[i+1] = 0;
pos[i] = 0;
}
for(i = 0; i < n; i++) {
x = n-A[i]+1;
y = query(x, bit);
l[i] = y;
modify(x, n, y+1, bit);
}
int lis = query(n, bit);
for(i = 0; i <= n; i++)
bit[i] = 0;
for(i = n-1; i >= 0; i--) {
x = A[i];
y = query(x, bit);
r[i] = y;
modify(x, n, y+1, bit);
}
for(i = 0; i < n; i++) {
if(l[i]+r[i]+1 == lis) {
pos[l[i]]++;
}
}
int cnt = 0, ans = 0;
for(i = n-1; i >= 0; i--) {
if(l[i]+r[i]+1 == lis) {
if(pos[l[i]] == 1) {
//printf("%d %d +\n", n-i, cnt+1);
cnt++;
ans ^= n-i+cnt;
}
}
}
printf("%d %d\n", cnt, ans);
//printf("%d\n", lis);
}
return 0;
}
題目要求最長遞增子序列，而哪些剃除掉後，會使得最長遞增子序列。
意即將所有最長遞增子序列列出後，該數值出現在所有最長遞增子序列的所有相同位置。
利用 BIT 可以找到遞增序列。
if (A[i] < A[j]) dp[j] = max(dp[j], dp[i]+1);
等價在 [0, A[j]-1] 中查找最大值，利用掃描線的做法。
最後會得到 ____L____O____R____
O是該元素所在位置，L是 可以接到 O 的最大 LIS，R是從 O開始的最大 LIS。
只要 L.length+R.length+1 == all.LIS 就是在 LIS 中，
記錄該元素所在的位置，最後再掃描在位置是不是唯一。
#include <stdio.h>
#include <string.h>
#define max(x,y) ((x)>(y)?(x):(y))
void modify(int idx, int l, int val, int T[]) {
while(idx <= l) {
T[idx] = max(T[idx], val);
idx += idx&(-idx);
}
}
int query(int idx, int T[]) {
int r = 0;
while(idx) {
r = max(r, T[idx]);
idx -= idx&(-idx);
}
return r;
}
int l[200005], r[200005], bit[200005];
int A[200005], pos[200005];
int main() {
int t, n, i, x, y;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(i = n-1; i >= 0; i--) {
scanf("%d", &A[i]);
bit[i+1] = 0;
pos[i] = 0;
}
for(i = 0; i < n; i++) {
x = n-A[i]+1;
y = query(x, bit);
l[i] = y;
modify(x, n, y+1, bit);
}
int lis = query(n, bit);
for(i = 0; i <= n; i++)
bit[i] = 0;
for(i = n-1; i >= 0; i--) {
x = A[i];
y = query(x, bit);
r[i] = y;
modify(x, n, y+1, bit);
}
for(i = 0; i < n; i++) {
if(l[i]+r[i]+1 == lis) {
pos[l[i]]++;
}
}
int cnt = 0, ans = 0;
for(i = n-1; i >= 0; i--) {
if(l[i]+r[i]+1 == lis) {
if(pos[l[i]] == 1) {
//printf("%d %d +\n", n-i, cnt+1);
cnt++;
ans ^= n-i+cnt;
}
}
}
printf("%d %d\n", cnt, ans);
//printf("%d\n", lis);
}
return 0;
}