pe vol31 151~155
最近好像没什么干劲啊…
Project Euler
Problem 151 : C++,裁纸,数学期望
Problem 152 : C++,1/2用整数的平方的倒数的和来表示的方法数
Problem 153 : C++,整除n的高斯整数之和
Problem 154 : C++,(x+y+z)200000 中有多少个系数是1012的整数倍
Problem 155 : C++,用18个相同容量的电容串联并联等能组成多少种不同的电容值
下面是详细内容:
pe problem 285
Project Euler 第285题
Pythagorean odds
选定一个正整数k,然后随机产生[0,1]上均匀分布的实数2个,a和b
那么当sqrt((k*a+1)^2+(k*b+1)^2)与k相差 0.5以内,则得k分,否则得0分
玩10^5次游戏,分别取k=1,2,…,10^5,那么最后总分的数学期望是多少
下面是我的解题过程:
pe problem 280
Project Euler 第280题
Ant and seeds
蚂蚁搬种子
5*5的格子上中间的格子里有一个蚂蚁
每次蚂蚁随机向相邻格子移动,不会移出5*5的格子
最底层的5个格子里分别有一个种子
当蚂蚁没有背种子的时候来到最底层有种子的格子里,就会背上种子
当蚂蚁背着种子的时候来到最顶层的没有种子的格子里,就会放下种子
求使种子全放到顶层所需步数的数学期望
下面是我的解题过程:
pe vol17 81~85
Project Euler
Problem 81 : C++,dp
Problem 82 : C++,dp
Problem 83 : C++,heap+dijkstra最短路
Problem 84 : C++,高斯消元,概率
Problem 85 : C++,数学,等差数列求和的应用
下面是详细内容:
contest hit The 34th ACM/ICPC Asia Regional Harbin Preliminary
9.13的哈尔滨网络赛…
The 34th ACM/ICPC Asia Regional Harbin Preliminary
这个在哪里可以继续做题呢?
数模和网络赛严重撞车…唉…还撞上2天网络赛挤在一起的这周…
然后不知道在哪里还能看题和交题…已经记不清楚题目了…
而且做的也不太好…
队伍排名80多…一共10题,出了4题,分别是BCDJ…有一题是最后四分钟1A的…真是全身发抖的感觉…
一开始J题很多人过…感觉是个约瑟夫环的变形…不过怎么都想不出怎么做…
然后看到B题…树长的好快…节点最多m个孩子节点,没满的话每单位时间可以长出一个,问n<=2^128个单位时间后树有多少节点
是个菲波那契数列的变形…构造个转移矩阵…m+1阶的…然后二分,还有高精度
高精度没写好,结果错了2次…最后AC了…
然后sky想了个二分+树状数组来做J题的方法…然后过了
然后yq做了C题…一个KM…过了
接着想H题…菲波那契数列那题…话说出题人是菲波那契数列控么…
但是sky想了几个公式,结果还是WA到死…
还剩30分钟的时候准备写D题…如果规模小到100的话我会用高斯消元搞掉…可是规模有10000…
我本想用高斯消元先写个小数据找找规律的…可是完全找不出…都是小数点后好多位都还没规律的…
没办法…画了个矩阵大概的样子给yq…yq冒出来一句什么追赶法…然后去找书,也没找到什么结果…
然后我就YY了个算法…因为矩阵只有对角线和对角线上面和下面一共三个斜线上有非零值…
我就从上到下扫一遍,下面一行减去上面一行乘以一个系数,使得下面一行对角线左边的数消掉为0
然后从下往上扫一遍,上面一行减去下面一行乘以一个系数,使得下面一行对角线右边的数消掉为0
这是矩阵除了主对角线和增广的那一列,其他都是0了,于是就把每个变量值解出来
此时只剩4分钟…全身发抖,测几组数据时连输入数据都输不对了…然后交掉…1A…顿时人软掉了…
简述:
A: 不记得了
B: 和前m项有关的菲波那契数列,转移矩阵,高精度
C: 排列数差异,KM
D: 博弈,数学期望,解线性方程组,根据方程组的特性弄个专门算法
E: 不记得了
F: 不记得了
G: 不记得了
H: 前两项乘以系数的菲波那契数列,不会
I: 不记得了
J: 约瑟夫问题变种,每次间隔人数不同,不知有没有公式,我们用的是树状数组+二分
下面是D题代码,没有详述:
RSS订阅