技术教程 编程教程 NOI考前乱写 正文

NOI考前乱写

2023-03-18,,

还有13天NOI，把各种乱七八糟的算法都重新过一遍还是比较有必要的。。。

//HDU 5046 Airport

//DancingLink

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 110

#define MAXD MAXN*MAXN

#define INF 0x3f3f3f3f

#define LL "%lld"

typedef long long qword;

struct point

{

        qword x,y;

};

point pl[MAXN];

qword dis(point p1,point p2)

{

        return abs(p1.x-p2.x)+abs(p1.y-p2.y);

}

int L[MAXD],R[MAXD],U[MAXD],D[MAXD];

int ptr[MAXN];

int tot[MAXN];

int col[MAXD];

int topd=;

int head=;

void cover(int now)

{

        for (int i=R[now];i!=now;i=R[i])

        {

                for (int j=U[i];j!=i;j=U[j])

                {

                        L[R[j]]=L[j];

                        R[L[j]]=R[j];

                }

        }

        for (int j=U[now];j!=now;j=U[j])

        {

                L[R[j]]=L[j];

                R[L[j]]=R[j];

        }

}

void recover(int now)

{

        for (int i=R[now];i!=now;i=R[i])

                for (int j=U[i];j!=i;j=U[j])

                        L[R[j]]=R[L[j]]=j;

        for (int j=U[now];j!=now;j=U[j])

                L[R[j]]=R[L[j]]=j;

}

int vv[MAXN];

int ff()

{

        int ret=;

        for (int i=R[head];i!=head;i=R[i])

                vv[col[i]]=true;

        for (int i=R[head];i!=head;i=R[i])

        {

                if (vv[col[i]])

                {

                        ret++;

                        for (int j=D[i];j!=i;j=D[j])

                        {

                                for (int k=R[j];k!=j;k=R[k])

                                {

                                        vv[col[k]]=false;

                                }

                        }

                }

        }

        return ret;

}

bool solve(int trst)

{

        if (L[head]==R[head] && L[head]==head)return true;

        if (!trst)return false;

        if (trst<ff())return false;

        pair<int,int> mnv=make_pair(INF,);

        for (int i=R[head];i!=head;i=R[i])

                mnv=min(mnv,make_pair(tot[i],i));

        int now=mnv.second;

        for (int i=D[now];i!=now;i=D[i])

        {

                cover(i);

                if (solve(trst-))return true;

                recover(i);

        }

        return false;

}

int main()

{

        freopen("input.txt","r",stdin);

        int nn;

        int n,m;

        int x,y,z;

        scanf("%d",&nn);

        int caseid=;

        while (nn--)

        {

                caseid++;

                scanf("%d%d",&n,&m);

                for (int i=;i<=n;i++)

                        scanf(LL LL ,&pl[i].x,&pl[i].y);

                memset(ptr,,sizeof(ptr[])*(n+));

                memset(tot,,sizeof(tot[])*(n+));

                qword l=-,r=1ll<<,mid;

                while (l+<r)

                {

                        mid=(l+r)>>;

                        topd=;

                        head=++topd;

                        L[head]=R[head]=head;

                        for (int i=;i<=n;i++)

                        {

                                int np=++topd;

                                col[np]=i;

                                R[np]=head;

                                L[np]=L[head];

                                L[R[np]]=np;

                                R[L[np]]=np;

                                D[np]=U[np]=np;

                                ptr[i]=np;

                        }

                        for (int i=;i<=n;i++)

                        {

                                int last=;

                                for (int j=;j<=n;j++)

                                {

                                        if (dis(pl[i],pl[j])<=mid)

                                        {

                                                int np=++topd;

                                                col[np]=j;

                                                tot[ptr[j]]++;

                                                D[np]=ptr[j];

                                                U[np]=U[ptr[j]];

                                                D[U[np]]=U[D[np]]=np;

                                                if (!last)

                                                {

                                                        L[np]=R[np]=np;

                                                }else

                                                {

                                                        L[np]=last;

                                                        R[np]=R[last];

                                                        L[R[np]]=R[L[np]]=np;

                                                }

                                                last=np;

                                        }

                                }

                        }

                        if (solve(m))

                        {

                                r=mid;

                        }else

                        {

                                l=mid;

                        }

                }

                printf("Case #%d: "LL"\n",caseid,r);

        }

}

DancingLink

半年没写DLX了，还能在30分钟内写出来，感觉不错。

DLX分为精确覆盖和完全覆盖，两者的区别大概是在cover和recover之中。

另外DLX也是需要剪枝的。

//bzoj 1135

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 210000

#define MAXT MAXN*5

#define lch (now<<1)

#define rch (now<<1^1)

#define smid ((l+r)>>1)

typedef long long qword;

struct sgt_node

{

        int lc,rc;

        qword lx,rx,mx;

        qword sum;

}sgt[MAXT];

void update(int now)

{

        sgt[now].lx=max(sgt[lch].lx,sgt[lch].sum+sgt[rch].lx);

        sgt[now].rx=max(sgt[rch].rx,sgt[rch].sum+sgt[lch].rx);

        sgt[now].sum=sgt[lch].sum+sgt[rch].sum;

        sgt[now].mx=max(max(sgt[lch].mx,sgt[rch].mx),sgt[lch].rx+sgt[rch].lx);

}

void Build_sgt(int now,int l,int r,int v)

{

        if (l==r)

        {

                sgt[now].sum=v;

                sgt[now].lx=sgt[now].rx=sgt[now].mx=v;

                return ;

        }

        Build_sgt(lch,l,smid,v);

        Build_sgt(rch,smid+,r,v);

        update(now);

}

void Modify_sgt(int now,int l,int r,int pos,int v)

{

        if (l==r)

        {

                sgt[now].sum+=v;

                sgt[now].lx+=v;

                sgt[now].rx+=v;

                sgt[now].mx+=v;

                return ;

        }

        if (pos<=smid)

                Modify_sgt(lch,l,smid,pos,v);

        else

                Modify_sgt(rch,smid+,r,pos,v);

        update(now);

}

int main()

{

        freopen("input.txt","r",stdin);

        int n,m,t,d;

        int x,y;

        scanf("%d%d%d%d",&n,&m,&t,&d);

        Build_sgt(,,n,-t);

        for (int i=;i<m;i++)

        {

                scanf("%d%d",&x,&y);

                Modify_sgt(,,n,x,y);

                if (sgt[].mx>(qword)t*d)

                {

                        printf("NIE\n");

                }else

                {

                        printf("TAK\n");

                }

        }

Hall

hall定理用于二分图匹配相关问题，在要求方案时用贪心或匈牙利算法，运用hall定理有利于优化时间复杂度。

//bzoj 3270

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cassert>

#include<cmath>

using namespace std;

#define MAXN 1010

#define MAXV MAXN

#define MAXE MAXN*20

typedef double real;

const real eps = 1e-;

struct Edge

{

        int np;

        Edge *next;

}E[MAXE],*V[MAXV];

int tope=-;

void addedge(int x,int y)

{

        E[++tope].np=y;

        E[tope].next=V[x];

        V[x]=&E[tope];

}

real ps[MAXN];

real mat[MAXN][MAXN];

real res[MAXN];

int deg[MAXN];

int main()

{

        freopen("input.txt","r",stdin);

        int n,m;

        int a,b;

        int x,y,z;

        scanf("%d%d",&n,&m);

        scanf("%d%d",&a,&b);

        a--;b--;

        for (int i=;i<m;i++)

        {

                scanf("%d%d",&x,&y);

                x--;y--;

                addedge(x,y);

                addedge(y,x);

                deg[x]++;

                deg[y]++;

        }

        for (int i=;i<n;i++)

                scanf("%lf",&ps[i]);

        for (int i=;i<n;i++)

        {

                for (int j=;j<n;j++)

                {

                        if (i==j)

                        {

                                mat[i*n+j][i*n+j]=;

                                continue;

                        }

                        Edge *ne1,*ne2;

                        for (ne1=V[i];ne1;ne1=ne1->next)

                                for (ne2=V[j];ne2;ne2=ne2->next)

                                        mat[ne1->np*n+ne2->np][i*n+j]=-*(-ps[i])*(-ps[j])/deg[i]/deg[j];

                        Edge *ne;

                        for (ne=V[i];ne;ne=ne->next)

                                mat[ne->np*n+j][i*n+j]=-*ps[j]*(-ps[i])/deg[i];

                        for (ne=V[j];ne;ne=ne->next)

                                mat[i*n+ne->np][i*n+j]=-*(-ps[j])*ps[i]/deg[j];

                        mat[i*n+j][i*n+j]=-ps[i]*ps[j];

                        mat[i*n+j][n*n]=;

                }

        }

        mat[a*n+b][n*n]=;

        int l=n*n;

        for (int i=;i<l;i++)

        {

                int x=-;

                for (int j=i;j<=l;j++)

                {

                        if (abs(mat[j][i])>eps)

                                x=j;

                }

                assert(x!=-);

                if (x!=i)

                        for(int j=;j<=l;j++)

                                swap(mat[i][j],mat[x][j]);

                for (int j=i+;j<l;j++)

                {

                        real tmp=mat[j][i]/mat[i][i];

                        for (int k=i;k<=l;k++)

                        {

                                mat[j][k]-=mat[i][k]*tmp;

                        }

                }

        }

        for (int i=l-;i>=;i--)

        {

                real tmp=mat[i][n*n];

                for (int j=i+;j<n*n;j++)

                        tmp-=res[j]*mat[i][j];

                res[i]=tmp/mat[i][i];

        }

        for (int i=;i<n;i++)

                printf("%.6lf ",res[i*n+i]);

}

概率1

概率期望dp以及高消在很多时候都是可以转化的，而适当的转化会使思维难度大大降低。

//Miller Rabin

//HDU 2138

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long qword;

qword pow_mod(qword x,qword y,int mod)

{

        qword ret=%mod;

        while (y)

        {

                if (y&)ret=ret*x%mod;

                x=x*x%mod;

                y>>=;

        }

        return ret;

}

bool MillerRabin(qword a,int n)

{

        int x=n-,y=;

        while ((x&)==)x>>=,y++;

        a=pow_mod(a,x,n);

        int pe=a;

        for (int i=;i<y;i++)

        {

                pe=a;

                a=a*a%n;

                if (a== && pe!=n- && pe!=)return false;

        }

        return a==?true:false;

}

int main()

{

    //    freopen("input.txt","r",stdin);

        int n;

        int x;

        int s[]={,,,,,};

        while (~scanf("%d",&n))

        {

                int ans=;

                for (int i=;i<n;i++)

                {

                        scanf("%d",&x);

                        if (x==)

                        {

                                continue;

                        }else if (x==)

                        {

                                ans++;

                                continue;

                        }

                        bool flag=true;

                        for (int j=;j<;j++)

                        {

                                if (s[j]>=x)continue;

                                if (!MillerRabin(s[j],x))

                                {

                                        flag=false;

                                        break;

                                }

                        }

                        if (flag)

                        {

                                ans++;

                        }

                }

                printf("%d\n",ans);

Miller Rabin

这种时候还理解什么，赶快背啊！

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

#define MAXN 110000

#define MAXM 210

#define BIG 1000000000000000LL

typedef long long qword;

int a[MAXN];

qword s[MAXN];

qword dp[][MAXN];

struct point

{

        qword x,y;

};

qword area(point p1,point p2,point p3)

{

        return (p1.x-p2.x)*(p1.y-p3.y) - (p1.y-p2.y)*(p1.x-p3.x);

}

point q[MAXN];

int main()

{

        freopen("input.txt","r",stdin);

        freopen("output.txt","w",stdout);

        int n,m;

        scanf("%d%d",&n,&m);

        for (int i=;i<=n;i++)

        {

                scanf("%d",&a[i]);

                //if (!a[i])i--,n--;

        }

        for (int i=;i<=n;i++)

                s[i]=s[i-]+a[i];

        for (int i=;i<;i++)

                for (int j=;j<=n;j++)

                        dp[i][j]=-BIG;

        int head,tail;

        point pt;

        dp[][]=;

        for (int i=;i<=m;i++)

        {

                head=;

                tail=-;

                for (int j=;j<=n;j++)

                {

                        pt.x=s[j-];

                        pt.y=-s[n]*s[j-]+dp[(i&)^][j-];

                        while (head<tail && area(q[tail-],q[tail],pt)>=)

                        {

                                if (area(q[tail-],q[tail],pt)==)

                                {

                                        cout<<"haha"<<endl;

                                }

                                tail--;

                        }

                        q[++tail]=pt;

                        while (head<tail && s[j]*q[head].x+q[head].y<=s[j]*q[head+].x+q[head+].y)

                                head++;

                        dp[i&][j]=s[j]*q[head].x+q[head].y + s[n]*s[j]-s[j]*s[j];

        //                printf("%lld ",dp[i&1][j]);

                }

                dp[i&][]=-BIG;

        //        printf("\n");

        }

        qword ans=;

        for (int i=;i<=n;i++)

                ans=max(ans,dp[m&][i]);

        printf("%lld\n",ans);

}

斜率优化

//POJ 1160

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 3100

#define MAXM 40

#define INF 0x3f3f3f3f

int w[MAXN][MAXN],w1[MAXN][MAXN];

int a[MAXN];

int dp[MAXM][MAXN];

pair<int,int> srange[MAXN];

int stack[MAXN];

int tops=-;

int main()

{

        freopen("input.txt","r",stdin);

        int n,m;

        int x,y,z;

        scanf("%d%d",&n,&m);

        for (int i=;i<=n;i++)

                scanf("%d",a+i);

        for (int i=;i<=n;i++)

        {

                for (int j=i;j<=n;j++)

                {

                        if ((i+j)/==(i+j-)/)

                                w[i][j]=w[i][j-]+a[j]-a[(i+j)/];

                        else

                                w[i][j]=w[i][j-]+(a[(i+j)/]-a[(i+j-)/])*(((i+j)/-i) - (j-(i+j)/))

                                        +a[j]-a[(i+j)/];

                }

        }

        memset(dp,INF,sizeof(dp));

        dp[][]=;

        srange[++tops]=make_pair(,n);

        stack[tops]=;

        for (int i=;i<=m;i++)

        {

                while (~tops)

                {

                        for (int j=srange[tops].first;j<=srange[tops].second;j++)

                                dp[i][j]=dp[i-][stack[tops]]+w[stack[tops]+][j];

                        tops--;

                }

                for (int j=;j<=n;j++)

                {

                        while (~tops && dp[i][j]+w[j+][srange[tops].first]<dp[i][stack[tops]]+w[stack[tops]+][srange[tops].first])

                                tops--;

                        if (~tops)

                        {

                                int l=srange[tops].first;

                                int r=srange[tops].second+;

                                while (l+<r)

                                {

                                        int mid=(l+r)>>;

                                        if (dp[i][j]+w[j+][mid]<dp[i][stack[tops]]+w[stack[tops]+][mid])

                                                r=mid;

                                        else

                                                l=mid;

                                }

                                srange[tops].second=l;

                                if (r<=n)

                                {

                                        srange[++tops]=make_pair(r,n);

                                stack[tops]=j;

                                }

                        }else

                        {

                                srange[++tops]=make_pair(,n);

                                stack[tops]=j;

                        }

                }

        }

        int ans=dp[m][n];

        printf("%d\n",ans);

        return ;

}

1D1D优化

//bzoj 1856

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MOD 20100403

#define MAXN 2001000

typedef long long qword;

qword fact[MAXN];

qword pow_mod(qword x,qword y)

{

        qword ret=;

        while (y)

        {

                if (y&)ret=ret*x%MOD;

                x=x*x%MOD;

                y>>=;

        }

        return ret;

}

qword C(int x,int y)

{

        if (x<y)return ;

        return fact[x]*pow_mod(fact[x-y],MOD-)%MOD*pow_mod(fact[y],MOD-)%MOD;

}

int main()

{

        //freopen("input.txt","r",stdin);

        int n,m;

        scanf("%d%d",&n,&m);

        fact[]=;

        for (int i=;i<=n+m;i++)

                fact[i]=fact[i-]*i%MOD;

        qword ans=C(n+m,n)-C(n+m,n+);

        ans=(ans%MOD+MOD)%MOD;

        printf("%d\n",(int)ans);

}

Catalan

Tarjan-缩点
Tarjan-边双&&非递归
Tarjan-点双
整体二分

//bzoj 3339

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<set>

using namespace std;

#define MAXN 210000

#define smid ((l+r)>>1)

int n,m;

int a[MAXN];

int tmp[MAXN],prv[MAXN];

const int big=;

struct qur_t

{

        int id,l,r,ans;

}qur[MAXN];

vector<qur_t> vec;

bool cmp_r(qur_t q1,qur_t q2)

{

        return q1.r<q2.r;

}

int res[MAXN];

void solve(int l,int r,vector<qur_t> &vec)

{

        if (l==r)

        {

                for (int i=;i<vec.size();i++)

                        res[vec[i].id]=l;

                return ;

        }

        vector<qur_t> v1,v2;

        multiset<int> S;

        sort(vec.begin(),vec.end(),cmp_r);

        for (int i=l;i<=smid;i++)

                S.insert(tmp[i]);

        int cur=n;

        for (int i=vec.size()-;i>=;i--)

        {

                while (vec[i].r<cur)

                {

                        if (a[cur]<=smid && a[cur]>=l)

                        {

                                S.erase(S.find(cur));

                                S.insert(prv[cur]);

                        }

                        cur--;

                }

                if (*S.begin()<vec[i].l)

                        v1.push_back(vec[i]);

                else

                        v2.push_back(vec[i]);

        }

        solve(l,smid,v1);

        solve(smid+,r,v2);

}

int main()

{

        freopen("input.txt","r",stdin);

        freopen("output.txt","w",stdout);

        int x,y,z;

        scanf("%d%d",&n,&m);

        for (int i=;i<=n;i++)

                scanf("%d",&a[i]);

        for (int i=;i<=n;i++)

        {

                prv[i]=tmp[a[i]];

                tmp[a[i]]=i;

        }

        for (int i=;i<=m;i++)

        {

                scanf("%d%d",&qur[i].l,&qur[i].r);

                qur[i].id=i;

        }

        vec.insert(vec.begin(),qur+,qur+m+);

        solve(,big+,vec);

        for (int i=;i<=m;i++)

                printf("%d\n",res[i]);

}

SBT && 动态凸包

NOI考前乱写的相关教程结束。

《NOI考前乱写.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!