整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

红书《题目与解读》第一章 数学 题解《ACM国际大学生程序设计竞赛题目与解读》

全书目录：《题目与解读》红书 训练笔记目录《ACM国际大学生程序设计竞赛题目与解读》

第一章 数学

1.1 概率

Problem A.Coupons （几何概型，概率）

UVA 10288

Problem

一共有 $n$ 种不同的优惠券，每次得到一个优惠券的概率相同，问期望多少次得到所有 $n$ 种优惠券，以带分数的形式输出。

Solution

方法一：

设 $f[i]$ 表示已经买到 $i$ 个优惠券的期望购买次数。

考虑最后一次购买，若买到的是一个新优惠券，则：

$$f[i]+=(f[i-1]+1)\times \frac{n-(i-1)}{n}$$

若买到的是一个已经买过但不是第 $i$ 个买的优惠券，则：

$$f[i]+=(f[i]+1)\times \frac{i-1}{n}$$​

整理得：

$$f[i]=f[i-1]+\frac{n}{n-i+1}$$​

即：

$$ans=\sum _{i=1}^n\frac{n}{n-i+1}=\sum _{i=1}^n\frac{n}{i}$$

显然最后的答案就是调和级数前缀和。

若数据较大的话可以 $O(1)$ 计算调和级数前缀和：

调和级数 $\sum _{i=1}^{\infty }\frac{1}{n}$ 的极限为 $\ln n+C$，其中 $C=0.57721566490153286060651209$ 是欧拉常数

方法二：

红书上的题解

当前已有 $k$ 种，显然得到新优惠券的概率为 $\frac{n-k}{n}$，显然是几何概型，所以期望是 $\frac{n}{n-k}$，所以答案就是 $\frac{n}{n}+\frac{n}{n-1}+\cdots +\frac{n}{1}=n\times \sum _{i=1}^n\frac{1}{i}$

Hint

数据较大，注意约分，除掉 $\gcd$

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
//#define ll __int128;
typedef long long ll;
const int N = 107;

int n, m;
int up[N], down[N]; 

ll lcm(int a, int b)

	return a / __gcd(a, b) * b;


int get_len(int x)
 
	int len = 0;
	while(x) 
		x /= 10;
		len ++ ;
	
	return len;


void solve()

	ll LCM = 1;
	for(int i = 1; i <= n; ++ i) 
		up[i] = n;
		down[i] = i;
		LCM = lcm(LCM, i);
		
	ll sum = 0;
	for(int i = 1; i <= n; ++ i) 
		sum += n * (LCM / i);
	
	ll d = __gcd(sum, LCM);
	sum /= d;
	LCM /= d;
	if(LCM == 1) 
		cout << sum << endl;
		return ;
	
	ll mo = sum % LCM;
	ll l = sum / LCM;
	for(int i = 1; i <= get_len(l) + 1; ++ i) cout << " ";
	cout << mo << endl;
	cout << l << " ";
	for(int i = 1; i <= get_len(LCM); ++ i) cout << "-";
	puts("");
	for(int i = 1; i <= get_len(l) + 1; ++ i) cout << " ";
	cout << LCM << endl;


signed main()

	while(scanf("%lld", &n) != EOF)  
		solve();
	
	return 0;

Problem B.Generator （KMP，期望，高斯消元）

ZOJ 2619

Problem

给定一个字符串 $S$ 和字符集大小 $n$ 。要求另生成一个字符串，它一开始为空，每次平均且独立地随机生成一个字符集中的字符添加到其末尾，生成出字串 $S$ 时停下，求所生成字符串的长度的期望。

Solution

显然生成的字符串越来越长，每次由 $n$ 种字符选择，那么就有 $i^n$ 种方案数，杂乱无章的无从下手。所以从对答案的贡献角度出发，发现对于答案而言，有用的只有最后生成的字符串 $T$ 的后缀与模式串 $S$ 的匹配长度。因此很多杂乱的字符串实际上对于答案而言是同一种状态，即一共只有 $0\sim L$ 种状态，表示两字符串匹配的长度。

这样就有了清晰的状态，考虑状态如何转移即可。

书中倒推由于都是未知的需要使用高斯消元解方程组，比较麻烦，精度还不能得到保障。我们这里利用一个小技巧，直接正推。利用 KMP ，$O(n)$ 求出失配数组 ${\text{nex}}_{i,j}$（当然要在失配的时候用）

反过来设 f[i] 为从状态 $0$ 到状态 $i$ 期望次数，答案显然就是 f[len]

则可以把原转移方程直接改写为：

$$f[i]=\frac{f[i+1]}{n}+\frac{1}{n}$$

虽然2012年出版的老书了，但是是由三次世界冠军的上海交大ACM队出版的书籍，选择的题目是ACM经典中的经典，书中有非常详细的题解，可以学到很多东西，值得一刷。目录第一部分第一章数学1.1概率1.2代数1.2.... 查看详情

《题目与解读》红书训练笔记目录《acm国际大学生程序设计竞赛题目与解读》

虽然2012年出版的老书了，但是是由三次世界冠军的上海交大ACM队出版的书籍，选择的题目是ACM经典中的经典，书中有非常详细的题解，可以学到很多东西，值得一刷。目录第一部分第一章数学1.1概率1.2代数1.2.... 查看详情

2018acm国际大学生程序设计竞赛上海大都会部分题解(代码片段)

题目链接2018ACM国际大学生程序设计竞赛上海大都会下午午休起床被同学叫去打比赛233然后已经过了2.5h了先挑过得多的做了....A题randx*n次点，每次judge一个点位端点的共线向量数判断是否大于给定x强行rand500次代码#include<bits/stdc... 查看详情

hihocoder1584bounce数学规律（acm-icpc国际大学生程序设计竞赛北京赛区(2017)网络赛）

#1584:Bounce时间限制:1000ms单点时限:1000ms内存限制:256MB描述ForArgo,itisveryinterestingwatchingacirclebouncinginarectangle.Asshowninthefigurebelow,therectangleisdividedintoN×Mgrids,andthecirclefitsexactlyonegrid.Th 查看详情

2018acm国际大学生程序设计竞赛上海大都会赛重现赛afruitninja(代码片段)

传送门题解：给你一堆点问你能不能找出一条直线，使其穿过的点大于n*x。题解：想起某道CF题目，给你一堆点问你能不能找出两条直线使其穿过所有的点。当时就是在一定时限内随机找了两个点，再枚举每个点是否满足，如果... 查看详情

acm-icpc国际大学生程序设计竞赛北京赛区(2017)网络赛题目9:minimum

时间限制:1000ms单点时限:1000ms内存限制:256MB描述Youaregivenalistofintegersa0,a1,…,a2^k-1.Youneedtosupporttwotypesofqueries:1.OutputMinx,y∈[l,r] {ax?ay}.2.Letax=y.输入ThefirstlineisanintegerT,indicati 查看详情

2021“数维杯”国际大学生数学建模竞赛a题思路

一、思路及完整代码思路下载链接：2021“数维杯”国际大学生数学建模竞赛A题思路二、题目三、数维杯国际大学生数学建模挑战赛数维杯国际大学生数学建模挑战赛 查看详情

2021“数维杯”国际大学生数学建模竞赛d题思路

一、思路及完整代码思路下载链接：2021“数维杯”国际大学生数学建模竞赛D题思路二、题目三、数维杯国际大学生数学建模挑战赛数维杯国际大学生数学建模挑战赛 查看详情

2021“数维杯”国际大学生数学建模竞赛c题思路

一、思路及完整代码思路下载链接：2021“数维杯”国际大学生数学建模竞赛C题思路二、题目三、数维杯国际大学生数学建模挑战赛数维杯国际大学生数学建模挑战赛 查看详情

2021“数维杯”国际大学生数学建模竞赛b题思路

一、思路及完整代码思路下载链接：2021“数维杯”国际大学生数学建模竞赛B题思路二、题目三、数维杯国际大学生数学建模挑战赛数维杯国际大学生数学建模挑战赛 查看详情

hihocoder1586acm-icpc国际大学生程序设计竞赛北京赛区(2017)网络赛-题目9:minimum线段树

https://hihocoder.com/problemset/problem/1586线段树操作，原来题并不难。。。。。要求乘积最小只要求区间内最大值、最小值和绝对值小的数，再判断min,max正负就行了。  1#include<iostream>2#include<cstdio>3#include<cstring>4#inc... 查看详情

2021-2022-1acm集训队每周程序设计竞赛-问题e:数学！-题解(代码片段)

传送门数学！题目描述输入描述输出描述样例一输入输出样例二输入输出提示题目分析AC代码数学！CMP跳蛙剪切数学？数学！逃离时间限制：1秒空间限制：128M题目描述给你两个长度分别为nnn和mmm的数组SSS... 查看详情

2021-2022-1acm集训队每周程序设计竞赛-问题d:数学？-题解(代码片段)

传送门分割题目描述输入描述输出描述样例一输入输出样例二输入输出提示题目分析AC代码分割CMP跳蛙剪切数学？数学！逃离时间限制：1秒空间限制：128M题目描述Tisfy:这是一道数学题？给你长度为nnn的数组aaa... 查看详情

acm-icpc国际大学生程序设计竞赛北京赛区(2017)网络赛

题目1:VisitingPekingUniversity时间限制:1000ms单点时限:1000ms内存限制:256MB描述Mingisgoingtotravelforndaysandthedateofthesedayscanberepresentedbynintegers:0,1,2,…,n-1.Heplanstospendmconsecutivedays（2≤m≤n）inBeijing.Dur 查看详情

[高数][高昆轮][高等数学上][第一章-函数与极限]03.函数的极限

例题6 习题1-3:2 4 10(记住直接使用) 查看详情

[高数][高昆轮][高等数学上][第一章-函数与极限]05.极限的运算法则

      查看详情

[高数][高昆轮][高等数学上][第一章-函数与极限]02.数列的极限

    例题3 习题1-2：2368 查看详情

现代软件工程第一章概论练习与讨论王旭阳（2,3,4）

2,34。正如题目所说的，写程序是个人行为，在做像ACM之类的题目时，自己根据题目要求写出若干行代码，利用某个算法完成题目要求，仅仅输入输出就足以，这就可以说是一个简单的程序，算是完成了一个程序。而一个软件是... 查看详情