加强政务公开与网站建设,建设局全称是什么,网站到期续费通知,网站空间单位传送门#xff1a;It’s bertrand paradox. Again! 标签#xff1a;随机
题目大意
有两个人分别用两种方式在二维平面上随机生成1e5个圆#xff0c;每个圆上的每一个点(x,y)都满足-100x100且-100y100#xff0c;现在将某个人生成的1e5个圆的圆心和半径告…传送门It’s bertrand paradox. Again! 标签随机
题目大意
有两个人分别用两种方式在二维平面上随机生成1e5个圆每个圆上的每一个点(x,y)都满足-100x100且-100y100现在将某个人生成的1e5个圆的圆心和半径告诉你问你这个人是谁。两个人生成圆的方式分别为11、随机等概率地从开区间(-100,100)生成两个整数x,y。 2、随机等概率地从闭区间[1,100]中生成一个r。3、判断(x,y )为圆心、r为半径的圆是否满足要求若不满足返回步骤2重新生成r若满足则将该圆加入到结果中。21、随机等概率地从开区间(-100,100)生成两个整数x,y随机等概率地从闭区间[1,100]中生成一个r。2、判断(x, y)为圆心、r为半径的圆是否满足要求若不满足返回步骤1重新生成x,y,r若满足则将该圆加入到结果中。 输入第一行一个正整数n1e5代表圆的总数。接下来n行每行三个整数xyr-100x,y100,0r100)分别代表圆心的坐标和半径。 输出如果这些圆是第一个人生成的输出“bit-noob”否则输出“buaa-noob”。
算法分析
显然这题跟随机有关我们只要暴力跑100个数据找规律就行了不是。好吧看来并不需要因为这题实在太简单了。我们先看两种生成方法有什么区别最明显的就是第一种方法要三步而第二种方法只要两步。观察多出来的一步我们会发现第一种方法的圆心和半径是分开生成的而第二种方法的圆心和半径是在同一步中同时生成的。因为两种方法都是随机的所以都有可能生成不符合要求的圆。遇到这种情况第一个人将半径重新生成直到圆符合要求第二个人则是将整个圆重新生成即圆心坐标和半径都替换。那么很容易看出第一个人生成的所有的圆的圆心坐标都是一次确定的只通过半径来调整圆的大小。所以他生成的1e5个圆的圆心位置是均匀分布在(-100,100)中的这种情况下一些靠近边缘的圆的半径一定很小。第二种方法每次都生成一个圆心坐标、半径都随机的圆形那么我们可以大胆地将每个圆半径都假设为其期望再思考圆心的位置。半径为50的情况下能符合条件的圆的圆心一定更靠近(0,0)。所以根据统计学的知识两种方法生成的圆的圆心到(0,0)的距离的平均值一定不同且第二种方法距离更小。那很显然存在一个标准值如果圆心到原点的距离大于这个值就是第一种方法生成的否则就是第二种方法生成的。要猜这个值也很简单因为圆心在均匀分布的条件下到原点的距离期望是50根号2也就是大概70左右如果比这个值小很多那肯定是第二种方法生成的。保守估计在1e5的数据量下平均值不会比期望偏差超过10故将标准值定为60。
代码实现
#include iostream
using namespace std;
#include algorithm
#include cstring
#include map
#include iomanip
#include cmath
mappairlong long,long long,bool mp;
long long n,m,T;
int ans;
int main(){long long i,j,l,r,x,y,c,d,h,w,mid,t,sum0;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinn;for(i1;in;i){cinxyc;sumsqrt(x*xy*y);}sum/n;if(sum60)coutbuaa-noob;else coutbit-noob;
}
