前排碎碎念
今天是去if楼的第二天，昨晚开了好久好久的会，小狮子要来湘潭找我了，有些开心。但是好好学习比较重要捏，那就让他先独守空房一阵子叭，诶嘿今天我值日，虽然我早上起不来但是可以晚上晚点走，主打一个新加坡作息。
浅浅看一下今天的任务清单好咯。
任务清单
- 高精度
- 快速幂
- 并查集
- 前缀和与拆分
- 最小生成树
并查集
简单来说并查集的任务就是查找祖先，合并祖先。是五一假期的任务，今天想去写最小生成树所以先复习一下下。
写的是板子：https://www.luogu.com.cn/problem/P3367
MLE了一发TLE了一发第三次才AC。
MLE是因为把合并和查找是否共同祖先都单独写了函数出来，开辟的空间有点大了。
TLE是因为find函数的路径压缩写错了
最后附一下AC代码：
点击查看代码
#include<iostream>
using namespace std;
int fa[10005];
int find(int a){
if(fa[a]==a)return a;
else return fa[a]=find(fa[a]);
}
int main(){
int n,m,z,x,y;
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
}
while(m--){
cin>>z>>x>>y;
if(z==1){
fa[find(x)]=find(y);
}
if(z==2){
if(find(x)==find(y))cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
return 0;
}
最小生成树
首先还是对板子题下手：https://www.luogu.com.cn/problem/P3366
感觉理解了但是写不出来，呜呜呜呜emo了。
最小生成树的两个算法分别是：kruskal算法和prim算法。
krusal的特点是归并边，每次选取不在同一个连通分量的权值最小的边加进来。
prim算法的特点是归并点，每次选取在该集合的点但是终点不在集合中的权值最小的边。
由于不会链式前向星于是想用prim算法，疑问点在于如何选取权值最小的边，因为起点是集合中的任意点所以...如何综合排序呢。
遇事不决抄题解bushi（怎么能学术作弊呢，当然是要做到学术诚信咯），但我还是在想要放弃的时候看了一下题解，发现自己实际上是被邻接表和邻接矩阵绕进去了，除了链式前向星这个比较难以理解的存储方式之外还有一个更为省事的，那就是结构体直接存图啊！！！好嘞开写！
然后用kruskal算法做了，但是连续两发WA，但是样例是ok的，所以纠结了一下发现自己的注释没有删...然后发现最后一个测试点RE了（芜湖起飞）
然后保存一下结果的输入输出，发现标准输出的结果是orz回想起题目说如果不连通输出orz...额外添加了一个判断是否遍历到最后一条边的if，然后快乐AC
代码如下：
点击查看代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fa[5005];
struct edge{
int u,v,w;
}e[200005];
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
bool cmp(edge x,edge y){
return x.w<y.w;
}
int main(){
int n,m,x,y,z,tt=0,cnt,p;
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
sort(e+1,e+m+1,cmp);
cnt=n-1;p=0;
while(cnt!=0){
p++;
x=e[p].u;y=e[p].v;z=e[p].w;
if(find(x)!=find(y)){
tt+=z;
cnt--;
fa[find(x)]=find(y);
//cout<<x<<" "<<y<<" "<<z<<endl;
}
if(p>m){
cout<<"orz"<<endl;
return 0;
}
}
cout<<tt<<endl;
return 0;
}
高精度
我哭死，高精度减法调了好久
实际上高精度本质就是将一个很大很大的数用字符串表示，然后对这个字符串进行操作。
要注意的就是需要把字符串反置存入数组，以及加减乘除的借位与进位，减法更要注意的是减数与被减数的大小差别（也就是是否会产生负数）
高精度复读机
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[1004];
int main(){
char s[1004 + 1];
scanf("%s", s);
int len=strlen(s);
for(int i=0;i<len;i++){
a[len-i-1]=s[i]-'0';
}
int i;
for(i=len-1;i>=1;i--){
if(a[i]!=0)break;
}
for(;i>=0;i--){
cout<<a[i];
}
cout<<endl;
return 0;
}
快速幂
本质：将a的（b+c）次方转换为a的b次方乘以a的c次方，从而降低复杂度。
方法：例如计算a的n次方，将n用二进制进行表示，二进制位置为1的地方相加
代码如下：
long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
前缀和
多维前缀和基于容斥原理
最基础的代码就是
{
b[0]=a[0];
b[i]=b[i-1]+a[i];
}
前些时候把基础的题做了一下，翻了翻列表发现自己曾经六月初有个题目没改完就放在那了所以就索性写一写这个题目了：https://www.luogu.com.cn/problem/P5638
注意他给出的数据是从i-1点到i点所用的时间ai；
ac代码如下：
点击查看代码
#include<iostream>
using namespace std;
long long a[1000005];//存储各个路的时间
long long s[1000005];//前缀和
long long as[1000005];//从ai点使用传送所能节省的时间
int main(){
long long n,k;
cin>>n>>k;
for(int i=2;i<=n;i++){
cin>>a[i];
}
s[1]=a[1];
for(int i=2;i<=n;i++){
s[i]=s[i-1]+a[i];
}
long long q,p;
for(int i=1;i<=n;i++){
q=i+k;
if(q>n)q=n;
as[i]=s[q]-s[i];
}
long long mx=0;
for(int i=1;i<=n;i++){
if(as[i]>mx)mx=as[i];
}
cout<<s[n]-mx<<endl;
return 0;
}