ACM

Atcoder - Chocolate Bar(简单几何)

Atcoder - Chocolate Bar(简单几何)
题意:给出一个由很多格子组成的矩形的宽高(2≤H,W≤105),然后将其分成三个矩形,求最大的矩形和最小的矩形最小的差值。题解:分成三个矩形只有四种情况,三份横着切,三份竖着切;一份横,两份竖着,一份竖着,两份横着。但是我们要是将宽高转换一下其实就两种情况。然后需要注意的就是一二开的情况,直接取中间剖分有可能不能得到最小的差值,还要往左右挪一挪才能得到最优解。代码:#include &l... 继续阅读 »
ACM

HDU - 6069 Counting Divisors(素数筛法+技巧质因数分解)

HDU - 6069 Counting Divisors(素数筛法+技巧质因数分解)
题目的意思是:给出l,r, k,求l到r区间内每个数的k次方的约数个数的和,再对998244353取余。这题用到的技巧还真是多啊,乱搞暴力肯定GG。首先我们来看看怎么求解约数的个数。一个数可以分解成多个质数的的乘积。假设p为质数(1不是质数啊,怎么每次都讲不听呢),所以有:n = p1^c1*p2^c2*p3^c3*......*pm^cm根据乘法原理:n的约数的个数就是(c1+1)(c2+1)(... 继续阅读 »
ACM

HDU - 5776 sum(前缀和、抽屉原理)

HDU - 5776 sum(前缀和、抽屉原理)
题目的意思是,给你一段序列,问你他的一段子序列能否被一个数整除。我们可以来看一个序列:a0,a1,a2......am......an......aq我们假设从a0到am的和模x为1,如果a0到an的和模x也为1,那么从am+1到an的和就能被x整除了。代码:StatusAcceptedTime62msMemory2348kBLength533LangG++#include <io... 继续阅读 »