HDu 4455 Substrings(カウント)
1778 ワード
タイトルリンク:hdu 4455 Substrings
nを与えて、それからn個の数a[1]~a[n]で、それからq回の問い合わせで、毎回wを与えて、数列a[i]をいくつかの連続的で要素数wの集合に分けて、各集合の中で現れた数字の種類を計算して、総和を出力します.
解題構想:最初は遍歴したアルゴリズムを思い浮かべ、集合要素をwとして保持し、毎回先頭を削除し、1つを加え、集合を移動し、数字の種類を維持する.このアルゴリズムの複雑さはo(n^2)であるが、タイムアウトし、その後、問題解を見て、dp[i]=dp[i-1]+sum[i]-cnt;
http://blog.csdn.net/gotoac/article/details/8188437
nを与えて、それからn個の数a[1]~a[n]で、それからq回の問い合わせで、毎回wを与えて、数列a[i]をいくつかの連続的で要素数wの集合に分けて、各集合の中で現れた数字の種類を計算して、総和を出力します.
解題構想:最初は遍歴したアルゴリズムを思い浮かべ、集合要素をwとして保持し、毎回先頭を削除し、1つを加え、集合を移動し、数字の種類を維持する.このアルゴリズムの複雑さはo(n^2)であるが、タイムアウトし、その後、問題解を見て、dp[i]=dp[i-1]+sum[i]-cnt;
http://blog.csdn.net/gotoac/article/details/8188437
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 1000005;
int n, vis[N], a[N];
__int64 sum[N], cnt, dp[N];
void init() {
memset(vis, -1, sizeof(vis));
memset(sum, 0, sizeof(sum));
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
sum[i - vis[a[i]]]++;
vis[a[i]] = i;
}
for (int i = n - 1; i >= 0; i--)
sum[i] += sum[i + 1];
}
void solve() {
memset(dp, 0, sizeof(dp));
dp[1] = n;
memset(vis, 0, sizeof(vis));
vis[a[n - 1]] = cnt = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] - cnt + sum[i];
vis[a[n - i]]++;
if (vis[a[n - i]] == 1) cnt++;
}
}
int main () {
while (scanf("%d", &n), n) {
init();
solve();
int q, w;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
scanf("%d", &w);
printf("%I64d
", dp[w]);
}
}
return 0;
}