牛客周赛37

题目：E-魔法之森的蘑菇

题目描述：

给你一张图，起点为$S$终点为$T$，起初任意选择前进方向，除非遇到 $*$，否则不能更改方向，遇到 $*$ 可以选择朝向除返回刚刚位置的其他方向，# 为障碍物，$.$ 为普通路径，求 $S$ $-$ $>T$ 最短距离。

题目分析：

起初很容易考虑BFS，遇到 $*$ 就把三个方向全加进去，遇到 $.$ 就按原来方向走，同时把走过的点打上标记，通过bfs最短路属性记录最小答案。这个思路是没错的，但是我们之所以把走过的点打上标记，是因为我们已经保证这个点的所有状态已经加到队列中去。但是这个题一个点的所有状态并不是单纯走到这个点，而是包含了从四种方向走来的四种状态，比如假设一开始走到 $x$ 点为 $2$ 步，但是由于 $x$ 点为 $.$ ,它的这个方向并不能对最短答案有贡献，所以可能有一个更长的但是方向不一样的路径经过这个点，并且能对最短答案造成贡献。所以上述思路只需要改成走到一个点被打上标记只能是带有特定方向的，再取每个点距离最小值，本质上其实就是一个以四个方向形成的分层图最短路。

题目代码：

int n, m, sx, sy, ex, ey, len[N][N][4], dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
bool st[N][N][4];
char g[N][N];
queue<array<int, 3>> q;
void solve()
{
    while (q.size())
        q.pop();
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {

            for (int k = 0; k < 4; k++)
                st[i][j][k] = 0, len[i][j][k] = 1e18;
            ;
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> g[i][j];
            if (g[i][j] == 'S')
                sx = i, sy = j, g[i][j] = '*';
            if (g[i][j] == 'T')
                ex = i, ey = j, g[i][j] = '*';
        }
    for (int i = 0; i < 4; i++)
        st[sx][sy][i] = 1, len[sx][sy][i] = 0;
    for (int i = 0; i < 4; i++)
    {
        int t = sx + dx[i];
        int z = sy + dy[i];
        if (t >= 1 && t <= n && z >= 1 && z <= m && (g[t][z] == '*' || g[t][z] == '.'))
            st[t][z][i] = 1, q.push({t, z, i}), len[t][z][i] = 1;
    }

    while (q.size())
    {
        auto [x, y, to] = q.front();
        q.pop();
        int t, z;
        // cout<<x<<" "<<y<<" "<<len[x][y]<<"\n";
        if (x == ex && y == ey)
            break;
        if (g[x][y] == '.')
        {
            t = x + dx[to], z = y + dy[to];
            if (t >= 1 && t <= n && z >= 1 && z <= m && (g[t][z] == '*' || g[t][z] == '.') && !st[t][z][to])
                q.push({t, z, to}), len[t][z][to] = min(len[t][z][to], len[x][y][to] + 1), st[t][z][to] = 1;
        }
        else if (g[x][y] == '*')
        {
            int tt;
            if (to == 0)
                tt = 1;
            else if (to == 1)
                tt = 0;
            else if (to == 2)
                tt = 3;
            else if (to == 3)
                tt = 2;
            for (int i = 0; i < 4; i++)
            {
                t = x + dx[i], z = y + dy[i];
                if (i != tt && t >= 1 && t <= n && z >= 1 && z <= m && (g[t][z] == '*' || g[t][z] == '.') && !st[t][z][i])
                    q.push({t, z, i}), len[t][z][i] = min(len[t][z][i], len[x][y][to] + 1), st[t][z][i] = 1;
            }
        }
    }
    int ans = 1e18;
    for (int i = 0; i < 4; i++)
        ans = min(ans, len[ex][ey][i]);
    if (ans != 1e18)
        cout << ans << "\n";
    else
        cout << -1 << "\n";
}

题目：F-三途川的摆渡人_

题目大意：

$n$个数，每个数为$a_i$ ,$（0<=a_i<=127）$，求 & 成 $0$ 的得最少个数，不能输出 $-1$。

题目分析：

从 & 的性质去拆位贪心考虑显然太麻烦，但是 & 具有传递性可以状态转移。设 dp[i][a[i]&j] 表示前i个物品，转移到 a[i]&j 的最小次数：

$$状态转移：dp[i][a[i]\&j]=\min(dp[i][a[i]\&j], dp[i-1][j]+1);$$

又因为相同的数&，结果一定不为$0$，所以前$n$个数直接优化成扫$0$ $~$ $127$以内存在的值即可，而且只用到上一层所以直接滚动数组优化：

$$状态转移：dp[1][i\&j]=min(dp[1][i\&j],dp[0][j]+1);$$

题目代码：

int dp[2][203],p[220];//滚动数组和记录0~127数存在与否的p
void solve(){
    int n;cin>>n;
    memset(p,0,sizeof p);
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        p[x]++;
    }
    memset(dp,0x3f,sizeof dp);
    for(int i=0;i<=200;i++){
        if(p[i]){
            dp[1][i]=1;//当前点选，并且没有比直接选当前点来组成当前点次数更小的了
            for(int j=0;j<=200;j++){
                dp[1][i&j]=min(dp[1][i&j],dp[0][j]+1);//dp[1][i&j]不选，后面为选的，取最小
            }
        }
        for(int j=0;j<=200;j++){
            dp[0][j]=dp[1][j];//滚动赋值
        }
    }
    if(dp[0][0]>n)cout<<-1<<"\n";
    else cout<<n-dp[0][0]<<"\n";//求得组成当前数最小个数，所以抛弃个数为n-dp[0][0]
}