A、*Chino with Geometry
theme:给定圆心坐标A与半径,给定两点c(x1,0)在y轴上,B(x2,y2);保证BC与圆A相割,如上图,求BD*BE的值。
solution:简单的数学几何推理。(一时推不出可以先考虑特殊情况,如BC过A点,则BD*BE=(AB-r)*(AB+r))
过A作BC垂线交于点F,设h=AF,连接AB,AD。
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int x0,y0,r,x1,y1;
cin>>x0>>y0>>r>>x1>>y1;
long long ab2=(x1-x0)*(x1-x0)+(y1-y0)*(y1-y0);
long long ans=ab2-r*r;
cout<<ans<<"\n";
}
F、*Chino with Expectation
theme:给定n个数的数组,q次询问,每次输入x,l,r,求把数列中的某个数加上
以后
的期望。
solution:关键是求出任l,r间元素之和,之后两种情况,加x在l,r之间元素上,和不在之间元素上。求和两种方法,求前缀和相减和用线段树。这题用前缀和十分简单。这里我用线段树:
#include<iostream>
#include<cstdio>
using namespace std;
int const SIZE=500010;
int t[4*SIZE];
void build(int k,int l,int r)
{
if(l==r)scanf("%d",&t[k]);
else
{
int mid=(l+r)/2;
build(k<<1,l,mid);
build((k<<1)+1,mid+1,r);
t[k]=t[k<<1]+t[(k<<1)+1];
}
}
void add(int k,int i,int delta,int l,int r)//没用上
{
if(l==r)
{
t[k]+=delta;
return;
}
int mid=(l+r)/2;
if(i<=mid)
add(k<<1,i,delta,l,mid);
else
add((k<<1)+1,i,delta,mid+1,r);
t[k]=t[k<<1]+t[(k<<1)+1];
}
int query(int k,int s,int e,int l,int r)
{
if(l==s&&r==e)return t[k];
int mid=(l+r)/2;
int ans=0;
if(e<=mid)
ans+=query(k<<1,s,e,l,mid);
else if(s>mid)
ans+=query((k<<1)+1,s,e,mid+1,r);
else
ans+=query(k<<1,s,mid,l,mid)+query((k<<1)+1,mid+1,e,mid+1,r);
return ans;
}
int main()
{
int n,q;
cin>>n>>q;
build(1,1,n);
while(q--)
{
int x,l,r;
scanf("%d%d%d",&x,&l,&r);
int d=r-l+1;
// cout<<query(1,l,r,1,n)<<endl;
double ans=1.0*query(1,l,r,1,n)/d/n*(n-d)+1.0*(query(1,l,r,1,n)+x)/d/n*d;
printf("%lf\n",ans);
}
}