精华内容
下载资源
问答
  • 基准时间限制:1.5秒 空间限制:131072KB 分值:80 区间内所有元素排序后,任意相邻两个元素值差为1的区间称为“连续区间” 如:3,1,2是连续区间,但3,1,4不是连续区间 给出一个1~n的排列,求出有...
    1810 连续区间
    基准时间限制:1.5 秒 空间限制:131072 KB 分值: 80
     
     
    区间内所有元素排序后,任意相邻两个元素值差为1的区间称为“连续区间”
    如:3,1,2是连续区间,但3,1,4不是连续区间
    给出一个1~n的排列,求出有多少个连续区间
    Input
    一个数n(n<=1,000,000)
    第二行n个数,表示一个1~n的排列
    Output
    一个数,表示有多少个连续区间
    Input示例
    5
    2 1 5 3 4
    Output示例
    9
    样例解释:
    区间[1,1][2,2][3,3][4,4][5,5][1,2][4,5][3,4][1,5]为连续区间//[l,r]表示从第l个数到第r个数构成的区间

     
    题解:
      分治计数
      先将序列划分为左右两边,只考虑左端点在左边部分,右端点在右边部分的答案
      也就是左边部分对右边部分答案的贡献
      可知
          Max{max(i),max(j)} - Min{min(i),min(j)} = j - i;
      共有4中互不影响的情况,其实这里分类讨论下就可以O(1)求出
    #include <bits/stdc++.h>
    inline long long read(){long long 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-'0';ch=getchar();}return x*f;}
    using namespace std;
    #define ls i<<1
    #define rs ls | 1
    #define mid ((ll+rr)>>1)
    #define MP make_pair
    typedef long long LL;
    typedef unsigned long long ULL;
    const long long INF = 1e18+1LL;
    const double pi = acos(-1.0);
    const int N = 1e6 + 10, M = 502, inf = 1e9;
    
    LL ans,mx[N],mx1[N],mn[N],mn1[N],vis[N * 3];
    int a[N],n;
    
    void solve(int ll,int rr) {
        if(ll == rr) return ;
        int last1 = -1,last2 = inf;
        for(int i = mid; i >= ll; --i)
            mx[i] = max(last1,a[i]),last1 = mx[i],
            mn[i] = min(last2,a[i]),last2 = mn[i];
        last1 = -1,last2 = inf;
        for(int i = mid+1; i <= rr; ++i)
            mx1[i] = max(last1,a[i]),last1 = mx1[i],
            mn1[i] = min(last2,a[i]),last2 = mn1[i];
    
        for(int i = ll; i <= mid; ++i) {
            int tmp = i + mx[i] - mn[i];
            if(tmp > mid && tmp <= rr
               && mx[i] > mx1[tmp] && mn[i] < mn1[tmp]) ans+=1;
        }
    
    
        for(int i = mid+1; i <= rr; ++i) {
            int tmp = i - mx1[i] + mn1[i];
            if(tmp >= ll && tmp <= mid
               && mx1[i] > mx[tmp] && mn1[i] < mn[tmp]) ans+=1;
        }
        int l = mid+1,r = mid;
        for(int i = mid; i >= ll; --i) {
           while(r < rr && mx[i] > mx1[r+1]) ++r, vis[r+mn1[r]+n]++;
           while(l <= r && mn[i] < mn1[l]) vis[l+mn1[l]+n]--,++l;
           ans += vis[i+mx[i]+n];
        }
        while(l <= r) vis[l+mn1[l]+n]--,l++;
    
        l = mid, r = mid+1;
        for(int i = mid+1; i <= rr; ++i) {
            while(r > ll && mx1[i] > mx[r-1]) r--,vis[r-mn[r]+n]++;
            while(l >= r && mn[l] > mn1[i]) vis[l-mn[l]+n]--,l--;
            ans += vis[i-mx1[i]+n];
        }
        while(l >= r) vis[l-mn[l]+n]--,l--;
        solve(ll,mid),solve(mid+1,rr);
    }
    int main() {
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i) a[i] = read();
        solve(1,n);
        printf("%lld\n",ans+n);
        return 0;
    }

     

     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     

    转载于:https://www.cnblogs.com/zxhl/p/7571066.html

    展开全文
  • 区间求和

    2016-12-03 13:28:00
    区间求和 基准时间限制:1秒 空间限制:131072KB 分值:80 LYK在研究一个有趣的东西。 假如有一个长度为n的序列,那么这个序列的权值将是所有有序二元组i,j的Σaj−ai其中1<=i<j<=n。 但是这个...
    基准时间限制:1 秒 空间限制:131072 KB 分值: 80
    LYK在研究一个有趣的东西。
    假如有一个长度为n的序列,那么这个序列的权值将是所有有序二元组i,j的 Σajai 其中1<=i<j<=n。
    但是这个问题似乎太简单了。
    于是LYK想在所有有序二元组k,l中若ak=al其中1<=k<l<=n,则将 a{k},a{k+1},...,a{l}  提出当做一个序列,计算它的权值。
    并统计所有这样的区间的权值和。
    由于答案可能很大,你只需要将答案对2^32取模即可。
    建议使用读入优化。
    Input
    第一行一个整数n(1<=n<=1000000),接下来一行n个数ai(1<=ai<=1000000)表示LYK的序列。
    Output
    一行表示答案。
    Input示例
    5
    3 4 5 5 3
    Output示例
    2
    分析:区间[l,r]对x(l<=x<=r)的贡献次数为2*x-l-r;
       所以维护前缀和,后缀和,然后对每个数算贡献即可;
       注意取模2^32等价于unsigned long long的溢出;

    代码:
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    #include <climits>
    #include <cstring>
    #include <string>
    #include <set>
    #include <map>
    #include <unordered_map>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <list>
    #define rep(i,m,n) for(i=m;i<=n;i++)
    #define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
    #define mod 1000000007
    #define inf 0x3f3f3f3f
    #define vi vector<int>
    #define pb push_back
    #define mp make_pair
    #define fi first
    #define se second
    #define ll long long
    #define pi acos(-1.0)
    #define pii pair<int,int>
    #define Lson L, mid, ls[rt]
    #define Rson mid+1, R, rs[rt]
    #define sys system("pause")
    #define intxt freopen("in.txt","r",stdin)
    const int maxn=1e6+10;
    using namespace std;
    ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
    ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
    inline ll read()
    {
        ll x=0;int 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-'0';ch=getchar();}
        return x*f;
    }
    int n,m,k,t,a[maxn];
    ll suml[maxn],sumr[maxn],numl[maxn],numr[maxn],pos[maxn],pre[maxn],f[maxn],fl[maxn],fr[maxn];
    unsigned ll ans;
    int main()
    {
        int i,j;
        scanf("%d",&n);
        rep(i,1,n)a[i]=read();
        rep(i,1,n)
        {
            numl[i]=numl[pos[a[i]]]+1;
            suml[i]=suml[pos[a[i]]]+i;
            pos[a[i]]=i;
        }
        memset(pos,0,sizeof(pos));
        for(i=n;i>=1;i--)
        {
            numr[i]=numr[pos[a[i]]]+1;
            sumr[i]=sumr[pos[a[i]]]+i;
            pos[a[i]]=i;
        }
        rep(i,1,n)
        {
            fl[i]=fl[i-1];
            fl[i]+=i*numr[i];
            fl[i]-=suml[i-1];
            f[i]=f[i-1]+numr[i]-numl[i-1];
        }
        for(i=n;i>=1;i--)
        {
            fr[i]=fr[i+1];
            fr[i]+=i*numl[i];
            fr[i]-=sumr[i+1];
            ans=ans+a[i]*(2*i*f[i]-fl[i]-fr[i]);
        }
        printf("%u\n",ans);
        //system("Pause");
        return 0;
    }

    转载于:https://www.cnblogs.com/dyzll/p/6128549.html

    展开全文
  • 量异常分值计算模型

    2019-06-06 15:09:33
    量异常分值计算模型 基线X (1)30日全日志,计算其每小时访问次数,将所有项累加后取项平均值,得出降噪后的每小时平均次数作为基线M; (2)30日每日日志,重复一过程计算每日每小时次数作为参考值; (3)利用...

    量异常分值计算模型

    1. 基线X

    (1)30日全日志,计算其每小时访问次数,将所有项累加后取项平均值,得出降噪后的每小时平均次数作为基线M;

    (2)30日每日日志,重复一过程计算每日每小时次数作为参考值;

    (3)利用(1)(2)过程产出数据计算标准差,计算出进30日访问行为波动情况C;

    (4)M+ -2C作为原始参考基线;

    (5)为避免产生不合理取值,取M的150%与50%作为参考区间佐证(4)产生基线;

    (6)将(4)(5)计算出的值域取上域及下域较大值确定基线范围;

    2. 报警

    (1)报警所用基线是针对个人数据,采用过程1(1)计算个人基线;

    (2)超出基线值域,则取值域中最近的值作为基线;

    3. 小时、单日量异常分值计算

    (1)取当前样本次数S  计算(S-X)/X 得出超出基线情况P

    (2)针对制定阈值对(1)产生的结果P进行分值计算;

    (3)采用分段函数

    a) 第一阶段(40%)采用斜率开始较大,后期平缓的对数函数,可快速将分值区分;

    b) 第二阶段(40%)拟合线性函数计算分值

    c) 第三阶段(20%)拟合指数函数计算分值

    (4)将warnScore展示为当前单维异常值

    多维打分规则

     

    1. 利用lnX函数,将离散率较大的报警频率映射至较小的离散区间
    2. 将映射后的数值正比例切分分值上限(100分),并根据比例得出每种报警的极限分值;
    3. 取单人的报警ID及分值top5报警,加权(1/2 N次方),求和,得出单种类报警异常分值
    4. 将c得出的分值映射至b得出的极限分值
    5. 循环d,累加后求出最终异常分值

    反比例系数分值

    a) 取ln(En/ni)为反比例系数,重新计算上一步的b过程

    b) 将二者得出的分值以决策树方式取较大分值一组记录;

    展开全文
  • 51Nod 1672 区间

    2017-10-27 10:59:09
    基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 小A有一个含有n个非负整数的数列与m个区间,每个区间可以表示为li,ri。 它想选择其中k个区间, ...

    基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题
     收藏
     关注
    小A有一个含有n个非负整数的数列与m个区间,每个区间可以表示为li,ri。
    它想选择其中k个区间, 使得这些区间的交的那些位置所对应的数的和最大。(是指k个区间共同的交,即每个区间都包含这一段,具体可以参照样例)

    在样例中,5个位置对应的值分别为1,2,3,4,6,那么选择[2,5]与[4,5]两个区间的区间交为[4,5],它的值的和为10。
    Input
    第一行三个数n,k,m(1<=n<=100000,1<=k<=m<=100000)。
    接下来一行n个数ai,表示小A的数列(0<=ai<=10^9)。
    接下来m行,每行两个数li,ri,表示每个区间(1<=li<=ri<=n)。
    Output
    一行表示答案
    Input示例
    5 2 3
    1 2 3 4 6
    4 5
    2 5
    1 4
    Output示例
    10
    Joe (题目提供者)


    分析:

    想明白以后确实是不难的,就是前期想着不好想。为了证明自己真的是理解了,把数据按左端点排序自己拍了一遍。


    解释一下这个题:

    我们首先把左端点从小到大排序(掌握以后,这个排序不论是排右端点、从大到小都可以做的),然后我们依次枚举左端点,我们把当前枚举的左端点 l 当做区间交的左端点,那么很明显,其他的区间的左端点肯定是要小于 l ,那么也就是说,前 k - 1 个端点不用枚举。

    接下来就是数据的处理了,我们枚举了左端点,然后找右端点的时候要尽量靠右,这个右端点该怎么找呢?我们用一个线段树记录右端点,当我们枚举第 x 个区间的时候,后面的区间的右端点都是干扰的,我们就先不让它加入线段树,当然,前面的端点都要在线段树里(当时是这一点没想到),然后在这些端点中找最靠右的右端点,然后算前缀和更新一下ans。

    然后我们要处理 x+1 区间了,我们把 x+1 的右端点加入线段数,重复前面的操作即可。


    #include
    #include
    #include
    #include
    
    #define MAXN 100005
    #define INF 0x3f3f3f3f
    using namespace std;
    typedef long long LL;
    LL sum[MAXN + 5];
    struct Node { int st,ed; }a[MAXN + 5];
    struct Seg_Ment_Tree{ int l,r,sum; }tre[MAXN << 2];
    inline bool cmp(Node a,Node b ) { return a.st < b.st; }
    
    void Build(int u,int l,int r) {
        tre[u].l = l,tre[u].r = r;
        if(l == r){ tre[u].sum = 0; return ; }
        int Mid = l + r >> 1;
        Build(u<<1,l,Mid); Build(u<<1|1,Mid + 1,r);
        tre[u].sum = tre[u<<1].sum + tre[u<<1|1].sum;
    }
    
    void Modify(int u,int pos) {
        if(tre[u].l == tre[u].r) { tre[u].sum ++; return; }
        int Mid = tre[u].l + tre[u].r >> 1;
        if(pos <= Mid) Modify(u<<1,pos);
        else Modify(u<<1|1,pos);
        tre[u].sum = tre[u<<1|1].sum + tre[u<<1].sum;
    }
    
    int Query(int u,int x) {
        if(tre[u].l == tre[u].r) return tre[u].l;
        if(tre[u<<1|1].sum >= x) return Query(u<<1|1,x);
        else return Query(u<<1,x - tre[u<<1|1].sum);
    }
    
    int main(int argc,char *argv[]) {
        int n,k,m,t;
        scanf("%d %d %d",&n, &k, &m);
        sum[0] = 0;
        for(int i=1; i<=n; ++i) {
            scanf("%d",&t);
            sum[i] = sum[i-1] + t;
        }
        for(int i=1; i<=m; ++i) scanf("%d %d",&a[i].st,&a[i].ed);
        sort(a + 1, a + m + 1,cmp);
        Build(1,1,n);
        for(int i=1; i<=k; ++i) 
            Modify(1,a[i].ed);
        LL Ans = 0;
        a[m + 1].ed = 1;
        for(int i=k; i<=m; ++i) {
            LL pos = Query(1,k);
            if(pos >= a[i].st) Ans = max(Ans,sum[pos] - sum[a[i].st - 1]);
            Modify(1,a[i + 1].ed);
        }
        printf("%I64d\n",Ans);
        return 0;
    }


    展开全文
  • 51nod 1672 区间

    2017-05-16 17:13:17
    基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 收藏 关注 小A有一个含有n个非负整数的数列与m个区间,每个区间可以表示为li,ri。 它想选择其中k个区间, 使得这些区间的交的那些位置所对应的...
  • 1810 连续区间(分治)

    2017-10-07 16:40:00
    基准时间限制:1.5秒 空间限制:131072KB 分值:80难度:5级算法题 区间内所有元素排序后,任意相邻两个元素值差为1的区间称为“连续区间” 如:3,1,2是连续区间,但3,1,4不是连续区间 给出一个1~n的排列,...
  • 51Nod-1672-区间

    2017-10-30 18:58:25
    基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 小A有一个含有n个非负整数的数列与m个区间,每个区间可以表示为li,ri。 它想选择其中k个区间, ...
  • 51 nod 1495 中国好区间

    2019-09-23 16:38:20
    基准时间限制:0.7秒 空间限制:131072KB 分值:80难度:5级算法题 阿尔法在玩一个游戏,阿尔法给出了一个长度为n的序列,他认为,一段好的区间,它的长度是>=k的,且该区间的第k大的那个数,一定...
  • 51nod-1672 区间

    2016-10-05 16:14:56
    基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 小A有一个含有n个非负整数的数列与m个区间,每个区间可以表示为li,ri。 它想选择其中k个区间, ...
  • poj1651 区间dp

    2016-03-04 11:01:38
    题目大意:每次从中间(取出两边)序列中取出一个数,则它的分值是它乘以与它相邻的两数,求去玩所有的中间数后分值和最小为多少 思路:区间dp,dp[i][j]表示从i到j的最优解,枚举从i到j最后移除的元素,有dp[i][j] = ...
  • 基准时间限制:1秒 空间限制:131072KB 分值:10难度:2级算法题 收藏 关注 一整数数列a1, a2, ... , an(有正有负),以及另一个整数k,求一个区间[i, j],(1 <= i <= j <= n),使得a[i] + .....
  • 51nod 1495 中国好区间

    2017-04-06 22:46:54
    基准时间限制:0.7 秒 空间限制:131072 KB 分值: 80 难度:5级算法题  收藏  关注 阿尔法在玩一个游戏,阿尔法给出了一个长度为n的序列,他认为,一段好的区间,它的长度是>=k的,...
  • 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 小A有一个含有n个非负整数的数列与m个区间,每个区间可以表示为li,ri。 它想选择其中k个区间, ...
  • 1174 区间中最大的数 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注 给出一个有N个数的序列,编号0 - N - 1。进行Q次查询,查询编号i至j的所有数中,最大的数是多少。 例如: 1 7 6 3 1...
  • 51nod1495 中国好区间

    2018-03-23 09:24:22
    1495 中国好区间 基准时间限制:0.7 秒 空间限制:131072 KB 分值: 80 难度:5级算法题 收藏 关注阿尔法在玩一个游戏,阿尔法给出了一个长度为n的序列,他认为,一段好的区间,它的长度是&gt;=k的,且该...
  • 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 小A有一个含有n个非负整数的数列与m个区间,每个区间可以表示为li,ri。 它想选择其中k个区间, ...
  • 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 lyk拥有一个区间。 它规定一个区间的价值为这个区间中所有数and起来的值与这个区间所有数or起来的值...
  • 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 小A有一个含有n个非负整数的数列与m个区间,每个区间可以表示为li,ri。 它想选择其中k个区间, ...
  • g[l][r]表示当前区间l,r之间最大分值的根节点是谁。用于之后的前序遍历输出。(前序遍历:根-左-右)(中序遍历:左-根-右) 当区间长度为1时,根节点没有左右儿子,故它的得分就为它自己本身。 当区间长度大于1时...
  • 基准时间限制:1秒 空间限制:131072KB 分值:40难度:4级算法题 lyk拥有一个区间。 它规定一个区间的价值为这个区间中所有数and起来的值与这个区间所有数or起来的值的乘积。 例如3个数2,3,6。它们and起来的值...
  • 51nod 1672 区间交(贪心)

    2017-10-22 17:00:26
    1672 区间交基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 收藏 关注小A有一个含有n个非负整数的数列与m个区间,每个区间可以表示为li,ri。它想选择其中k个区间, 使得这些区间的交的...
  • 基准时间限制:1 秒 空间限制:131072 KB 分值: 160 我们定义“区间的价值”为一段区间的最大值*最小值。 一个区间左端点在L,右端点在R,那么该区间的长度为(R-L+1)。 现在聪明的杰西想要知道,对于长度为k的...
  • 因为连续的东西有分值,所以应该记录一下连续的有多少个。  只要记录与边界连续的有多少个就能涵盖所有的连续了。只记一边的边界即可。 两个转移:用掉记录的那些连续的 或 在自己区间中再找一个一样颜色的使连续...
  • 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 小A有一个含有n个非负整数的数列与m个区间,每个区间可以表示为li,ri。 它想选择其中k个区间, ...
  • 51nod 1495:中国好区间

    2015-12-31 17:42:22
    基准时间限制:0.7 秒 空间限制:131072 KB 分值: 80 难度:5级算法题  收藏  关注 阿尔法在玩一个游戏,阿尔法给出了一个长度为n的序列,他认为,一段好的区间,它的长度是>=k的,...
  • 51NOD 1434 区间LCM

    2017-06-01 22:13:29
    1434 区间LCM 题目来源: TopCoder 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 收藏 关注 一个整数序列S的LCM(最小公倍数)是指最小的正整数X使得它是序列S中所有元素的倍数,那么LCM(S)=X...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 321
精华内容 128
关键字:

区间分值