关键词:
题目背景
MooFest, 2004 Open
题目描述
约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很
多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i 头奶牛的坐标为Xi,没有两头奶牛的坐标是相同的。奶牛们的叫声很大,第i 头和第j 头奶牛交流,会发出max{Vi; Vj}×|Xi − Xj | 的音量,其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力。假设每对奶牛之间同时都在说话,请计算所有奶牛产生的音量之和是多少。
输入输出格式
输入格式:
• 第一行:单个整数N,1 ≤ N ≤ 20000
• 第二行到第N + 1 行:第i + 1 行有两个整数Vi 和Xi,1 ≤ Vi ≤ 20000; 1 ≤ Xi ≤ 20000
输出格式:
• 单个整数:表示所有奶牛产生的音量之和
输入输出样例
说明
朴素O(N2)
类似于归并排序的二分O(N logN)
树状数组O(N logN)
V*+abs(a_1-X)+V*abs(a_2-X)+V*abs(a_3-X)+....
\\=V*(abs(a_1-X)+abs(a_2-X)+abs(a_3-X)+.......)
\\
=V*(a_1-X+a_2-X+X-a_3)
\\
=V*((-N*X+(a_1+a_2+..+a_N)) +M*X-(a_3+...a_M)
推公式的题目
设当前奶牛的音量为V,坐标为X,ai表示第i头奶牛的坐标
假定a1,a2>X,a3<X(方便理解)
我们发现abs不满足分配率(就是abs(a+b)!=abs(a)+abs(b) )
此时我们分情况讨论
设有n个奶牛的坐标比X大,有m个奶牛的坐标比X小,把上面的abs拆开
那么对于N,M,a1+a2+...,a3+,,,
利用用树状数组求逆序对的思想
我们可以用两个树状数组维护
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<deque> 7 #include<queue> 8 #define LL long long 9 #define lb(x) ((x)&(-x)) 10 using namespace std; 11 const LL MAXN=40000001; 12 inline LL read() 13 { 14 char c=getchar();LL x=0,f=1; 15 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} 16 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f; 17 } 18 struct node 19 { 20 LL v,x; 21 }cow[MAXN]; 22 LL n; 23 int comp(const node &a,const node &b) 24 { 25 return a.v<b.v; 26 } 27 LL tree_num[MAXN]; 28 LL tree_sum[MAXN]; 29 LL MAXX; 30 inline void Point_Add(LL pos,LL val,bool how) 31 { 32 while(pos<=MAXX) 33 { 34 if(how==1)tree_num[pos]+=val; 35 else tree_sum[pos]+=val; 36 pos+=lb(pos); 37 } 38 } 39 inline LL Interval_Ask(LL pos,bool how) 40 { 41 LL ans=0; 42 while(pos) 43 { 44 if(how==1) ans=ans+tree_num[pos]; 45 else ans=ans+tree_sum[pos]; 46 pos-=lb(pos); 47 } 48 return ans; 49 } 50 int main() 51 { 52 n=read(); 53 for(LL i=1;i<=n;i++) cow[i].v=read(),cow[i].x=read(),MAXX=max(MAXX,cow[i].x); 54 sort(cow+1,cow+n+1,comp); 55 LL ans=0; 56 for(LL i=1;i<=n;i++) 57 { 58 // 1:数量 0:和 59 ans+=cow[i].v*( ( -cow[i].x*( Interval_Ask(MAXX,1)-Interval_Ask(cow[i].x,1) ) + (Interval_Ask(MAXX,0)-Interval_Ask(cow[i].x,0)) )+ 60 cow[i].x*Interval_Ask(cow[i].x,1)-(Interval_Ask(cow[i].x,0)) ); 61 Point_Add(cow[i].x,1,1); 62 Point_Add(cow[i].x,cow[i].x,0); 63 } 64 printf("%lld",ans); 65 return 0; 66 }
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没有两头... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没有两头... 查看详情
p2345奶牛集会andp2657低头一族
做法是一样的题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为... 查看详情
题解p2345奶牛集会(代码片段)
题目一道树状数组的题。话说题目直接告诉做法是什么鬼?首先这个题直接暴力是(O(n^2))的,不能通过(评论里说可以?可能数据太水了,建议加强)考虑优化,首先对于答案里的(max),可以直接通过排序优化掉,即把数据从小... 查看详情
洛谷p2986[usaco10mar]伟大的奶牛聚集(树形动规)
题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会,来自全国各地的奶牛将来参加这一次集会。当然, 查看详情
luogup2345奶牛集会
二次联通门: luoguP2345奶牛集会 /*luoguP2345奶牛集会权值线段树以坐标为下标,坐标为值建立线段树对奶牛按听力由小到大排序对于要查的牛每次第i次放入奶牛起作用的v就是vi; 每次ans+=(xi*sum-sumxl)*vi+(... 查看详情
luogup2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没... 查看详情
usaco2004moofest奶牛集会(代码片段)
题目问题描述约翰的n头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没有两头奶牛的坐标是相... 查看详情
[usaco]2004openmoofest奶牛集会(代码片段)
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没有两头... 查看详情
奶牛集会(moofest,usaco2004open)
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没有两头... 查看详情
洛谷p1578奶牛浴场
P1578奶牛浴场题目描述由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛场中的一个固定的位置产... 查看详情
[wc2002][洛谷p1578]奶牛浴场
洛谷题解里那个人可真是话多呢。 题目描述由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛... 查看详情
洛谷p1472奶牛家谱cowpedigrees
P1472奶牛家谱CowPedigrees102通过193提交题目提供者该用户不存在标签USACO难度普及+/提高 提交 讨论 题解 最新讨论暂时没有讨论题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个... 查看详情
洛谷p1154奶牛分厩
P1154奶牛分厩农夫约翰有N(1<=N<=5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号Si,所有的奶牛都睡在一个有K个厩的谷仓中,厩的编号为0到K-1。每头奶牛都知道自己该睡在哪一个厩中,因为约翰教... 查看详情
洛谷——p1154奶牛分厩
P1154奶牛分厩题目描述农夫约翰有N(1<=N<=5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号Si,所有的奶牛都睡在一个有K个厩的谷仓中,厩的编号为0到K-1。每头奶牛都知道自己该睡在哪一个厩中,因... 查看详情
洛谷p1154奶牛分厩
题目描述农夫约翰有N(1<=N<=5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号Si,所有的奶牛都睡在一个有K个厩的谷仓中,厩的编号为0到K-1。每头奶牛都知道自己该睡在哪一个厩中,因为约翰教会... 查看详情
[usaco10mar]伟大的奶牛聚集
[USACO10MAR]伟大的奶牛聚集Bessie正在计划一年一度的奶牛大集会,来自全国各地的奶牛将来参加这一次集会。当然,她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个,这些农场由N-1条道路... 查看详情