[NPSC][歸併樹] a656. E. 胖胖天天天胖＠Morris' Blog

2013-04-12 17:41:01| 人氣797| 回應0 | 上一篇 | 下一篇

[NPSC][歸併樹] a656. E. 胖胖天天天胖

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

胖胖天，天天胖！

身為一個專業飲料愛好者，胖胖天經常研究飲料相關的問題並樂此不疲。現在有許多飲料在胖胖天面前排成一排，每個飲料都有其購買的成本。他想從特定區段中挑出盡量多瓶飲料，使得總成本不超過他錢包裡的錢，請問他最多可以挑幾瓶呢？

聰明的胖胖天已經先寫了一個程式來輔助他喝遍天下的飲料，但謹慎的他還是請你也寫一份來確認他寫的程式是否正確。但為了肉眼比對方便，聰明的胖胖天決定比較結果的雜湊值就好，也就是假設對每次詢問所能購買的瓶數依序為p₁, p₂, ..., p_k，則我們定義其雜湊值為(p₁ + 1)^(p₂ + 2)^...^(p_k + k)，其中^代表xor 運算。

輸入說明：

輸入檔的第一行有一個正整數T (T<=514)，表示接下來總共有幾筆測試資料。

每一筆測試資料第一行有兩個正整數N,Q (N,Q<=10⁵)，代表總共有N 瓶飲料，胖胖天將問你Q 個問題。飲料編號由左到右為1, 2, ...,N。下一行有N 個非負整數，依序代表每瓶飲料的購買成本，飲料的成本不會超過10⁴。再接下來有Q 行，每行有三個整數L,R, S (1<=L<=R<=N, 0<=S<=10⁹)，代表胖胖天想問你如果他錢包裡剛好有S 元，他最多可以買幾瓶編號在L 到R 之間的飲料呢？

輸出說明：

對於每筆測試資料，請輸出其對應的雜湊值。若對雜湊值之運算有所疑惑可以參考題目B 所附之程式碼。

範例輸入：

範例輸出：

3
6

提示：

出處：

NPSC 2012 高中組決賽 (管理：xavier13540)

题目简述：
在指定区间抓取总合不大于 S 的元素集合，而集合大小越大越好

题目分析：
对于区间[L，R]很明显地，从小排到大，依序挑入即可，照贪婪的思路。
但没办法对每个询问区间进行排序，因此使用归并树。
将合并排序的每个过程记录下来，然后二分边界数值。
小心，等价的边界数值要特别处理。

/*********************************************************/
/* Problem: a656 "E. 胖胖天天天胖" from NPSC 2012 高中組決賽*/
/* Language: CPP (3083 Bytes)                           */
/* Result: AC(3.7s, 10.8MB) judge by this@ZeroJudge    */
/* Author: morris1028 at 2013-04-12 09:00:55           */
/********************************************************/

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
short ST[20][100010];
int AST[20][100010];
void build(int dep, int l, int r) {
    if(l < r) {
        int m = (l+r)/2, i;
        memcpy(ST[dep+1]+l, ST[dep]+l, (r-l+1)*2);
        build(dep+1, l, m);
        build(dep+1, m+1, r);
        int idx1 = l, idx2 = m+1, top = l, tmp = 0;
        while(idx1 <= m && idx2 <= r) {
            if(ST[dep+1][idx1] < ST[dep+1][idx2])
                ST[dep][top] = ST[dep+1][idx1++];
            else
                ST[dep][top] = ST[dep+1][idx2++];
            tmp += ST[dep][top];
            AST[dep][top++] = tmp;
        }
        while(idx1 <= m) {
            ST[dep][top] = ST[dep+1][idx1++];
            tmp += ST[dep][top];
            AST[dep][top++] = tmp;
        }
        while(idx2 <= r) {
            ST[dep][top] = ST[dep+1][idx2++];
            tmp += ST[dep][top];
            AST[dep][top++] = tmp;
        }
    }
    if(l == r)
        AST[dep][l] = ST[dep][l];
}
int L, R, S;
int key, Count, cost, same;
void query(int dep, int l, int r, int ql, int qr) {
    if(cost > S)   return ;
    if(l == ql && r == qr) {
        int ff = upper_bound(ST[dep]+l, ST[dep]+r+1, key)-(ST[dep]+l);
        int gg = lower_bound(ST[dep]+l, ST[dep]+r+1, key)-(ST[dep]+l);
        same += ff-gg;
        if(gg) {
            Count += gg;
            cost += AST[dep][gg+l-1];
        }
        return;
    }
    int m = (l+r)/2;
    if(m >= qr)
        query(dep+1, l, m, ql, qr);
    else if(m < ql)
        query(dep+1, m+1, r, ql, qr);
    else {
        query(dep+1, l, m, ql, m);
        query(dep+1, m+1, r, m+1, qr);
    }
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int t;
    int n, q, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &q);
        for(i = 1; i <= n; i++) {
            //scanf("%d", &ST[0][i]);
            ReadInt(&j);
            ST[0][i] = j;
        }
        build(0, 1, n);
        int ans = 0;
        ST[0][0] = 0;
        for(i = 1; i <= q; i++) {
            //scanf("%d %d %d", &L, &R, &S);
            ReadInt(&L);
            ReadInt(&R);
            ReadInt(&S);
            int l = 0, r = n, m;
            int x = 0;
            while(l <= r) {
                m = (l+r)/2;
                key = ST[0][m], Count = 0, cost = 0, same = 0;
                query(0, 1, n, L, R);
                if(cost <= S) {
                    l = m+1;
                    if(key)
                        Count += min((S-cost)/key, same);
                    if(Count > x)   x = Count;
                } else
                    r = m-1;
            }
            ans ^= x+i;
        }
        printf("%d\n", ans);
    }
    return 0;
}

我要檢舉

#a656#E. 胖胖天天天胖#歸併樹

台長： Morris

您可能對以下文章有興趣

b046. E. 智慧型單字查詢

b043. B. 踩地雷回來了

b255. D. 跑跑卡丁車

b238. A. 腹黑、傲嬌

人氣(797) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:[NPSC][線段樹] a651. D. 小可魚兒向上游
此分類上一篇:[ZJ][翻轉處理] a315. D 滿州國皇帝之璽

回應(0)