atcoder ABC 232 B~E题解

目录

• B
• C
• D
• E

 

---

作者：@炒鸡垃圾的XCR
本文为作者原创，转载请注明出处：https://www.cnblogs.com/XCRblogs/p/16482636.html

---

Top

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";
}
折叠 

Top

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;
}
折叠 

Top

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;
}

折叠 

Top

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]\ast (h-2)+X[i-1][1]\ast (h-1)$

另一个数组也是同理

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

$Y[i][0]=Y[i-1][0]\ast (w-2)+Y[i-1][1]\ast (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;
}
折叠