模板
本模板用于2019年5月安徽省程序设计竞赛
起手
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
return b == 0 ? a : gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a*b/gcd(a,b);
}
ll ksm(ll x,ll n,ll mod){
ll res = 1;
x = x % mod;
while(n > 0){
if(n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
int main(){
freopen("in","r",stdin);
clock_t st,ed;
st = clock();
/*………………*/
ed = clock();
printf("Use Time:%f\n",((double)(ed - st)/CLOCKS_PER_SEC));
return 0;
}
一、深搜的剪枝策略
1.找数字
给一个数$ n$,让你找出一个只由 $0,1 $组成的十进制数 $m$,要求这个正整数 $m $可以被$ n $整除
/*
input:
2
output:
10
对于输入整数 n 的每一个值,输出 m 的相应值,保证有一个数字长度小于 19 位的数字。如果有一个给定值 n 有多个解,其中任何一个都是可以接受的
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll f;
void dfs(ll num,ll flag,ll step){
if(m) return ;
if((num % n == 0) && (num != 0)){
m = num;
return ;
}
if(step == 19){
return ;
}
dfs(num*10, 0, step + 1);
if(flag == 0){
dfs(num+1, 1, step);
}
}
int main(){
cin>>n;
m = 0;
dfs(0, 0, 1);
cout<<m<<endl;
return 0;
}
2.全排列
输入$n$,打印输出$1-n$的全排列
/*
input:
3
output:
6
123
132
213
231
312
321
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll vis[15];
ll ans[15];
void dfs(ll step){
//输出要求满足
if(step == n + 1){
for(ll i=1;i<=n;i++){
printf("%lld",ans[i]);
}
printf("\n");
return ;
}
for(ll i=1;i<=n;i++){
if(!vis[i]){
vis[i] = 1;
ans[step] = i;
dfs(step + 1);//取了
vis[i] = 0;
}
}
}
ll cnt;
int main(){
scanf("%lld",&n);
cnt = 1;
for(ll i=2;i<=n;i++){
cnt *= i;
}
printf("%lld\n",cnt);
dfs(1);
return 0;
}
3.蒜头君的旅游计划
$n$个城市,$n*n$的矩形表示每两个城市之间的火车花费,求从$1$号城市把所有景点旅游一遍并且回到$1$号城市的最小花费
/*
input:
4
0 1 1 1
1 0 2 1
5 5 0 6
1 1 3 0
output:
8
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int G[20][20];
bool vis[20];
int ans = 1000000000;
int n;
void dfs(int u, int cnt, int sum){
if(sum >= ans){
return ;
}
if(cnt == n){
ans = min(ans, sum + G[u][1]);
}
vis[u] = 1;
// 枚举当前城市可能到达的下一个城市
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i, cnt + 1, sum + G[u][i]);
}
}
vis[u] = 0;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>G[i][j];
}
}
dfs(1, 1, 0);
cout<<ans<<endl;
return 0;
}
4.正方形
首先输入一个整数 $n(4 \le n \le 20)$,表示木棍数量,接下来输入 $n $根木棍的长度 $p_i(1 \le p_i \le 10000)$
如果蒜头君能拼出正方形,输出"Yes",否则输出"No"。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int sum = 0;
int s1;
int le[4] = {0}, a[21], b[21] = {0};
bool ok = 0;
void dfs(int x, int j){
if(x == 4){
ok = 1;
return ;
}
if(ok){
return ;
}
if(le[x] > s1){
return ;
}
if(le[x] == s1){
dfs(x + 1, 1);
}else{
for(int f=j;f<=n;++f){
if(b[f] == 0){
b[f] = 1;
le[x] += a[f];
dfs(x, f + 1);
le[x] -= a[f];
b[f] = 0;
}
}
}
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum += a[i];
}
s1 = sum / 4;
if(sum % 4 != 0){
cout << "No";
return 0;
}
dfs(1, 1);
if(ok){
cout<<"Yes";
}else{
cout<<"No";
}
}
二、最短路径算法
1.$Dijkstra$算法
解决单源最短路径问题常用 Dijkstra 算法,用于计算一个顶点到其他所有顶点的最短路径。Dijkstra 算法的主要特点是以起点为中心,逐层向外扩展(这一点类似于 bfs,但是不同的是,bfs 每次扩展一个层,但是 Dijkstra 每次只会扩展一个点),每次都会取一个最近点继续扩展,直到取完所有点为止。
注意:Dijkstra 算法要求图中不能出现负权边。
①、$Dijkstra$算法流程
我们定义带权图$ G $所有顶点的集合为$ V$,接着我们再定义已确定从源点出发的最短路径的顶点集合为$ U$,初始集合 $U $为空,记从源点$ s $出发到每个顶点$ v $的距离为 $dist_v $,初始 $dist_s$=0。接着执行以下操作:
-
从 $V−U $中找出一个距离源点最近的顶点$v$,将$v$加入集合$ U$。
-
并用 $dist_v$和顶点 $v $连出的边来更新和 $v $相邻的、不在集合 $U$ 中的顶点的 $dist$,这一步称为松弛操作。
-
重复步骤 1 和 2,直到 $V=U$或找不出一个从$ s$ 出发有路径到达的顶点,算法结束。
如果最后 $V \neq U$,说明有顶点无法从源点到达;否则每个$ dist_i$表示从 $s$ 出发到顶点$ i $的最短距离。
Dijkstra 算法的时间复杂度为$ \mathcal{O}(V^2)$,其中 $V$ 表示顶点的数量。
Dijkstra 是解决无负边权的图的单源最短路问题,经常使用邻接表存储。
不优化的时间复杂度是 $O(V^2 + E)$
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, fail;
edge() {}
edge(int _v, int _w, int _fail) {
v = _v;
w = _w;
fail = _fail;
}
} e[M << 1];
int head[N], len;
void init() {
memset(head, -1, sizeof(head));
len = 0;
}
void add(int u, int v, int w) {
e[len] = edge(v, w, head[u]);
head[u] = len++;
}
void add2(int u, int v, int w) {
add(u, v, w);
add(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void dijkstra(int u) {
memset(vis, false, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
for (int i = 0; i < n; ++i) {
int mi = inf;
for (int j = 1; j <= n; ++j) {
if (!vis[j] && dis[j] < mi) {
mi = dis[u = j];
}
}
if (mi == inf) {
return;
}
vis[u] = true;
for (int j = head[u]; ~j; j = e[j].fail) {
int v = e[j].v;
int w = e[j].w;
if (!vis[v] && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
}
}
}
}
int main() {
init();
int u, v, w;
cin >> n >> m;
while (m--) {
cin >> u >> v >> w;
add2(u, v, w);
}
dijkstra(1);
cout << dis[n] << endl;
return 0;
}
②、基于小根堆优化的$Dijkstra$算法
用一个set来维护点的集合,这样的时间复杂度就优化到了 $\mathcal{O}((V+E)\log V)$,对于稀疏图的优化效果非常好
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
typedef pair<int, int> PII;
set<PII, less<PII> > min_heap;
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
bool dijkstra(int s) {
// 初始化 dist、小根堆和集合 U
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
min_heap.insert(make_pair(0, s));
dist[s] = 0;
for (int i = 0; i < n; ++i) {
if (min_heap.size() == 0) { // 如果小根堆中没有可用顶点,说明有顶点无法从源点到达,算法结束
return false;
}
// 获取堆顶元素,并将堆顶元素从堆中删除
set<PII, less<PII> >::iterator iter = min_heap.begin();
int v = iter->second;
min_heap.erase(*iter);
vst[v] = true;
// 进行和普通 dijkstra 算法类似的松弛操作
for (int j = p[v]; j != -1; j = e[j].next) {
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
// 先将对应的 pair 从堆中删除,再将更新后的 pair 插入堆
min_heap.erase(make_pair(dist[x], x));
dist[x] = dist[v] + e[j].w;
min_heap.insert(make_pair(dist[x], x));
}
}
}
return true; // 存储单源最短路的结果
}
③、基于优先队列优化的$Dijkstra$算法
我们在 $node $节点里面记录对应的点的最短路,然后每次更新一个点的最短路后都把这个点压入到优先队列里面(不管之前有没有被压入到队列里面),这样就一定能够保证优先队列对的性质不会改变
这个代码的时间复杂度实际上会比用真正的堆要慢一点,因为有的点可能会入队多次,但是每一条边最多导致一次入队,所以这个算法的时间复杂度为 $\mathcal{O}(E\log E)$。其中$ E $为边的数量。
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
struct node {
int u;
int dist;
node(int _u, int _dist) : u(_u), dist(_dist) {}
bool operator < (const node &x) const {
return dist > x.dist;
}
}; // 记录点的结构体
bool dijkstra(int s) {
// 初始化 dist、小根堆和集合 U
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
priority_queue<node> min_heap;
dist[s] = 0;
min_heap.push(node(s, 0));
while (!min_heap.empty())
// 获取堆顶元素,并将堆顶元素从堆中删除
int v = min_heap.top().u;
min_heap.pop();
if (vst[v]) {
continue;
}
vst[v] = true;
// 进行和普通 dijkstra 算法类似的松弛操作
for (int j = p[v]; j != -1; j = e[j].next) {
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
dist[x] = dist[v] + e[j].w;
min_heap.push(node(x, dist[x]));
}
}
}
return true;
}
2.$SPFA$算法
SPFA(Shortest Path Faster Algorithm)算法是单源最短路径的一种算法,通常被认为是 Bellman-ford 算法的队列优化,在代码形式上接近于宽度优先搜索 BFS,是一个在实践中非常高效的单源最短路算法。
①、$SPFA$算法流程
在 $SPFA$ 算法中,使用 $d_i$表示从源点到顶点$i$的最短路,额外用一个队列来保存即将进行拓展的顶点列表,并用 $inq_i$来标识顶点$i$是不是在队列中。
1.初始队列中仅包含源点,且源点 $s$ 的 $d_s=0$。
2.取出队列头顶点 $u$,扫描从顶点 $u$ 出发的每条边,设每条边的另一端为 $v$,边$<u,v>$ 权值为 $w$,若 $d_u+w<d_v$,则
-
将 $d_v$修改为 $d_u+w$
-
若 $v$ 不在队列中,则
-
将 $v $入队
3.重复步骤 2 直到队列为空
最终$ d$ 数组就是从源点出发到每个顶点的最短路距离。如果一个顶点从没有入队,则说明没有从源点到该顶点的路径。
$SPFA$ 的空间复杂度为$ \mathcal{O}(V)$。如果顶点的平均入队次数为 $k$,则 $SPFA $的时间复杂度为 $\mathcal{O}(kE)$O,对于较为随机的稀疏图,根据经验 $k$ 一般不超过 4。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
struct edge{
int v, w, fail;
edge(){}
edge(int _v, int _w, int _fail){
v = _v;
w = _w;
fail = _fail;
}
}e[M << 1];
int head[N], len;
void init(){
memset(head, -1, sizeof(head));
len = 0;
}
void add(int u, int v, int w){
e[len] = edge(v, w, head[u]);
head[u] = len++;
}
void add2(int u, int v, int w){
add(u, v, w);
add(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void spfa(int u){
memset(vis, false, sizeof(vis));
vis[u] = true;
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
queue<int> q;
q.push(u);
while(!q.empty()){
u = q.front();
q.pop();
vis[u] = false;
for(int j = head[u];~j;j = e[j].fail){
int v = e[j].v;
int w = e[j].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
if(!vis[v]){
q.push(v);
vis[v] = true;
}
}
}
}
}
int main() {
init();
int u, v, w;
cin>>n>>m;
while(m--){
cin>>u>>v>>w;
add2(u, v, w);
}
spfa(1);
cout<<dis[n]<<endl;
return 0;
}
②、$SPFA$判断负环
$Dijkstra$不能处理有负权的图,而 $SPFA$ 可以处理任意不含负环(负环是指总边权和为负数的环)的图的最短路,并能判断图中是否存在负环
但是 $SPFA $可以用来判断负环,在进行 $SPFA $时,用一个数组 $cnt_i$来标记每个顶点入队次数。如果一个顶点入队次数 $cnt_i$大于顶点总数 n,则表示该图中包含负环。一般情况下,$SPFA$ 判负环都只用在有向图上,因为在无向图上,一条负边权的边就是一个负环了
memset(in, 0, sizeof in);
in[u] = 1;
// 修改入队部分的操作
if(!vis[v]){
q.push(v);
vis[v] = true;
++in[v];
if(in[v] > n){
return true;
}
}
3、$floyd$多源最短路算法
$∀1≤k≤n,dp [i] [j] = min(dp[i] [j],dp[i][k]+ dp [k][j])$
int g[N][N];
void floyd(int n) {
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
三、不带权图算法
1.拓扑排序
对一个 有向无环图$ G $进行拓扑排序,是将 $G$中的所有顶点排成一个线性序列,使得图中任意一对顶点 $u$ 和 $v$,若边 $<u,v> \in E(G)$,则 $u$ 在线性序列中出现在 $v$之前。通常,这样的线性序列称为满足拓扑次序的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序.
①、算法流程
拓扑排序算法主要由以下两步循环执行,直到不存在入度为 0 的顶点为止。
-
选择一个入度为 0 的顶点并将它输出;
-
删除图中从顶点连出的所有边。
循环结束,若输出的顶点数小于图中的顶点数,则表示该图中存在回路,也就是无法进行拓扑排序;否则输出的顶点序列就是一个拓扑序列。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge {
int v, next;
int len;
} E[MAX_M];
int p[MAX_N], eid;
void init() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v) {
E[eid].v = v;
E[eid].next = p[u];
p[u] = eid++;
}
int n, m;
int indegree[MAX_N];
void topo(){
/* 如果要求为字典序,修改为
priority_queue <int, vector<int>, greater<int> > q;
*/
queue<int> q;
for(int i=1;i<=n;i++){
if(indegree[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int now = q.front();
cout<<now<<endl;
q.pop();
for(int i=p[now];i!=-1;i=E[i].next){
int v = E[i].v;
indegree[v]--;
if(indegree[v] == 0){
q.push(v);
}
}
}
}
int main() {
init();
memset(indegree, 0, sizeof(indegree));
cin>>n>>m;
for(int i=0;i<m;i++){
int u, v;
cin>>u>>v;
insert(u, v);
indegree[v]++;
}
topo();
return 0;
}
2.欧拉回路和欧拉路径
若图 $G$ 中存在这样一条路径,使得它恰好通过 $G$ 中每条边一次,则称该路径为欧拉路径。
若该路径是一个环路,则称为欧拉回路。
具有欧拉回路的图称为欧拉图。
具有欧拉路径但不具有欧拉回路的图称为半欧拉图。
①、有关欧拉路的重要性质
无向图
-
一个无向图 $G$ 存在欧拉路径当且仅当无向图 $G$ 是连通图,且该图中有两个奇度顶点(度数为奇数)或者无奇度顶点。
-
当无向图 $G$ 是包含两个奇度顶点的连通图时,$G$ 的欧拉路径必定以这两个奇度顶点为端点。
-
一个无向图 $G$ 存在欧拉回路当且仅当无向图 $G$ 连通且不存在奇度顶点。
有向图
- 一个有向图 $G$ 存在欧拉路径当且仅当 $G$ 是弱连通的有向图(将有向边全部看成无向边后该图是连通图),且满足以下两个条件之一:
- 所有顶点的入度和出度相等;
- 有一个顶点的出度与入度之差为 $1$,一个顶点的出度与入度之差为 $−1$,其余顶点的入度和出度相等。
- 当有向图 $G$ 包含两个入度和出度不相同的顶点且有欧拉路径时,欧拉路径必定以这两个入度出度不相同的顶点为端点。
- 一个有向图 $G$ 存在欧拉回路当且仅当图 $G$ 是连通的有向图,且所有顶点的入度和出度相等。
3.例题
1.拓扑判环
这个代码每次仅将一个入度为0的元素放入队列中
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105][105], r[105];
void topu(int n){
int rr = 0, s = 0, flag = 0;
while(rr < n && !flag){
flag = 1;//1标记拓扑队列内没有元素
for(int i=0;i<n;i++){
if(r[i] == 0){
s++;// 进拓扑的元素+1
flag = 0; // 标记要开始新的拓扑
r[i]--; //更改入度
for(int j=0;j<n;j++){
// 扫描更改所有入度
if(a[i][j]){
r[j]--;
}
}
break;
}
}
}
if(s == n){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
int main() {
int n, m;
cin>>n>>m;
memset(a, 0, sizeof(a));
memset(r, 0, sizeof(r));
for(int i=0;i<m;i++){
int x, y;
cin>>x>>y;
if(!a[x][y]){
a[x][y] = 1;
r[y]++;
}
}
topu(n);
return 0;
}
四、状态压缩动态规划
1.例题讲解
$n$ 个人在做传递物品的游戏,编号为 $1-n$。游戏规则是这样的:开始时物品可以在任意一人手上,他可把物品传递给其他人中的任意一位;下一个人可以传递给未接过物品的任意一人。即物品只能经过同一个人一次,而且每次传递过程都有一个代价;不同的人传给不同的人的代价值之间没有联系。 求当物品经过所有 $n$ 个人后,整个过程的总代价是多少。
解析
我们就可以将“当前传递过物品的人的集合、最后一个传递到的人”作为状态进行动态规划,用$dp[i][j]$表示这个状态的最小代价。
这里,我们就要用到状态压缩:把“传递过物品的人的集合”压缩为一个整数。我们用二进制表示这个集合,比如一共$5$个人,第 $0、3、4 $个人被传递过(为了方便起见,序号从 $0$ 开始),就用 $11001_{(2)}$表示,该集合的十进制表示为 $25$。
注意到 $j$ 是最后一个被传递到的人,也就是说必须在传递集合 $i$ 中标记为 $1$,即合法状态必须满足$(i & (1 << j)) != 0$。如果从 $j$ 传递到 $k$,那 $k$ 必须不在集合 $i$ 里,即必须满足$(i & (1 << k)) == 0$。
转移方程为$dp[i | 1 << k][k] = min(dp[i | 1 << k][k], dp[i][j] + a[j][k])$,其中$a[j][k]$为从 $j$ 传递到 $k$ 的代价。
因为开始时物品可以在任意一人手上,所以把$dp[1 << i][i]$置为 $0$,其它状态置为无穷大。
总的时间复杂度为 $\mathcal{O}(n^22^n)$。
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < n; i++) {
dp[1 << i][i] = 0;
}
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
for (int k = 0; k < n; k++) {
if (!(i & (1 << k))) {
dp[i | 1 << k][k] =
min(dp[i | 1 << k][k], dp[i][j] + a[j][k]);
}
}
}
}
}
int ans = INF;
for (int i = 0; i < n; i++) {
ans = min(ans, dp[(1 << n) - 1][i]);
}
2.旅行商问题
$TSP$ 是一道经典的 $NP-$完全问题,在规模比较小的时候可以用动态规划求解。
有 $n $个城市,两两之间均有道路直接相连。给出每个城市 $i$ 和 $j$ 之间的道路长度 $dist(i,j)$,求一条经过每个城市一次且仅一次,最后回到起点的路线,使得经过的道路总长度最短。$ n \le16$ ,城市编号为 $0\sim n-1$。
因为路线是一个环,可以规定任意点为起点和终点,不妨设城市 $0$ 为起点和终点。设 $d(S,i)$表示当前在城市$i$,已访问城市集合为 $S$ 的最短长度,则 $d(S,i)=\min{ d(S-{i},j)+dist(j,i)|i\in S}$。
初始时 $d(0,{0})=0$,最终答案为$ \min {d({0,1,2,\cdots,n-1},i)+dist(i,0)|i\ne0}$。
时间复杂度为 $\mathcal{O}(n^22^n)$。
memset(dp, 0x3f, sizeof(dp));
dp[1][0] = 0;
for (int s = 0; s < (1 << n); s++) {
for (int i = 0; i < n; i++) {
if (s & (1 << i)) {
for (int j = 0; j < n; j++) {
if (j != i && (s & (1 << j))) {
dp[s][i] =
min(dp[s][i], dp[s ^ 1 << i][j] + dist[j][i]);
}
}
}
}
}
int ans = INF;
for (int i = 1; i < n; i++) {
ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
}
3.取方格问题
给定一个 $n \times m$的矩阵,行数和列数都不超过$20$,其中有些格子可以选,有些格子不能选。现在你需要从中选出尽可能多的格子,且保证选出的所有格子之间不相邻(没有公共边)。
#include <iostream>
using namespace std;
int a[21][20];
int state[21];
int dp[21][1 << 20];
bool ok(int now){ //判断行内是否相交
return (now & (now >> 1)) == 0;
}
bool fit(int now, int i){ //判断选取状态是否和符合第i行的输入
return (now | state[i]) == state[i];
}
bool not_intersect(int now, int prev){ //判断状态now和状态prev能否放在相邻的行
return (now & prev) == 0;
}
int count(int now){ // 统计状态Now选取了多少个元素
int s = 0;
while(now){
s += (now & 1);
now >>= 1;
}
return s;
}
int main() {
int n, m;
cin >> n >> m;
// 行从 1 开始,列从 0 开始,这样后面处理起来方便
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
// 二维矩阵压成一维
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
if(a[i][j]){
state[i] += (1 << j);
}
}
}
// 最外层一共n行,行位元素集合为1<<m
// 找到一个可行的行以后,枚举上一行的所有状态
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<m);j++){
if(ok(j) && fit(j, i)){
for(int k=0;k<(1<<m);k++){
if(ok(k) && fit(k, i-1) && not_intersect(j, k)){
dp[i][j] = max(dp[i][j], dp[i-1][k] + count(j));
}
}
}
}
}
int ans = 0;
for(int i=0;i<(1<<m);i++){
ans = max(ans, dp[n][i]);
}
cout<<ans<<endl;
return 0;
}
五、二分法
1. 分割数组的最大值
例题:对于一串数$num$,比如$num=[1,3,4,7,1,4,3,8]$,可以将数组中连续若干个数合并为一组 gi。将这串数组分成至多$ k$组,当$k=4 $的时候,每组数的总和的最大值$max(gi)$最小是多少?
#include <iostream>
using namespace std;
const int N = 1e3 + 9;
const int inf = 0x3f3f3f3f;
int n, k, a[N];
bool check(int x){
int now = 0, cnt = 0;
for(int i=0;i<n;++i){
if(now + a[i] > x){
++cnt;
now = a[i];
}else{
now += a[i];
}
}
return cnt <= k;
}
int cal(int l, int r){
while(l < r){
int mid = (l + r) >> 1;
if(check(mid)){
r = mid;
}else{
l = mid + 1;
}
}
return l;
}
int main() {
int ma = -inf, sum = 0;
cin >> n >> k;
for(int i=0;i<n;++i){
cin>>a[i];
ma = max(ma, a[i]);
sum += a[i];
}
cout<< cal(ma, sum) <<endl;
return 0;
}
2. 01分数规划
01 分数规划是这样的一类问题,有一堆物品,每一个物品有一个收益 a i ,一个代价 bi,我们要求一个方案,使选择的 k 个元素 $ \frac{\sum{a_i}} { \sum{b_i}} ∑b_i ∑a_i $ 最大值
分数规划的基本**是,我们先假设:
$$
f(x) = \frac{\sum^{n}{0}{x_i}*{a_i}} { \sum^{n}{0}{x_i}*{b_i}}
$$
其中$x_i$ 只有两个取值 0, 1来表示是否选取第 i 个物品,并且 $\sum_0^n x_i = k$,一定选 k 个元素
继续假设有一组 x 在 f(x) = v的时候,为最优解,上式变形如下:
$$
\sum^{n}{0}{x_i}{(a_i - vb_i)} = 0
$$
我们现在对 v二分,如果 v过大的时候,$\sum^{n}{0}{x_i}{(a_i - vb_i)} < 0$,我们无论如何怎么选择这 k个元素,都不会找到一组使得$\sum^{n}_{0}{x_i}{(a_i - vb_i)} >= 0$的x。而实际上,我们只需要对n个元素按照$a_i - v*b_i$ 排序后,选出最大的k个就是最大值了
反之,v过小的时候,$\sum^{n}_{0}{x_i}{(a_i - vb_i)} > 0$ ,那么我们就能根据选出来的最大的k个$a_i - v*b_i$ 的和来判断v和最后答案的关系,从而进行二分
double g(double v) {
for (int i = 0; i < n; ++i) { // 计算 a(x) - v * b(x)
tmp[i] = a[i] - v * b[i];
}
sort(tmp, tmp + n);
double sum = 0;
for (int i = n - k; i < n; ++i) { // 选择 k 个最大的比值
sum += tmp[i];
}
return sum;
}
double cal() {
double l = 0, r = 1e10;
while (r - l > eps) {
double mid = (l + r) / 2;
if (g(mid) > 0) {
l = mid;
} else {
r = mid;
}
}
return l;
}
3.三分法
三分法解决凸形或者凹形函数的极值
二分法解决连续不间断函数的零点
$$
请计算下面方程的的最大值 (0 \le \theta \le \frac{\pi}{2})
$$
$$
y = \frac{( - x + l * sin(θ)+\frac{d}{cos(θ)})}{tan(θ)}
$$
经过求导计算发现这个方程式凸函数,所以符合三分的使用要求,所以这道题目我们可以使用三分法来计算
#include <iostream>
#include <cmath>
using namespace std;
const double pi = acos(-1);
const double eps = 1e-9;
double x, y, l, d;
double f(double du){
return (-x + l*sin(du) + d / cos(du)) / tan(du);
}
double cal(){
double l = 0, r = pi / 2;
while(r - l > eps){
double mid = (l + r) / 2;
double mmid = (mid + r) / 2;
if(f(mid) < f(mmid)){
l = mid;
}else{
r = mmid;
}
}
return l;
}
int main() {
cin>>x>>l>>d;
printf("%.3lf\n", cal());
return 0;
}
4.两数之和
给定一个包含 $n$ 个整数的数组 $a$,保证每个数字不重复,从中取出两个不同数,使得他们的和值为$ s$,求一共有多少种不同的选取方案。
/*
input:
10 7
-3 -2 -4 4 8 9 3 -1 10 0
ouput:
4
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, s;
ll a[1000005];
int main(){
ll ans = 0;
cin>>n>>s;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
for(int i=0;i<n;i++){
ll y = s - a[i];
ll l = i, r = n;
bool flag = false;
while(l <= r){
ll mid = (l + r) >> 1;
if(a[mid] == y){
flag = true;
break;
}else if(a[mid] < y){
l = mid + 1;
}else{
r = mid - 1;
}
}
if(flag){
ans++;
}
}
cout<<ans<<endl;
return 0;
}
5.对数方程
求解关于 x 的方程$ x + ln(x) = a$的解,其中 $a$ 为常数
/*
input:
10
output:
7.929420
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
double a;
double f(double x){
return x + log(x) - a;
}
int main(){
cin>>a;
double l = 0,r = 1e9;
while(r - l > eps){
double mid = (l + r) / 2;
if(f(mid) <= 0){
l = mid;
}else{
r = mid;
}
}
printf("%.6lf\n", l);
return 0;
}
6.气球消消乐
蒜头君有 $n$ 只气球,蒜头君把气球排成一排。初始时,气球都是白色,现在蒜头君想用 $m$ 种颜色给气球涂色,如果相邻的气球的颜色相同,这 2 个气球会发生消消乐,蒜头君希望你求出会发生消消乐的涂色方法有多少种。最后答案对$ 10^9+7 $取模。
/*
input:
3 4
output:
28
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ksm(ll x,ll n,ll mod){
ll res = 1;
x = x % mod;
while(n > 0){
if(n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
int main(){
ll n, m;
const ll mod = 1e9+7;
cin>>n>>m;
cout<<(ksm(m, n, mod) - (ksm(m-1, n-1, mod)*m)%mod + mod) % mod<<endl;
return 0;
}
7.切割钢管
$n$根钢管,第$i$根钢管长度为$a_i$,将n根钢管切割成至少$k$根长度相同的钢管,问钢管切割后最长为多少
/*
input:
8 8
12 3 14 12 14 20 4 8
output:
7
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10005;
int a[maxn];
int main(){
int n, k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
int l = 0, r = 100000001;
while(l < r){
int mid = (l + r)>>1;
int cnt = 0;
for(int i=0;i<n;i++){
cnt += a[i] / mid;
}
if(cnt >= k){
l = mid + 1;
}else{
r = mid;
}
}
cout<<r - 1<<endl;
return 0;
}
8.火车站台连锁店
铁路线上有 n 个车站,假设这条铁路线是一条直线,其中每个站点的坐标为 $x_1,x_2,\ldots,x_n$
蒜头君一共要开办 m 个连锁店,并且不希望连锁店离得太近,以使得整体的收益最大化。他希望他的连锁店之间的最近距离尽可能大,你能帮他算出这个最大的最近距离吗?
输入为$n、m、x[]$
/*
input:
5 4
5
7
10
28
9
output:
2
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
int a[maxn];
int n, m;
bool check(int mid){
int last = 0;
int cnt = 1;
while(last < n - 1){
int j;
for(j = last+1;j<n;++j){
if(a[j] - a[last] >= mid){
last = j;
++cnt;
break;
}
}
if(j == n){
break;
}
}
if(cnt >= m){
return 1;
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int l = 0, r = a[n-1];
while(l < r){
int mid = (l + r) >> 1;
if(check(mid)){
l = mid + 1;
}else{
r = mid;
}
}
cout<<r - 1<<endl;
return 0;
}
六、基础数论
1.欧几里得算法
快速计算2个数的最大公约数
// 可直接用__gcd(a, b)
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a%b);
}
时间复杂度为$O(logN)$,可以证明其递归层数不会超过$4.7851*lgonN+1.6723$
2.Eratosthenes 素数筛选
for (int i = 2; i <= n; i++) {
is_prime[i] = true;
}
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j +=i) {
is_prime[j] = false;
}
}
}
优化后时间复杂度比$O(NloglogN)$还要低
3.积性函数
积性函数是满足下列性质的一类函数
$$
f(mn) = f(m)*f(n),∀gcd(m,n) = 1
$$
欧拉函数$ ϕ(n)$:小于等于 n 的所有数中与 n 互质的数的个数
例如$ϕ(10) = 4$,因为1,3,7,9均和10互质
欧拉函数为积性函数
$$
ϕ(x) = x(1 - (1/p1))(1 - (1/p2))(1 - (1/p3))\cdots*(1 - (1/pn)),其中 p_1,p_2 \cdots,p n 是 x 的所有质因数
$$
欧拉定理:若$a,b$互质,则有
$$
a^{ϕ(n)}≡ 1: (mod :n)
$$
特例:费马小定理
$$
a^{p-1}≡ 1: (mod :p)
$$
其他性质
$$
\displaystyle \sum^{}_{d|n}{ϕ(d) = n}
$$
求一个数的欧拉函数值
int res = n;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
res = res / i * (i - 1);
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
res = res / n * (n - 1);
}
cout << res << endl;
区间预处理欧拉函数
for (int i = 1; i <= n; i++) {
phi[i] = i;
}
for (int i = 2; i <= n; i++) {
if (phi[i] == i) {
for (int j = i; j <= n; j += i) {
phi[j] = phi[j] / i * (i - 1);
}
}
}
欧拉函数例题:
$$
给定一个整数 n,请问有多少个整数 i满足条件:gcd(i, n) = 1,1 \leq i \leq n
$$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n;
cin>>n;
int res = n;
for(int i=2;i*i<=n;i++){
if(n % i == 0){
res = res / i * (i-1);
while(n%i == 0){
n /= i;
}
}
}
if(n > 1){
res = res / n * (n-1);
}
cout<<res<<endl;
return 0;
}
4.矩阵
矩阵乘法
struct matrix {
int n, m;
int a[100][100];
};
// A.m == B.n
matrix matrix_mul(matrix A, matrix B) {
matrix C;
C.n = A.n;
C.m = B.m;
for (int i = 0; i < A.n; ++i) {
for (int j = 0; j < B.m; ++j) {
C.a[i][j] = 0;
for (int k = 0; k < A.m; ++k) {
C.a[i][j] += A.a[i][k] * B.a[k][j];
}
}
}
return C;
}
int n; // 所有矩阵都是 n * n 的矩阵
struct matrix {
int a[100][100];
};
matrix matrix_mul(matrix A, matrix B, int mod) {
// 2 个矩阵相乘
matrix C;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
C.a[i][j] = 0;
for (int k = 0; k < n; ++k) {
C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;
}
}
}
return C;
}
matrix unit() {
// 返回一个单位矩阵
matrix res;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) {
res.a[i][j] = 1;
} else {
res.a[i][j] = 0;
}
}
}
return res;
}
matrix matrix_pow(matrix A, int n, int mod) {
// 快速求矩阵 A 的 n 次方
matrix res = unit(), temp = A;
for (; n; n /= 2) {
if (n & 1) {
res = matrix_mul(res, temp, mod);
}
temp = matrix_mul(temp, temp, mod);
}
return res;
}
七、线段树和树状数组基础
1.线段树
1.建树
const int maxn = 10010;
int minv[4 * maxn], a[maxn];
// id 表示结点编号,l, r 表示左右区间
void build(int id, int l, int r) {
if (l == r) {
minv[id] = a[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
// pushup函数
minv[id] = min(minv[id << 1], minv[id << 1 | 1]);
}
2.单点更新
// 把 x 位置更为成为 v
void update(int id, int l, int r, int x, int v) {
if (l == r) {
minv[id] = v;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
update(id << 1, l, mid, x, v);
} else {
update(id << 1 | 1, mid + 1, r, x, v);
}
pushup(id);
}
3.单点查询
int query(int id, int l, int r, int x) {
if (l == r) {
return minv[id];
}
int mid = (l + r) >> 1;
if (mid <= x) {
return query(id << 1, l, mid, x);
} else {
return query(id << 1 | 1, mid + 1, r, x);
}
}
4.区间查询
int query(int id, int l, int r, int x, int y) {
if (x <= l && r <= y) { // 如果完全包含,直接返回
return minv[id];
}
int mid = (l + r) >> 1;
int ans = inf;
if (x <= mid) {
ans = min(ans, query(id << 1, l, mid, x, y)); // 如果左区间包含,递归的查询左子树
}
if (y > mid) {
ans = min(ans, query(id << 1 | 1, mid + 1, r, x, y)); // 如果右区间包含,递归的查询右子树
}
return ans;
}
2.树状数组
1.区间查询
//getsum(r) - getsum(l-1)
int lowbit(int x){
return x & -x;
}
int getsum(int x) {
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
res += C[i];
}
return res;
}
2.单点更新
void update(int x, int v) {
for (int i = x; i <= n; i += lowbit(i)) {
C[i] += v;
}
}
3.差分序列
给定包含 $n$ 个数的数组 $a_1, a_2, \cdots a_n$。有 $q$ 次操作
每次操作把区间$ [l, r$] 上的数加上 $v$。最后求出数列每个位置的数。
我们对于数列做差分,得到差分序列 $d$。那么对于每次更新区间$ [l, r]$,实际上只有$ a_l - a_{l - 1}$和 $a_{r + 1} - a_r$的值会发生变化,也就是 $d_{l}$会增加 $v$,$d_{r + 1}$会减少 $v$。那么每次更新只需要处理差分序列中的两个值。
得到最后的差分序列,然后还原成原数列就可以了。
#include <iostream>
using namespace std;
const int maxn = 110;
int a[maxn], d[maxn];
int main() {
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=n;++i){
d[i] = a[i] - a[i-1];
}
int q;
cin>>q;
while(q--){
int l,r,v;
cin>>l>>r>>v;
d[l] += v;
d[r+1] -= v;
}
for(int i=1;i<=n;++i){
a[i] = a[i-1] + d[i];
cout<<a[i]<<" ";
}
return 0;
}
4.杂乱的模板
1.线段树求区间最大值(区间和值需要修改一下max部分,改为+)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int c[N << 4];
void update(int o, int l, int r, int x, int v){
if(x <= l && r <= x){
c[o] = v;
return;
}
int mid = l + r >> 1;
if(x <= mid){
update(o << 1, l, mid, x, v);
}
if(mid < x){
update(o << 1 | 1, mid + 1, r, x, v);
}
c[o] = max(c[o << 1] , c[o << 1 | 1]);
}
int query(int o, int l, int r, int x, int y){
if(x <= l && r <= y){
return c[o];
}
int mid = l + r >> 1;
int res = 0;
if(x <= mid){
res = max(res, query(o << 1, l, mid, x, y));
}
if(mid < y){
res = max(res, query(o << 1 | 1, mid + 1, r, x, y));
}
return res;
}
int main() {
int n, v, m;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> v;
update(1, 1, n, i, v);
}
string s;
while(m--){
int x,y;
cin >> s;
cin >> x >> y;
if(s[0] == 'Q'){
cout<<query(1, 1, n, x, y)<<endl;
}else if(s[0] == 'U'){
update(1, 1, n, x, y);
}
}
return 0;
}
2.区间修改(lazy标记)
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+7;
int N,Q;
LL a[maxn],t[4*maxn],laz[4*maxn];
void build(int rt,int l,int r)
{
if(l==r)
{
t[rt]=a[l];
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
t[rt]=t[rt<<1]+t[rt<<1|1];
}
void pushdown(int rt,int l,int r)
{
if(laz[rt]==0)
return;
int mid=(l+r)>>1;
t[rt<<1]+=laz[rt]*(mid-l+1);
laz[rt<<1]+=laz[rt];
t[rt<<1|1]+=laz[rt]*(r-mid);
laz[rt<<1|1]+=laz[rt];
laz[rt]=0;
}
void updata(int rt,int l,int r,int a,int b,LL c)
{
if(a<=l&&r<=b)
{
t[rt]+=c*(r-l+1);
laz[rt]+=c;
return;
}
pushdown(rt,l,r);
int mid=(l+r)>>1;
if(b<=mid)
updata(rt<<1,l,mid,a,b,c);
else if(a>mid)
updata(rt<<1|1,mid+1,r,a,b,c);
else
{
updata(rt<<1,l,mid,a,b,c);
updata(rt<<1|1,mid+1,r,a,b,c);
}
t[rt]=t[rt<<1]+t[rt<<1|1];
}
LL query(int rt,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)
return t[rt];
if(r<ql||l>qr)
return 0;
pushdown(rt,l,r);
int mid=(l+r)>>1;
return query(rt<<1,l,mid,ql,qr)+query(rt<<1|1,mid+1,r,ql,qr);
}
int main()
{
scanf("%d %d",&N,&Q);
for(int i=1;i<=N;i++)
scanf("%lld",&a[i]);
build(1,1,N);
while(Q--)
{
getchar();
char C=getchar();
int a,b;
scanf("%d %d",&a,&b);
if(C=='C')
{
LL c;
scanf("%lld",&c);
updata(1,1,N,a,b,c);
}
else
printf("%lld\n",query(1,1,N,a,b));
}
return 0;
}
八、考研复习着玩(杂项)~
1.KMP算法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<"["<<x<<"]"<<endl
#define bug printf("***********\n")
void read(int &x){
char ch = getchar();x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
const int maxn = 1000005;
const int maxm = 10005;
char a[maxn],b[maxm];
int nex[maxm];
int n,m;
int kmp(){
int i1=0,i2=0,ans=0;
while(i1 < n){
if(i2 == -1 || a[i1] == b[i2]){
i1++;
i2++;
}
else i2 = nex[i2];
if(i2 == m){
i2 = 0;
ans++;
}
}
return ans;
}
void getnext(){
memset(nex,-1,sizeof(nex));
nex[0] = -1;
nex[1] = 0;
int i = 2;
int cn = 0;
while(i <= m){
if(b[i-1] == b[cn]){
nex[i++] = ++cn;
}else if(cn > 0){
cn = nex[cn];
}else{
nex[i++] = 0;
}
}
/*for(int j=0;j<5;j++){
cout<<nex[j]<<" ";
}*/
}
int main(){
//freopen("in","r",stdin);
int T;
scanf("%d",&T);
while(~(scanf("%s",a))){
if(a[0]=='#') break;
scanf("%s",&b);
//cin>>b>>a;
n = strlen(a);
m = strlen(b);
getnext();
cout<<kmp()<<endl;
}
return 0;
}
2.bitset
构造函数
bitset<n> b;
b有n位,每位都为0.参数n可以为一个表达式.
如bitset<5> b0;则”b0”为”00000”;
bitset<n> b(unsigned long u);
b有n位,并用u赋值;如果u超过n位,则顶端被截除
如:bitset<5>b0(5);则”b0”为”00101”;
bitset<n> b(string s);
b是string对象s中含有的位串的副本
string bitval ( “10011” );
bitset<5> b0 ( bitval4 );
则”b0”为”10011”;
bitset<n> b(s, pos);
b是s中从位置pos开始位的副本,前面的多余位自动填充0;
string bitval (“01011010”);
bitset<10> b0 ( bitval5, 3 );
则”b0” 为 “0000011010”;
bitset<n> b(s, pos, num);
b是s中从位置pos开始的num个位的副本,如果num<n,则前面的空位自动填充0;
string bitval (“11110011011”);
bitset<6> b0 ( bitval5, 3, 6 );
则”b0” 为 “100110”;
os << b
把b中的位集输出到os流
os >>b
输入到b中,如”cin>>b”,如果输入的不是0或1的字符,只取该字符前面的二进制位.
bool any( )
是否存在置为1的二进制位?和none()相反
bool none( )
是否不存在置为1的二进制位,即全部为0?和any()相反.
size_t count( )
二进制位为1的个数.
size_t size( )
二进制位的个数
flip()
把所有二进制位逐位取反
flip(size_t pos)
把在pos处的二进制位取反
bool operator[]( size_type _Pos )
获取在pos处的二进制位
set()
把所有二进制位都置为1
set(pos)
把在pos处的二进制位置为1
reset()
把所有二进制位都置为0
reset(pos)
把在pos处的二进制位置为0
test(size_t pos)
在pos处的二进制位是否为1?
unsigned long to_ulong( )
用同样的二进制位返回一个unsigned long值
string to_string ()
返回对应的字符串.
3.组合数学
1.求解组合数$ C (n, k) % p $
方法1(逆元求法):
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
int f[N], finv[N], inv[N];
void init(void) { //要求MOD是质数,预处理时间复杂度O(n)
inv[1] = 1;
for (int i=2; i<N; ++i) {
inv[i] = (MOD - MOD / i) * 1ll * inv[MOD%i] % MOD;
}
f[0] = finv[0] = 1;
for (int i=1; i<N; ++i) {
f[i] = f[i-1] * 1ll * i % MOD;
finv[i] = finv[i-1] * 1ll * inv[i] % MOD;
}
}
方法2:$C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m)$
const int N = 2000 + 10;
const int MOD = 1e9 + 7;
int comb[N][N];
void init(void) { //对MOD没有要求,预处理时间复杂度O(n^2)
for (int i=0; i<N; ++i) {
comb[i][i] = comb[i
][0] = 1;
for (int j=1; j<i; ++j) {
comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
if (comb[i][j] >= MOD) {
comb[i][j] -= MOD;
}
}
}
}
方法3(Lucas定理,大组合数取模, HDOJ 3037为例):
ll f[N];
void init(int p) { //f[n] = n!
f[0] = 1;
for (int i=1; i<=p; ++i) f[i] = f[i-1] * i % p;
}
ll pow_mod(ll a, ll x, int p) {
ll ret = 1;
while (x) {
if (x & 1) ret = ret * a % p;
a = a * a % p;
x >>= 1;
}
return ret;
}
ll Lucas(ll n, ll k, int p) { //C (n, k) % p
ll ret = 1;
while (n && k) {
ll nn = n % p, kk = k % p;
if (nn < kk) return 0; //inv (f[kk]) = f[kk] ^ (p - 2) % p
ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - 2, p) % p;
n /= p, k /= p;
}
return ret;
}
int main(){
init (p);
printf ("%I64d\n", Lucas (n + m, n, p));
return 0;
}
ll extend_gcd(ll a,ll b,ll &x,ll &y){
if(a == 0 && b == 0) return -1;
if(b == 0){
x = 1;
y = 0;
return a;
}
ll d = extend_gcd(b,a%b,y,x);
y -= a/b*x;
return d;
}
ll inv(ll a,ll n){
ll x,y;
ll d = extend_gcd(a,n,x,y);
if(d == 1) return (x%n+n)%n;
else return -1;
}
ll ksm(ll x,ll n,ll mod){
ll res = 1;
x = x % mod;
while(n > 0){
if(n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
//m 中 选 n 个
ll getc(ll m,ll n){
ll mc=1,nc=1;
for(ll i=m;i>m-n;i--){
mc*=i;
mc%=mod;
}
for(ll i=n;i>=1;i--){
nc*=i;
nc%=mod;
}
return mc*inv(nc,mod)%mod;
}
2.二项式定理
又称牛顿二项式定理,是指两个整数的整数幂次的展开式。 $ \displaystyle (x+y)^n=\sum C_n^i x^{n-i}y^i=\binom n 0 x^n+\binom n 1 x^{n-1}y+\cdots+\binom n n y^n$
4.并查集
int par[MAX_N];
int rank[MAX_N];
//初始化n个元素
void init(int n){
for(int i=0;i<n;i++){
par[i] = i;
rank[i] = 0;
}
}
//查询树的根
int find(int x){
if(par[x] == x){
return x;
}else{
return par[x] = find(par[x]);
}
}
//合并x和y所属的集合
void unite(int x,int y){
x = find(x);
y = find(y);
if(x == y) return;
if(rank[x] < rank[y]){
par[x] = y;
}else{
par[y] = x;
if(rank[x] == rank[y]) rank[x]++;
}
}
//判断x和y是否属于同一个集合
bool same(int x,int y){
return find(x) == find(y);
}
5.搜索
DFS
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m;
char field[105][105]; //园子
void dfs(int x,int y){
field[x][y]='.';
for(int dx = -1;dx <= 1;dx++){
for(int dy = -1;dy <= 1;dy++){
int nx=x+dx,ny=y+dy;
if(nx>=0 && nx<n && ny<m && ny>=0 && field[nx][ny] =='W') dfs(nx,ny);
}
}
return ;
}
void solve(){
int res = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(field[i][j]=='W'){
dfs(i,j);
res++;
}
}
}
printf("%d\n",res);
}
void init(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",field[i]);
}
int main()
{
//freopen("input.txt","r",stdin);
init();
solve();
return 0;
}
BFS
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y,step;
};
int vis[8][8];//8X8储存棋盘
int sx,sy,ex,ey,ans;
int to[8][2]={-1,-2,-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2};
//第一个8对应的是马的8种移动情况
//第二个2代表的是ch1横坐标和纵坐标变化时对应的数值
int check(int x,int y)
{
if(x<0 || y<0 || x>=8 || y>=8)//超出了棋盘的范围
return 1;//超出范围,返回1
if(vis[x][y])//非0为真 ,此处为检验该位置是否之前已经用过
return 1;//该位置以前使用过,返回1
return 0;//该位置没有超出范围且没有用过,返回0
}
void bfs()//void结尾不需要return
{
int i;
queue<node> Q;//队列容器
node a,next;//a和next变成结构体头
a.x = sx;//ch1横坐标
a.y = sy;//ch1纵坐标
a.step = 0;// 目前ch1的坐标变化步骤为0
vis[sx][sy] = 1;//将ch1目前坐标的位置的数值标志为1
Q.push(a);//将a整个扔进去,Q是node类型,只能向其中添加node类型的元素,
//node类型看作一个元素而一个node元素又包含其他的元素
while(!Q.empty())//若Q不空则运行
{
a = Q.front();//返回第一个元素,队顶元素
//访问queue队首元素,如例:q.front(),即最早被压入队列的元素
Q.pop();//弹出Q中的第一个元素,并且不会返回数值(出队)
if(a.x == ex && a.y == ey)//ch1是否到达ch2的坐标
{
ans = a.step;//把当前的步骤数赋给ans
}
for(i = 0;i<8;i++)
{
next = a;//pop已经弹出上一个队顶元素,现在是下一个
next.x+=to[i][0];//ch1的横坐标的变化
next.y+=to[i][1];//ch1的纵坐标的变化
if(check(next.x,next.y))//调用上面的实参函数check
continue;//如果返回为1,跳出本次循环,后面三步骤跳过
next.step = a.step+1;//目前进行过的步骤次数+1
vis[next.x][next.y] = 1;//将该位置变更状态为已经使用过的位置
Q.push(next);//将next整个扔进队列里面
}
}
return ;
}
int main()
{
char ch1[10],ch2[10];
while(~scanf("%s%s",ch1,ch2))//等价于!=EOF
{
//ASCII码
sx = ch1[0]-'a';//ch1横坐标
sy = ch1[1]-'1';//ch1纵坐标
ex = ch2[0]-'a';//ch2横坐标
ey = ch2[1]-'1';//ch2纵坐标
memset(vis,0,sizeof(vis));//将vis数组整个清零
bfs();//调用bfs函数
printf("To get from %s to %s takes %d knight moves.\n",ch1,ch2,ans);
}
return 0;
}
6.dp
1.01背包
for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
if(j>=c[i]){
dp[i][j] = max(dp[i-1][j-c[i]]+w[i], dp[i-1][j]);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
for(int i=1;i<=N;i++){
for(int j=V;j>=c[i];j--){
dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
}
}
2.完全背包
for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
if(j >= c[i]){
dp[i][j] = max(dp[i][j-c[i]]+w[i], dp[i-1][j]);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
for(int i=1;i<=N;i++){
for(int j=c[i];j<=V;j++){
dp[j] = max(dp[j-c[i]]+w[i], dp[j]);
}
}
3.多重背包
for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
for(int k=0;k<=n[i];k++){
if(j >= c[i]*k){
dp[i][j] = max(dp[i-1][j - c[i]*k] + w[i]*k, dp[i][j]);
}
}
}
}
for(int i=1;i<=N;i++){
for(int j=V;j>=0;j--){
for(int k=0;k<=n[i];k++){
if(j>=c[i]*k){
dp[j] = max(dp[j - c[i]*k]+w[i]*k, dp[j]);
}
}
}
}
二进制优化
#include <iostream>
using namespace std;
int n[110], c[110], w[110];
int nc[1000], nw[1000];
int dp[5010];
int main() {
int N, V;
cin >> N >> V;
for (int i = 1; i <= N; ++i) {
cin >> w[i] >> c[i] >> n[i];
}
int ncnt = 0;
// 二进制拆分
for (int i = 1; i <= N; ++i) {
int k;
// 找到最大的 k
for (k = 1; n[i] - (1 << k) + 1 > 0; ++k) {
nc[ncnt] = (1 << (k - 1)) * c[i];
nw[ncnt] = (1 << (k - 1)) * w[i];
++ncnt;
}
--k;
// 最后一组
nc[ncnt] = (n[i] - (1 << k) + 1) * c[i];
nw[ncnt] = (n[i] - (1 << k) + 1) * w[i];
++ncnt;
}
// 01 背包
for (int i = 0; i < ncnt; ++i) {
for (int j = V; j >= nc[i]; --j) {
dp[j] = max(dp[j], dp[j - nc[i]] + nw[i]);
}
}
cout << dp[V] << endl;
return 0;
}
更加易懂的二进制优化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool dp[500005];
int n[10];
int nc[500005];
int flag = 0;
int main(){
freopen("dolls.in","r",stdin);
freopen("dolls.out","w",stdout);
memset(n, 0, sizeof(n));
memset(dp, false, sizeof(dp));
int V = 0;
int k = 0;
for(int i=1;i<=6;i++){
cin>>n[i];
if(n[i]) dp[i] = true;
V = V + n[i] * i;
}
if(V % 2 == 1){
cout<<"Can't be divided."<<endl;
return 0;
}
int ncnt = 0;
for(int i=1;i<=6;i++){
int c = n[i];
for(int k = 1;k <= c; k = k * 2){
++ncnt;
nc[ncnt] = k*i;
c -= k;
}
++ncnt;
nc[ncnt] = c * i;
}
dp[0] = true;
for(int i=1;i<=ncnt;i++){
for(int j=V/2;j>=nc[i];j--){
dp[j] |= dp[j - nc[i]];
if(dp[V/2]){
break;
}
}
if(dp[V/2]){
break;
}
}
if(dp[V/2]) cout<<"Can be divided."<<endl;
else cout<<"Can't be divided."<<endl;
return 0;
}
4.数位dp
不要62
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<"["<<x<<"]"<<endl
#define bug printf("***********\n")
void read(int &x){
char ch = getchar();x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
int n,m;
int dp[10][2],a[10];
int dfs(int len,bool lead,bool limit){
if(len < 0) return 1;
if(dp[len][lead] != -1 && !limit) return dp[len][lead];
int ans = 0,i,e=limit?a[len]:9;
for(i=0;i<=e;i++){
if(!(lead && i == 2) && i != 4){
ans += dfs(len-1,i==6,limit&&i == e);
}
}
if(!limit){
dp[len][lead] = ans;
}
return ans;
}
int solve(int x){
int len = 0;
while(x){
a[len++] = x % 10;
x /= 10;
}
return dfs(len-1,0,1);
}
int main(){
//freopen("in","r",stdin);
while(~scanf("%d %d",&n,&m)){
if(n == 0 && m == 0) break;
memset(dp,-1,sizeof(dp));
memset(a,0,sizeof(a));
printf("%d\n",solve(m) - solve(n-1));
}
return 0;
}
typedef long long ll;
int a[20];
ll dp[20][state];//不同题目状态不同
ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零
{
//递归边界,既然是按位枚举,最低位是0,那么pos==-1说明这个数我枚举完了
if(pos==-1) return 1;/*这里一般返回1,表示你枚举的这个数是合法的,那么这里就需要你在枚举时必须每一位都要满足题目条件,也就是说当前枚举到pos位,一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
//第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
/*常规写法都是在没有限制的条件记忆化,这里与下面记录状态是对应,具体为什么是有条件的记忆化后面会讲*/
int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
ll ans=0;
//开始计数
for(int i=0;i<=up;i++)//枚举,然后把不同情况的个数加到ans就可以了
{
if() ...
else if()...
ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的
/*这里还算比较灵活,不过做几个题就觉得这里也是套路了
大概就是说,我当前数位枚举的数是i,然后根据题目的约束条件分类讨论
去计算不同情况下的个数,还有要根据state变量来保证i的合法性,比如题目
要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类,
前一位如果是6那么这意味就不能是2,这里一定要保存枚举的这个数是合法*/
}
//计算完,记录状态
if(!limit && !lead) dp[pos][state]=ans;
/*这里对应上面的记忆化,在一定条件下时记录,保证一致性,当然如果约束条件不需要考虑lead,这里就是lead就完全不用考虑了*/
return ans;
}
ll solve(ll x)
{
int pos=0;
while(x)//把数位都分解出来
{
a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来,反正注意数位边界就行
x/=10;
}
return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的,显然比最高位还要高的一位视为0嘛
}
int main()
{
ll le,ri;
while(~scanf("%lld%lld",&le,&ri))
{
//初始化dp数组为-1,这里还有更加优美的优化,后面讲
printf("%lld\n",solve(ri)-solve(le-1));
}
}
5.区间dp
for(int len = 1;len<=n;len++){//枚举长度
for(int j = 1;j+len<=n+1;j++){//枚举起点,ends<=n
int ends = j+len - 1;
for(int i = j;i<ends;i++){//枚举分割点,更新小区间最优解
dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
}
}
}
7.字典树
const int MAX_N = 10000; // Trie 树上的最大结点数
const int MAX_C = 26; // 每个结点的子结点个数上限
struct Trie {
int *ch[MAX_N]; // ch 保存了每个结点的 26 个可能的子结点编号,26 对应着 26 种小写字母,也就是说,插入的字符串全部由小写字母组成。初始全部为 -1
int tot; // 总结点个数(不含根结点),初始为 0
int cnt[MAX_N]; // 以当前结点为终端结点的 Trie 树中的字符串个数
void init() { // 初始化 Trie 树,根结点编号始终为 0
tot = 0;
memset(cnt, 0, sizeof(cnt));
memset(ch, 0, sizeof(ch)); // 将 ch 中的元素初始化为 NULL
}
void insert(char *str) {
int p = 0; // 从根结点(0)出发
for (int i = 0; str[i]; ++i) {
if (ch[p] == NULL) {
ch[p] = new int[MAX_C]; // 只有 p 当包含子结点的时候才去开辟 ch[p] 的空间
memset(ch[p], -1, sizeof(int) * MAX_C); // 初始化为 -1
}
if (ch[p][str[i] - 'a'] == -1) { // 该子结点不存在
ch[p][str[i] - 'a'] = ++tot; // 新增结点
}
p = ch[p][str[i] - 'a']; // 在 Trie 树上继续插入字符串 str
}
cnt[p]++;
}
int find(char *str) { // 返回字符串 str 的出现次数
int p = 0;
for (int i = 0; str[i]; ++i) {
if (ch[p][str[i] - 'a'] == -1) {
return 0;
}
p = ch[p][str[i] - 'a'];
}
return cnt[p];
}
};
/*
char now[MAX_LEN];
void dfs(int p, int len) {
if (cnt[p] > 0) {
now[len] = '\0';
while (cnt[p] --> 0) {
cout << now << endl;
}
}
for (int i = 0; i < 26; ++i) {
if (ch[p][i]) {
now[len] = 'a' + i;
dfs(ch[p][i], len + 1);
}
}
}
*/
8.容斥原理
求区间 $[a, b]$ 上和 $x$ 互质的数的个数。
解法:首选把 $x$分解质因子,$x=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}$ 。其中$p_1,p_2,\cdots p_m$都是质数,我们称为 $x$ 的因子。这时我们来容斥。初始的时候有 $b-a+1$个数,减去$ [a,b] $上和$ p_1,p_2,\cdots p_m$不互质的数的个数,然后加上$ [a,b]$ 上同时和 $p_1p_2,p_1p_3,\cdots p_1p_m, p_2p_3, \cdots p_{m-1}p_{m-2}$不互质的数个数$ \cdots \cdots$。
#include <iostream>
#include <vector>
using namespace std;
vector<int> breakdown(int x) {
vector<int> l;
for (int i = 2; i * i <= x; ++i) {
int cnt = 0;
while (x % i == 0) {
++cnt;
x /= i;
}
if (cnt) {
l.push_back(i);
}
}
if (x > 1) {
l.push_back(x);
}
return l;
}
int main() {
int a = 10, b = 20, x = 15;
vector<int> list = breakdown(x);
int ans = 0, len = list.size();
for (int i = 0; i < (1 << len); ++i) {
int cnt = 0, pp = 1;
for (int j = 0; j < len; ++j) {
if (i & (1 << j)) {
++cnt;
pp *= list[j];
}
}
ans += (b / pp - (a - 1) / pp) * ((cnt & 1) ? -1 : 1);
}
cout << ans << endl;
return 0;
}
9.数制转换
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Arbitrary_change(ll n,int m){
char s[100];
int i;
for(i=0;n>0;i++){
if(n%m<10){
s[i] = n%m + '0';
}else{
s[i] = n%m - 10 + 'A';
}
n /= m;
}
ll cnt = 0;
for(n=i;n>0;n--){
cnt = cnt * 10 + (s[n-1] - '0');
}
return cnt;
}
ll Ten_change(int n,string str){
ll ans = 0, sum = 1;
for(int i = str.length(); i > 0; i--){
if(str[i-1] >='A') ans = ans + (str[i - 1] - 'A'+10) * sum;
else ans = ans + (str[i - 1] - '0') * sum;
//cout<<ans<<endl;
sum *= n;
}
return ans;
//printf("%d\n", ans);
}
int main() {
int T;
cin>>T;
string x;
ll ans;
while(T--){
cin>>x;
ans = 0;
for(int i=2;i<=10;i++){
ans += Ten_change(i, x);
}
cout<<ans<<endl;
}
return 0;
}
10.JAVA
1.简介:
Java中两个类BigDecimal(表示浮点数)和BigInteger(表示整数);
分别表示不可变的任意精度的整数和不可变的有符号的任意精度的十进制数(浮点数)。
主要用于高精度计算中。这两个类使得java中的大数,高精度运算变得很简单。
使用时注意每个单词首字母大写~新手很容易犯这个错/(ㄒoㄒ)/~~
使用这两个类的时候需要加上包 import java.math.*;
或是直接打:
import java.math.BigInteger;
import java.math.BigDecimal;
2.声明与赋值
通常以这种方法声明:
BigInteger a;
BigDecimal b;
也可将声明和赋值写在一起:
BigDecimal a=new BigDecimal("0");
还有常用的常量赋值方法:
A=BigInteger.ONE //=1
B=BigInteger.TEN //=10
C=BigInteger.ZERO //=0
相当于:
BigInteger A = BigInteger.valueOf(1);
BigInteger B = BigInteger.valueOf(10);
BigInteger C = BigInteger.valueOf(0);
$valueOf()$,可将数据转换为指定类型:
具体用法如下;
int a = 3;
BigInteger b = BigInteger.valueOf(a);
//即b = 3;(int)
2.输入方法:
例:
while(cin.hasNext()) //等同于!=EOF
{
int n;
BigInteger m;
n=cin.nextInt(); //读入一个int;
m=cin.BigInteger();//读入一个BigInteger;
System.out.print(m.toString());
System.out.print(m);
}
3.一些基础运算:
$add();$//加法
$substract(); $//减法
$multiply();$ //乘法
$divided(); $//相除取整
$remainder();$ //取余
$pow(); //a.pow(b) = a ^ b$
$gcd(); $//最大公约数
$abs(); $//绝对
$negate();$ //取反数
$mod(); //a.mod(b) = a % b = a.remainder(b)$
$max(); min();$
$compareTo(); $//比较
$equals();$ //比较是否相等
$a+b$的例子:
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
BigInteger a, b;
int T;
Scanner in = new Scanner(System.in);
//Scanner cin = new Scanner(new BufferedInputStream(System.in));
T = in.nextInt();
for (int i = 1; i <= T; ++i) {
System.out.println("Case" + " " + i + ":");
a = in.nextBigInteger();
b = in.nextBigInteger();
if (i < T) {
System.out.println(a + " + " + b + " = " + a.add(b) );
System.out.println();
} else {
System.out.println(a + " + " + b + " = " + a.add(b));
}
}
}
}
a+b浮点数的例子:
import java.util.*;
import java.math.*;
public class Main{
public static void main(String []args){
BigDecimal a;
BigDecimal b;
a=new BigDecimal("0");
b=new BigDecimal("0");
Scanner cin=new Scanner(System.in);
while(cin.hasNext())
{
a=cin.nextBigDecimal();
b=cin.nextBigDecimal();
a=a.add(b);
String str=a.stripTrailingZeros().toPlainString();
//stripTrailingZeros()这个方法是用来去掉末尾的0的。
//toPlainString()这个方法是使字符串大数变成普通的数字字符组成的字符串,
//如果不使用这个方法很可能数字变成了科学计数法,带E的那种。
System.out.println(str);
}
}
}