acm题目求算法知道XXX has an array of length n.XXX wants to know tha

来源：学生作业帮编辑：神马作文网作业帮分类：英语作业时间：2024/09/22 18:31:24

acm题目求算法知道
XXX has an array of length n.XXX wants to know that,for a given w,what is the sum of the distinct elements’ number in all substrings of length w.For example,the array is { 1 1 2 3 4 4 5 } When w = 3,there are five substrings of length 3.They are (1,1,2),(1,2,3),(2,3,4),(3,4,4),(4,4,5)
The distinct elements’ number of those five substrings are 2,3,3,2,2.
So the sum of the distinct elements’ number should be 2+3+3+2+2 = 12.
Input
There are several test cases.
Each test case starts with a positive integer n,the array length.The next line consists of n integers a1,a2…an,representing the elements of the array.
Then there is a line with an integer Q,the number of queries.At last Q lines follow,each contains one integer w,the substring length of query.The input data ends with EOF For all cases,0

这题不容易想到,一看题目,看到这数据范围,看到查询的方式.一直在往树状数组或者线段树方面去想.
想到了用DP解决就不难了.
用DP的思路O(n)复杂度解决.
以样例为例说明：
1 1 2 3 4 4 5；
明显dp[1]=n=7;
长度为1的时候有7个区间.从长度为1到长度为2,就是把前6个区间往后增加一个数,把最后一个区间去掉.
增加的6个数要看在该区间是否出现过,只要看它上一个相等的元素距离是否大于2（这里有四个大于2,而1个小于,就是1,1）
所以dp[2]=dp[1]-1+4;

以此类推就可以得出所以的dp值了.
dp[i]=dp[i-1]-A+B;
减的A是最后一个长度为i-1的区间的不同数的个数,这个很容易预处理得出来.
加的B是第t个数到它上一个数的距离大于i-1的个数.
这个B值也容易得出.
用s[i]表示离上一个数的距离为i的个数,不断减掉就得到B了.
你可以追问,我把代码贴出来
再问：贴一下，你确定能过？
再答： const int MAXN=1000010; int a[MAXN]; int f[MAXN]; int s[MAXN]; long long dp[MAXN]; int ss[MAXN]; int main() { int n; int m; while(scanf("%d",&n)==1 && n) { memset(f,0,sizeof(f)); memset(s,0,sizeof(s)); for(int i=1;i

1.he wants to have()word with you i know,()word has come tha XXX has promised to bring to justice the killers of …… = xxx, xxx 跪求英语强人翻译 This certifies that XXX has been named to the Dean' 题目《第一次xxx》作文英语翻译According to our records,xxx has been maintaining accoun 老师让写作文,题目《我爱xxx》,求题目! 求四字词语：xxx月xxx前xxx床xxx明xxx光求四字词语：xxx举xxx头xxx望xxx明xxx月 The number of people who XXX going to vote XXX more than 400 XXX除18等于360,求XXX