首页 > 其他 > 详细

牛客提高集训营3

时间：2018-09-25 15:09:00      阅读：155      评论：0      收藏：0      [点我收藏+]

目录

2018.9.23 牛客提高集训营3

时间：3.5h
期望得分：100+60+0
实际得分：100+0+0

比赛链接

A 管道维修(递推 期望)

题目链接

我们可以算每个点要需恰好清k次的概率，但实际上只需要算每个点至少需清k次的概率。
一个格子期望清理次数 = 至少需1次的概率 + 至少需2次的概率 + 至少需3次的概率...
即我们要对每个点算它周围每一圈菱形上的点的概率的乘积。注意到菱形的四条边可以由左右两个点再乘上两个点的概率直接得到，所以可以\(O(n^3)\)预处理。
如图：技术分享图片
为了左右对称可以最后算正上正下那俩格子。

一看这题不就像我昨天讲的题的部分分么，但是菱形不会处理，于是就写了个看似\(n^4\)的BFS。
写完试了下状态数确实不是很多只有\(1.3\times10^8\)。因为常数大1.85s过的。。
讲题的时候有人说不该放\(n^4\)过，拜托要是真\(n^4\)怎么可能过。就算从中心点扩展也到不了\(n^2\)。

//57ms  2328KB
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 100000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define mod 1000000007
#define Inv(x) FP(x,mod-2)
typedef long long LL;
const int N=202;

int P[N][N],L[N][N>>1],R[N][N>>1];
char IN[MAXIN],*SS=IN,*TT=IN,OUT[3000000],*O=OUT;

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
void print(int x)
{
    if(x>9) print(x/10);
    *O++ = x%10+'0';
}
inline int FP(int x,int k)
{
    int t=1;
    for(; k; k>>=1,x=1ll*x*x%mod)
        if(k&1) t=1ll*t*x%mod;
    return t;
}

int main()
{
    int n=read(),m=read();
    for(int i=1; i<=n; ++i)
        for(int j=1,t1,t2; j<=m; ++j)
            P[i][j]=1ll*read()*Inv(read())%mod;
    for(int i=1; i<=n; ++i,*O++='\n')
    {
//      memset(L,0,sizeof L), memset(R,0,sizeof R);
        for(int j=1; j<=m; ++j)
        {
            int lim=std::min(std::min(i-1,n-i),std::min(j-1,m-j));
            for(int k=1; k<=lim; ++k)
            {
                if(k==1) L[j][k]=P[i][j-1];
                else L[j][k]=1ll*L[j-1][k-1]*P[i-k+1][j-1]%mod*P[i+k-1][j-1]%mod;
            }
        }
        for(int j=m; j; --j)
        {
            int lim=std::min(std::min(i-1,n-i),std::min(j-1,m-j));
            for(int k=1; k<=lim; ++k)
            {
                if(k==1) R[j][k]=P[i][j+1];
                else R[j][k]=1ll*R[j+1][k-1]*P[i-k+1][j+1]%mod*P[i+k-1][j+1]%mod;
            }
        }
        for(int j=1; j<=m; ++j)
        {
            LL ans=P[i][j],sum=P[i][j],tmp;
            int lim=std::min(std::min(i-1,n-i),std::min(j-1,m-j));
            for(int k=1; k<=lim; ++k)
                tmp=1ll*L[j][k]*R[j][k]%mod*P[i-k][j]%mod*P[i+k][j]%mod,
                sum=tmp*sum%mod, ans+=sum;
            print(ans%mod), *O++=' ';
        }
    }
    fwrite(OUT,O-OUT,1,stdout);

    return 0;
}

B 公平竞赛(BFS最小环)

题目链接

把每个点拆成(u,u+n)，表示胜负两个点，胜向负连边、负向胜连边。
找最小环可以BFS。我们要对每个点BFS，第一次找到环就可以break。
复杂度\(O(Tn^2)\)。
当然对所有点只访问一次也是可以的。因为BFS出现环时不会继续，可以用倍增求出出现环的两点的LCA，然后算距离。
这样复杂度\(O(Tn\log n)\)。
另外是二分图所以不会出现奇环。

标算\(O(Tn^2),n=5000\)真是醉了。

//510ms 15796KB
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 100000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define BIT 13
typedef long long LL;
const int N=10005,M=2e6+7;

int n,Min,U,V,W,fa[N],dis[N],st[N][14],A[N],Enum,H[N],nxt[M],to[M];
bool vis[N];
char IN[MAXIN],*SS=IN,*TT=IN;

#define AE(u,v) to[++Enum]=v,nxt[Enum]=H[u],H[u]=Enum
inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
inline int LCA(int u,int v)
{
    if(dis[u]<dis[v]) std::swap(u,v);
    for(int t=dis[u]-dis[v],i=BIT; ~i; --i)
        if(t>>i&1) u=st[u][i];
    if(u==v) return u;
    for(int i=BIT; ~i; --i)
        if(st[u][i]!=st[v][i]) u=st[u][i],v=st[v][i];
    return st[u][0];//fa[u]
}
void BFS(int s)
{
    static int q[N];

    int h=0, t=1;
    vis[s]=1, q[0]=s, dis[s]=0, st[s][0]=fa[s]=0/*!*/;
    while(h<t)
    {
        int x=q[h++];
        for(int i=H[x],v; i; i=nxt[i])
        {
            if(!vis[v=to[i]])
            {
                st[v][0]=fa[v]=x, dis[v]=dis[x]+1;
                for(int j=1; j<=BIT; ++j) st[v][j]=st[st[v][j-1]][j-1];
                vis[v]=1, q[t++]=v;
            }
            else if(v!=fa[x])
            {
                int w=LCA(x,v);
                if(Min>dis[x]+dis[v]-2*dis[w]+1) Min=dis[x]+dis[v]-2*dis[w]+1, U=x, V=v, W=w;
            }
        }
    }
}

int main()
{
    int type=read();
    while(n=read(),n)
    {
        Enum=0, memset(H,0,sizeof H);
        memset(vis,0,sizeof vis);

        int m=read();
        for(int i=1,u,v; i<=m; ++i) u=read(),v=read(),AE(u,v+n),AE(v+n,u);
        Min=N;
        for(int i=1; i<=n; ++i) if(!vis[i]) BFS(i);
        if(Min==N) puts("-1");
        else
        {
            printf("%d\n",Min);
            while(U!=W) printf("%d ",U>n?U-n:U), U=fa[U];
            printf("%d",W>n?W-n:W); int t=0;
            while(V!=W) A[++t]=V>n?V-n:V, V=fa[V];
            while(t) printf(" %d",A[t--]); putchar('\n');
        }
    }
    return 0;
}

C 急开锁(博弈论)

题目链接
题面醉了。没注意到是最差情况下，没想博弈论然后就去搞B了。

技术分享图片
\(k=2\)时就是Fibonacci Nim。
然后这实在没理解（困），先弃疗了。
技术分享图片

//这是一份AC代码(not mine)
#include<cstdio>
typedef long long ll;
ll a[30000005]; ll tot,tmp;
int main ()
{
    ll t; scanf("%lld",&t);
    while(t--)
    {
        tot=0,tmp=1;
        ll k,l; scanf("%lld%lld",&k,&l);
        if(l<=k+1) { printf("DOG\n"); continue; }
        for(ll i=1;i<=k+1;i++) a[++tot]=1ll*i;
        while(1)
        {
            while(a[tmp]*k<=(a[tot]-1ll)) tmp++;
            a[tot+1]=a[tot]+a[tmp]; tot++;
            if(a[tot]>=l) break;
        }
        if(a[tot]>l) printf("GOD\n");
        if(a[tot]==l) printf("DOG\n");
    }
    return 0;
}

考试代码

A

/*
卡常记录 
5.464 s
5.241 s
算了.
把bool换了啊。（然后慢了）
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 100000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define mod 1000000007
#define fir first
#define sec second
#define mp std::make_pair
#define pr std::pair<int,int>
#define Inv(x) FP(x,mod-2)
typedef long long LL;
const int N=202,D[6]={1,0,-1,0,1};

int n,m,p[N][N],pw2[N*N];
bool vis[N][N];
char IN[MAXIN],*SS=IN,*TT=IN,OUT[3000000],*O=OUT;
struct Node
{
    Node() {}
    Node(int x,int y,int d):x(x),y(y),d(d) {}
    int x,y,d;
}q[N*N];

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
void print(int x)
{
    if(x>9) print(x/10);
    *O++ = x%10+'0';
}
inline int FP(int x,int k)
{
    int t=1;
    for(; k; k>>=1,x=1ll*x*x%mod)
        if(k&1) t=1ll*t*x%mod;
    return t;
}
//int SUM;
void Solve(int x,int y)
{
//  static int TIME=0;

//  ++TIME;
    int lim=std::min(std::min(x,n-x+1),std::min(y,m-y+1));
    int h=0,t=1,sum=1,sumnow=1,now=0,tot=1;
    q[1]=Node(x,y,0), vis[x][y]=1;
    LL ans=0;
    while(h<t)
    {
//      ++SUM;
        ++h;
        int x=q[h].x,y=q[h].y,d=q[h].d+1;
        sumnow=1ll*sumnow*p[x][y]%mod;
        if(h==tot)
        {
            now+=4, tot+=now, ans+=1ll*sum*(d-1)%mod*(1-sumnow+mod)%mod;
            sum=1ll*sum*sumnow%mod, sumnow=1;
        }
        if(d==lim) continue;
        for(int i=0,xn,yn; i<4; ++i)
        {
            if(vis[xn=x+D[i]][yn=y+D[i+1]]) continue;
            vis[xn][yn]=1, q[++t]=(Node(xn,yn,d));
        }
    }
    for(int i=1; i<=t; ++i) vis[q[i].x][q[i].y]=0;
    ans+=1ll*lim*sum%mod;
    print(ans%mod), *O++=' ';
//  printf("%d ",(int)(ans%mod));
}
void Solve2(int x,int y)
{
    int lim=std::min(std::min(x,n-x+1),std::min(y,m-y+1));
    int h=0,t=1,sum=p[x][y],now=4;
    LL ans=0;
    for(int d=1; d<lim; ++d)
    {
        ans+=1ll*sum*d%mod*(1-pw2[now]+mod)%mod;
        sum=1ll*sum*pw2[now]%mod;
        now+=4;
    }
    ans+=1ll*lim*sum%mod;
    print(ans%mod), *O++=' ';
}
bool Subtask2()
{
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j) if(p[i][j]!=500000004) return 0;
    pw2[0]=1;
    for(int i=1,lim=n*m; i<=lim; ++i) pw2[i]=1ll*pw2[i-1]*500000004%mod;
    for(int i=1; i<=n; ++i,*O++='\n')
        for(int j=1; j<=m; ++j) Solve2(i,j);
    fwrite(OUT,O-OUT,1,stdout);
    return 1;
}

int main()
{
//  freopen("A.in","r",stdin);
//  freopen("A.out","w",stdout);

    n=read(),m=read();
    for(int i=1; i<=n; ++i)
        for(int j=1,t1,t2; j<=m; ++j)
            p[i][j]=1ll*read()*Inv(read())%mod;
    if(Subtask2()) return 0;

//  for(int i=1; i<=n; ++i,putchar('\n'))
    for(int i=1; i<=n; ++i,*O++='\n')
        for(int j=1; j<=m; ++j) Solve(i,j);
//  print(SUM);
    fwrite(OUT,O-OUT,1,stdout);

    return 0;
}

B

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 100000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=5003,M=2e6+7;

int n,m,Max,fa[N],A[N],Ans[N],Enum,H[N],nxt[M],to[M],dis[N][2];
bool flag,vis[N][2];
char IN[MAXIN],*SS=IN,*TT=IN;

#define AE(u,v) to[++Enum]=v,nxt[Enum]=H[u],H[u]=Enum
inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
void DFS1(int x,int f,int d)
{
    d^=1;
    vis[x][d]=1;
    for(int i=H[x],v; i&&!flag; i=nxt[i])
    {
        if((i&1)!=d||(v=to[i])==f) continue;
        if(vis[v][d^1])
        {
            flag=1; int t=0;
            for(int p=x; p!=v; p=fa[p]) A[++t]=p;
            A[++t]=v; printf("%d\n",t);
            for(int p=t; p; --p) printf("%d ",A[p]); putchar('\n');
            return;
        }
        fa[v]=x, DFS1(v,x,d);
    }
}
void DFS2(int x,int f,int d)
{
    d^=1;
    vis[x][d]=1;
    for(int i=H[x],v,ds=dis[x][d]+1; i; i=nxt[i])
    {
        if((i&1)!=d||(v=to[i])==f) continue;
        if(vis[v][d^1])
        {
            if(dis[x][d]-dis[v][d^1]>0)
            {
                int t=0;
                for(int p=x; p!=v; p=fa[p]) A[++t]=p;
                A[++t]=v;
                if(t<Max)
                {
                    Max=t;
                    for(int i=1; i<=t; ++i) Ans[i]=A[i];
                }
            }
            continue;
        }
        dis[v][d^1]=ds, fa[v]=x, DFS2(v,x,d);
    }
}
void DFS3(int x,int f,int d)
{
    d^=1;
    vis[x][d]=1;
    for(int i=H[x],v,ds=dis[x][d]+1; i; i=nxt[i])
    {
        if((i&1)!=d||(v=to[i])==f) continue;
        if(vis[v][d^1])
        {
            if(dis[x][d]-dis[v][d^1]>0)
                Max=std::min(Max,dis[x][d]-dis[v][d^1]);
            continue;
        }
        dis[v][d^1]=ds, fa[v]=x, DFS3(v,x,d);
    }
}
void DFS4(int x,int f,int d)
{
    d^=1;
//  printf("DFS4(%d,%d,%d) dis:%d\n",x,f,d,dis[x][d]);
    vis[x][d]=1;
    for(int i=H[x],v,ds=dis[x][d]+1; i&&!flag; i=nxt[i])
    {
        if((i&1)!=d||(v=to[i])==f) continue;
        if(vis[v][d^1])
        {
            if(dis[x][d]-dis[v][d^1]==Max)
            {
                printf("%d\n",Max+1); int t=0;
//              printf("Output! %d->%d\n",v,x);
                for(int p=x; p!=v; p=fa[p]) A[++t]=p;//, printf("->%d",p);
                A[++t]=v;
                for(int p=t; p; --p) printf("%d ",A[p]); putchar('\n');
                flag=1; return;
            }
            continue;
        }
        dis[v][d^1]=ds, fa[v]=x, DFS4(v,x,d);
    }
}

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);

    int type=read();
    while(n=read(),n)
    {
        Enum=1, memset(H,0,sizeof H);
        memset(vis,0,sizeof vis);

        m=read();
        for(int i=1,u,v; i<=m; ++i) u=read(),v=read(),AE(v,u),AE(u,v);
        flag=0;
        if(type)
        {
            for(int i=1; i<=n; ++i)
            {
                if(!vis[i][1]) DFS1(i,i,0);
                if(flag) break;
            }
            if(!flag) puts("-1");
        }
        else if(n<=2000)
        {
            Max=N;
            for(int i=1; i<=n; ++i)
                if(!vis[i][1]) dis[i][1]=0, DFS2(i,i,0);
            if(Max==N) puts("-1");
            else
            {
                printf("%d\n",Max);
                for(int p=Max; p; --p) printf("%d ",Ans[p]); putchar('\n');
            }
        }
        else
        {
            Max=N;
            for(int i=1; i<=n; ++i)
                if(!vis[i][1]) dis[i][1]=0, DFS3(i,i,0);
//          puts("OK");
            if(Max==N) puts("-1");
            else
            {
                memset(vis,0,sizeof vis);
                for(int i=1; i<=n; ++i)
                {
                    if(!vis[i][1]) dis[i][1]=0, DFS4(i,i,0);
                    if(flag) break;
                }
            }
        }
    }
    return 0;
}

C

打表未遂

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e5+5;

inline LL read()
{
    LL now=0,f=1;register char c=gc();
    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now*f;
}
void Subtask1(int K,int L)
{
    static bool f[703][703][2];

    memset(f,0,sizeof f);
    for(int i=1; i<L; ++i) f[i][i][0]=1;
    for(int i=1; i<L; ++i)
    {
        for(int j=1; j<=i; ++j)
        {
            int lim=std::min(L,j*K);
            
            
        }
        
    }
    
}
void Work()
{
    int K=read(); LL L=read();
//  if(L<=700) {Subtask1(K,L); return;}
    if(L>1e15) puts("GOD");
    else puts("DOG");
    
}

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);

    for(int T=read(); T--; Work());
    return 0;
}

牛客提高集训营3

原文：https://www.cnblogs.com/SovietPower/p/9699436.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！