while (NOIp_2018.rp<inf)
    NOIp_2018.rp++;

放些板子，早上熟悉一下。主要是数论和图论，数据结构还是比较熟练的。

int gcd(int x,int y)
{
    if (y==0) return x;
    return gcd(y,x%y);
}

void exgcd(int a,int b,int &x,int &y) //ax+by=gcd(a,b)
{
    if (b==0) x=1,y=0;
    else
    {
        exgcd(b,a%b,y,x);
        y-=a/b*x;
    }
}


inline void dijkstra()
{
    priority_queue <pr,vector<pr>,greater<pr> > q;
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;i++) dis[i]=1e9;
    dis[s]=0;
    q.push(mp(0,s));
    while (!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,w=edge[i].w;
            if (mn[x]+x<mn[y])
            {
                mn[y]=mn[x]+w;
                q.push(mp(mn[y],y));
            }
        }
    }
}

inline void spfa()
{
    queue <int> q;
    for (int i=1;i<=n;i++) dis[i]=1e9;
    memset(in,0,sizeof(in));
    dis[s]=0;
    q.push(s);
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        in[x]=0;
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,w=edge[i].w;
            if (dis[x]+w<dis[y])
            {
                dis[y]=dis[x]+w;
                if (!in[y])
                {
                    q.push(y);
                    in[y]=1;
                }
            }
        }
    }
}
bool spfa(int x) //判负环
{
    in[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to,w=edge[i].w;
        if (dis[x]+w<dis[y])
        {
            dis[y]=dis[x]+w;
            if (!in[y]) return spfa(y);
            else return 1; //有负环
        }
    }
    in[x]=0;
    return 0;
}


inline void getnext()////p[k]表示前缀，p[j]表示后缀
{
    Next[0]=-1;
    int ly=y.length(),k=-1,j=0;
    while (j<ly)
    {
        if (k==-1 || y[j]==y[k])
        {
            j++; k++;
            Next[j]=k;
        }
        else k=Next[k];
    }
}
inline void kmp()
{
    int i=0,j=0,lx=x.length(),ly=y.length();
    while (i<lx)
    {
        if (j==-1 || x[i]==y[j]) i++,j++;
        else j=Next[j];
        if (j==ly) 
        {
            cout<<i-j+1<<endl;
            j=Next[j];
        }
    }
}


inline int manacher()
{
    int mx,id,mxlen=0;
    for (int i=0;i<l;i++)
    {
        if (i<mx) p[i]=min(p[2*id-i],mx-i);
        else p[i]=1;
        while (y[i-p[i]]==y[i+p[i]]) p[i]++;
        if (mx<i+p[i])
        {
            id=i;
            mx=i+p[i];
        }
        mxlen=max(mxlen,p[i]-1);
    }
    return mxlen;
}

inline void get_prime()
{
    memset(ss,1,sizeof(ss));
    ss[0]=ss[1]=0;
    for (int i=2;i<=n;i++)
    {
        if (ss[i]) zs[++cnt]=i;
        for (int j=1;j<=cnt && zs[j]*i<=n;j++)
        {
            ss[zs[j]*i]=0;
            if (i%zs[j]==0) break;
        }
    }
}

inline ll POW(ll x,ll y)
{
    ll m=1,n=x;
    while (y)
    {
        if (y&1) m=m*n%k;
        y>>=1;
        n=n*n%k;
    }
    return m%k;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/noip2018-rp++.html