头像

Chaosliang


访客:2347

离线:17小时前


活动打卡代码 AcWing 1107. 魔板

Chaosliang
17小时前

注意:

1.这题中我默认读法是从上到下从左到右,与原题目不匹配,其实可以修改,二刷的时候再改

2.unordered_map不太会用

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

char g[2][4];

unordered_map<string, pair<char, string>> pre;
unordered_map<string, int> dist;



string move0(string state)
{
    string t = state;
    for(int i = 0; i < 4; ++ i)
        t[i] = state[i+4];
    for(int i = 4; i < 8; ++ i)
        t[i] = state[i-4];
    return t;
}


string move1(string state)
{
    string t = state;
    for(int i = 1; i < 4; ++ i)
    {
        t[i] = state[i-1];
        t[i + 4] = state[i-1 + 4];
    }
    t[0] = state[3];
    t[4] = state[7];
    return t;
}

string move2(string state)
{
    string t = state;
    int tp = t[1];
    t[1] = t[5];
    t[5] = t[6];
    t[6] = t[2];
    t[2] = tp;
    return t;
}

int bfs(string start, string end)
{
    if(start == end)    return 0;
    queue<string> q;
    q.push(start);
    dist[start] = 0;

    while(!q.empty())
    {
        string t = q.front();
        q.pop();
        string m[3];
        m[0] = move0(t);
        m[1] = move1(t);
        m[2] = move2(t);

        for(int i = 0; i < 3; ++ i)
        {
            if(!dist.count(m[i]))
            {
                dist[m[i]] = dist[t] + 1;
                pre[m[i]] = {'A'+i, t};
                q.push(m[i]);
                if(m[i] == end) return dist[end];
            }
        }
    }
    return -1;
}

int main()
{
    // string t = "12348765";
    // cout << move0(t) << endl;
    // cout << move1(t) << endl;
    // cout << move2(t) << endl;
    // cout << t << endl;
    string start, end;
    for(int i = 0; i < 8; ++ i)
    {
        int x;
        cin >> x;
        end += char(x + '0');
    }
    // cout << end << endl;
    swap(end[4], end[7]), swap(end[5], end[6]);
    start = "12348765";
    int step = bfs(start, end);
    cout << step << endl;
    string res;
    while(end != start)
    {
        res += pre[end].first;
        end = pre[end].second;
    }
    reverse(res.begin(), res.end());
    if(step > 0)    cout << res << endl;
}


活动打卡代码 AcWing 173. 矩阵距离

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1005, M = N*N;

char g[N][N];

int dist[N][N];
PII q[M];

int n, m;

int hh = 0, tt = -1;

int main()
{
    memset(dist, -1, sizeof(dist));
    cin >> n >> m;
    for(int i = 0; i < n; ++ i)
        cin >> g[i];
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
        {
            if(g[i][j] == '1')
            {
                dist[i][j] = 0;
                q[++ tt] = {i, j};
            }
        }
    while(hh <= tt)
    {
        int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
        PII t = q[hh ++];
        for(int i = 0; i < 4; ++ i)
        {
            int qx = t.x + dx[i], qy = t.y + dy[i];
            if(qx < 0 || qx > n-1 || qy < 0 || qy > m-1)    continue;
            if(dist[qx][qy] != -1)  continue;
            dist[qx][qy] = dist[t.x][t.y] + 1;
            q[++ tt] = {qx, qy};
        }
    }
    for(int i = 0; i < n; ++ i)
    {
        for(int j = 0; j < m; ++ j)
        {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1100. 抓住那头牛

注意

这题主要注意上界

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5+5; // v*2-2 <=> (v-1)*2 

int n, k;
int dis[N];
int q[N];

int dfs()
{
    memset(dis, -1, sizeof(dis));
    int hh = 0, tt = -1;
    dis[n] = 0;
    q[++ tt] = n;
    while(hh <= tt)
    {
        int t = q[hh++]; //注意++位置
        if(t == k)  return dis[t];
        if(dis[t+1] == -1 && t+1 < N) 
        {
            dis[t+1] = dis[t] + 1;
            q[++tt] = t+1;
        }
        if(dis[t-1] == -1 && t-1>0)
        {
            dis[t-1] = dis[t] + 1;
            q[++tt] = t-1;
        }
        if(dis[t*2] == -1 && t*2 < N)
        {
            dis[t*2] = dis[t] + 1;
            q[++tt] = t*2;
        }
    }
    return -1;
}

int main()
{
    cin >> n >> k;
    cout << dfs() << endl;
}


活动打卡代码 AcWing 188. 武士风度的牛

注意

注意输入是先列后行

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 155, M = N*N;

int n, m;

char g[N][N];
int sx=-1, sy=-1;
PII q[M];
int dist[N][N];

int bfs()
{
    int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    int hh = 0, tt = -1;
    memset(dist, -1, sizeof(dist));
    dist[sx][sy] = 0;
    q[++ tt] = {sx, sy};
    while(hh <= tt)
    {
        PII tp = q[hh ++];//注意++位置
        for(int i = 0; i < 8; ++ i)
        {
            int a = tp.x + dx[i], b = tp.y + dy[i];
            if(a < 0 || a > n-1 || b < 0 || b > m-1)    continue;
            if(dist[a][b] != -1)    continue;
            if(g[a][b] == '*')  continue;
            if(g[a][b] == 'H')
            {
                return dist[a][b] = dist[tp.x][tp.y] + 1; 
            }
            dist[a][b] = dist[tp.x][tp.y] + 1;
            q[++ tt] = {a, b};
        }
    }
    return -1;
}

int main()
{
    cin >> m >> n; //注意
    for(int i = 0; i < n; ++ i)
    {
        cin >> g[i];
        for(int j = 0; j < m; ++ j)
        if(g[i][j] == 'K')
        {
            sx = i, sy = j;
        }
    }
    cout << bfs() << endl;
    return 0;
}


活动打卡代码 AcWing 1076. 迷宫问题

注意

1. 反向求解最短路方便打印路径

2. 入队出队++放在前面还是后面不要弄错了

3. pre数组起到了st数组的作用

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

#define x first
#define y second

using namespace std;

const int N = 1005, M = N*N;
typedef pair<int, int>  PII;

int n;

int g[N][N];
PII q[M];
PII pre[N][N];

void bfs(int sx, int sy)
{
    memset(pre, -1, sizeof(pre));
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    int hh = 0, tt = -1;
    pre[sx][sy] = {0, 0}; //随便写
    q[++ tt] = {sx, sy};
    while(hh <= tt)
    {
        PII t = q[hh ++];
        for(int i = 0; i < 4; ++ i)
        {
            int nx = t.x + dx[i], ny = t.y + dy[i];
            if(nx < 0 || nx > n-1 || ny < 0 || ny > n-1)    continue;
            if(pre[nx][ny].x != -1)   continue;
            if(g[nx][ny] == 1)  continue;
            pre[nx][ny] = t;
            q[++ tt] = {nx, ny};
        }
    }
}


int main()
{
    cin >> n;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
        {
            cin >> g[i][j];
        }
    bfs(n-1, n-1);
    PII point(0, 0); //打印路线
    while(true)
    {
        cout << point.x << " " << point.y << endl;
        if(point.x == n-1 && point.y == n-1)   break;
        point = pre[point.x][point.y];
    }
    return 0;
}


活动打卡代码 AcWing 1106. 山峰和山谷

注意平原即是山顶,也是山谷

#include <iostream>
#include <cstdio>
#include <algorithm>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 1005, M = N*N;
int n;

int g[N][N];
PII q[M];
bool st[N][N];
bool has_higher, has_lower;

void bfs(int sx, int sy)
{
    int hh = 0, tt = -1;
    st[sx][sy] = true;    
    q[++tt] = {sx, sy};

    while(hh <= tt)
    {
        int qx = q[hh].x, qy = q[hh].y;
        ++ hh;
        for(int i = qx-1; i <= qx+1; ++ i)
            for(int j = qy-1; j <= qy+1; ++ j)
            {
                if(i < 0 || i > n-1 || j < 0 || j > n-1)    continue;
                if(i == qx && j == qy)  continue;
                if(g[i][j] != g[qx][qy])
                {
                    if(g[i][j] > g[qx][qy]) has_higher = true;
                    else    has_lower = true;
                    continue;
                }
                if(!st[i][j])
                {
                    st[i][j] = true;
                    q[++tt] = {i, j};
                }
            }
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
        {
            cin >> g[i][j];
        }
    int num_high = 0, num_low = 0;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
        {

            if(!st[i][j])
            {
                has_higher = false, has_lower = false;
                bfs(i, j);
                if(!has_higher)     ++ num_high;
                if(!has_lower)      ++ num_low;
            }
        }
    cout << num_high << " " << num_low << endl;
    return 0;
}


活动打卡代码 AcWing 1098. 城堡问题

知识点:BFS + 简单二进制

#include <iostream>
#include <algorithm>
#include <cstdio>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55, M = N*N;

PII q[M];
int g[N][N];
bool st[N][N];
int n, m;

int bfs(int sx, int sy)
{
    int hh = 0, tt = -1;
    st[sx][sy] = true;
    q[++ tt] = {sx, sy};
    int area = 1;
    int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

    while(hh <= tt)
    {
        int qx = q[hh].x, qy = q[hh].y;
        ++ hh;
        for(int i = 0; i < 4; ++ i)
        {
            if(g[qx][qy] >> i & 1)  continue;
            int a = qx + dx[i], b = qy + dy[i];
            if(a < 0 || a > n-1 || b < 0 || b > m-1)    continue;
            if(st[a][b])    continue;
            st[a][b] = true;
            ++ area;
            q[++ tt] = {a, b};
        }
    }
    return area;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
        {
            cin >> g[i][j];
        }
    int cnt = 0, area = 0;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
        {
            if(!st[i][j])
            {
                area = max(area, bfs(i, j));
                ++ cnt;
            }
        }
    cout << cnt << endl;
    cout << area << endl;
    return 0;
}


活动打卡代码 AcWing 1097. 池塘计数

注意

判定map是否走过的st数组可以省略,直接把map的’W’改为’.’

#include <iostream>
#include <algorithm>
#include <cstdio>

#define x first 
#define y second 

using namespace std;
typedef pair<int, int> PII;
const int N = 1005, M = N*N;

int n, m;
char g[N][N];
PII q[M];

void bfs(int sx, int sy)
{
    int hh = 0, tt = -1;
    q[++tt] = {sx, sy};
    g[sx][sy] = '.';
    while(hh <= tt)//队列不空
    {
        int qx = q[hh].x, qy = q[hh].y;
        ++ hh;
        for(int i = qx-1; i <= qx+1; ++ i)
            for(int j = qy-1; j <= qy+1; ++ j)
            {
                if(qx == i && qy == j)    continue; //可省略
                if(i < 0 || i > n-1 || j < 0 || j > m-1)    continue;
                if(g[i][j] == '.')  continue;
                q[++tt] = {i, j};
                g[i][j] = '.';
            }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; ++ i)
        cin >> g[i];
    int cnt = 0;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
        {
            if(g[i][j] == 'W')
            {
                bfs(i, j);
                ++ cnt;
            }
        }
    cout << cnt << endl;
    return 0;
}


活动打卡代码 AcWing 1077. 皇宫看守

状态真的很难,f数组的初始化不会

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1505, M = 2*N, INF = 0x3f3f3f3f;

int h[N], e[M], w[M], ne[M], idx;

int n;

//f[i, j]三大状态
//j = 0: i节点没放守卫,被父节点的守卫看到
//j = 1: i节点放了守卫,被自己的守卫看到
//j = 2: i节点没放守卫,被子节点中至少有一个守卫看到(有很多子节点)
int f[N][3]; 

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int father)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dfs(j ,u);
        f[u][0] += min(f[j][1], f[j][2]); 
        f[u][1] += min(min(f[j][0], f[j][1]), f[j][2]);
    }
    f[u][2] = INF;//思考一下,初始化了所有的叶子结点
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        f[u][2] = min(f[u][2], f[j][1]+f[u][0]-min(f[j][1], f[j][2]));//理解很数学
    }
}

int main()
{
    //初始化1
    memset(h, -1, sizeof(h));

    //输入
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int a, k, m;
        cin >> a >> k >> m;
        w[a] = k;
        while(m --)
        {
            int b;
            cin >> b;
            add(a, b);
            add(b, a);
        }
    }
    //初始化2
    int root = 1;//假定为根节点
    for(int i = 1; i <= n; ++ i)
    {
        f[i][1] = w[i];
    }

    dfs(root, -1);//对于无向树可以随便一个点当做根节点
    cout << min(f[root][1], f[root][2]) << endl;
    return 0;
}


活动打卡代码 AcWing 323. 战略游戏

算法:树状DP + 状态机DP

注意点:

1.看到min记住初始化最大

2. 有向单边树邻接表大小不用2倍

3.多组数据的题目注意检查初始化

4.st数组用来寻找根节点

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1505;

int h[N], e[N], ne[N], idx; //每条边只出现一次

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

bool st[N]; //非根节点

int n;

int f[N][2];

void dfs(int u)
{
    int sum0=0, sum1=0;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        sum0 += f[j][1];
        sum1 += min(f[j][0], f[j][1]);//看到min记住初始化最大
    }
    f[u][0] = sum0;
    f[u][1] = sum1 + 1;
}

int main()
{
    while(scanf("%d", &n) != -1)//多组数据记得初始化
    {
        memset(h, -1, sizeof(h));
        memset(st, 0, sizeof(st));
        memset(f, 0x3f,sizeof(f)); //最大
        idx = 0;
        for(int i = 0; i < n; ++ i)
        {
               int a, num;
               scanf("%d:(%d)", &a, &num);
               while(num --)
               {
                   int b;
                   cin >> b;
                   add(a, b);
                   st[b] = true;
               }
        }
        int root = 0;//从0开始
        while(st[root])    ++ root;
        dfs(root);
        cout << min(f[root][0], f[root][1]) << endl;
    }
    return 0;
}