首页 > ACM题库 > HDU-杭电 > HDU 4000-Fruit Ninja-树状数组-[解题报告]HOJ
2015
04-14

HDU 4000-Fruit Ninja-树状数组-[解题报告]HOJ

Fruit Ninja

问题描述 :

Recently, dobby is addicted in the Fruit Ninja. As you know, dobby is a free elf, so unlike other elves, he could do whatever he wants.But the hands of the elves are somehow strange, so when he cuts the fruit, he can only make specific move of his hands. Moreover, he can only start his hand in point A, and then move to point B,then move to point C,and he must make sure that point A is the lowest, point B is the highest, and point C is in the middle. Another elf, Kreacher, is not interested in cutting fruits, but he is very interested in numbers.Now, he wonders, give you a permutation of 1 to N, how many triples that makes such a relationship can you find ? That is , how many (x,y,z) can you find such that x < z < y ?

输入:

The first line contains a positive integer T(T <= 10), indicates the number of test cases.For each test case, the first line of input is a positive integer N(N <= 100,000), and the second line is a permutation of 1 to N.

输出:

The first line contains a positive integer T(T <= 10), indicates the number of test cases.For each test case, the first line of input is a positive integer N(N <= 100,000), and the second line is a permutation of 1 to N.

样例输入:

2
6
1 3 2 6 5 4
5 
3 5 2 4 1

样例输出:

Case #1: 10
Case #2: 1

 http://acm.hdu.edu.cn/showproblem.php?pid=4000

题意:对1–n的一个排列,求所有的i<j<k且a[i]<a[k]<a[j]的个数。。。

 

分析:比赛的时候总是想不出来怎么做,老想着单纯枚举i或者j或者k来求得结果,不知道变通。。。实际上可以换个方向思考,对每个位置考虑后面有多少比他大的数,则这个小的后面跟两个大的个数为x(x-1)/2,然后肯定要减去后面的所有组成的i<j<k且a[i]<a[j]<a[k]的个数,这两种操作都可以解决,则问题就转化为扫描一遍数组而已了。。。

 

代码:

#include <stdio.h>
#include <iostream>
using namespace std;

const int N=100001;
int a, n, f[N];
__int64 ans, tmp, tmp1;

void insert(int i)
{
	for(; i<=n; i+=i&(-i))
		f[i] += 1;
}
int query(int i)
{
	int tmp=0;
	for(; i>0; i-=i&(-i))
		tmp += f[i];
	return tmp;
}

int main()
{
	int i, cas, cas1=1;
	scanf("%d", &cas);
	while(cas--)
	{
		scanf("%d", &n);
		ans = 0;
		for(i=1; i<=n; i++)
			f[i] = 0;
		for(i=1; i<=n; i++)
		{
			scanf("%d", &a);
			insert(a);
			tmp = query(a-1);
			tmp1 = (n-a)-(i-1-tmp);
			ans -= tmp*tmp1;
			if(tmp1>=2)
				ans += tmp1*(tmp1-1)/2;
		}
		printf("Case #%d: %I64d\n", cas1++, ans%100000007);
	}

	return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ggggiqnypgjg/article/details/6753644


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  4. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])