Project Euler 简要题目报告

介绍

这是一个简单的PE题解报告，从第101题开始。第1题到100题由于完成时间较为久远，等到以后有机会再补充。

题目

101:拉格朗日插值公式把每一项BOP求出来然后求和
102:判断一个点是否在多边形内，一般可以使用射线法。这题比较简单，可以判断三角形面积和是否与原点和顶点连线后分成3块的面积和相等。若原点不在三角形内，那么3块面积和显然会更大一些。
103:枚举每一层的数字，保证每一层比上一层要大。枚举一层判断一次合法性，同时设置一个枚举的上限，保证枚举次数不会太多。
104:可暴力判断，但实在太慢了。主要是如何快速求出前9位和后9位。后9位可以直接模，前九位可以用斐波那契数列的通项公式以10为底取对数再取小数点后9位就是了。
105:类似103，先排序判断是否满足条件2，然后计算出每个子集判断是否有重复的
106:显然2个subset只有元素个数相同才有比较的意义。如何判断2个subset是不是要比较呢，如果2个subset的元素贪心的从大到小匹配，其中一个subset的每一个元素都比另一个大显然是不需要比较的。对于剩下的情况就是需要进行比较的。为了加速判断，使用了位运算。
107:裸最小生成树
108:我写了个暴力直接丢在那里跑。效率非常低下，好的做法可见这里
109:brute force
110:思路见这里
111:对于一个数字d，从大到小枚举最多存在多少重复的d，然后搜索符合条件的所有数字，判断是否质数。判断一个数是不是质数可以先用线性筛法求出1e6内的质数然后看看是否整除这个数
112:枚举
113:见这里
114:dp计数。f[i]表示第i格子是黑色，i-1格子是红色的方案数。
115:同114
116:dp f[i]表示第[i-x,i]个格子放砖块的方案。g[i]统计前缀和
117:dp f[i][j]表示第i个格子用的颜色。0为黑色，1为红色，2为绿色，3为蓝色
118: 枚举1-9的所有置换，计算每一种置换能组成多少合法的集合。计算时保证元素递增，这样保证了不重复计算。
119: 没有特别好的思路。我的做法参加这里
120: here
121: dp f[i][j]表示前i轮拿出了j个蓝色盘子。
122: 对于每一个k都搜索一次，求和
123: 同120
124: 分解质因数
125: 枚举连续平方数和判断是不是回文数
126: 推了一个递推式然后暴力。暴力的技巧参考了Google搜出来的解法
127: 枚举a和b。优化：由gcd的性质，gcd(a,b)=gcd(a,a-b),第一个条件等价于只有gcd(a,b)=1，同时互质也说明了rad(abc)=rad(a)*rad(b)*rad(c)