广州 noip 模拟赛 9-18

· · 个人记录

广州 noip 模拟赛 9-18

9-18

T1

题目大意
给你 2n+1 个点，每个点有一个坐标 (x,y) , x 相同的或 y 相同的可以两两匹配 。问你删掉某个点后是否会形成 n 个匹配 。

solution

我们把每个点化成边 ，然后跑一个边联通分量 ，这样会形成一个个连通块 ，我们统计一下每个联通块中边数 ，可以发现这样至少有一个连通块的边数为奇数，可以发现，当边数为奇数的数量超过 1 ，呢么肯定都是 NG ,否则我们考虑奇数的呢个连通块 ，我们考虑其中的每一座桥 ，若这个桥将连通块分为两个偶数的，呢他是合法的 ，否则不合法 ，当不是桥的时候显然合法 。 


/**************************************************************
    Problem: 2385
    User: sdqd09
****************************************************************/

#include<iostream>  
#include<cstdio>
#include<cstring> 
#define de() cout<<"test"<<"\n"
using namespace std;

const int maxn=2e6+10;

struct Le
{
    int nt,to;
}edge[maxn<<2];

int head[maxn],br[maxn],siz[maxn],num=1,cnt,vis2[maxn],dfn[maxn],low[maxn],rt[maxn],RT,U[maxn],V[maxn],vis[maxn];
int n;

void add(int f,int t) {
    edge[++num].nt=head[f];
    edge[num].to=t;
    head[f]=num;
}

void tarjan(int u,int fa) {
    low[u]=dfn[u]=++cnt;rt[u]=RT;
    for(int i=head[u];i;i=edge[i].nt) {
        int v=edge[i].to;
        if(v==fa) continue ; 
        if(!vis2[i]&&!vis2[i^1]) {
            siz[u]++;
        }vis2[i]=1;
        if(!dfn[v]) {
            tarjan(v,u);
            siz[u]+=siz[v];
            low[u]=min(low[v],low[u]);
            if(low[v]>dfn[u]) { 
                br[i>>1]=1;
            } 
        } 
        else low[u]=min(low[u],dfn[v]);
    }
}

int main()
{
    scanf("%d",&n);
    n=n<<1|1;
    for(int i=1;i<=n;++i) {
        scanf("%d%d",&U[i],&V[i]);V[i]+=n;
        vis[U[i]]=vis[V[i]]=1;
        add(U[i],V[i]);add(V[i],U[i]);
    } 
    for(int i=1;i<=(n<<1);++i) {  
        if(!dfn[i]&&vis[i]) {  
            tarjan(RT=i,0);
        } 
    } 
    int f=0;
    for(int i=1;i<=n;++i) { 
        if(siz[rt[i]]&1) {
            if(rt[i]!=f&&f!=0) {
                f=-1;break ;
            }
            f=rt[i];
        }
    }
    for(int i=1;i<=n;++i) {
    //  cout<<rt[i]<<"*\n";
        if(f==-1) {
            puts("NG");continue ;
        }
        if(siz[rt[U[i]]]&1) {
            int u=U[i],v=V[i];
            if(siz[u]<siz[v]) swap(u,v);
            if(br[i]) {
                if(siz[v]&1) {
                    puts("NG");
                }else {
                    puts("OK");
                }
            }else {
                puts("OK");
            }
        }else {
            //cout<<U[i]<<" "<<rt[U[i]]<<" "<<siz[rt[U[i]]]<<"\n";
            //cout<<"2333"<<"\n";
            puts("NG");
        }
    }
    return 0;
}

T2

给你在 [0,1] 的实数中随机出权值和键值，然后插入到一颗 treap 中 ，问这个 treap 最后的深度分别为 [1,n] 的概率 。

solution

我们考虑两次随机出后 ，我们发现我们的插入顺序是对他的形态没有改变的，所以我们考虑按权值排序后，再按键值差 ，其实就相当于我们随机了一个排列 ，然后插入 treap 的深度的概率 。 我们设 f[i][j] 为目前深度不超过 i ，使用了 j 个点的概率 。
然后我们枚举根 ，和除根外 ，左右儿子的大小 。

f[i][j]=\sum_{k=1}^{j}f[i-1][k] * f[i-1][j-k]

最后答案就是 f[i][n]-f[i-1][n]

我们知道 treap 的期望树高是 log 的，所以我们只要跑 50 便就好了 。
然后上面的柿子显然是可以 FFT 优化的 。

O(Anlogn) 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>  

using namespace std;

const int maxn=2e5+10;

double f[51][maxn]; 
struct com
{
    double x,y;
    com(){}
    com(double xx,double yy):x(xx),y(yy){} 
}a[maxn];
const double Pi=acos(-1.0);
com operator - (com &A,com &B) {
    return com(A.x-B.x,A.y-B.y);
}
com operator + (com &A,com &B) {
    return com(A.x+B.x,A.y+B.y);
} 
com operator * (com &A,com &B) {
    return com(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);
}
com operator / (com &A,double x) {
    return com(A.x/x,A.y/x);
}

int n;
int limit=1,l,r[maxn];
void FFT(com *A,int type)
{
    for(int i=0;i<limit;++i) if(i<r[i]) swap(A[i],A[r[i]]);
    for(int mid=1;mid<limit;mid<<=1) {
        com Wn=com(cos(Pi/mid),type*sin(Pi/mid));
        for(int R=mid<<1,j=0;j<limit;j+=R) {
            com w=com(1,0);
            for(int k=0;k<mid;++k,w=w*Wn) {
                com x=A[j+k],y=w*A[j+k+mid];
                A[j+k]=x+y;
                A[j+k+mid]=x-y;
            }
        }
    }
    if(type==-1) {
        for(int i=0;i<limit;++i) a[i]=a[i]/(1.0*limit);
    }
}
double last;
int main()
{
    scanf("%d",&n);
    f[0][0]=1.0;
    a[0]=com(1,0);
    while(n+n>=limit) limit<<=1,++l;
    for(int i=0;i<limit;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    for(int j=1;j<=min(50,n);++j) {
        FFT(a,1);
        for(int i=0;i<limit;++i) a[i]=a[i]*a[i];
        FFT(a,-1);
        for(int i=n;i<limit;++i) a[i]=com(0,0);
        for(int i=n;i;i--) a[i]=a[i-1]/(1.0*i);
        a[0]=com(1,0);
        printf("%.10lf\n",fabs(a[n].x-last));last=a[n].x;
    }
    for(int i=51;i<=n;++i) {
        printf("%.10lf\n",0.0);
    }
    /*for(int i=1;i<=min(50,n);++i) {
        for(int j=1;j<=n;++j) {
            for(int k=1;k<=j;++k) {
                f[i][j]+=f[i-1][k-1]*f[i-1][j-k];
            } 
            f[i][j]/=1.0*j;
            f[i][0]=1.0;
            //f[i][j]+=f[i-1][j];
        }
    }
    for(int i=1;i<=n;++i) {
        printf("%.10lf\n",f[i][n]-f[i-1][n]);
    }*/
    return 0;
}

T3

给你一个 W * H 的矩型 ，每个位置有一个点值，然后两个点的最短路就是这两个点之间的路径的点权和的最小值 。

有 q 次询问 。

W<=10

solution

整体二分板子题 


#include<bits/stdc++.h> 
#define de() cout<<"test"<<"\n" 
#define ll long long 
using namespace std;

const int maxn=1e5+10;
const ll inf=1e16;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};

int n,m,Q;
int a[11][maxn],vis[11][maxn];ll dis[11][maxn];
struct Q
{
    int x,y,X,Y,id;
}q[maxn],q1[maxn],q2[maxn];
ll ans[maxn];
struct node
{
    int x,y;ll d;
};
bool operator < (node a,node b) {
    return a.d>b.d;
} 
void dij(int x,int y,int L,int R) {
    priority_queue<node> q;
    for(int i=1;i<=n;++i) {
        for(int j=L;j<=R;++j) dis[i][j]=inf,vis[i][j]=0;
    } dis[x][y]=a[x][y];
    q.push((node){x,y,dis[x][y]});
    while(!q.empty()) {
        node X=q.top();q.pop();
        int xx=X.x,yy=X.y;
        //;de();
        if(vis[xx][yy]) continue ;
        vis[xx][yy]=1;
        for(int i=0;i<4;++i) { 
            int xxx=xx+dx[i],yyy=yy+dy[i];              
            if(xxx<1||xxx>n||yyy<L||yyy>R) continue ;   
            if(dis[xx][yy]+a[xxx][yyy]<dis[xxx][yyy]) { 
                dis[xxx][yyy]=dis[xx][yy]+a[xxx][yyy];  
                q.push((node){xxx,yyy,dis[xxx][yyy]});  
            } 
        } 
    }
}

void so(int l,int r,int L,int R) {
    //cout<<l<<" "<<r<<" "<<L<<" "<<R<<"\n";
    if(l>r||L>R) return ;
    int mid=(l+r)>>1;
    for(int i=1;i<=n;++i) {
        dij(i,mid,l,r);
        for(int j=L;j<=R;++j) {
        //  cout<<dis[q[j].x][q[j].y]<<"\n";
            ans[q[j].id]=min(ans[q[j].id],dis[q[j].x][q[j].y]+dis[q[j].X][q[j].Y]-a[i][mid]); 
        }
    }   
    if(l==r) return ;
    int x=0,y=0;
    for(int i=L;i<=R;++i) {
        if(q[i].y<mid&&q[i].Y<mid) q1[++x]=q[i];
        if(q[i].y>mid&&q[i].Y>mid) q2[++y]=q[i];
    }
    for(int i=1;i<=x;++i) q[L+i-1]=q1[i];
    for(int i=1;i<=y;++i) q[L+x+i-1]=q2[i];
    so(l,mid,L,L+x-1);so(mid+1,r,L+x,L+x+y-1);
}

int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=m;++i) {
        for(int j=1;j<=n;++j) scanf("%d",&a[j][i]);
    }
    for(int i=1;i<=Q;++i) scanf("%d%d%d%d",&q[i].x,&q[i].y,&q[i].X,&q[i].Y),q[i].id=i;
    for(int i=1;i<=Q;++i) ans[i]=inf;
    so(1,m,1,Q);
    for(int i=1;i<=Q;++i) cout<<ans[i]<<"\n";
    return 0;

}