FZU 2159 WuYou

Proceed big numbers A and B,A and B have same digits(Both A and B have no prelude zeros),A contains uncertain digits marking ‘?’.Find a largest A to make A < B.

策略是先从前往后扫描一遍已知的数位,如果相等的话,放过当前位,如果当前位a>b这时停止扫描,纪录扫到的位置i,记录状态为1,如果当前位a<b这时停止扫描记录扫描到位置i,状态为2.

对与状态1,如果我们不能在i之前找到一个‘?’使这一位正好比b少1,那么无解,找到了的话,就记录这个新位置为i,跳到状态2。

对于状态2,只要令i左边的数位和B一样,右边的数位都是9就可以了。

都完成之后,做一下最终检查,注意只有一位数时首位可以为0,A!=B就可以了。

HDU 1730 Northcott Game

我把做错了的也发出来,一种典型的做错了的思路就是:先查Tom和Jerry的初始位置有空隙的行的个数,如果是奇数就是一种情况偶数另外一种情况,这个是不正确的。

正确的思路:我们可以把问题转化为没行空隙的大小就是每堆石子的个数,双方每轮任选一堆,取少则为1多则任意大枚石子,先取完获胜,这就是典型的Nim博弈。所以把每一行空隙大小(abs(a-b)-1)挨个xor,然后看看是不是0就行了。

HDU 4112 Break the Chocolate

利用思维陷阱虐菜的水题(然后就逼视了ˊ_>ˋ),用刀切那个地方不能头脑简单,如果有一个1 1 8的巧克力,只要切3下就可以(半分,放一起再半分,放一起再半分)。可以先从1维入手,发现二进制类似的这个取值规律,然后升维考虑。

 

HDU 4920 Matrix Multiplication

 

上面的T下面的过,开始我还以为是TMD被逗了,直到我看到了这个:

http://blog.csdn.net/a775700879/article/details/11750703

然后我就吓尿了。。。10倍的效率差距

上面的那个,是利用了乘法式子中可以通过调整固定一个值,如果这个值是0就可以剪枝不循环这次的第三重直接往下走了,但是收效甚微。

getchar()的输入挂。。。那货我伺候不来,感觉太玄了没有写。

而下面那个是把原来i,j,k循环中的k拿了出来做了第一重,这样带来的变化是原来第三重循环要跳k次行,现在的话第三重循环不再跳行。多维数组是线性存储的,CPU缓存比较小会经常更新,跳列的话,就很有可能无法利用CPU缓存的优势(注意缓存直连CPU,比内存还要快),因为当跳到下一行的时候,刚才那一行可能就被从CPU缓存中清除了,相当于第三重循环里面没有用到CPU缓存机能。

所以当疯狂访问数组的时候,时间卡的很丧病,就要看看是不把CPU缓存机能给浪费了。

POJ 3740 Easy Finding

搜索题,但是BFS不可以,DFS的话优化还特别寸,写了几个版本都过不了,挺邪乎的。

PS:好长时间没做题,想必是遭了报应了。

ZOJ 3558 How Many Sets III

这个题很不错,卡了我半星期,再加上这个题没有题解,所以这次认真一些,因为不会LaTeX,这个题解写着挺吃力的。

题意
给定一个集合,这个集合的内容一定是{1,2,3,…,n}这个样子,要你求出这个集合的子集中,自成等差数列的有多少个。
举个例子,给出n=4,那么集合为{1,2,3,4},符合要求的子集有{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{2,3,4},{1,2,3,4},一共有9个,输出9就可以了。

AC做法
特别感谢cos65535的题解(日文)。cos65535さん、ありがとうございます!
这里我来说明一下这个做法,对于一个给定的n,一共有1~n-1这些可能的公差,对于每个公差a,形成的等差数列最多有((n-1)/a)+1项,也就是最多可以扣掉(n-1)/a个公差。扣掉b个公差的话,可以最多形成n-ab个等差数列。
在这里举个例子来说明这个,给出一个n=8,求公差为3的情况,那么可以算出对于8,可以扣掉最多2个3保证等差数列的起点不出界。扣掉一个3的时候,形成2项的等差数列,这个等差数列的终点最大为8,也就是{5,8},把这个数列整个减1,这样就得到{4,7}{3,6}{2,5},{1,4},一共是5个(8-1*3),同样地扣掉两个3的时候,形成3项的等差数列,终点最大为8,即{2,5,8},像刚才那样整体减1,得到{1,4,7},一共是2个(8-2*3).2+5=7,这个就是公差3的时候可以组成的等差数列数目了。
这个方法写成公式很简单,就是\sum_{a=1}^{n-1}\sum_{x=1}^{{floor}((n-1)/a)}(n-ax)
但是光有这个公式还不够,因为题目的数据范围是10^9,而上面介绍的那个做法是O(n^2)的时间复杂度,超时不可避啊。
优化需要两次,第一次是当公差一定时,我们可以用等差数列求和公式一次性求出来当前公差可以得到的当差数列数量。第二次是当我们使用完等差数列求和公式后,我们发现得到的式子中出现了n/a的形式,对于一定的na<=n,一共有sqrt(n)n/a值(整数除法的特点),利用这一特点,我们可以只枚举1~sqrt(n-1),我用这个范围枚举的是“最大可扣掉公差数目b”,对于给定的b,它适用于公差从(n-1)/b(n-1)/(b+1)的情况,这里我们改造一下之前等差数列求和优化好的式子,再用一次等差数列求和。同时不要忘了我们的b值只枚举到了sqrt(n-1),每一次算出(n-1)/b其实就是对应的sqrt(n-1)以上的只对应一个公差的b值。

接下来上代码:

 

递推方法
感谢于济凡同学。
对于1~n这个集合的满足要求的子集数目,设定为f(n),对于n-1这个数,小于等于它的数中可以整除它的数的数量设定为g(n),我们有递推关系式f(n)=2f(n-1)-f(n-2)+g(n)
这里说明思路,{1,2,…,n}这个集合,我们可以看成是{1,…,n-1}这个集合组成的全部等差数列,加上{2,…,n}这个集合组成的全部等差数列,但是我们发现{2,…,n-1}这个集合的等差数列算了两次,我们要去掉一次,但是我们还是少了一种情况,就是以1开头,n结尾的等差数列数目,这个就是g(n)了。

 

另一种求等差数列个数的方法
感谢铲神。
已知等差数列的公差、最后一项和首项,藉由等差数列通项公式,我们可以求出可用的等差数列数量。\sum_{a}^{n-1}\sum_{b}\frac{b-a_{1}}{a}其中a是公差b是最后一项a_{1}是首项,现在是n^2的时间复杂度,接下来优化为下面的形式,为n的时间复杂度,但是怎么弄成sqrt(n)的复杂度我实在想不出来了。。。
CodeCogsEqn

 

 

 

Scroll to top