洛谷比赛 U4858 sum

U4858 sum

题目提供者666sb666

最新讨论

题目背景

定义一个序列的价值为序列中相邻元素差的绝对值之和。

如序列{2,1,3}的价值为|2-1|+|1-3|=3，而序列{4}的价值为0。

题目描述

现对于一给定序列，求价值最大的子序列的数量。

保证原序列中相邻的两个数不同。

注意：子序列不用连续

输入输出格式

输入格式：

第一行一个正整数n，表示序列中元素的个数。

接下来n行，每行一个数表示序列中的一个元素。

输出格式：

一个数表示数量。答案对1000000007取模。

输入输出样例

输入样例#1：

3

1

2

3

输出样例#1：

2

说明

样例解释：

40%：n<=1000

100%：n<=100000

数组中的元素的范围在int内

/*

恩想到正解了.

恩想的太多+码力太差.

W到挺.

*/

#include<iostream>

#include<cstdio>

#define MAXN 100001

#define mod 1000000007

#define LL long long

using namespace std;

LL s[MAXN],n,tot,a[MAXN],ans=1,t;

LL read()

{

    LL x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

LL ab(int x,int y)

{

    if(x-y<=0) return y-x;

    return x-y;

}

LL mi(LL a,LL b)

{

    LL tot=1;

    while(b)

    {

        if(b&1) tot=(tot*a)%mod;

        a=(a*a)%mod;

        b>>=1;

    }

    return tot;

}

int main()

{

    n=read();

    for(int i=1;i<=n;i++) a[i]=read();

    for(int i=2;i<=n;i++)

    {

        if(a[i]<a[i-1]) t++;

        else if(t>1) ans=(ans*mi(2,t-1))%mod,t=0;

    }

    if(t>1) ans=(ans*mi(2,t-1))%mod,t=0;

    for(int i=2;i<=n;i++)

    {

        if(a[i]>a[i-1]) t++;

        else if(t>1) ans=(ans*mi(2,t-1))%mod,t=0;

    }

    if(t>1) ans=(ans*mi(2,t-1))%mod;

    cout<<ans;

    return 0;

}

/*

正解还是比较好想的.

观察一下有的数是没有贡献的.

比如

1 2 3 4 5 4 3 2 1.

ans就是|5-1|+|1-5|.

那么中间的数可选可不选.

用乘法原理就可以了.

*/

#include<iostream>

#include<cstdio>

#define MAXN 100001

#define mod 1000000007

#define LL long long

using namespace std;

LL s[MAXN],n,tot,a[MAXN],ans=1,t;

LL read()

{

    LL x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

LL ab(int x,int y)

{

    if(x-y<=0) return y-x;

    return x-y;

}

LL mi(LL a,LL b)

{

    LL tot=1;

    while(b)

    {

        if(b&1) tot=(tot*a)%mod;

        a=(a*a)%mod;

        b>>=1;

    }

    return tot;

}

int main()

{

    n=read();

    for(int i=1;i<=n;i++) a[i]=read();

    for(int i=2;i<=n;i++)

    {

        if(a[i]<a[i-1]) t++;

        else if(t>1) ans=(ans*mi(2,t-1))%mod,t=0;

    }

    if(t>1) ans=(ans*mi(2,t-1))%mod,t=0;

    for(int i=2;i<=n;i++)

    {

        if(a[i]>a[i-1]) t++;

        else if(t>1) ans=(ans*mi(2,t-1))%mod,t=0;

    }

    if(t>1) ans=(ans*mi(2,t-1))%mod;

    cout<<ans;

    return 0;

}

巴特西

洛谷比赛 U4858 sum

最新文章

热门文章