POJ PKU 1990 MooFest 解题报告

为什么我用线段数这么不灵活呢?

大概思路是线段数记录某牛之前的坐标小于这个牛的牛的坐标和和牛的个数

然后其他部分线性数组记录

OK,贴代码

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

#define MAXN 20005
class cow
{
public:
    int v;
    int pos;
    cow(){};
    ~cow(){};
};

bool cmp(cow a,cow b)
{
    return a.v < b.v;
}
cow cw[MAXN];
long long belowXNT[MAXN];//树状数组,保存小于等于某坐标的牛的个数,计算时使用
long long belowXN[MAXN];//一般数组,保存小于等于某坐标和索引的牛的个数
long long velowXRT[MAXN];//树状数组,保存索引小于等于某的牛且坐标也小于它的牛的坐标之和,计算时使用
long long velowXR[MAXN];//一般数组,保存索引小于等于某的牛且坐标也小于它的牛的坐标之和
long long velowXRA[MAXN];//一般数组,保存小于等于某牛的坐标之和

int lowbit(int t)
{
    return t&(t^(t-1));
}
void setVal(int pos, int num, long long treeG[], int maxn)
{
    while (pos <= maxn)
    {
        treeG[pos] += num;
        pos += lowbit(pos);
    }
}
long long getSum(int pos, long long treeG[])
{
    long long sum = 0;
    while (pos > 0)
    {
        sum += treeG[pos];
        pos -= lowbit(pos);
    }
    return sum;
}



int main()
{
    int i,n;
    long long output = 0;
    memset(belowXN, 0, sizeof(belowXN));
    memset(belowXNT, 0, sizeof(belowXN));
    memset(velowXR, 0, sizeof(velowXR));
    memset(velowXRA, 0, sizeof(velowXRA));
    memset(velowXRT, 0, sizeof(velowXRT));
    scanf("%d",&n);
    for(i = 0 ; i < n ; i ++)
        scanf("%d %d", &cw[i].v, &cw[i].pos);

    sort(cw, cw + n, cmp);
    for(i = 0 ; i < n ; i ++)
    {
        velowXRA[i] = velowXRA[i - 1] + cw[i].pos;
        setVal(cw[i].pos, 1, belowXNT, MAXN);
        setVal(cw[i].pos, cw[i].pos, velowXRT, MAXN);
        velowXR[i] = getSum(cw[i].pos, velowXRT);
        belowXN[i] = getSum(cw[i].pos, belowXNT);
    }

    for(i = 1 ; i < n ; i ++)
        //output += cw[i].v * ((belowXN[i] - 1) * cw[i].pos - velowXR[i] + cw[i].pos + velowXRA[i] - velowXR[i] - (i - belowXN[i] + 1) * cw[i].pos);
        output += cw[i].v * ((belowXN[i] - i + belowXN[i] - 1 ) * cw[i].pos - 2 * velowXR[i] + velowXRA[i]);//这里是上面式子的简化版

    printf("%lld\n",output);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

cf1051F. The Shortest Statement(最短路)

由于边数的限制,非树边连接的点不会超过$2*(m - (n - 1)) = 42$个

12340
来自专栏数据结构与算法

洛谷P3128 [USACO15DEC]最大流Max Flow(树上差分)

边差分就是对边进行操作,我们在$u, v$除加上$val$,同时在$lca$处减去$2 * val$

13330
来自专栏数据结构与算法

07:清泉-改(prime+堆)

时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 512000kB描述 华北电力大学可以抽象为一张有n个点m条边的无向图. 现在所有的边都...

284100
来自专栏数据结构与算法

cf1042F. Leaf Sets(贪心)

考场上想的贪心是对的:考虑一棵子树,如果该子树内最深的两个节点的距离相加$>k$就删掉最深的那个点,向上update的时候只返回最深的点的深度

17730
来自专栏数据结构与算法

洛谷P1306 斐波那契公约数

题目描述 对于Fibonacci数列:1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题:第n项和第m项的最大公约数是多...

36160
来自专栏编程

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程? 其实说起来宏就是用公式来加工零件,比如说椭圆,如果没有宏的话,我们要逐点算出曲线上的点,然后慢慢来用直线逼近,如果是个光洁度要...

21880
来自专栏章鱼的慢慢技术路

Direct3D 11 Tutorial 7:Texture Mapping and Constant Buffers_Direct3D 11 教程7:纹理映射和常量缓冲区

在上一个教程中,我们为项目引入了照明。 现在我们将通过向我们的立方体添加纹理来构建它。 此外,我们将介绍常量缓冲区的概念,并解释如何使用缓冲区通过最小化带宽使用...

11040
来自专栏码匠的流水账

使用opennlp进行文档分类

要对文档进行分类,需要一个最大熵模型(Maximum Entropy Model),在opennlp中对应DoccatModel

32010
来自专栏数据结构与算法

洛谷P1282 多米诺骨牌

题目描述 多米诺骨牌有上下2个方块组成,每个方块中有1~6个点。现有排成行的 上方块中点数之和记为S1,下方块中点数之和记为S2,它们的差为|S1-S2|。例如...

29640
来自专栏数据结构与算法

洛谷P1316 丢瓶盖

题目描述 陶陶是个贪玩的孩子,他在地上丢了A个瓶盖,为了简化问题,我们可以当作这A个瓶盖丢在一条直线上,现在他想从这些瓶盖里找出B个,使得距离最近的2个距离最大...

36050

扫码关注云+社区

领取腾讯云代金券