Noip2015在即，蒟蒻wy决定开始复习noip的各种算法。Noip2015,RP++!
持续更新中，欢迎指导。。。。。。
Day1 今天是7月27日，距Noip2015还有130天，蒟蒻wy开始复习排序。。。
int a[10001];
int t[10001];
void msort(int l,int r){
int mid=(l+r)/2;
msort(l,mid);
msort(mid+1,r);
int i=l,j=mid+1,k=l;
while (i<=mid&&j<=r)
if (a[i]<=a[j]) t[k++]=a[i++];
else t[k++]=a[j++];
while (j<=r) t[k++]=a[j++];
while (i<=mid) t[k++]=a[i++];
for (int i=l;i<=r;++i)
a[i]=t[i];
}
int N;
int a[10001];
void Insert_sort(){
for (int i=2;i<=N;++i){
int key=a[i],j=i-1;
while (key<a[j]){
a[j+1]=a[j];
--j;
}
a[j+1]=key;
}
}
自从转了C++，再也不会快排的wy,决定跳过快排、选排and冒泡。。。
至于桶排、计算排序and基数排序，蒟蒻在此就不提了啊。。。
Day2 今天是7月28日，Ioi在哈萨克斯坦举行，距Noip2015还有129天，蒟蒻wy决定一边膜拜神犇，一边复习高精。。。
struct Number{
int len;
int a[66666];
Number (){
len=1;
memset(a,0,sizeof(a));
}
};
Number operator = (const char * Num){
len=strlen(Num);
for (int i=0;i<len;++i)
a[i+1]=Num[len-i-1]-'0';
return *this;
}
Number operator = (const int &Num){
if (!Num)return *this;
len=0;
for (int k=Num;k;k/=10)
a[++len]=k%10;
return *this;
}
当然赋值不同于初始化，让蒟蒻在结构体里加两行。。。
Number (int Num){
*this=Num;
}
Number (const char *Num){
*this=Num;
}
下面判一下大小关系
bool operator > (const Number &b){
if (len>b.len) return true;
if (len<b.len) return false;
for (int i=len;i;--i)
if (a[i]>b.a[i]) return true;
else if (a[i]<b.a[i]) return false;
return false;
}
bool operator < (const Number &b){
if (len<b.len) return true;
if (len>b.len) return false;
for (int i=len;i;--i)
if (a[i]<b.a[i]) return true;
else if (a[i]>b.a[i]) return false;
return false;
}
bool operator == (const Number &b){
if (len!=b.len) return false;
for (int i=len;i;--i)
if (a[i]!=b.a[i]) return false;
return true;
}
bool operator >= (const Number &b){
if ( *this > b ) return true;
if ( *this == b ) return true;
return false;
}
bool operator <= (const Number &b){
if ( *this < b ) return true;
if ( *this == b ) return true;
return false;
}
现在开始写运算了。。。
Number operator + (const Number &b){
Number c;
c.len=max(len,b.len);
int k=0;
for (int i=1;i<=c.len;++i){
c.a[i]=a[i]+b.a[i]+k;
k=c.a[i]/10;
c.a[i]%=10;
}
if (k)c.a[++c.len]=k;
return c;
}
Number operator - (const Number &b){
//蒟蒻wy表示写的是被减数>=减数的减法
Number c;
c.len=len;
int k=0;
for (int i=1;i<=c.len;++i){
if (a[i]-k<b.a[i]){
c.a[i]=a[i]-k+10-b.a[i];
k=1;
}
else {
c.a[i]=a[i]-k-b.a[i];
k=0;
}
}
for (;c.len>1&&!c.a[c.len];)
--c.len;
return c;
}
Number operator * (const Number &b){
Number c;
c.len=len+b.len;
for (int ai=1;ai<=len;++ai){
int k=0;
for (int bi=1;bi<=b.len;++bi){
c.a[ai+bi-1]+=a[ai]*b.a[bi]+k;
k=c.a[ai+bi-1]/10;
c.a[ai+bi-1]%=10;
}
c.a[ai+b.len]=k;
}
for (;c.len>1&&!c.a[c.len];)
--c.len;
return c;
}
Number operator / (const int &b){
Number c;
c.len=len;
int k=0;
for (int i=c.len;i;--i){
c.a[i]=(k*10+a[i])/b;
k=(k*10+a[i])%b;
}
for (;c.len>1&&!c.a[c.len];)
--c.len;
return c;
}
Number operator / (const Number &b){
Number a=*this;
Number c;
c.len=max(1,len-b.len+1);
for (int i=c.len;i;--i){
Number tmp;
tmp.len=b.len+i-1;
memcpy(tmp.a+i,b.a+1,sizeof(int)*tmp.len);
for (;a>=tmp;){
a-=tmp;
c.a[i]++;
}
}
for (;c.len>1&&!c.a[c.len];)
--c.len;
return c;
}
还有其他一些运算。。。
Number operator += (const Number &a){
*this = *this +a;
return *this;
}
Number operator -= (const Number &a){
*this = *this-a;
return *this;
}
Number operator *= (const Number &a){
*this = *this * a;
return *this;
}
Number operator /=(const int &a){
*this = *this/a;
return *this;
}
Number operator /= (const Number &a){
*this = *this/a;
return *this;
}
Day3 今天是7月29日，距Noip2015还有128天，蒟蒻wy要把高精压一压位。。。
Number operator = (const char * Num){
int l=strlen(Num);
len=0;
int k;
for (int i=0;i<l;++i){
if (!(i%8)){
//蒟蒻wy表示一般压8位。。。
k=1;
++len;
}
a[len]+=(Num[l-i-1]-'0')*k;
k*=10;
}
return *this;
}
void read(){
char Num[66666];
scanf("%s",Num);
*this = Num;
}
void write(){
printf("%d",a[len]);
for (int i=len-1;i;--i)
printf("%08d",a[i]);
printf("\n");
}
各类运算其实是一样的，wy在此就不赘述，只是乘法时注意一下不要爆int了。。。
Day4 今天是7月30日，Ioi中国队被韩国队虐了/(ㄒoㄒ)/~~，距Noip2015还有127天，蒟蒻wy悲伤地复习了一下并查集。。。
int fa[23333]; for (int i=1;i<=N;++i) fa[i]=i;
int find(int x){
return x==fa[x]?x:find(fa[x]);
}
int find(int x){
int r=x;
while (r!=fa[r])
r=fa[r];
int i=x,j;
while (i!=r){
j=fa[i];
fa[i]=r;
i=j;
}
return r;
}
void Merge(int x,int y){
x=find(x);
y=find(y);
if (x==y) return;
fa[x]=y;
}
void Merge(int x,int y){
x=find(x);
y=find(y);
if (x==y) return;
if (rank[x]<=rank[y]){
fa[x]=y;
if (rank[x]==rank[y])
rank[y]++;
}
else fa[y]=x;
}
Day5 今天是7月31日，首都北京申办冬奥会成功啦~\(≧▽≦)/~，距Noip2015还有126天，蒟蒻wy生成一颗最小生成树。。。
int N;
struct Edge{
int x,y,w;
}e[66666];
int fa[66666];
int rank[66666];
int find(int x){
return x==fa[x]?x:find(fa[x]);
}
void Merge(int x,int y){
x=find(x);
y=find(y);
if (x==y) return;
if (rank[x]<=rank[y]){
fa[x]=y;
if (rank[x]==rank[y])
rank[y]++;
}
else fa[y]=x;
}
int cmp(const Edge &x,const Edge &y){
return x.w<y.w;
}
int Kruskal(){
sort(e+1,e+N+1,cmp);
for (int i=1;i<=N;++i)
fa[i]=i;
int cnt=N,Ans=0;
for (int i=1;i<=N;++i){
int u1=find(e[i].x);
int u2=find(e[i].y);
if (u1==u2) continue;
Merge(u1,u2);
Ans+=e[i].w;
if (--cnt==1) break;
}
return Ans;
}
int N;
int tot;
int vis[66666];
int first[66666];
int next[66666];
int end[66666];
int value[66666];
void add(int x,int y,int z){
next[++tot]=first[x];
first[x]=tot;
end[tot]=y;
value[tot]=z;
}
struct Edge{
int x,key;
Edge (int u,int w){
x=u; key=w;
}
};
priority_queue <Edge> Q;
bool operator < (const Edge &x,const Edge &y){
return x.key>y.key;
}
//优先队列是从大到小排序的
int Prim(){
memset(vis,0,sizeof(vis));
vis[1]=1;
for (int k=first[1],v;v=end[k],k;k=next[k])
Q.push(Edge(v,value[k]));
int Ans=0,cnt=0;
for (;!Q.empty();){
Edge e=Q.top();
Q.pop();
if (vis[e.x]) continue;
vis[e.x]=1;
Ans+=e.key;
++cnt;
if (cnt==N-1) break;
for (int k=first[e.x],v;v=end[k],k;k=next[k])
if (!vis[v])
Q.push(Edge(v,value[k]));
}
return Ans;
}
Day6 今天是8月1日，距Noip2015还有125天，蒟蒻wy探寻一下最短路。。。
int N,tot;
struct Edge{
int u,v,w;
Edge(int x=0,int y=0,int s=0){
u=x; v=y; w=s;
}
}e[23333];
int dis[2333][2333];
void Floyed_Warshall(){
for (int i=1;i<=tot;++i)
dis[e[i].u][e[i].v]=dis[e[i].v][e[i].u]=e[i].w;
for (int k=1;k<=N;++k)
for (int i=1;i<=N;++i)
for (int j=1;j<=N;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
int tot;
int first[66666];
int next[66666];
int end[66666];
int value[66666];
int dist[66666];
int vis[66666];
queue <int> Q;
void add(int x,int y,int z){
next[++tot]=first[x];
first[x]=tot;
end[tot]=y;
value[tot]=z;
}
void SPFA(int s){
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[s]=0;
vis[s]=1;
Q.push(s);
for (;!Q.empty();){
int u=Q.front();
Q.pop();
vis[u]=0;
for (int k=first[u],v;v=end[k],k;k=next[k])
if (dist[v]>dist[u]+value[k]){
dist[v]=dist[u]+value[k];
if (!vis[v]){
vis[v]=1;
Q.push(v);
}
}
}
}
int tot;
int first[66666];
int next[66666];
int end[66666];
int value[66666];
int vis[66666];
int dist[66666];
void add(int x,int y,int z){
next[++tot]=first[x];
first[x]=tot;
end[tot]=y;
value[tot]=z;
}
struct point{
int x,key;
point (int u,int s){
x=u; key=s;
}
};
priority_queue <point> H;
bool operator < (const point &x,const point &y){
return x.key>y.key;
}
void Dijkstra(int s){
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
vis[s]=1;
H.push(point(s,dist[s]=0));
for (;!H.empty();){
int u=(H.top()).x;
H.pop();
if (vis[u])continue;
vis[u]=1;
for (int k=first[u],v;v=end[k],k;k=next[k])
if (dist[v]>dist[u]+value[k]){
dist[v]=dist[u]+value[k];
H.push(point(v,dist[v]));
}
}
}
Day7 今天是9月26日，蒟蒻wy又回来啦。。。听说距Noip2015 have only 49天,让wy堆一个堆来压压惊。。。
void Put(int x){
heap[++size]=x;
for (int now=size,next;next=now/2,next&heap[now]<heap[next];now=next)
swap(heap[now],heap[next]);
}
int Get(){
int get=heap[1];
heap[1]=heap[size--];
for (int now=1,next;next=now*2,next<=size;now=next){
if (next<size&&heap[next+1]<heap[next]) ++next;
if (heap[now]<=heap[next]) break;
swap(heap[now],heap[next]);
}
return get;
}
Ps:以上是小根堆。。。
以下C++自带版。。。
void put(int x){
heap[++size]=x;
push_heap(heap+1,heap+size+1); //-->这是大根堆
push_heap(heap+1,heap+size+1,greater <int> () ); //-->这是小根堆
}
int get(){
pop_heap(heap+1,heap+size+1); //-->这是大根堆
pop_heap(heap+1,heap+size+1,greater <int> () ); //-->这是小根堆
return heap[size--];
}
Day8 今天是10月2日，国庆长假第二天。。。距Noip2015还有43天,wy默默地来了个拓扑排序。。。
#include<queue>
#include<cstdio>
using namespace std;
const int MaxN=66666;
queue <int> Q;
int N,M,cnt,tot,s[MaxN],d[MaxN];
int first[MaxN],next[MaxN],end[MaxN];
void Add(int x,int y){
next[++tot]=first[x]; first[x]=tot; end[tot]=y;
}
void Get(){
for (int i=1;i<=M;++i){
int x,y;
scanf("%d%d",&x,&y);
d[y]++;
Add(x,y);
}
}
void TopoSort(){
cnt=0;
for (int i=1;i<=N;++i)
if (!d[i]) Q.push(i);
for (;!Q.empty();){
int u=Q.front();
Q.pop();
s[++cnt]=u;
for (int k=first[u],v;v=end[k],k;k=next[k])
if (!(d[v]--)) Q.push(v);
}
}
评论 (0)
