bzoj3570 Dzy Loves Physics I - ShinriiTin's Blog - 博主是sb
bzoj2048 书堆
codeforces 372D Choosing Subtree is Fun

bzoj3570 Dzy Loves Physics I

ShinriiTin posted @ 2015年6月11日 18:28 in 未分类 with tags 不知道这是个什么玩意儿系列 , 454 阅读

看到题面就傻了。。。

完全弹性碰撞:m1v1+m2v2=m1v1'+m2v2'

由动能定理得:0.5*m1*v12+0.5*m2*v2=0.5*m1*v1'2+0.5*m2*v2'2

当m1=m2时,v1'=v2,v2'=v1

又有条件a*v=C,即dv/dt *v=C

两边同时积分得: 0.5*v2=C*t

解得v=sqrt(2*C*t)

所以。。。求原来k小的速度,再算出现在的速度即可

Portal

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAXN=1e5+5;

int bit[MAXN],sz;

inline void Add(int x){
	for(;x<=sz;x+=x&-x)++bit[x];
}

inline int kth(int k){
	int ans=0;
	for(int i=19;~i;--i){
		ans+=1<<i;
		if(ans>=sz||bit[ans]>=k)ans-=1<<i;
		else k-=bit[ans];
	}
	return ans+1;
}

int n,q,C,a[MAXN],h[MAXN<<1];

int opt[MAXN],t[MAXN],x[MAXN];

inline int Hash(int x){
	return lower_bound(h+1,h+1+sz,x)-h;
}

int main(){
	scanf("%d%d",&n,&C);
	for(int i=1;i<=n;++i){
		scanf("%d%*d%*d",a+i);
		h[++sz]=a[i];
	}
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		scanf("%d",opt+i);
		if(opt[i])scanf("%d%d",t+i,x+i);
		else scanf("%d%*d%*d",x+i),h[++sz]=x[i];
	}
	sort(h+1,h+1+sz);
	sz=unique(h+1,h+1+sz)-(h+1);
	for(int i=1;i<=n;++i)Add(Hash(a[i]));
	for(int i=1;i<=q;++i){
		if(opt[i]){
			int v=h[kth(x[i])];
			printf("%.3f\n",sqrt(2.*C*t[i]+1.*v*v));
		}
		else Add(Hash(x[i]));
	}
	return 0;
}
 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter