首页 > 代码库 > 算是回归的第一晚 (啥也不记得了。。从模板开刷!!)

算是回归的第一晚 (啥也不记得了。。从模板开刷!!)

技术分享
#include <ctype.h>#include <cstdio>#define N 10000050void read(int &x){    x=0;bool f=0;    char ch=getchar();    while(!isdigit(ch)) {if(ch==-) f=1;ch=getchar();}    while(isdigit(ch)) {x=x*10+(int)ch-0;ch=getchar();}    x=f?(~x)+1:x;}int n,m,Prime[N],num;bool isPrime[N];int main(){    read(n);read(m);    for(int i=2;i<=n;i++)    {        if(!isPrime[i]) Prime[num++]=i;        for(int j=0;j<num&&i*Prime[j]<=n;j++)        {            isPrime[i*Prime[j]]=1;            if(i%Prime[j]==0) break;        }    }    isPrime[0]=isPrime[1]=1;    for(int x;m--;)    {        read(x);        if(isPrime[x]) printf("No\n");        else printf("Yes\n");    }    return 0;}
【模板】线性筛素数
技术分享
#include <ctype.h>#include <cstdio>#define N 10050void read(int &x){    x=0;bool f=0;    char ch=getchar();    while(!isdigit(ch)) {if(ch==-) f=1;ch=getchar();}    while(isdigit(ch)) {x=x*10+(int)ch-0;ch=getchar();}    x=f?(~x)+1:x;}int fa[N],n,m;int find_(int x){return fa[x]==x?x:fa[x]=find_(fa[x]);}int main(){    read(n);read(m);    for(int i=1;i<=n;i++) fa[i]=i;    for(int type,x,y;m--;)    {        read(type);read(x);read(y);        if(type==1)        {            int fx=find_(x),fy=find_(y);            if(fx!=fy) fa[fy]=fx;        }        else if(type==2) find_(x)==find_(y)?printf("Y\n"):printf("N\n");    }    return 0;}
【模板】并查集
技术分享
#include <ctype.h>#include <cstdio>#define N 4000005void read(int &x){    x=0;bool f=0;char ch=getchar();    while(!isdigit(ch)) {if(ch==-) f=1;ch=getchar();}    while(isdigit(ch)) {x=x*10+(int)ch-0;ch=getchar();}    x=f?(~x)+1:x;}int n,heap[N],top;void swap(int &x,int &y){    int tmp=y;    y=x;    x=tmp;}void push_heap(int m){    heap[++top]=m;    int now=top;    while(now>1)    {        int next=now/2;        if(heap[next]<heap[now]) break;        swap(heap[now],heap[now/2]);        now=next;    }}void heap_pop(){    heap[1]=heap[top--];    int now=1;    while(now*2<=top)    {        int next=now<<1;        if(heap[next]>heap[next+1]) next++;        if(heap[next]>=heap[now]) break;        swap(heap[next],heap[now]);        now=next;    }}int main(){    read(n);    for(int x,y;n--;)    {        read(x);        if(x==1) read(y),push_heap(y);        else if(x==2) printf("%d\n",heap[1]);        else heap_pop();    }    return 0;}
【模板】堆
技术分享
#include <algorithm>#include <ctype.h>#include <cstdio>#define N 200005using namespace std;void read(int &x){    x=0;bool f=0;    char ch=getchar();    while(!isdigit(ch)) {if(ch==-) f=1;ch=getchar();}    while(isdigit(ch)) {x=x*10+(int)ch-0;ch=getchar();}    x=f?(~x)+1:x;}int n,m;struct node{    int x,y,z;    bool operator<(node a)const     {        return z<a.z;    }}edge[N];bool vis[N];int fa[N],cnt;int find_(int x){    return x==fa[x]?x:fa[x]=find_(fa[x]);}int main(){    read(n);read(m);    for(int i=1;i<=n;i++) fa[i]=i;    for(int x,y,z;m--;)    {        read(x);read(y);read(z);        edge[++cnt].x=x;        edge[cnt].y=y;        edge[cnt].z=z;    }    sort(edge+1,edge+1+cnt);    int ans=0,num=0;    for(int i=1;i<=cnt;i++)    {        int fx=edge[i].x,fy=edge[i].y;        if(find_(fx)!=find_(fy))        {            fa[find_(fy)]=find_(fx);            ans+=edge[i].z;            num++;            if(num==n-1) break;         }    }    printf("%d\n",ans);    return 0;}
【模板】最小生成树

 

算是回归的第一晚 (啥也不记得了。。从模板开刷!!)