HDU 4455 – Substrings [计数+递推]

Link

点击打开hdu题目链接

Mean

给定一个长为n的数组,数组中的数大于0小于10^6。询问q次,询问长度为w的子数组(连续的)的权值和,子数组的权值为其数组中的不同元素的个数.

Analyse

计数+递推的好题,这道题很容易往线段树或者树状数组方面想,但都会超时。正解是预处理一下然后递推。关键是能想到很多条件可以通过预处理得到,另外要注意内存使用,尽量少开数组,不要超内存,同时要注意可能会爆int。具体解法可以参考http://blog.csdn.net/gotoac/article/details/8188437

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1024000;
int n, v[maxn], t[maxn];
ll sum[maxn], dp[maxn];

void init() {
    for(int i = 0; i < n; ++i)
        scanf("%d", v + i);
    memset(t, -1, sizeof(t));
    memset(sum, 0, sizeof(sum));
    for(int i = 0; i < n; ++i) {
        ++sum[i-t[v[i]]];
        t[v[i]] = i;
    }
    for(int i = n; i >= 0; --i)
        sum[i] += sum[i+1];
}

void solve() {
    dp[1] = n;
    memset(t, false, sizeof(t));
    t[v[n-1]] = true;
    int suf = 1;
    for(int i = 2; i <= n; ++i) {
        dp[i] = dp[i-1] - suf + sum[i];
        if(!t[v[n-i]]) ++suf;
        t[v[n-i]] = true;
    }
}

void query() {
    int q; scanf("%d", &q);
    while(q--) {
        int x; scanf("%d", &x);
        printf("%lld\n", dp[x]);
    }
}

int main() {
    while(scanf("%d", &n), n) {
        init();
        solve();
        query();
    }
    return 0;
}

欢迎留言