템플릿 요약

88019 단어 거푸집
본 블로그의 모든 템플릿은 테스트를 거쳐 정확함을 보증합니다.
병합 정렬
#include
#include
#include
#include
using namespace std;
const int N=1e5+77;
int a[N],n,tmp[N];
void Sort(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    Sort(l,mid);
    Sort(mid+1,r);
    int i=l,j=mid+1,t=l;
    bool start;
    while(i<=mid||j<=r)
    {
        if(i>mid) start=1;
        else
        if(j>r) start=0;
        else
        if(a[i]<=a[j]) start=0;
        else start=1;

        if(start) tmp[t++]=a[j++];
        else tmp[t++]=a[i++];
    }
    for(int i=l;i<=r;i++) a[i]=tmp[i];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     scanf("%d",&a[i]);
    Sort(1,n);
    for(int i=1;i<=n;i++)
     printf("%d ",a[i]);
    return 0; 
}

LCS 
#include
#include
#include
#include
#include
#include
#include
using namespace std;
map <int,int> ma; 
int n,m;
int s1[300009],s2[300009];
int a[300009],low[300009],len;
int find(int l,int r,int z)
{
    int mid;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(low[mid]<=z)
         l=mid+1;
        else r=mid-1;
    }
    return l;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
      scanf("%d",&s1[i]);
    for(int i=1;i<=m;i++)
      scanf("%d",&s2[i]);
    for(int i=1;i<=m;i++)
      ma[s2[i]]=i;
    for(int i=1;i<=n;i++)
      a[i]=ma[s1[i]];
    int t=1;
    while(a[t]==0) t++;
    low[++len]=a[t];
    for(int i=2;i<=n;i++)
    {
        if(a[i]==0) continue;
        if(a[i]>low[len])
         low[++len]=a[i];
        else
         {
            //low[upper_bound(low+1,low+len+1,a[i])-low]=a[i];
            low[find(1,len,a[i])]=a[i];
         }
    }   
    printf("%d",len);
    return 0;

}
#include
#include
#include
#include
#include 
using namespace std;
const int N=1e5+77;
int n,f[N],a[N],b[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);

    for(int i=1;i<=n;i++) f[b[i]]=i,b[i]=0;
    for(int i=1;i<=n;i++) a[i]=f[a[i]];

    int len=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>b[len]) b[++len]=a[i];
        else b[upper_bound(b+1,b+len+1,a[i])-b]=a[i];
    }
    printf("%d
",len);
    return 0;
}

작은 B의 질문(모팀)
#include
#include
#include
#include
#include 
using namespace std;
const int N=5e4+77;
struct Q{
    int qv,id,l,r;
}q[N];
int n,m,k,a[N],ans[N],cnt[N],sum;
bool cmp(Q x,Q y)
{
    if(x.qv==y.qv) return x.r<y.r;
    return x.qv<y.qv;
}
void add(int x)
{
    if(!x) return;
    sum-=cnt[x]*cnt[x];
    cnt[x]++;
    sum+=cnt[x]*cnt[x];
}
void del(int x)
{
    if(!x) return;
    sum-=cnt[x]*cnt[x];
    cnt[x]--;
    sum+=cnt[x]*cnt[x];
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int limit=sqrt(n+10);
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        q[i].l=l,q[i].r=r;
        q[i].qv=q[i].l/limit;
        q[i].id=i;
    } 
    sort(q+1,q+m+1,cmp);

    int l=0,r=0;
    for(int i=1;i<=m;i++)
    {
        while(r<q[i].r)
        {
            add(a[++r]);
        }
        while(r>q[i].r)
        {
            del(a[r--]);
        }
        while(l<q[i].l)
        {
            del(a[l++]);
        }
        while(l>q[i].l)
        {
            add(a[--l]);
        }

        ans[q[i].id]=sum;
    }
    for(int i=1;i<=m;i++)
     printf("%d
",ans[i]);
    return 0;
}

함께 조사하여 모으다
#include
#include
#include
#include
#include 
using namespace std;
const int N=1e4+77;
int n,m,f[N];
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        int fx=find(x),fy=find(y);
        if(opt==1)
        {
            if(fx==fy) continue;
            f[fx]=fy;
        }
        else
        {
            if(fx==fy) printf("Y
");
            else printf("N
");
        }
    } 
    return 0;
}

최소 스패닝 트리
#include
#include
#include
#include
using namespace std;
const int M=2e5+77;
const int N=5077;
struct E{
    int x,y,z;
}e[M];
int n,m,f[N],ans;
bool cmp(E a,E b)
{
    return a.zint find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
    }
    sort(e+1,e+m+1,cmp);

    int cnt=n;
    for(int i=1;i<=m;i++)
    {
        int fx=find(e[i].x),fy=find(e[i].y);
        if(fx==fy) continue;
        f[fx]=fy;
        ans+=e[i].z;
        cnt--;
        if(cnt==1) break;
    }
    if(cnt==1) printf("%d
",ans);
    else printf("orz
");
    return 0;
}

문자열 해시
#include
#include
#include
#include
#define LL long long
using namespace std;
const int mo=1e9+7;
const int moo=1e9+9;
const int b1=31;
const int b2=29;
const int M=1507;
const int N=1e4+77; 
int n,ans;
struct H{
    LL a,b;
}q[N];
char s[M];
bool cmp(H x,H y)
{
    return x.a<y.a;
}
LL hash()
{
    LL h=0;
    int len=strlen(s);
    for(int i=0;i*b1%mo+s[i]-'0')%mo;
    return h;
}
LL Hash()
{
    LL h=0;
    int len=strlen(s);
    for(int i=0;i*b2%moo+s[i]-'0')%moo;
    return h;
}
int main()
{
    scanf("%d
",&n);
    for(int i=1;i<=n;i++)
    {
        gets(s);
        q[i].a=hash();
        q[i].b=Hash();
    }
    q[0].a=q[0].b=-1;
    sort(q+1,q+n+1,cmp);
    for(int i=1;i<=n;i++)
      if(q[i].a!=q[i-1].a||q[i].b!=q[i-1].b)
        ans++;
    printf("%d
",ans);
    return 0;
}

최단 경로 spfa O (K*m/RP)
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int N=1e4+77;
const int M=5e5+77;
const int inf=2147483647;
int n,m,s;
int head[N],nxt[M],to[M],cost[M],tot;
LL dis[N]; 
bool vis[N];
void add(int x,int y,int z)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
    cost[tot]=z;
}
void spfa()
{
    queue <int> q;
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=nxt[i])
          if(dis[to[i]]>dis[x]+cost[i]){
            dis[to[i]]=dis[x]+cost[i];
            if(!vis[to[i]])
            {
                vis[to[i]]=1;
                q.push(to[i]);
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z); 
        if(i<=n) dis[i]=inf;
    }
    spfa();
    for(int i=1;i<=n;i++)
       printf("%lld ",dis[i]);
    return 0; 
}

최단 거리 Dijsktra O (n^n)
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int N=1e4+77;
const int M=5e5+77;
const int inf=2147483647;
int n,m,s;
int head[N],nxt[M],to[M],cost[M],tot;
LL dis[N]; 
bool vis[N];
void add(int x,int y,int z)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
    cost[tot]=z;
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z); 
        if(i<=n) dis[i]=inf;
    }
    dis[s]=0;
    for(int i=1;iint minn=inf,x=0;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&minn>dis[j])
             minn=dis[j],x=j;
        }
        if(!x) break;
        vis[x]=1;
        for(int j=head[x];j;j=nxt[j])
          if(dis[to[j]]>dis[x]+cost[j])
            dis[to[j]]=dis[x]+cost[j];
    }
    for(int i=1;i<=n;i++)
     printf("%d ",dis[i]);
    return 0;
}

트리 배열(단일 수정 + 구간 구화)
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int N=5e5+77;
int n,m;
LL a[N],b[N];
void update(int i,LL x)
{
    for(;i<=n;i+=i&(-i))
      b[i]+=x;
}
LL query(int x)
{
    LL s=0; 
    for(int i=x;i>=1;i-=i&(-i))
      s+=b[i];
    return s;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        update(i,a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int opt,x,y;
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d",&x,&y);
            update(x,y);
        }
        else
        {
            scanf("%d%d",&x,&y);
            LL ans=query(y);
            ans-=query(x-1);
            printf("%lld
",ans);
        }
    }
    return 0;
}

세그먼트 트리 1구간 수정 + 구간 구화
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int N=1e5+77; 
struct H{
    LL sum,ad;
    int len;
}z[4*N];
int n,m,a[N];
void build(int o,int l,int r)
{
    if(l==r){
        z[o].sum=a[l];
        z[o].len=r-l+1;
        return;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    z[o].sum=z[o<<1].sum+z[o<<1|1].sum;
    z[o].len=r-l+1;
}
void push_down(int o)
{
    if(z[o].ad)
    {
        LL ad=z[o].ad;
        z[o<<1].sum+=ad*z[o<<1].len;
        z[o<<1|1].sum+=ad*z[o<<1|1].len; 
        z[o<<1].ad+=ad;
        z[o<<1|1].ad+=ad;
        z[o].ad=0;
    }
}
LL query(int o,int l,int r,int ql,int qr)
{
    if(ql>r||qr=r) return z[o].sum;

    push_down(o);

    int mid=(l+r)>>1;
    LL s=0;
    s+=query(o<<1,l,mid,ql,qr);
    s+=query(o<<1|1,mid+1,r,ql,qr);
    return s;
}
void change(int o,int l,int r,int ql,int qr,LL add)
{
    if(ql>r||qr=r) 
    {
        z[o].sum+=add*z[o].len;
        z[o].ad+=add;
        return;
    } 

    push_down(o);

    int mid=(l+r)>>1; 
    change(o<<1,l,mid,ql,qr,add);
    change(o<<1|1,mid+1,r,ql,qr,add); 
    z[o].sum=z[o<<1].sum+z[o<<1|1].sum;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    build(1,1,n);

    for(int i=1;i<=m;i++)
    {
        int opt,l,r,k;
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d%d",&l,&r,&k);
            change(1,1,n,l,r,k);    
        }
        else
        {
            scanf("%d%d",&l,&r);
            LL ans=query(1,1,n,l,r);
            printf("%lld
",ans);
        }
    }
    return 0;
}

ST 표
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+77;
int n,m,a[N],ans;
int MAX[N][20];
int main()
{ 
    //freopen("b.txt","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),MAX[i][0]=a[i];
    for(int j=1;(1<for(int i=1;i<=n;i++)
        {
            if(i+(1<1<=n)
            MAX[i][j]=max(MAX[i][j-1],MAX[i+(1<1)][j-1]);
        }
    }
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int t=log2(r-l+1);
        ans=max(MAX[l][t],MAX[r-(1<1][t]);
        printf("%d
",ans);
    }
    return 0;
}

KMP 
#include
#include
#include
#include
using namespace std;
const int N=1000007;
int nxt[N],len1,len2,ans[N],cnt;
char a[N],b[N];
void next_make()
{
    int i=0,j=-1;
    nxt[0]=-1;
    while(iif(j==-1||b[i]==b[j])
          nxt[++i]=++j;
        else 
          j=nxt[j];
    }
}
void match(int i,int j)
{
    while(iwhile(jif(j==-1||a[i]==b[j])
             i++,j++;
            else j=nxt[j];
        }
        if(j==len2) ans[++cnt]=i-len2+1,j=nxt[j];
    }
}
int main()
{
    cin>>a;len1=strlen(a);
    cin>>b;len2=strlen(b);

    next_make();
    match(0,0);
    for(int i=1;i<=cnt;i++)
     printf("%d
",ans[i]);
    for(int i=1;i<=len2;i++)
     printf("%d ",nxt[i]);
    return 0;
}

선형 곱셈 역원
증명서
#include
#include
#include
#include
#define LL long long 
using namespace std;
const int N=3e6+7;
LL n,p,a[N];
int main()
{
    scanf("%lld%lld",&n,&p);
    a[1]=1;
    printf("%d
",a[1]);
    for(int i=2;i<=n;i++)
    {
        a[i]=-(p/i)*(a[p%i]);
        a[i]=(a[i]%p+p)%p;
        printf("%lld
",a[i]);
    } 
    return 0;
}

Tarjan LCA
#include
#include
#include
#include
#define LL long long 
using namespace std;
const int N=500007;
int n,m,s;
int head[N],nxt[2*N],to[2*N],tot;
int qhead[N],qnxt[2*N],qto[2*N],qtot,lca[2*N];
int f[N];
bool vis[N];
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void qadd(int x,int y)
{
    qto[++qtot]=y;
    qnxt[qtot]=qhead[x];
    qhead[x]=qtot;
}
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]); 
}
void dfs(int x)
{
    f[x]=x;
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        if(!vis[to[i]])
        {
            dfs(to[i]);
            f[to[i]]=x;
        }
    }
    for(int i=qhead[x];i;i=qnxt[i])
    {
        if(vis[qto[i]])
        {
            lca[i]=find(qto[i]);
            if(i%2) lca[i+1]=lca[i];
            else lca[i-1]=lca[i];
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;iint x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }

    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        qadd(x,y);qadd(y,x);
    }

    dfs(s);

    for(int i=1;i<=m;i++)
    {
        printf("%d
",lca[2*i]);
    }
    return 0;
}

LCA 추가
#include
#include
#include
#include
#define LL long long 
using namespace std;
const int N=500007;
int n,m,s;
int head[N],nxt[2*N],to[2*N],tot;
int dep[N],f[N][22];
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dfs(int x,int father)
{
    for(int i=head[x];i;i=nxt[i])
    {
        if(to[i]==father) continue;
        dep[to[i]]=dep[x]+1;
        f[to[i]][0]=x;
        dfs(to[i],x); 
    }
}
int find(int x,int y)
{
    if(x==y) return x; 
    if(dep[x]int i,j;
    for(i=20;i>=0;i--)
    {
        if(dep[x]==dep[y]) break;
        if(f[x][i])
          if(dep[f[x][i]]>=dep[y])
            x=f[x][i];
    }

    if(x==y) return x;

    for(i=20;i>=0;i--)
    {   
        if(f[x][i]&&f[y][i]&&f[x][i]!=f[y][i])//           
            x=f[x][i],y=f[y][i];
    }
    return f[x][0];
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;iint x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }

    dfs(s,0);

    for(int j=1;(1<for(int i=1;i<=n;i++)
        {
            if(f[f[i][j-1]][j-1])
             f[i][j]=f[f[i][j-1]][j-1];
        }
    }

    for(int i=1;i<=m;i++)
    {
        int x,y,ans;
        scanf("%d%d",&x,&y);
        ans=find(x,y);
        printf("%d
",ans); 
    }
    return 0;
}

Tarjan 축소점 + 트리 dp (spfa도 사용 가능)
#include
#include
#include
#include
#define LL long long 
using namespace std;
const int N=1e4+7;
const int M=1e5+7;
int n,m,a[N];
int head[N],nxt[M],to[M],tot;
int color[N],dfn[N],low[N],dfs_num,color_num,stack[N],top;
int cnt[N],sum[N],f[N];
bool vis[N];
LL ans,son_max[N];
int X[M],Y[M];
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dfs(int x)
{
    stack[++top]=x;
    dfn[x]=++dfs_num;
    low[x]=dfs_num;
    vis[x]=1;

    for(int i=head[x];i;i=nxt[i])
    {
        if(!dfn[to[i]])
        {
            dfs(to[i]);
            low[x]=min(low[x],low[to[i]]);
        }
        else if(vis[to[i]]) low[x]=min(low[x],dfn[to[i]]);
    }

    if(low[x]==dfn[x])
    {
        vis[x]=0;
        color[x]=++color_num;
        cnt[color_num]++;
        sum[color_num]+=a[x];
        while(stack[top]!=x)
        {
            vis[stack[top]]=0;
            color[stack[top]]=color_num;
            cnt[color_num]++;
            sum[color_num]+=a[stack[top]];
            top--;
        }
        top--;
    }
}
LL DFS(int x)
{
    LL s=sum[x],p=0;
    for(int i=head[x];i;i=nxt[i])
    {
        p=max(p,(son_max[to[i]])?son_max[to[i]]:son_max[to[i]]=DFS(to[i]));
    }
    return son_max[x]=s+p;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        X[i]=x;
        Y[i]=y;//       
    }

    for(int i=1;i<=n;i++)
     if(!dfn[i]) dfs(i);

    memset(nxt,0,sizeof(nxt));
    memset(to,0,sizeof(to));
    memset(head,0,sizeof(head));
    tot=0;

    for(int i=1;i<=m;i++)
    {
        if(color[X[i]]!=color[Y[i]])
        add(color[X[i]],color[Y[i]]);
    }

    for(int i=1;i<=color_num;i++)
    {
         ans=max(ans,DFS(i));
    }

    printf("%lld
",ans);
    return 0;
}

이분도 최대 일치 (헝가리 알고리즘)
#include
#include
#include
#include
using namespace std;
const int N=1009;
int match[2*N];
bool book[2*N];
int head[2*N],nxt[N*N],to[N*N],tot;
int n,m,e,ans;
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int dfs(int x)
{
    for(int i=head[x];i;i=nxt[i])
    {
        if(!book[to[i]])
        {
            book[to[i]]=1;
            if(!match[to[i]]||dfs(match[to[i]]))
            {
                match[x]=to[i];
                match[to[i]]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=e;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(v>m) continue;
        add(u,v+n);add(v+n,u);
    }

    for(int i=1;i<=n;i++)
    {
        memset(book,0,sizeof(book));
        ans+=dfs(i);
    }
    printf("%d
",ans);
    return 0; 
}

dfs_spfa판단 마이너스 링
그 사상은 광도 우선의 사상을 채택하여 우리가 새로운 노드를 확장할 때마다 항상 그것을 대열의 끝에 두는데 그 단점은 교체의 연속성을 중단하는 것이다.실제로 깊이 우선 사상을 채택하면 우리는 이 새로운 노드에서 계속 확장할 수 있다.그래서 알고리즘의 실현 방식은 끊임없이 새로운 노드에서 아래로 돌아가며 해답을 구하는 것으로 바꿀 수 있다.마이너스 고리에 대한 판단은 더욱 간단해 보인다. 왜냐하면 마이너스 고리 a1->a2->가 존재한다면...ak->a1, 그러면 알고리즘이 실행될 때 어느 점 a1에서 Dfs를 시작하고 마지막에 이 점으로 돌아갑니다.따라서 현재 노드가 귀속 창고에 있는지 보조수 그룹으로 기록하면 마이너스 링을 신속하게 검출할 수 있다.
#include
#include
#include
#define LL long long 
using namespace std;
const int N=200007;
/*inline LL read()
{
    LL x,p=1;
    char ch=getchar();
    while(ch'9') 
    {
        if(ch=='-') p=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'9',ch=getchar();
    return x*p;
}*/
int Q,n,m;
int head[N],nxt[2*N],to[2*N],cost[2*N],tot;
int dis[N];
bool vis[N],exist;
void add(int x,int y,int z)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
    cost[tot]=z;
}
void init()
{
    memset(head,0,sizeof(head));
    memset(to,0,sizeof(to));
    memset(nxt,0,sizeof(nxt));
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    tot=0;
    exist=0;
}
void dfs_spfa(int x)
{
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        if(dis[to[i]]>dis[x]+cost[i])
        {
            if(vis[to[i]]) {
                exist=1;
                return;
            }
            dis[to[i]]=dis[x]+cost[i];
            dfs_spfa(to[i]);
        } 
    }
    vis[x]=0;
}
int main()
{
    scanf("%d",&Q);
    while(Q--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            if(z<0) add(x,y,z);
            else {
                add(x,y,z);
                add(y,x,z);
            }
        }
        for(int i=1;i<=n;i++)
        {
            dfs_spfa(i);
            if(exist) break;
        }
        if(exist) printf("YE5
");
        else printf("N0
");
    }
    return 0;
}

오라 함수의 선형 체 (부수소수 선형 체)
#include
#include
#include
#include
using namespace std;
const int N=1e7+7;
int prime[N],cnt,phi[N];
bool np[N];
void PHI()
{
    phi[1]=1;
    np[0]=1,np[1]=1;
    for(int i=2;iif(!np[i]) 
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&1ll*i*prime[j]1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int main()
{
    PHI();
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      printf("%d
",phi[i]);
    return 0;
}

동여방정식
#include
#include
#include
#include
#define LL long long
using namespace std;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    LL gcd=exgcd(b,a%b,x,y);
    LL tmp=x;
    x=y;
    y=tmp-a/b*y;
    return gcd;
}
int main()
{
    LL a,b,x,y;
    scanf("%lld%lld",&a,&b);
    LL gcd=exgcd(a,b,x,y);
    printf("%lld",(x+b)%b);
    return 0;
}

고정승 고정
#include
#include
#include
#include
using namespace std;
const int N=1e4+7;
const int P=1e4;
char s1[N],s2[N];
int a[N],b[N],c[2*N];
int len1,len2,l1,l2;
int main()
{
    scanf("%s",s1);l1=strlen(s1);
    scanf("%s",s2);l2=strlen(s2);

    len1=len2=1;
    int x=1;
    for(int i=l1-1;i>=0;i--)
    {
        a[len1]+=(s1[i]-'0')*x;
        x=(x<<1)+(x<<3);
        if(x==P) x=1,++len1; 
    }
    x=1;
    for(int i=l2-1;i>=0;i--)
    {
        b[len2]+=(s2[i]-'0')*x;
        x=(x<<1)+(x<<3);
        if(x==P) x=1,++len2;
    }

    for(int i=1;i<=len1;i++)
    {
        x=0;
        for(int j=1;j<=len2;j++)
        {
            c[i+j-1]+=a[i]*b[j]+x;
            x=c[i+j-1]/P;
            c[i+j-1]%=P;
        }
        c[i+len2]+=x;
    }
    int len=len1+len2;
    while(len>1&&!c[len]) len--;

    printf("%d",c[len--]);
    for(int i=len;i>=1;i--)
     printf("%04d",c[i]);
    return 0;
}

저정밀
#include
#include
#include
#include
#define LL long long
using namespace std;
const int P=1e9;
const int N=1e5;
char s[N];
LL a[N],b;
int main()
{
    scanf("%s%lld",s,&b);
    int L=strlen(s);
    LL k=1;int len=1;
    for(int i=L-1;i>=0;i--)
    {
        a[len]+=(s[i]-'0')*k;
        k=(k<<1)+(k<<3);
        if(k==P) k=1,++len;
    }
    for(int i=len;i>=1;i--)
    {
        a[i-1]+=a[i]%b*P;
        a[i]/=b;
    }
    while(len>=1&&!a[len]) len--;

    printf("%lld",a[len--]);
    for(int i=len;i>=1;i--)
     printf("%09d",a[i]);
    return 0;
}

고정승 고정
#include
#include
#include
#include
using namespace std;
const int N=1e4+7;
const int P=1e4;
char s1[N],s2[N];
int a[N],b[N],c[2*N];
int len1,len2,l1,l2;
int main()
{
    scanf("%s",s1);l1=strlen(s1);
    scanf("%s",s2);l2=strlen(s2);

    len1=len2=1;
    int x=1;
    for(int i=l1-1;i>=0;i--)
    {
        a[len1]+=(s1[i]-'0')*x;
        x=(x<<1)+(x<<3);
        if(x==P) x=1,++len1; 
    }
    x=1;
    for(int i=l2-1;i>=0;i--)
    {
        b[len2]+=(s2[i]-'0')*x;
        x=(x<<1)+(x<<3);
        if(x==P) x=1,++len2;
    }

    for(int i=1;i<=len1;i++)
    {
        x=0;
        for(int j=1;j<=len2;j++)
        {
            c[i+j-1]+=a[i]*b[j]+x;
            x=c[i+j-1]/P;
            c[i+j-1]%=P;
        }
        c[i+len2]+=x;
    }
    int len=len1+len2;
    while(len>1&&!c[len]) len--;

    printf("%d",c[len--]);
    for(int i=len;i>=1;i--)
     printf("%04d",c[i]);
    return 0;
}

행렬 쾌속 멱 (여러 번 오프라인 질문)
연산자 qwq를 다시 불러오지 않습니다
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int MOD=1e9+7;
LL A[4][4]={
    0,0,0,0,
    0,1,1,0,
    0,0,0,1,
    0,1,0,0,};
LL ans[5][5],tmp[5][5],b[107],B[5][5],C[5][5];
int n;
struct H{
    int id,x;
}q[107];
bool cmp(H a,H b)
{
    return a.xx;
}
LL q_pow(LL p)
{
    p--;
    for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) B[i][j]=C[i][j]=A[i][j];
    while(p)
    {
        if(p&1)
        {
            for(int i=1;i<=3;i++)
             for(int j=1;j<=3;j++)
              tmp[i][j]=B[i][j],B[i][j]=0;
            for(int i=1;i<=3;i++)
             for(int j=1;j<=3;j++)
              for(int k=1;k<=3;k++)
               (B[i][j]+=(tmp[i][k]*C[k][j])%MOD)%=MOD;
        }
        for(int i=1;i<=3;i++)
           for(int j=1;j<=3;j++)
              tmp[i][j]=C[i][j],C[i][j]=0;
        for(int i=1;i<=3;i++)   
          for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
              (C[i][j]+=(tmp[i][k]*tmp[k][j])%MOD)%=MOD;
        p>>=1;
    }
    for(int i=1;i<=3;i++)
     for(int j=1;j<=3;j++)
       tmp[i][j]=ans[i][j],ans[i][j]=0;
     for(int i=1;i<=3;i++)  
      for(int j=1;j<=3;j++)
       for(int k=1;k<=3;k++)
        (ans[i][j]+=(tmp[i][k]*B[k][j])%MOD)%=MOD;
    return ans[1][1];
}
int main()
{
    scanf("%d",&n);
    ans[1][1]=1,ans[1][2]=1,ans[1][3]=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&q[i].x);
        q[i].id=i;
    }
    sort(q+1,q+n+1,cmp);

    bool first=1;
    for(int i=1;i<=n;i++)
    {
        if(q[i].x<=3)
        {
            b[q[i].id]=1;
            continue;
        }
        if(first) b[q[i].id]=q_pow(q[i].x-3),first=0;
        else
        {
            if(q[i].x==q[i-1].x) b[q[i].id]=b[q[i-1].id];
            else 
            b[q[i].id]=q_pow(q[i].x-q[i-1].x);
        }
    }
    for(int i=1;i<=n;i++)
     printf("%lld
",b[i]);
    return 0;
}
my batis 의 간단 한 인 스 턴 스
[Php] include (require) 파일 을 포함 하 는 주의 사항

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage