uva 10730 - Antiarithmetic?

简介: 点击打开链接uva 10730 思路:枚举等差中项 分析: 1 给定一个n个数的序列判断是否有等差子序列 2 很明显我们如果要判断是否有等差子序列的话,只要去判断是否有长度为3的等差子序列 3 对于n

点击打开链接uva 10730


思路:枚举等差中项
分析:
1 给定一个n个数的序列判断是否有等差子序列
2 很明显我们如果要判断是否有等差子序列的话,只要去判断是否有长度为3的等差子序列
3 对于n<=10000,那么我们怎么去判断呢,由于我们要找的是是否有三个的等差序列,那么我们可以枚举每一个数作为等差中项,然后去判断
4 假设现在我们枚举num[i]作为等差中项,那么第一个数在0~i-1之间,第二个数是在i+1~n-1之间,这个时候如果单存利用for循环去找时间复杂度不能接受,那么我们想到能减少多少复杂度呢?
5 我们知道set内部利用的是红黑数,所以说set的查找是logN的比O(n)快,所以呢我们利用set来找第二个数那么这样降低了时间复杂度。

代码:

#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int const MAXN = 10010;
int n , num[MAXN];
set<int>s;

bool solve(){
    //枚举每一个数作为等差中项
    for(int i = 0 ; i < n ; i++){
        //左边
        s.erase(num[i]);
        for(int j = 0 ; j < i ; j++){
            //右边
            int value = 2*num[i]-num[j];  
            if(s.find(value) != s.end())   
              return true; 
        }
    }
    return false;
}

int main(){
    char str[10];
    while(scanf("%s" , str)){
        if(!strcmp(str , "0")) 
            break;
        sscanf(str , "%d:" , &n);
        s.clear();
        for(int i = 0 ; i < n ; i++){
            scanf("%d" , &num[i]);
            s.insert(num[i]);
        }
        printf("%s\n" , solve() ? "no" : "yes");
    }
    return 0;
}



目录
相关文章
UVa11776 - Oh Your Royal Greediness!
UVa11776 - Oh Your Royal Greediness!
50 0
UVa 10082 WERTYU
UVa 10082 WERTYU
125 0
|
算法
UVA题目分类
题目 Volume 0. Getting Started 开始10055 - Hashmat the Brave Warrior 10071 - Back to High School Physics 10300 - Ecological Premium 458 - The Decoder 494...
1563 0
uva 10273 Eat or Not to Eat?
点击打开链接uva 10273 思路: 暴力求解 分析: 1 题目要求没有吃掉的奶牛的个数已经最后一次吃掉奶牛的天数 2 没有其它的方法只能暴力,对于n头牛的n个周期求最小公倍数,然后在2个公倍数之内暴力求解 代码: #inclu...
812 0
|
机器学习/深度学习 并行计算 AI芯片
刘汝佳uva 字符串专题
第一题   palindrome 点击打开链接uva 401 题目意思:给定一个字符串判断是什么类型 分析: 1 根据输出我们知道这个字符串总共有4种类型 2 首先应该是否是“palindrome ”,判断的理由很简单直接对这个...
1131 0
|
Python 人工智能 资源调度
UVA11525
题意:给定N与K(均为正整数)可以确定第K个全排列(1..N的全排列),但N较大,现以N=sigma(Si×(K-i)!)(i=1..K)的形式,输入K以及Si,i=1..K,请输出第K个全排列 分析:逆向去想,对于一个给定的全排列可以确定它的序号K,K的表达式形式与N类似,发现从Si可以确定第K个全排列中的第i项,具体用线段树实现查找第i项即可。
605 0
UVA11437
题目: In the picture below you can see a triangle ABC. Point D, E and F divides the sides BC, CA and AB into ratio 1:2 respectively.
720 0
UVA3295
题意:给出一个a*b的网格,在网格上取不共线的三点构成三角形,求三角形总数。分析:就是一一道简单的组合数计算题目,设总结点数为n,则取三个节点的个数为C(n,3),然后减去横向、竖向、斜向的三点共线的个数即可,斜线三点共线等价于所枚举的矩形的长宽成倍数关系,即gcd不为1 代码如下: #incl...
658 0