Educational Codeforces Round 118 (Rated for Div. 2)（D，E）

D

D

这个题大意给我们一个长度为\(n\)的序列，然后我们需要知道有多少个满足一下条件的子序列

对于这一个序列，长度为\(k\)，对于每一个\(i\)(\(1<=i<=k\)),都需要满足以下条件的子序列数量为多少

对于里面的\(i\),均满足\(\vert x_i-mex(x_1,x_2,x_3,...x_i) \vert<=1\)

对于满足上面的条件的子序列，有两种

第一种，\(0,1,2,3,4,5，...k\),这一种\(mex\)为\(k+1\),满足条件

第二种，\(0,1,2,3,...k-2,k\),这一种\(mex\)为\(k-1\)满足条件

所以我们可以用一个\(dp\)数组来记录

\(dp[i] [0]\)是满足第一种条件的子序列的情况，\(dp[i] [1]\)是满足第二种条件的子序列的情况，\(i\)代表的是此时的如果此时的最后一个，我们需要得到的数\(x\),加一，因为初状态\(dp[0] [0]\)不会和出现\(0\)重复

所以每一个数都加一

怎么转移呢

假如此时已经有了一个\(x\)

对于\([1,x]\)，可以可以加在\([1,x]\)的后面，还可以在\([1,x-1]\)的后面

dp[x][0]+=dp[x][0];//[1,x]变成[1,x]
dp[x][0]+=dp[x-1][0];//[1,x-1]变成[1,x]

那么对于\([1,x-2] \cup {x}\)也可以放入一个\(x\),还是\([1,x-2] \cup {x}\)

 dp[x][1]+=dp[x][1];//

那么对于\([1,x] \cup {x+2}\)也可以放入一个\(x\),还是\([1,x] \cup {x+2}\)

 dp[x+2][1]+=dp[x+2][1];

对于\([1,x-2]\),我们还是可以更新\([1,x-2] \cup {x}\)的值

if (x>1)
 {
    dp[x][1]+=dp[x-2][0];
 }

具体看代码

#include <iostream>
#include <vector>
using namespace std;
const int maxn=5e5+10;
#define int long long 
const int mod=998244353;
int t,n,a[maxn];
void solve()
{
    cin>>n;
    vector<vector<int>>dp(n+5,vector<int>(3,0));
    dp[0][0]=1;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        x++;
        dp[x][0]+=dp[x][0];//[1,x]变成[1,x]
        dp[x][0]+=dp[x-1][0];//[1,x-1]变成[1,x]
        dp[x][1]+=dp[x][1];//
        dp[x+2][1]+=dp[x+2][1];
        if (x>1)
        {
            dp[x][1]+=dp[x-2][0];
        }
        dp[x][0]%=mod;
        dp[x][1]%=mod;
        dp[x+2][1]%=mod;
    }
    int ans=0;
    for (int i=1;i<=n+1;i++)
    {
        ans+=dp[i][0]+dp[i][1];
        ans%=mod;
    }
    cout<<ans<<'\n';
    return ;
}
signed main ()
{
    cin>>t;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}

E

E

这个题意思比较难理解，最后理解正确了就可以知道这个题的意思了

这个就是判断每一个点有几个可以走的方向，只有只有一条可以走的方向才可以改变那个位置上的字符，理解这个就很好办了

但是咋一看，我没有看出这个意思

现在我也只可以简单的理解一下

这里有一个机器，如果我们给出了一个可以走的方向，但是他是疯狂的，他一定走的不是我给的那个方向，我们需要让这个机器人走到目的地

那我们可以看成目的地到最初的位置这一条路上如果某一个位值只有一个方向是可以行走的，那么就我们给出的指令只有那一个，但是这个机器不会按照指令来，那么就一定不可以到达目的地了，所以这个位置我们就相当于让这个位置上的机器人直达目的地

以上是全是本人拙见

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int maxn=1e6+10;
int n,m;
string s[maxn];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
bool check(int x,int y)
{
    int cnt=0;
    for (int d=0;d<4;d++)
    {
        int tx=x+dx[d];
        int ty=y+dy[d];
        if (tx<=0||tx>n||ty<0||ty>=m) continue;
        if (s[tx][ty]=='.') cnt++;
    }
    return cnt<2;
}
void bfs(int sx,int sy)
{
    queue<pair<int,int>>q;
    q.push({sx,sy});
    while (!q.empty())
    {
        auto [x,y]=q.front();
        q.pop();
        for (int d=0;d<4;d++)
        {
            int tx=x+dx[d];
            int ty=y+dy[d];
            if (tx<=0||tx>n||ty<0||ty>=m) continue;
            if (s[tx][ty]!='.') continue;
            if (check(tx,ty))
            {
                s[tx][ty]='+';
                q.push({tx,ty});
            }
        }
    }
    return ;
}
void solve()
{
    cin>>n>>m;
    int sx=0,sy=0;
    bool find=false;
    for (int i=1;i<=n;i++)
    {
        cin>>s[i];
        for (int j=0;j<m&&!find;j++)
        {
            if (s[i][j]=='L')
            {
                sx=i,sy=j;
                find=true;
            }
        }
    }
    bfs(sx,sy);
    for (int i=1;i<=n;i++)
    {
        cout<<s[i]<<'\n';
    }
    return ;
}
signed main ()
{
    int t;
    cin>>t;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}