codeforces 27 C. Unordered Subsequence
http://codeforces.com/contest/27/problem/C 题意：给出一个序列，问是否存在一个disordered的子序列。。输出长度并输出组成子序列的下表（1..n）。如果有多组，输出任意一组。 disordered的意思是。。升序或者降序（不严格也可以)之外的情况。 思路： 首先我们可以知道，我们要找的子序列至少需要三个点。因为两个点怎么看都是有序的。而如果有k个点（k>3）组成的子序列存在。。那么机智得去掉其中一些点，可以只剩三个 ，同样满足题意。所以我们只需要找到三个点即可。如果把点以下标为横坐标，值为纵坐标花在坐标系上，就是找一个v型或者倒v型的三个点。
第二，我们可以将找三个点的问题转化成用第一个点+找两个点的问题。我们可以证明，如果解存在，那么包含第一个点的解也一定存在。我们可以用反证法证明，如果我们选了第1个点，然后从第2个点到第n个点。。我们找不到两个点与第一个点构成一个v型，那么整个序列一定是升序或者降序，无解，与前提矛盾。
**需要注意的，判断方向的时候我用了乘，可能会爆int,记得用long long **
/* ***********************************************
Author :111qqz
Created Time :2015年12月29日 星期二 19时36分55秒
File Name :code/cf/problem/27C.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7LL a[N];
8int n;
9int main()
10{
11 #ifndef ONLINE_JUDGE
12// freopen("code/in.txt","r",stdin);
13 #endif
14 cin>>n;
15 for ( int i = 1 ; i <= n ; i++) cin>>a[i];
1 bool ok = true;
2 for ( int i = 2 ; i <= n-1 ;i++)
3 {
4 if ((a[i]-a[1])*(a[i+1]-a[i])<0) //注意long long
5 {
6 ok = false;
7 printf("3\n1 %d %d\n",i,i+1);
8 break;
9 }
10 }
11 if (ok)
12 {
13 puts("0");
14 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}