分类 ACM/ICPC 中的文章

ACM – Uva10375 – 组合数公式

有些匪夷所思的题目。。注释部分加上就WA,不加就AC。。 推公式,因为$$C(n,k) = C(n,k-1) * (n-k+1)/k$$ 所以$$ans = \frac{C(n, k)}{C(r, s)}\qquad$$改成递推即可。……

阅读全文

ACM – UVA11029 – 快速幂,快速前幂

后面的三位快速幂即可,但是前面三位不好求。经过分析,每一位都有可能牵扯到前三位的值,因此无法具体的作出判断。 如果使用模方法省去后面的部分,必定会造成误差,随着省略的部分增多,误差积累势必会越来越大。(错了一组数据) 最佳的方法还是数学分析(参考了题解): 分析n,$a = log_{10}^n$,则$n = a ^ {10}$。分解a = i + d,i为正数部分,d为小数部分。那么i影响的仅仅是位数,d影响的则是具体的数字。 这样得到的值是准确的。另外对浮点数取余……

阅读全文

ACM – UVA10820 – 欧拉函数

给出一个Answer(x,y)函数,x,y属于[1,N],$Answer(k_x, k_y)$可以由Answer(x,y)得出,目的是求需要计算多少Answer(x,y)。 就是求1,N范围的欧拉函数的加和。欧拉函数的定义是与N互质的数的个数,所以需要如此计算。一开始没有发现就是求欧拉惭愧惭愧。……

阅读全文

ACM – UVA571 – 模方程

一开始在扩展gcd上想了许久没有办法将得出的数字直接转换成为相应的输出,后来发现就是模方程。 因为不求最佳解,所以直接使用ca*x = n (mod cb)即可。这个方程的解可以覆盖全部的n,因为该方程如果有解,则n是gcd(ca, cb)的倍数。因为ca, cb互质 gcd (ca, cb) = 1,所以明显通过单纯的加满B,向A中倒,然后清空A就可以遍历所有n的解(尽管可能不是最佳解)。 不能是cb*x = n (mod ca),因为n可能大于ca. 如果求最佳解,显然是bfs。当然这到题目也可以dfs来做,不过明显要复杂很多。……

阅读全文

ACM – Uva10717 – lcm+dfs

今天不适合刷题。。。 题意:一个桌子4条腿,每条腿由一种硬币构成,四条腿必须一样长,请问如何最接近给出的标准桌子高度,输出两个最接近的值。 更新两个值的时候错误的判断如果lcm大于h就不再更新了,却没有想到高于h的部分依然可以更新,只是不能更新小于h的部分了。……

阅读全文

ACM – UVa10791 – divide prime

谢天谢地终于过了。 就是求分解质因数后的和,如果是质数那么返回1+n本身。 一开始直接暴力求两个质因数的情况,铁定不对啊。。 第二次发现策略有问题,转为使用枚举质因数,然后发现仅仅是质因数LCM有问题啊。。 第三次没有考虑质数 第四次没有考虑Case 第五次不记得了。 第七次AC,哭了真是。。一定要先分析好题目啊。 ……

阅读全文

ACM – Uva106 – 勾股定理

從維基百科的勾股數條目參考來的通解: 給一個任意數對(X,Y),用以下公式代替 $A = X^2 – Y^2$ $B = 2XY$ $C = X^2 + Y^2$ 得出的A,B,C就是一組勾股數。 若 (X,Y) 恰好互質而且一奇一偶,那麼會得到一組(A,B,C)互質的勾股數。 知道通解後,雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。 按照台湾同胞的题解。 — 勾股数公式也是很神奇的啊。。。 此外还学习了bitset,因为是按位存储,所以比一般的bool来的更加迅速,也更加节省时间。……

阅读全文

ACM – Uva10673 – 扩展gcd

水题一发。。直接使用floor和ceil函数,然后暴力即可。。。 如果使用快速的方法,就是扩展gcd。其中d的初始值没有关系,最后返回的是gcd(a,b). 暴力算法 扩展gcd算法 速度更快,0.012……

阅读全文

ACM – UVA11121 – 进制

题意是由10进制转换成-2进制,但是明显我分析错了,所以写了调了接近一下午的bug。。。 有时间再写正常的题解。 题解: 如果当前数位和输入n符号相同,那么不做处理,如果不同且为1,那么下一位(即左边一位)做+1处理 — 因为下一位是上一位的2倍,就相当于做一个变号处理。……

阅读全文

ACM – 莫比乌斯反演

昨天卡了这道题目,今天特意来看看莫比乌斯反演。 其中,$∑_{d|n}$含义为整除. ACdreamer大大的讲解 看了这篇文章即可= = wikipedia的公式: 以上就是具体的公式,此外,还有线性筛法: 这段代码也是摘自AC大大。我们得到这个东西有什么用? 简单来说,就是简化计算数论函数和的计算的过程,进行加速。 在HDU5212中,给出的题解是: 这道题需要一些莫比乌斯反演、线性筛的知识 定义$f(x)=x∗(x−1)$ 题目所求即为$\Sigma(f(gcd(ai,aj)|i!=j,1≤i,j≤n)$ 先用线性筛求出miu在[1,10000]的函数值 利用莫比乌斯反演公式我们可以$O(vlogv)$暴力求解出函数g(就是$f(n)/miu$)在[1,10000]的函数值,其中g满足: $\Sigma(g(d)|x)$ 这样所求答案即为: $\Sigma(g(d)∗cnt(d)∗cnt(d)|1≤d≤10000)$,其中cnt函数满足: cnt(x)=在a1,a2,..,an中是x的倍数的个数 而cnt的取值也可以$O(vlogv)$暴力计算出 所以总的时间复杂度就是$O(vlogv)$的 就是这样。……

阅读全文