头像

我是java同学




离线:4小时前


最近来访(100)
用户头像
Mup丶Superman
用户头像
Royal
用户头像
一塌糊涂
用户头像
yxc的小迷妹
用户头像
要么不做要么做绝
用户头像
xhalz里的大蒟蒻
用户头像
Bochi
用户头像
surplus_9
用户头像
acwing_0909
用户头像
Hurricane27
用户头像
聪明陈
用户头像
Weather
用户头像
薛定猫的谔_9
用户头像
阿瑟初学者
用户头像
glimpse_
用户头像
1357649762
用户头像
psyche
用户头像
吴钩_9
用户头像
晓曦_6
用户头像
DreamFather

问题 ac币

1ac币是抵1元吗




#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;
typedef pair<int, int> PII;

int n, m;
int g[N][N];
int d[N][N];
PII q[N * N];

int bfs()
{
    int hh = 0, tt = 0;
    q[0] = {0, 0}; //

    memset(d, -1, sizeof d);

    d[0][0] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (hh <= tt)
    {
        auto t = q[hh ++];

        for (int i = 0; i < 4; i ++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q[ ++ tt] = {x, y};
            }
        }
    }

    return d[n - 1][m - 1];
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}



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

using namespace std;

const int N = 110;
typedef pair<int, int> PII;

int n, m;
int g[N][N]; //存矩阵图
int d[N][N]; //存每一个点到起点的距离
PII q[N * N];


int bfs()
{
    int hh = 0, tt = 0;
    q[0] = {0, 0};

    memset(d, -1, sizeof d); //把所有距离初始化成-1,表示没有走过

    d[0][0] = 0; //表示已经走过(初始位置)

    //尝试往上下左右四个方向拓展有技巧,不用写四个判断,可以用向量表示
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (hh <= tt)
    {
        auto t = q[hh ++ ]; //取出队头元素
        //每一次枚举四个方向
        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) //空地上为0,并且还没有被走过
            {
                d[x][y] = d[t.first][t.second] + 1; //搜到的最佳路径定成1
                q[ ++ tt] = {x, y}; //把当前点加进队列
            }
        }
    }

    return d[n - 1][m - 1];  //把右下角点的距离输出即为答案
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}


活动打卡代码 AcWing 844. 走迷宫

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

using namespace std;

const int N = 110;
typedef pair<int, int> PII;

int n, m;
int g[N][N]; //存矩阵图
int d[N][N]; //存每一个点到起点的距离
PII q[N * N];


int bfs()
{
    int hh = 0, tt = 0; //因为已经放了一个坐标进去,所以tt = 0
    q[0] = {0, 0}; //一维数组也可以存一个坐标

    memset(d, -1, sizeof d); //把所有距离初始化成-1,表示没有走过

    d[0][0] = 0; //表示已经走过(初始位置)

    //尝试往上下左右四个方向拓展有技巧,不用写四个判断,可以用向量表示
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (hh <= tt)
    {
        auto t = q[hh ++ ]; //取出队头元素
        //每一次枚举四个方向
        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) //空地上为0,并且还没有被走过
            {
                d[x][y] = d[t.first][t.second] + 1; //搜到的最佳路径定成1
                q[ ++ tt] = {x, y}; //把当前点加进队列
            }
        }
    }

    return d[n - 1][m - 1];  //把右下角点的距离输出即为答案
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}



#include <iostream>

using namespace std;

const int N = 100010;
int p[N], siz[N];   //siz存储节点数量
int n, m;

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) 
    {
        p[i] = i;
        siz[i] = 1;     //把每个父节点初始化数量为1
    }

    while (m --)
    {
        int a, b;
        string op;
        cin >> op;

        if (op == "C") 
        {
            cin >> a >> b;
            if (find(a) == find(b)) continue;   //如果两个节点的父节点相同,就没有必要相加
            siz[find(b)] += siz[find(a)];       //把a节点的数量加到b节点上
            p[find(a)] = find(b);
        }
        else if(op == "Q1")
        {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else 
        {
            cin >> a;
            printf("%d\n", siz[find(a)]);
        }
    }
    return 0;
}



#include <iostream>

using namespace std;

const int N = 100010;
int n, m;
int p[N],siz[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);

    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
    {
        p[i] = i;
        siz[i] = 1;
    }

    while (m --)
    {
        int a, b;
        char op[5];
        scanf("%s", op);

        if (op[0] == 'C') 
        {
            scanf("%d%d", &a, &b);
            if (find(a) == find(b)) continue;
            siz[find(b)] += siz[find(a)];
            p[find(a)] = find(b);
        }
        else if (op[1] == '1')
        {
            scanf("%d%d", &a, &b);
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            scanf("%d", &a);
            printf("%d\n", siz[find(a)]);
        }
    }
    return 0;
}



#include <iostream>

using namespace std;

const int N = 100010;
int p[N];
int n, m;

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    while (m --)
    {
        int a, b;
        string op;
        cin >> op >> a >> b;

        if (op == "M") p[find(a)] = find(b);
        else 
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}



#include <iostream>

using namespace std;

const int N = 100010 * 31;
int son[N][2], idx;
int a[N];
int n;

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if (son[p][!u]) 
        {
            p = son[p][!u];
            res = res * 2 + !u;
        }
        else 
        {
            p = son[p][u];
            res = res * 2 + u;
        }
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);

    int res = 0;
    for (int i = 0; i < n; i ++)
    {
        insert(a[i]);
        int t = query(a[i]);
        res = max(res, a[i] ^ t);
    }
    printf("%d\n", res);

    return 0;
}



#include <iostream>

using namespace std;

typedef long long ULL;

const int N = 100010, P = 131;
int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    scanf("%d%d%s", &n, &m, str + 1);

    p[0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }

    while (m --)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;

        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}




#include <iostream>

using namespace std;

typedef long long ULL;

const int N = 100010, P = 131;
char str[N];
int n, m;
ULL p[N], h[N];

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    scanf("%d%d%s", &n, &m, str + 1);

    p[0] = 1;
    for (int i = 1; i <= n; i ++) 
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }

    while (m --)
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}