2015
04-14

# 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

#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;
}

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]）