作者： itewqq

发布于

[暑期集训][数学][数论][组合数学] SPOJ Square-free integers

（其实一开始想的是错的，实际上就是mu[i]^2的前缀和S

先考虑对立面，2到n之间有多少个数可以被平方数整除？可以枚举从2到sqrt(n)，然后把可以被这些数字的平方整除的算上，也就是n/(i^2)个对于每个来说。但是这里会有重复的，比如i分别为2，3，6时，算上了4，9，36，其中36被算了两遍，所以要加加减减。（好吧其实我也还没自己证明出来但是今天有点疲回头填坑ooorz
继续阅读“[暑期集训][数学][数论][组合数学] SPOJ Square-free integers”

发布于

[暑期集训][数学][递推] 51nod 1383

题意要求求出给定整数分解为2的幂之和的方法数量。（貌似这题还有两个加强版orz日后填坑

写出前几项后可以观察出来规律：当n为奇数的时候 f(n)=f(n-1)，当n为偶数的时候f(n)=f(n/2)+f(n-2)。

这个规律的由来其实很简单，奇数的时候一定每一种分解都有至少一个1，说明这个1不是造成这些分法不同的原因，那么去掉他之后这些分法仍然是不同的，也就是数量没有减少，所以f(n)=f(n-1)。        而偶数的时候可以观察到分法可以分为两类，一类是有1的，这时候必定至少有两个1（因为n为偶数），换句话说这一类里面每种分法都有两个1，那么跟奇数那个同理这个也不是造成这些分法彼此不同的原因，所以去掉之后仍然是不同的也就是数量不会减少，这一部分相当于是f(n-2)；   另一部分都是2的倍数，那么把他们全部除以2的话也仍然保持不同也就是数量没有变，也就是说这一部分相当于f(n/2)。

一开始没写记忆化果断T了几发。。。
继续阅读“[暑期集训][数学][递推] 51nod 1383”

发布于

[紫书][单调栈][思维] 求最大周长矩形 UVa12265

总感觉此题似曾相识，有很类似的求面积而非周长的题目？

题意给出长方形地图然后让求每个点对应的可贩卖的最大周长的矩形面积。考虑每一行的话，往上累计，然后就变成了一维的，在前面一些xx中求得最大/最小值的题，一般直接暴力会超时然后就用单调数据结构优化，这里左边每次动都相当于一个新的开始，所以就是添加和删除操作都在右侧进行，单调栈走起了。
继续阅读“[紫书][单调栈][思维] 求最大周长矩形 UVa12265”

发布于

[紫书][思维] 非常见模型 物理 思维与分析 UVa1442

紫书第八章这些题。。有点意思的啊。。

题意让往一个不规则的二维洞穴里面加水问每个地方都不碰到天花板的话最多能装多少水。当然很容易想到用在一点画一条横线然后与其他天花板不相交，但是没想出来怎么在低复杂度求和具体实现。看了紫书题解，才发现这条横线左右两边可以分开来求，这样求一边的时候就可以扫描一遍数组而不用O(n^2)去计算了， 继续阅读“[紫书][思维] 非常见模型 物理 思维与分析 UVa1442”