2021 百度之星大赛初赛第一场题解

• Marvolo • 0条评论 •

比赛信息

比赛地址

Solved 5/8

Rank 81/1864

[A] 迷失

题意

给出一个无向图，一开始有一个人在1​号点，要到n​号点去。他可以移动k​次，每次移动会从当前点随机移动到相邻的点上。有一些边在经过之后会给一个 Buff 效果。问他移动k次，恰好移动到n，且吃了奇数次 Buff 的概率是多少。

题解

点的数量很少，只有100。但是k却很大，达到了10^{6}。数据规模很明显在暗示矩阵快速幂。

维护两个概率矩阵a,b​，元素a[i][j]​表示从i​移动到j​​，且吃了奇数次 Buff 的概率；b[i][j]表示吃了偶数次 Buff 的概率。对矩阵乘法做一个简单的修改，有：

a[i][j]=\sum_{k=1}^{n}a[i][k]*b[k][j]+b[i][k]+a[k][j]

b[i][j]=\sum_{k=1}^{n}a[i][k]*a[k][j]+b[i][k]+b[k][j]​​​

就是分奇偶进行维护，最后的答案为a[1][n]​​。​

注意一开始矩阵中的元素并不是0和1，而是这条边被用到的概率(也就是端点度数的倒数)。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 110
#define INF 0x3f3f3f3f
#define MOD 998244353
using namespace std;

int T,n,m,k,i,j,x,y,z,flag;
LL p,q;

struct Data{
    LL x,y;
}a[N][N],b[N][N],c[N][N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline LL Mi(LL x,LL y){
    LL p=x,t=1,Res=1;
    for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
    return Res;
}

IL void Mul(){
    reg int i=0,j=0,k=0;
    if (!flag){
        flag=1;
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
                b[i][j]=a[i][j];
        return;
    }
    memset(c,0,sizeof(c));
    for (k=1;k<=n;k++)
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++){
                c[i][j].x=(c[i][j].x+a[i][k].x*b[k][j].y%MOD)%MOD;
                c[i][j].x=(c[i][j].x+a[i][k].y*b[k][j].x%MOD)%MOD;
                c[i][j].y=(c[i][j].y+a[i][k].x*b[k][j].x%MOD)%MOD;
                c[i][j].y=(c[i][j].y+a[i][k].y*b[k][j].y%MOD)%MOD;
            }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            b[i][j]=c[i][j];
}

IL void Self(){
    reg int i=0,j=0,k=0;
    memset(c,0,sizeof(c));
    for (k=1;k<=n;k++)
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++){
                c[i][j].x=(c[i][j].x+a[i][k].x*a[k][j].y%MOD)%MOD;
                c[i][j].x=(c[i][j].x+a[i][k].y*a[k][j].x%MOD)%MOD;
                c[i][j].y=(c[i][j].y+a[i][k].x*a[k][j].x%MOD)%MOD;
                c[i][j].y=(c[i][j].y+a[i][k].y*a[k][j].y%MOD)%MOD;
            }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            a[i][j]=c[i][j];
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        n=read();   m=read();   k=read();
        memset(a,0,sizeof(a));
        for (i=1;i<=m;i++){
            x=read();   y=read();   z=read();
            if (z==1)   a[x][y].x=a[y][x].x=1;
            else a[x][y].y=a[y][x].y=1;
        }
        for (i=1;i<=n;i++){
            int tot=0;
            for (j=1;j<=n;j++)
                if (a[i][j].x == 1 || a[i][j].y==1) tot++;
            tot=Mi(tot,MOD-2);
            for (j=1;j<=n;j++)
                a[i][j].x*=tot,a[i][j].y*=tot;
        }
        flag=0;
        for (i=1;i<=k;i<<=1){
            if (i&k)    Mul();
            Self();
        }
        printf("%lld\n",b[1][n].x);
    }
    return 0;
}

[C] 鸽子

题意

有n​个电脑，其中有一台是坏的，坏电脑一开始在第k​个位置。有m​个交换操作要被依次执行，每次交换两台电脑的位置。现在对于每一个i​，求出坏电脑想要在最后停留在i​位置，最少需要忽略几个交换操作。

题解

f[i][j]表示执行完前i次操作后，坏电脑停留在j位置的最少忽略次数。不妨设第i次被交换的两个位置是u,v。则有f[i][u]=Min(f[i-1][v],f[i-1][u]+1)。也就是坏电脑要么随交换操作被换过来，要么本身就在这个位置，然后忽略一次操作留在原地。

按操作执行的时间顺序依次进行转移即可，此时注意到第一维其实是可以压掉的，直接用f[i]表示停留在i位置的忽略次数就行。初始状态f[i]=inf,f[k]=0​。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;

int T,i,j,n,m,k,x,y;
int f[N];

struct Data{
    int x,y;
}a[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        n=read();   m=read();   k=read();
        for (i=1;i<=m;i++){
            a[i].x=read();  a[i].y=read();
        }
        for (i=1;i<=n;i++)  f[i]=INF;
        f[k]=0;
        for (i=1;i<=m;i++){
            x=f[a[i].x];    y=f[a[i].y];
            f[a[i].x]=Min(x+1,y);
            f[a[i].y]=Min(y+1,x);
        }
        for (i=1;i<=n;i++){
            printf("%d",(f[i]==INF)?-1:f[i]);
            if (i!=n)   putchar(' ');
        }
        puts("");
    }
    return 0;
}

[D] 萌新

题意

给出a,b,求最大最小的c，满足1<c\leq max(a,b)且a \equiv b (\mod c)。

题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 800010
#define INF 0x3f3f3f3f
using namespace std;

int T,i;
int a,b,c,d,flag;
int v[N],p[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL void Ready(){
    reg LL i=0,j=0,x=0;
    for (i=2;i<=800000;i++){
        if (v[i])   continue;
        p[++p[0]]=i;
        for (j=i*i;j<=800000;j+=i)  v[j]=1;
    }
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    Ready();
    while (T--){
        scanf("%d%d",&a,&b);
        if (a==b && a==1){
            puts("-1 -1");
            continue;
        }

        if (a==b){
            printf("2 %d\n",a);
            continue;
        }

        c=Max(a,b)-Min(a,b);
        if (c==1){
            puts("-1 -1");
            continue;
        }

        flag=0;
        for (i=1;i<=p[0];i++){
            if (c%p[i] == 0){
                printf("%d ",p[i]);
                flag=1;
                break;
            }
        }

        if (flag==0)    printf("%d ",c);
        printf("%d\n",c);
    }
    return 0;
}

[F] 毒瘤数据结构题

题意

给出一个长度为n​​​​的数列，数列每个位置初始值都是0。接下来有n​​​​个操作，每个操作要么将x​​​​位置修改为1，要么询问假如将x​​​​位置修改为1后，最大的i​​使得\sum_{p=1}^{i}a_{p}=i​​是多少。

题解

树状数组维护前缀和，对于每个查询二分答案。虽然时间复杂度为O(n \log n \log n)，但是常数很小，可以AC。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define low(x) (x&(-x))
#define IL inline
#define reg register
#define LL long long
#define N 5000010
#define INF 0x3f3f3f3f
using namespace std;

int n,i,x,y;
int t[N],a[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

char buf[1<<15],*fs,*ft;
inline char gc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int gint(){
    int x=0,ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=gc();
    return x;
}   //Fastest Read

inline int Query(int x){
    int Ans=0,i=0;
    for (i=x;i;i-=low(i))    Ans+=t[i];
    return Ans;
}

inline void Add(int x,int val){
    int i=0;
    for (i=x;i<=n;i+=low(i))    t[i]+=val;
}

IL void Work(){
    reg int i=0,low=0,high=0,mid=0,ans=0;
    low=1; high=n;
    while (low<=high){
        mid = (low+high)>>1;
        if (Query(mid) == mid)  ans=mid,low=mid+1;
        else high=mid-1;
    }
    printf("%d\n",ans+1);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=gint();
    for (i=1;i<=n;i++){
        x=gint();   y=gint();
        if (x==1){
            if (a[y]==1) continue;
            Add(y,1);   a[y]=1;
        }
        else {
            if (!a[y])  Add(y,1);
            Work();
            if (!a[y])  Add(y,-1);
        }
    }
    return 0;
}

[H] 猎人杀

题意

太长懒得打了：

image-20210731162544340

题解

直接模拟即可。注意人数小于等于2的时候游戏就结束了，而不是小于2。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 55
#define INF 0x3f3f3f3f
using namespace std;

int T,n,i,j;
int a[N][N],v[N],d[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL void Work(){
    reg int res=n,i=0,j=0,now=0;
    for (i=1;i<=n;i++)  if (d[i])   now=i;

    while (res>2){
        for (i=1;i<=n;i++){
            if (v[a[now][i]]==1)    continue;
            v[a[now][i]]=1;
            now=a[now][i];
            break;
        }
        res--;

        if (d[now]==1){
            puts("lieren");
            return;
        }
    }

    for (i=1;i<=n;i++)
        if (v[i]==0 && d[i]){
            puts("langren");
            return;
        }
    puts("lieren");
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        n=read();
        for (i=1;i<=n;i++)  d[i]=read();
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
                a[i][j]=read();
        memset(v,0,sizeof(v));
        Work();
    }
    return 0;
}

总结

和去年第一场比难度下降了很多，去年想做出4,5题的难度还是非常高的，今年也就一道矩阵快速幂够看。剩下的三个题基本上只有个位数的人会做（先坑着，有机会补一个题解）；参赛人数相比去年也缩水了不少，少了200人左右的样子，可能和当天有牛客比赛有关系吧。1000个晋级名额，一共约2000人参赛，只要做出2道题，且罚时不要过于离谱的话就能晋级复赛。

整场比赛前半段时间非常不在状态，一开始以为难度按顺序排列，死磕了一会A题，写了一个矩阵快速幂残篇后，才被队友提醒后面还有签到题，然后连 WA 三次...后面正常地跟榜，切题，找回了一些感觉，鸽子那个题也很快就推导了出来。后面一看压轴题不可做就跑去写题解了，最终比赛3h，划水2h。

复赛名额已经到手，今年能拿一件T恤就算成功。

声明: 本文采用 BY-NC-SA 协议进行授权，如无注明均为原创，转载请注明转自 Marvolo
本文地址: 2021 百度之星大赛初赛第一场题解
DP 数学 树状数组 模拟 矩阵快速幂
说点什么
登录
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...