B

模拟，水题

#include<bits/stdc++.h>

using namespace std;

char s1[100005],s2[100005];

int a1[100005],a2[100005],bj;

int main()

{

    cin>>s1>>s2;

    int len=strlen(s1);

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

    {

        a1[i]=s1[i]-97;

        a2[i]=s2[i]-97;

    }

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

    {

        bj=0;

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

        {

            a1[j]=(a1[j]+1)%26;

        }

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

        {

            if(a1[j]!=a2[j])

            {

                bj=1;

                break;

            }

        }

        if(bj==0)

        {

            cout<<"Yes";

            return 0;

        }

    }

    cout<<"No";

}

C

全排列求出P数组的所有可能，邻接矩阵存图，对每个\(P_i\)进行一次判断

#include <bits/stdc++.h>

using namespace std;

int ans[100001],n,m,bj[100001];

int sq1[10][10],sq2[10][10];

struct node

{

    int x,y;

}bian[100];

void dfs(int k)

{

    int i;

    if(k>n)

    {

        int bz=0;

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

        {

            if(sq2[ans[bian[i].x]][ans[bian[i].y]]!=1)

            {

                return;

            }

        }

        cout<<"Yes";

        exit(0);

    }

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

    {

        if(!bj[i])

        {

            ans[k]=i;

            bj[i]=1;

            dfs(k+1);

            bj[i]=0;

            ans[k]=0;

        }

    }

}

int main()

{

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

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

    {

        int x,y;

        cin>>x>>y;

        sq1[y][x]=1,sq1[x][y]=1;

        bian[i].x=x,bian[i].y=y;

    }

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

    {

        int x,y;

        cin>>x>>y;

        sq2[x][y]=1,sq2[y][x]=1;

    }

    dfs(1);

    cout<<"No";

    return 0;

}

D

每个位置(i,j)都可以从(i-1,j)和(i,j-1)走到，因此状态转移方程是\(f_{i,j}=f_{i-1,j}+f_{i,j-1}\),但当(i-1,j)或(i,j-1)有墙时就不能通过，

所以需要进行特判

#include<bits/stdc++.h>

using namespace std;

int ans,n,m,dp[1005][1005],bj[101][101],maxn;

char c[1005][1005];

int main()

{

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

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

    {

        scanf("%s",c[i]+1);

    }

    dp[1][1]=1;

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

    {

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

        {

            if(c[i][j]=='#'||(dp[i-1][j]==0&&dp[i][j-1]==0))//判断是否有墙

            {

                continue;

            }

            dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1])+1);

            ans=max(ans,dp[i][j]);

        }

    }

    cout<<ans;

}

E

DP题

设\(x[K][1]\)表示上下移动\(K\)次达到了\((x2,y2)\)，

\(x[K][0]\)表示上下移动\(K\)次没达到\((x2,y2)\)，

\(y[K][1]\)表示左右移动\(K\)次达到了\((x2,y2)\)，

\(y[K][0]\)表示左右移动\(K\)次没达到\((x2,y2)\)，

那么我们就可以得到状态转移方程

\(x[i][1]\):第\(i\)步到达了，那么\(i-1\)步一定是没有到达的,因为不可以静止不动

\(x[i][1]=x[i-1][0]\)

\(x[i][0]\):第\(i\)步没有到达，那么第\(i-1\)步可以分为没有到达与到达

如果第\(i-1\)步没有到达\(X[i-1][0]\) 又因为第i步也没有达到所以第\(i\)步有\(h-2\)种选择（不能是终点和不动）

如果第\(i-1\)步到达了 \(X[i-1][1]\) 又因为第i步也没有达到所以第\(i\)步有\(h-1\)种选择（不能不动）

\(X[i][0]=X[i-1][0]*(h-2)+X[i-1][1]*(h-1)\)

另一个数组也是同理

\(Y[i][1]=Y[i-1][0]\)

\(Y[i][0]=Y[i-1][0]*(w-2)+Y[i-1][1]*(w-1)\)

当\(x1==x2\)的时候\(X\)在第0步的时候就已经到达终点即\(X[0][1]=1\)

否则\(X[0][0]=1\)

当\(y1==y2\)的时候\(Y\)在第0步的时候就已经到达终点即\(Y[0][1]=1\)

否则\(Y[0][0]=1\)

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 998244353

ll X[1000010][2],Y[1000010][2];

ll jc[1000010],inv[1000010];

ll n,m,k,x1,Y1,x2,y2;

ll qmi(ll a,ll b,ll p)

{

    if(!a)return 0;

    a%=p;

    ll res=1;

    while(b)

    {

        if(b&1)res=res*a%p;

        a=a*a%p;

        b>>=1;

    }

    return res;

}

ll C(ll a,ll b)

{

    if(a<b)return 0;

    return jc[a]*inv[b]%mod*inv[a-b]%mod;

}

int main()

{

    cin>>n>>m>>k;

    cin>>x1>>Y1>>x2>>y2;

    X[0][x1==x2]=1;

    Y[0][Y1==y2]=1;

    for(ll i=1;i<=k;i++)

    {

        X[i][1]=X[i-1][0];

        X[i][0]=(X[i-1][0]*(n-2)%mod+X[i-1][1]*(n-1)%mod)%mod;

        Y[i][1]=Y[i-1][0];

        Y[i][0]=(Y[i-1][0]*(m-2)%mod+Y[i-1][1]*(m-1)%mod)%mod;

    }

    jc[0]=inv[0]=1;

    for (ll i=1;i<1000010;i++)

    {

        jc[i]=jc[i-1]*i%mod;

        inv[i]=inv[i-1]*qmi(i,mod-2,mod)%mod;

    }

    ll res=0;

    for(ll i=0;i<=k;i++)

    {

        ll t=C(k,i)*X[i][1]%mod*Y[k-i][1]%mod;//组合数算答案，给x分配i步,y就是k-i步,还要乘一个C(k,i)

        res=(res+t)%mod;

    }

    cout<<res<<endl;

}

巴特西

atcoder ABC 232 B~E题解

B

C

D

E

最新文章

热门文章