Foreverzeus的ACM算法模板大全

下载需积分: 50 | PDF格式 | 4.16MB | 更新于2024-07-21 | 25 浏览量 | 举报

"foreverzeus大木板 ACM模板" 这篇文档是ACM竞赛编程的模板，包含了一系列关于算法和数学工具的详细总结，适合于准备ACM或ICPC等算法竞赛的选手。以下是对其中主要知识点的详细说明： 1. **数论**： - **最大公约数（GCD）和最小公倍数（LCM）**：在求解整数关系时常用到的基础工具。 - **快速筛选素数**：一种高效的空间优化的素数筛法，适用于大量素数判断。 - **扩展欧几里得算法**：求解线性不定方程、模线性方程、求逆、中国剩余定理以及分数取模等问题。 - **浮点库函数<math>**：用于处理浮点数计算的库函数，可能包括开方、指数、对数等操作。 - **快速幂取模**：快速计算一个数的幂并取模，是算法中的常用技巧。 - **分解质因数**：将一个数分解为其质因数的乘积。 - **欧拉函数**：计算小于等于给定数n的正整数中与n互质的数的数量。 - **阶乘的总结**：包括阶乘0的个数、阶乘右边第一非0的数、阶乘的位数以及判断是否能整除阶乘。 - **母函数**：在序列和问题中，通过母函数来求解特定类型的序列。 2. **约瑟夫环问题**：一种经典的动态规划问题，涉及环形结构的处理。 3. **容斥原理**：用于统计不重叠集合元素的个数，如计算有无交集的子集的总数。 4. **排列组合**：基础的组合数学概念，用于计算特定排列或组合的数量。 5. **Babystep, Giantstep**：解决模意义下大整数的平方根问题。 6. **Polya计数**：用于统计具有某种性质的对象的计数方法。 7. **Rabin-Miller和Pollard-rho算法**：两种著名的素性测试方法。 8. **鸽笼原理**：基本的抽屉原理，用于证明存在至少一个情况的发生。 9. **Stirling数**：在组合数学中用于计数问题，有第一类Stirling数和第二类Stirling数。 10. **快速确定C(n,k)的奇偶性**：在不需要计算完整值的情况下确定组合数的奇偶性。 11. **素数表**：预先生成素数列表，以提高查询效率。 12. **暴力求循环节**：用于计算循环小数的循环节长度。 13. **负权数**：处理包含负权边的图算法问题。 14. **C(n+m,m)%M**：快速计算组合数模M的值。 15. **三分极值**：在一定范围内寻找极大值或极小值的算法。 16. **高精度**：处理超过标准数据类型范围的大整数运算。 17. **Printf格式表**：用于控制输出格式，例如精度、宽度等。 18. **位运算**：在位级别进行计算，如位与、位或、位异或和位移位，常用于优化算法。 **图论**部分涵盖了图算法的核心知识点： 1. **Dijkstra算法**：单源最短路径算法，适用于没有负权边的图。 2. **Bellman-Ford算法**：可以处理负权边的最短路径问题。 3. **SPFA算法**：一种基于队列的改进Dijkstra算法，处理负权边但可能出现误判。 4. **Floyd-Warshall算法**：求解所有顶点间的最短路径。 5. **最小生成树**：Kruskal和Prim算法用于找到无向图的最小生成树。 6. **欧拉回路与欧拉通路**：在图中寻找路径，满足所有边恰好经过一次或两次。 7. **拓扑排序**：对有向无环图（DAG）进行线性排序。 8. **二分图**：图中每条边连接两个不同颜色的节点，用于匹配问题。 9. **Kuhn-Munkres算法（KM算法）**：解决二分图的最大匹配问题。 10. **最近公共祖先（LCA）**：在树形结构中找到两个节点的最近公共祖先。 11. **强连通分量**：在有向图中，每个节点都可以到达其他所有节点的子图。 12. **无向图的连通问题**：涉及割点和桥的概念，用于分析图的连通性。这个模板为ACM竞赛提供了全面的参考资料，涵盖了算法竞赛中常见的数论、图论问题以及部分组合数学问题，对于准备比赛或者提高编程能力都非常有帮助。

展开

2010 04 人生已经太匆匆我好害怕总是泪眼朦胧… Foreverzeus

16 / 256

res2 = res[0][(num2 - num5) % 4];

else res2 = 1;

res3 = res[1][num3 % 4];

res7 = res[2][num7 % 4];

res9 = res[3][num9 % 4];

ans = res2 * res3 * res7*res9;

ans = ans % 10;

printf("%5d -> %d\n", n, ans);

}

附：再观察 poj 1150 The Last Non-zero Digit

求的是 P=C(n,m)中的最后非零位

因为 P(n,m)实际上等于 n! / (n-m)!

故代码可以这样写

int main()

{

int n,m;

while (scanf("%d %d",&n,&m)!=EOF)

{

int num2=get2(n)-get2(n-m);

int num5=get5(n)-get5(n-m);

int num3=fcount(n,3)-fcount(n-m,3);

int num7=fcount(n,7)-fcount(n-m,7);

int num9=fcount(n,9)-fcount(n-m,9);

int res2,res3,res7,res9,ans=1;

if(num5>num2) {printf("5\n");continue;}//修正 num5大于

num2 在此处是有可能出现的

if (num2>num5)

res2=res[0][(num2-num5)%4];

else res2=1;

res3=res[1][num3%4];

res7=res[2][num7%4];

res9=res[3][num9%4];

ans=res2*res3*res7*res9;

ans=ans%10;

printf("%d\n",ans);

}

值得注意的是有时候输入可能很大比如 zoj 的 1222

此时可以利用下面这个模板求最后非 0 位

int lastdigit(char* buf){

const int

mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};

int len=strlen(buf),a[MAXN],i,c,ret=1;

if (len==1)

return mod[buf[0]-'0'];

for (i=0;i<len;i++)

a[i]=buf[len-1-i]-'0';

for (;len;len-=!a[len-1]){

ret=ret*mod[a[1]%2*10+a[0]]%5;

for (c=0,i=len-1;i>=0;i--)

c=c*10+a[i],a[i]=c/5,c%=5;

}

return ret+ret%2*5;

}

③：求 n！的位数

如何计算 n!的位数

http://162.105.81.212/JudgeOnline/problem?id=1423

int n;

const double e = 2.7182818284590452354;

const double pi = 3.141592653589793239;

double f( int a )

{

return log10( sqrt( 2 * pi * a ) ) + a * log10( a / e );

}

int main()

{

int cas, ans;

double i, s;

scanf( "%d", &cas );

while( cas-- )

{

scanf( "%d", &n );

if( n < 100000 )

{

for( s=0, i=1; i<=n; i++ )

s += log10( i );

}

else s = f( n );

ans = (int)s;

if( ans <= s )

ans++;

printf( "%d\n", ans );

}

2010 04 人生已经太匆匆我好害怕总是泪眼朦胧… Foreverzeus

17 / 256

return 0;

}

④：判断数值 m 是否可以整除 n!

此时可对 m 先分解质因数得到质因子 p[i]，和质因子个数 e[i]

那么此时再求阶乘中的每个 p[i]因子的个数 c 若出现 c 否则则

可以.例题：zoj 1850 Factovisors

1.9:母函数

入门：若有 1 克、2 克、3 克、4 克的砝码各一枚，能称出哪几种重量？

各有几种可能方案？

如何解决这个问题呢？考虑构造母函数。

如果用 x 的指数表示称出的重量，则：

1 个 1 克的砝码可以用函数 1+x 表示，

1 个 2 克的砝码可以用函数 1+x2 表示，

1 个 3 克的砝码可以用函数 1+x3 表示，

1 个 4 克的砝码可以用函数 1+x4 表示

几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：

(1+x)(1+x

)(1+x

)

=(1+x+x

)(1+x

)

=1+x+x

+2x

1：基础 ——整数划分

2 ：hdu 1398 Square Coins

有 n 中币每种都是平方数比如 1，4，9，16....(最大只到 17^2)

问组成 n 的情况有多少种可能；那么此时增量就是 t*t；结果 res.c[n]的

系数既是答案；

G(x)=(1+x+x

+„)(1+x

+„)„

3：有权值为 1 2 5 的三种价格其数量分别为 num[1],num[2],num[3]问其

最少不能组成的价格是多少；



󰇛



󰇜

󰇛















󰇟



󰇠

󰇜󰇛󰇛



󰇜

󰇛



󰇜󰇛



󰇜󰇟󰇠󰇜󰇛



󰇛



󰇜󰇛



󰇜󰇟󰇠󰇜

要注意各变量的控制；

4：poj 3046 Ant Counting

有 n 种不同总数的蚂蚁 m 群问组成不同的 s 到 t

组能有多少中可能结果取后六位数

3 sets with 1 ant: {1} {2} {3}

5 sets with 2 ants: {1,1} {1,2} {1,3} {2,2} {2,3}

5 sets with 3 ants: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}

3 sets with 4 ants: {1,2,2,3} {1,1,2,2} {1,1,2,3}

1 set with 5 ants: {1,1,2,2,3}

这是一个特殊的母函数

(1+x+x^2+...+x^num[1])(1+x+...+x^num[2])(1+x+...+x^num[3])...(1+x+...+x^

num[n])

增量也为 1；

统计时只要累加：for (i = s; i <= t; i++){ans += res.c[i];ans %= mod;}

*模板 Gene存一个多项式 c为x^i系数长度为len

struct Gene {

int c[N], len;

Gene() {

}

Gene(int n) {

memset(c, 0, sizeof (c));

len = n;

for (int i = 0; i <= n; i++)//具体情况而定 c[i]表示的是

指数为i系数不存在要赋值为0

c[i] = 1;

}

};

*其中t为增量根据不同情况增量不同； a.len和b.len分别为多项式的

末端

Gene mul(Gene a, Gene b, int t) {

int i, j, k;

int len = a.len + b.len;

Gene res;

memset(res.c, 0, sizeof (res.c));

res.len = len;

for (i = 0; i <= a.len; i++)

for (j = 0; j <= b.len; j += t) {

res.c[i + j] += a.c[i];

}

return res;

}

void solve() {

int i;

Gene res; //当前式子的长度到达x^num[i];

res.len = num[1];

for (i = 0; i <= n; i += t)

res.c[i] = 1; //对系数存在的赋值为1

Sample Input

3 5 2 3

Sample Output

2010 04 人生已经太匆匆我好害怕总是泪眼朦胧… Foreverzeus

18 / 256

for (i = 2; i <= n; i++) {

Gene tmp;

memset(tmp.c, 0, sizeof (tmp.c));

tmp.len = num[i]; //当前式子的长度到达x^num[i];

res = mul(res, tmp);

}

问题 3：

Gene mul(Gene a, Gene b, int t)

{

int i, j, k,len = a.len + b.len;

Gene res(m);

memset(res.c, 0, sizeof (res.c));

for (i = 0; i <= m; i++)//不能超过num[t]*dk[t]

for (j = 0; j <= num[t] * dk[t] && i + j <= m; j += dk[t])

res.c[i + j] += a.c[i];

return res;

}

int main()

{

int i, j, k, a;

while (scanf("%d %d %d", &num[1], &num[2], &num[3]) != EOF)

{

if (!num[1] && !num[2] && !num[3]) break;

m = num[1] + num[2]*2 + num[3]*5; //总价钱

Gene res(num[1]); //能够组成num[1]个

for (i = 2; i <= 3; i++)

{

Gene tmp;

memset(tmp.c, 0, sizeof (tmp.c));

tmp.len = m;

res = mul(res, tmp, i); //增量为i

}

for (i = 1; i <= m; i++)

if (res.c[i] == 0) break;

cout << i << endl;

}

1.10:约瑟夫环问题

问题描述：n 个人（编号 1~(n))组成一个环，从 1 开始报数，报到(m)的

退出，剩下的人继续从 1 开始报数。求胜利者的编号；当 m 为 2 有特殊

解法；

* 复杂度O(n)同时输出每次出列人数

* n人数m步长k为起始数

* 5 1 3 即为：从开始数每数到则出列

* */

int main() {

int i, p, t;

while (cin >> n) {

scanf("%d %d", &k, &m);

i = 0;

while (++i <= n) {

p = i * m;

while (p > n) {

p = p - n + (p - n - 1) / (m - 1);

}

if (k == 1) t = p;

else t = (p + k + n - 2) % n + 1;

cout << t << endl;

}

return 0;

}

*复杂度O(n)

*参数分别为：人数，出圈步长;

*其中n为人数，m为出圈步长，k为第一个开始数的人(不出圈的)

*注意题目n,m,k的范围不排除输入有可能m大于n，k大于m

LLD Josephus(LLD n, LLD m, LLD k) {

LLD t=0;

for (LLD i = 1; i <= n; i++)

t = (t + m - 1) % i + 1;

return (t+k-2)%n+1; //返回最后一人的位置

}

* 对于某些题目输入是n，m，t ，t为第一个出圈的人，于是可以先倒

推出第一个数的人为：k=(n*10000+t-m)%n+1;

* 所乘以的数据由题目规模决定，防止越界和出现负数。此时便可调用

函数Josephus（n,m,k）

* */

*复杂度O(min(n,m))

* k = (k + m - 1) % i + 1，可以看出，当i比较大而k+m-1比较小的时

2010 04 人生已经太匆匆我好害怕总是泪眼朦胧… Foreverzeus

19 / 256

候，k就处于一种等差递增的状态，这个等差递增的过程并不是必须的，

可以跳过。

* 我们设一中间变量x，列出如下等式：

* k + m * x - 1 = i + x

* 解出x，令k = k + m * x，将i + x直接赋值给 i，这样就跳过了中

间共x重的循环，从而节省了等差递增的时间开销。

* 可是其中求出来的x + i可能会超过n，这样的结果事实上已经告诉我

们此时可以直接结束算法了，即：

* k = k + m * (n - i) ;

* i = n;

* 结束。

* 另外对于m = 1的情况可以单独讨论：

* 当k == 1时，最终结果就是n；

* 当k != 1时，最终结果就是(k + n - 1) % n。

//复杂度：当n>m的时候为O(m), 当m<=n时为O(n) 适用于n很大的时候

LLD Josephus(LLD n, LLD m, LLD pos) { //分别为：人数（从1到n），

出列的间隔（从当前位置开始从1数到m的人出列），起使报数位置

if (m == 1)return n;

if (n == 1)return 1;

LLD k = 0, i, x;

for (i = 2; i <= n; i++) {

x = (i - k - 1) / m;

if (i + x <= n) {

i += x;

k += m * x;

}

else {

k += m * (n - i);

i = n;

}

if (i <= n)k = (k + m) % i;

}

return (k + pos - 1) % n + 1;

}

int main() {

LLD n, m;

while(cin>>n>>m){

LLD t = Josephus(n, m, 1);

cout << t << endl;

}

//poj 1781 in danger

//一群人围成一个圈每数 2 就出一个人问最后留下的是第几个人

//数据量大输入为 xyez 表示 xy 后面有几个 0

//方法：装换为 2 进制将人数 n 用 2 进制表示位移一位就是答案

int Josephus(int n)

{

int i = 1;

while(i <= n)

i<<=1;

return ( (n - (i>>1) )<<1) + 1;

}

1.11:容斥原理

容斥原理：

在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计

算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑

重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再

把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，

这种计数的方法称为容斥原理。

两个集合的容斥关系公式：A∪B = A+B – A∩B

三个集合的容斥关系公式：A∪B∪C = A+B+C – A∩B – B∩C – C∩A

+ A∩B∩C

*容斥原理

*求在到m中能被p[0]或p[1]或p[2]...整除的数有多少个 pnum为p的个

数，结果保存在ans中,初始化ans为

*p为升序排列,注意数组的起始点是从0开始的

*根据公式A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C

#define LLD long long

int p[N];

int n, m, pnum;

LLD ans;

*根据公式A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C

*其中s为标记此次是加上还是减去

void dfs(int t, int k, int s) {

int tmp, i;

for (i = k; i < pnum; i++) {

tmp = lcm(t, p[i]); //此处是两数的最小公倍数

if (tmp == 0 || t > m) return;

if (s % 2) ans -= m / tmp;

2010 04 人生已经太匆匆我好害怕总是泪眼朦胧… Foreverzeus

20 / 256

else ans += m / tmp;

dfs(tmp, i + 1, s + 1);

}

int main() {

int i, j;

while (scanf("%d %d", &n, &m) != EOF) {

for (i = 0; i < n; i++)

scanf("%d", &p[i]);

ans = 0;

pnum = n;

dfs(1, 0, 0);

cout << ans << endl;

}

1-n 中与 1-m 中 gcd(i,j)=k 的个数

（k=0 特判）

hdu1695 GCD 求 1 到 n 中与 1 到 m 中 gcd(i,j)=k 的数的个数（k=0 特判）

hdu 2841Visible Trees 求在 n*m 的矩阵中站在(0,0)能看到的树有多少棵

(该问题转化为在该矩阵中存在多少个点 gcd（i,j）==1 的数的个数)

//prime_factor()传入n, 返回不同质因数的个数

//p存放质因数e存放对应质因数的个数

const int N = 100055;

bool pr[N];

int p[100], e[100]; //p质因数 e个数

int plist[N];

int n, m, tpr, pnum; //tpr为质因数的个数

LLD ans, res;

void init()//素数

int prime_factor(int n, int *p, int *e)//分解质因数

*若n是质数p的k次幂，

* φ(n)=p^k-p^k-1=(p-1)*p^(k-1)因为除了p的倍数

* 外，其他数都跟n互质。

* 欧拉函数是积性函数，即是说若m,n互质，

* φ(n*m)= φ(n)* φ(m);

* 返回1到t中与t互质的数的个数

LLD Euler(int t, int &len) {

int i, j;

LLD tmp, ans = 1, res;

len = prime_factor(t, p, e);

for (i = 0; i < len; i++) {

tmp = 1;

t = e[i] - 1;

while (t--) {

tmp *= p[i];

}

res = tmp * (p[i] - 1);

ans = ans*res;

}

return ans;

}

void dfs(int t, int k, int s) {

int tmp, i;

for (i = k; i < pnum; i++) {

tmp = lcm(p[i], t);

if (tmp == 0 || t > m) return;

if (s % 2) ans -= m / tmp;

else ans += m / tmp;

dfs(tmp, i + 1, s + 1);

}

int main() {

// freopen("R:\in.txt","r",stdin);

int T, i, j, k, tmp;

int cases = 1;

init();

scanf("%d", &T);

while (T--) {

scanf("%d %d %d %d %d", &i, &n, &i, &m, &k);

if (k == 0) {//注意特判

printf("Case %d: 0\n", cases++);

continue;

}

n = n / k;

m = m / k;

if (n == 0 || m == 0) {

printf("Case %d: 0\n", cases++);

continue;

}

*其中n和m去较小的一个

*tmp = Euler(i, pnum);dfs(1, 0, 0);求出ans既是1到m中整

除i的数的个数那么m-ans即为gcd(i,j)（j为1到m）的数的个数

*又其中(i,j)和(j,i)视为相同一对，故此时再减去tmp(即时1

剩余255页未读，继续阅读

身份认证购VIP最低享 7 折!

30元优惠券

_Cade_

粉丝: 164

Foreverzeus的ACM算法模板大全

上海交大ACM模板_上海交大ACM模板_ACM模板_

杭电ACM模板（属于杭电的）

acm模板_acm模板

ACM模板-f_zyj.zip_ACM模板_ACM模板-f_zyj_CSDN积分_acm必备模板_f_zyj ACM

浙江大学的ACM模板

ACM模板(浙大).zip_浙江大学ACM算法模板

浙江大学 ACM 模板

上海交大ACM模板.zip_上海交大ACM模板_上海大学

ACM模板大全（各个高校的ACM模板）

kuangbin的ACM模板（新）_ACM模板_ACM算法总结_

最新资源