CSP-J复赛准备 模板题
文章目录
CSP-J复赛准备 模板题最小生成树单源最短路径链式前向星堆优化
并查集树状数组-点修改树状数组-区间修改线性筛简单DP01背包完全背包高精度加高精度减二叉建树求二叉树先序
整理了一些有点难度的常用板子,希望 RP++
最小生成树
#include<bits/stdc++.h>
using namespace std
;
const int MAX_M
= 200010;
const int MAX_NODE
= 5010;
struct s
{
int a
;
int b
;
int z
;
} con
[MAX_M
];
int father
[MAX_NODE
];
bool vis
[MAX_NODE
];
bool cmp(s a
, s b
){
return a
.z
<b
.z
;
}
int find_root(int x
) {
if(father
[x
]!=-1) {
return father
[x
] = find_root(father
[x
]);
}
return x
;
}
int union_(int x
, int y
) {
int x_root
= find_root(x
);
int y_root
= find_root(y
);
if(x_root
!=y_root
) {
father
[y_root
] = x_root
;
return 1;
}
return 0;
}
int main() {
memset(father
, -1, sizeof(father
));
int m
, n
, x
, y
, z
, ans
= 0;
cin
>>n
>>m
;
for(int i
=0; i
<m
; i
++) {
cin
>>x
>>y
>>z
;
con
[i
].a
= x
;
con
[i
].b
= y
;
con
[i
].z
= z
;
}
sort(con
, con
+m
, cmp
);
for(int i
=0; i
<m
; i
++) {
if(union_(con
[i
].a
, con
[i
].b
)) {
vis
[con
[i
].a
] = true;
vis
[con
[i
].b
] = true;
ans
+= con
[i
].z
;
}
}
for(int i
=1; i
<=n
; i
++) {
if(!vis
[i
]) {
cout
<<"orz"<<endl
;
return 0;
}
}
cout
<<ans
<<endl
;
return 0;
}
单源最短路径
链式前向星
#include<bits/stdc++.h>
using namespace std
;
const int MAXN
= 10001;
const int MAXM
= 500001;
const int INF
= 2147483647;
struct edge
{
int from
;
int to
;
int w
;
int next
;
};
edge e
[MAXM
];
struct node
{
int w
;
int id
;
friend bool operator <(const node
& a
, const node
& b
) {
return a
.w
>b
.w
;
}
};
int cnt
= 0;
int head
[MAXN
], vis
[MAXN
], m
, n
, s
;
long long dis
[MAXN
];
void add(int from
, int to
, int w
) {
e
[++cnt
].from
= from
;
e
[cnt
].to
= to
;
e
[cnt
].w
= w
;
e
[cnt
].next
= head
[from
];
head
[from
] = cnt
;
}
priority_queue
<node
> q
;
void dijkstra(int s
) {
for(int i
=1;i
<=n
;i
++) {
dis
[i
]=INF
;
}
dis
[s
]=0;
q
.push((node
){0,s
});
while(!q
.empty()) {
node x
=q
.top();
q
.pop();
int u
=x
.id
;
if(vis
[u
])
continue;
vis
[u
]=1;
for(int i
=head
[u
];i
;i
=e
[i
].next
) {
int v
=e
[i
].to
;
if(dis
[v
]>dis
[u
]+e
[i
].w
) {
dis
[v
]=dis
[u
]+e
[i
].w
;
q
.push((node
){dis
[v
],v
});
}
}
}
}
void printAns() {
for(int i
=1; i
<=n
; i
++) {
cout
<<dis
[i
]<<" ";
}
cout
<<endl
;
}
int main() {
cin
>>n
>>m
>>s
;
int x
, y
, z
;
for(int i
=0; i
<m
; i
++) {
cin
>>x
>>y
>>z
;
add(x
, y
, z
);
}
dijkstra(s
);
printAns();
return 0;
}
堆优化
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 100010;
typedef unsigned long long ull
;
struct Edge
{
int from
;
int to
;
ull w
;
};
struct Node
{
int n
;
ull w
;
friend bool operator < (const Node
& a
, const Node
& b
) {
return a
.w
>b
.w
;
}
};
int n
, m
, s
= 1;
ull dis
[maxn
+1];
vector
<Edge
> edges
;
vector
<int > head
[maxn
];
void addEdge(int from
, int to
, ull w
) {
edges
.push_back((Edge
){from
, to
, w
});
head
[from
].push_back(edges
.size()-1);
}
priority_queue
<Node
> pq
;
void dijsktra(int start
) {
for(int i
=1; i
<=n
; i
++) {
dis
[i
] = 1e10;
}
dis
[start
] = 0;
pq
.push((Node
){start
, 0});
while(!pq
.empty()) {
Node temp
= pq
.top();pq
.pop();
int n
= temp
.n
;
ull w
= temp
.w
;
if(w
!=dis
[n
]) {
continue;
}
for(int i
=0; i
<head
[n
].size(); i
++) {
Edge
& now
= edges
[head
[n
][i
]];
if(dis
[now
.to
]>dis
[now
.from
]+now
.w
) {
dis
[now
.to
] = dis
[now
.from
] + now
.w
;
pq
.push((Node
){now
.to
, dis
[now
.to
]});
}
}
}
}
void print_ans() {
for(int i
=1; i
<=n
; i
++) {
cout
<<dis
[i
]<<" ";
}
cout
<<endl
;
}
int main() {
cin
>>n
>>m
>>s
;
int from_
, to_
;
ull w
;
for(int i
=0; i
<m
; i
++) {
cin
>>from_
>>to_
>>w
;
addEdge(from_
, to_
, w
);
}
dijsktra(s
);
print_ans();
return 0;
}
并查集
#include<iostream>
#include<cstring>
using namespace std
;
const int maxn
= 10010;
int father
[maxn
] ;
void init() {
memset(father
, -1, sizeof(father
));
}
int find_father(int x
) {
if(father
[x
]==-1) {
return x
;
}
return father
[x
] = find_father(father
[x
]);
}
void union_(int x
, int y
) {
int x_root
= find_father(x
);
int y_root
= find_father(y
);
if(x_root
!=y_root
)
father
[x_root
] = y_root
;
}
int main() {
init();
int m
, n
, x
, y
, z
;
int x_r
=0, y_r
=0;
cin
>>n
>>m
;
for(int i
=0; i
<m
; i
++) {
cin
>>z
>>x
>>y
;
if(z
==1)
union_(x
, y
);
else {
x_r
= find_father(x
);
y_r
= find_father(y
);
if(x_r
==y_r
)
cout
<<"Y"<<endl
;
else
cout
<<"N"<<endl
;
}
}
return 0;
}
树状数组-点修改
#include<iostream>
using namespace std
;
const int maxn
= 5000000;
int d
[maxn
] , n
;
int lowbit(int x
) {
return x
&(-x
);
}
int query(int x
) {
register int sum
= 0;
while(x
) {
sum
+= d
[x
];
x
-= lowbit(x
);
}
return sum
;
}
void modify(int x
, int v
) {
while(x
<=n
) {
d
[x
] += v
;
x
+= lowbit(x
);
}
}
int main(int argc
, char const *argv
[])
{
#ifdef ONLINE_JUDGE
#endif
ios
::sync_with_stdio(0);
cin
.tie(0), cout
.tie(0);
int m
, temp
;
cin
>>n
>>m
;
for(int i
=1; i
<=n
; i
++) {
cin
>>temp
;
modify(i
, temp
);
}
int option
, x
, y
;
for(int i
=0; i
<m
; i
++) {
cin
>>option
>>x
>>y
;
if(option
==1)
modify(x
, y
);
else if(option
==2)
cout
<<query(y
) - query(x
-1)<<endl
;
}
return 0;
}
树状数组-区间修改
#include<iostream>
using namespace std
;
const int maxn
= 500000 + 10000;
int d
[maxn
], n
, m
;
int lowbit(int x
) {
return x
&(-x
);
}
int query(int x
) {
register int sum
= 0;
while(x
) {
sum
+= d
[x
];
x
-= lowbit(x
);
}
return sum
;
}
void modify(int x
, int v
) {
while(x
<=n
) {
d
[x
] += v
;
x
+= lowbit(x
);
}
}
int main(int argc
, char const *argv
[])
{
#ifndef ONLINE_JUDGE
#endif
ios
::sync_with_stdio(0);
cin
.tie(0), cout
.tie(0);
cin
>>n
>>m
;
int temp
, temp2
= 0, option
, l
, r
, x
;
for(int i
=1; i
<=n
; i
++)
cin
>>temp
, modify(i
, temp
- temp2
), temp2
= temp
;
for(int i
=1; i
<=m
; i
++) {
cin
>>option
;
if(option
==1) {
cin
>>l
>>r
>>x
;
modify(l
, x
);
modify(r
+1, -x
);
}
else {
cin
>>x
;
cout
<<query(x
)<<endl
;
}
}
return 0;
}
线性筛
#include<iostream>
using namespace std
;
int n
, m
;
int prime
[1000000];
bool noprime
[100000005];
int main() {
cin
>>n
>>m
;
noprime
[0] = noprime
[1] = true;
for(int i
=2; i
<=n
; i
++)
{
if(!noprime
[i
]) {
prime
[++prime
[0]] = i
;
}
for(int j
=1; j
<=prime
[0] && prime
[j
]*i
<=n
; j
++) {
noprime
[i
*prime
[j
]] = true;
if(i
%prime
[j
]==0) break;
}
}
int temp
;
for(int i
=0; i
<m
; i
++) {
cin
>>temp
;
if(noprime
[temp
] ) cout
<<"No"<<endl
;
else cout
<<"Yes"<<endl
;
}
return 0;
}
简单DP
#include<iostream>
using namespace std
;
const int maxm
= 210;
const int maxn
= 210;
int m
, n
, f
[maxm
][maxn
];
int max3(int a
, int b
, int c
) {
return max(max(a
, b
), c
);
}
int main() {
cin
>>m
>>n
;
int tmp
;
for(int i
=1; i
<=m
; i
++) {
for(int j
=1; j
<=n
; j
++) {
cin
>>tmp
;
f
[i
][j
] = max3(f
[i
-1][j
-1], f
[i
-1][j
], f
[i
-1][j
+1]) + tmp
;
}
}
cout
<<max3(f
[m
][n
/2], f
[m
][n
/2+1], f
[m
][n
/2+2])<<endl
;
return 0;
}
01背包
#include<iostream>
using namespace std
;
const int MAXM
= 105;
const int MAXT
= 1005;
int v
[MAXM
], w
[MAXM
],
f
[MAXM
][MAXT
];
int main(){
int t
, m
;
cin
>>t
>>m
;
for(int i
=1; i
<=m
; i
++) {
cin
>>w
[i
]>>v
[i
];
}
for(int i
=1; i
<=m
; i
++) {
for(int j
=t
; j
>0; j
--) {
if(w
[i
]<=j
) {
f
[i
][j
] = max(f
[i
-1][j
], f
[i
-1][j
-w
[i
]]+v
[i
]);
}
else {
f
[i
][j
] = f
[i
-1][j
];
}
}
}
cout
<<f
[m
][t
]<<endl
;
return 0;
}
完全背包
#include<iostream>
using namespace std
;
const int maxm
= 233333;
int t
, m
, f
[maxm
];
int main() {
cin
>>t
>>m
;
int w
, v
;
for(int i
=1; i
<=m
; i
++){
cin
>>w
>>v
;
for(int j
=w
; j
<=t
; j
++){
f
[j
] = max(f
[j
], f
[j
-w
]+v
);
}
}
cout
<<f
[t
]<<endl
;
return 0;
}
高精度加
#include<iostream>
#include<cstring>
using namespace std
;
const int maxn
= 510;
char a
[maxn
], b
[maxn
];
int a2
[maxn
], b2
[maxn
], c2
[maxn
];
int main() {
cin
>>a
;
cin
>>b
;
int strlena
= strlen(a
);
int strlenb
= strlen(b
);
int i
;
for(i
=0; i
<strlena
; i
++) {
a2
[i
] = a
[strlena
- i
- 1]-'0';
}
for(i
=0; i
<strlenb
; i
++) {
b2
[i
] = b
[strlenb
- i
- 1]-'0';
}
int tot
= max(strlena
, strlenb
);
int y
= 0;
for(i
=0; i
<tot
; i
++) {
c2
[i
] = a2
[i
] + b2
[i
] + y
;
y
= c2
[i
] / 10;
c2
[i
] %= 10;
}
if(y
!=0)
cout
<<y
;
for(i
=tot
-1; i
>=0; i
--) {
cout
<<c2
[i
];
}cout
<<endl
;
return 0;
}
高精度减
#include<iostream>
#include<cstring>
using namespace std
;
const int maxn
= 10100;
char a
[maxn
], b
[maxn
];
int a2
[maxn
], b2
[maxn
], c2
[maxn
];
int cmp() {
int i
;
if(strlen(a
)>strlen(b
)) {
return 2;
}
else if(strlen(b
)>strlen(a
)) {
return 1;
}
else {
for(i
=0; i
<strlen(a
); i
++) {
if(a
[i
]-'0'<b
[i
]-'0') {
return 1;
}
if(a
[i
]-'0'>b
[i
]-'0') {
return 2;
}
}
return 0;
}
return 0;
}
void swapab() {
int i
;
for(i
=0; i
<strlen(a
); i
++) {
c2
[i
] = a2
[i
];
}
memset(a2
, 0, sizeof a2
);
for(i
=0; i
<strlen(b
); i
++) {
a2
[i
] = b2
[i
];
}
memset(b2
, 0, sizeof b2
);
for(i
=0; i
<strlen(a
); i
++) {
b2
[i
] = c2
[i
];
}
memset(c2
, 0, sizeof c2
);
}
int main() {
cin
>>a
;
cin
>>b
;
int strlena
= strlen(a
);
int strlenb
= strlen(b
);
int i
;
for(i
=0; i
<strlena
; i
++) {
a2
[i
] = a
[strlena
- i
- 1] - '0';
}
for(i
=0; i
<strlenb
; i
++) {
b2
[i
] = b
[strlenb
- i
- 1] - '0';
}
bool isFushu
= false;
switch(cmp()) {
case 1:
isFushu
= true;
swapab();
swap(strlena
, strlenb
);
break;
case 0:
cout
<<0<<endl
;
return 0;
case 2:
isFushu
= false;
break;
}
if(isFushu
)
cout
<<'-';
int tot
= max(strlena
, strlenb
);
int jiewei
= 0;
for(i
=0; i
<tot
; i
++) {
c2
[i
] = a2
[i
] - b2
[i
] - jiewei
;
if(c2
[i
]<0) {
jiewei
= 1;
c2
[i
] = 10 + c2
[i
];
}
else {
jiewei
= 0;
}
}
bool notOK
= true;
for(i
=tot
-1; i
>=0; i
--) {
if(notOK
) {
if(c2
[i
]!=0) {
notOK
= false;
}
else continue;
}
cout
<<c2
[i
];
}
cout
<<endl
;
return 0;
}
二叉建树
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std
;
const char NULL_SUB
= '*';
const int maxn
= 2049;
char tree
[maxn
];
int string_
[maxn
], n
;
void build_tree(int root
, int from
, int to
) {
int left_subtree
= 2 * root
;
int right_subtree
= 2 * root
+ 1;
int mid
= (from
+ to
) / 2;
if(from
==to
) {
switch(string_
[from
]) {
case 0:
tree
[root
] = 'B';
break;
case 1:
tree
[root
] = 'I';
break;
}
tree
[left_subtree
] = NULL_SUB
;
tree
[right_subtree
] = NULL_SUB
;
return;
}
else{
build_tree(left_subtree
, from
, mid
);
build_tree(right_subtree
, mid
+ 1, to
);
if(tree
[left_subtree
]==tree
[right_subtree
]) {
if(tree
[left_subtree
]=='B') {
tree
[root
] = 'B';
}
else if(tree
[left_subtree
]=='I'){
tree
[root
] = 'I';
}
else {
tree
[root
] = 'F';
}
}
else {
tree
[root
] = 'F';
}
}
}
void print_ans(int root
) {
if(tree
[root
]!=NULL_SUB
) {
int left_subtree
= root
* 2;
int right_subtree
= root
* 2 + 1;
print_ans(left_subtree
);
print_ans(right_subtree
);
putchar(tree
[root
]);
}
}
int main() {
cin
>>n
;
n
= pow(2, n
);
char temp
;
for(int i
=0; i
<n
; i
++) {
cin
>>temp
;
string_
[i
] = temp
- '0';
}
build_tree(1, 0, n
-1);
print_ans(1);
putchar('\n');
return 0;
}
求二叉树先序
#include<iostream>
#include<cstring>
using namespace std
;
string zx
, hx
;
int tree
[1000];
void build(int root
, int rootnum
, int from
, int to
);
int findRoot(int l
, int r
);
void xxbl(int root
);
int main() {
memset(tree
, -1, sizeof(tree
));
cin
>>zx
>>hx
;
build(1, findRoot(0, zx
.length()-1), 0, zx
.length()-1);
xxbl(1);
cout
<<endl
;
return 0;
}
void build(int root
, int rootnum
, int from
, int to
) {
tree
[root
] = rootnum
;
int lchild
= root
* 2;
int rchild
= root
* 2 + 1;
if(rootnum
== from
+1) {
tree
[lchild
] = from
;
}
else {
int nextrootnum
= findRoot(from
, rootnum
-1);
if(nextrootnum
!=-1)
build(lchild
, nextrootnum
, from
, rootnum
-1);
}
if(rootnum
== to
-1) {
tree
[rchild
] = to
;
}
else {
int nextrootnum
= findRoot(rootnum
+1, to
);
if(nextrootnum
!=-1)
build(rchild
, nextrootnum
, rootnum
+1, to
);
}
}
int findRoot(int l
, int r
) {
int root
= -1;
int maxa
= -10;
for(int i
=l
; i
<=r
; i
++) {
if((int)hx
.find(zx
[i
])>maxa
) {
maxa
= (int)hx
.find(zx
[i
]);
root
= i
;
}
}
return root
;
}
void xxbl(int root
) {
int lchild
= root
* 2;
int rchild
= root
* 2 + 1;
if(tree
[root
]!=-1) {
cout
<<zx
[tree
[root
]];
}else
{
return;
}
xxbl(lchild
);
xxbl(rchild
);
}
转载请注明原文地址: https://mac.8miu.com/read-495114.html