头像

王俊吉




在线 


最近来访(81)
用户头像
ACwing123
用户头像
sknnn
用户头像
Zxx
用户头像
ACG2021
用户头像
carlruan
用户头像
yxc
用户头像
笑笑虎
用户头像
Alter_3
用户头像
冷冷月光
用户头像
kobe88
用户头像
haimx
用户头像
Winter8
用户头像
2790249197
用户头像
Edviv
用户头像
上官莲
用户头像
risufanple
用户头像
潘总
用户头像
我要出去乱说
用户头像
ZJZF
用户头像
三元十碗糯米饭

活动打卡代码 AcWing 2060. 奶牛选美

#include <iostream>
#include <cstring>
#include <queue>
#include <deque>

using namespace std;

const int N = 60;
char g[N][N];
int st[N][N], idx = 1;
int dist[N][N];
typedef pair<int, int> PII;
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
#define x first
#define y second

int main()
{
    int n, m;
    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 (!st[i][j] && g[i][j] == 'X')
            {
                queue<PII> q;
                q.push({ i, j });

                while (q.size())
                {
                    auto t = q.front(); q.pop();
                    st[t.x][t.y] = idx;
                    for (int k = 0; k < 4; k++)
                    {
                        int a = t.x + dx[k], b = t.y + dy[k];
                        if (a >= 0 && a <= n && b >= 0 && b <= m)
                        {
                            if (g[a][b] == 'X' && !st[a][b])
                            {
                                st[a][b] = idx;
                                q.push({ a, b });
                            }
                        }
                    }
                }
                idx++;
            }
        }
    }
    int sx, sy, ex, ey;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (st[i][j] == 1)sx = i, sy = j;
            else if (st[i][j] == 2) ex = i, ey = j;
        }
    }
    deque<PII> q;
    q.push_back({ sx, sy });
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[sx][sy] = 0;
    while (q.size())
    {
        auto t = q.front(); q.pop_front();
        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        if (t.x == ex && t.y == ey)break;

        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a >= 0 && a <= n && b >= 0 && b <= m )
            {
                int w = 0;
                if (g[a][b] == '.')w = 1;
                if (dist[a][b] > dist[t.x][t.y] + w)
                {
                    dist[a][b] = dist[t.x][t.y] + w;
                    if (w) q.push_back({ a, b });
                    else q.push_front({ a, b });
                }
            }
        }
    }
    cout << dist[ex][ey];
    return 0;
}



题目链接 奶牛选美

错误的代码:
似乎是最短路部分有问题

#include <iostream>
#include <cstring>
#include <queue>
#include <deque>

using namespace std;

const int N = 60;
char g[N][N];
int st[N][N], idx = 1;
int dist[N][N];
typedef pair<int, int> PII;
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
#define x first
#define y second

int main()
{
    int n, m;
    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 (!st[i][j] && g[i][j] == 'X')
            {
                queue<PII> q;
                q.push({ i, j });

                while (q.size())
                {
                    auto t = q.front(); q.pop();
                    st[t.x][t.y] = idx;
                    for (int k = 0; k < 4; k++)
                    {
                        int a = t.x + dx[k], b = t.y + dy[k];
                        if (a >= 0 && a <= n && b >= 0 && b <= m)
                        {
                            if (g[a][b] == 'X' && !st[a][b])
                            {
                                st[a][b] = idx;
                                q.push({ a, b });
                            }
                        }
                    }
                }
                idx++;
            }
        }
    }
    int sx, sy, ex, ey;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (st[i][j] == 1)sx = i, sy = j;
            else if (st[i][j] == 2) ex = i, ey = j;
        }
    }
    deque<PII> q;
    q.push_back({ sx, sy });
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[sx][sy] = 0;
    while (q.size())
    {
        auto t = q.front(); q.pop_front();
        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        if (t.x == ex && t.y == ey)break;

        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a >= 0 && a <= n && b >= 0 && b <= m )
            {
                int w = 0;
                if (g[a][b] == '.')w = 1;
                if (dist[a][b] > dist[t.x][t.y] + w)
                {
                    dist[a][b] = dist[t.x][t.y] + w;
                    if (w) q.push_back({ a, b });
                    else q.push_front({ a, b });
                }
            }
        }
    }
    cout << dist[ex][ey];
    return 0;
}


活动打卡代码 AcWing 2019. 拖拉机

#include <iostream>
#include <deque>
#include <cstring>

using namespace std;

const int N = 1010;

bool g[N][N], st[N][N];
int dist[N][N];

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

typedef pair<int, int> PII;
deque<PII> q;

int main()
{
    int n, sx, sy;
    cin >> n >> sx >> sy;
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x][y] = true;
    }
    memset(dist, 0x3f, sizeof dist);
    q.push_back({ sx, sy });
    dist[sx][sy] = 0;
    while (q.size())
    {
        auto t = q.front(); q.pop_front();
        if (st[t.first][t.second])continue;
        st[t.first][t.second] = true;
        if (t.first == 0 && t.second == 0) break;
        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 < N)
            {

                if (dist[x][y] > dist[t.first][t.second] + g[x][y])
                {
                    dist[x][y] = dist[t.first][t.second] + g[x][y];
                    if (g[x][y])q.push_back({ x,y });
                    else q.push_front({ x,y });
                }
            }
        }
    }
    cout << dist[0][0];
    return 0;
}


活动打卡代码 AcWing 2014. 岛

#include <iostream>
#include <cstring>
#include <queue>
#include <deque>

using namespace std;

const int N = 60;
char g[N][N];
int st[N][N], idx = 1;
int dist[N][N];
typedef pair<int, int> PII;
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
#define x first
#define y second

int main()
{
    int n, m;
    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 (!st[i][j] && g[i][j] == 'X')
            {
                queue<PII> q;
                q.push({ i, j });

                while (q.size())
                {
                    auto t = q.front(); q.pop();
                    st[t.x][t.y] = idx;
                    for (int k = 0; k < 4; k++)
                    {
                        int a = t.x + dx[k], b = t.y + dy[k];
                        if (a >= 0 && a <= n && b >= 0 && b <= m)
                        {
                            if (g[a][b] == 'X' && !st[a][b])
                            {
                                st[a][b] = idx;
                                q.push({ a, b });
                            }  
                        }
                    }
                }
                idx++;
            }
        }
    }
    int sx, sy, ex, ey;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (st[i][j] == 1)sx = i, sy = j;
            else if (st[i][j] == 2) ex = i, ey = j;
        }
    }
    deque<PII> q;
    q.push_back({ sx, sy });
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[sx][sy] = 0;
    while (q.size())
    {
        auto t = q.front(); q.pop_front();
        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        if (t.x == ex && t.y == ey)break;

        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m)
            {
                int w = 0;
                if (g[a][b] == '.')w = 1;
                if (dist[a][b] > dist[t.x][t.y] + w)
                {
                    dist[a][b] = dist[t.x][t.y] + w;
                    if (w) q.push_back({ a, b });
                    else q.push_front({ a, b });
                }
            }
        }
    }
    cout << dist[ex][ey];
    return 0;
}


活动打卡代码 AcWing 2005. 马蹄铁

#include <iostream>
#include <cstdio>

using namespace std;

char borad[10][10];
bool st[10][10];
int ans, n;

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

void dfs(int x,int y,int l, int r)
{
    st[x][y] = true;
    if (l == r)
    {
        ans = max(ans , l + r);
        st[x][y] = false;
        return;
    }
    for (int i = 0 ; i < 4; i ++)
    {
        int a = x + dx[i] ,b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < n && !st[a][b])
        {
            if (borad[x][y] == ')' && borad[a][b] == '(')continue;
            if (borad[a][b] == '(')dfs(a, b, l + 1, r);
            else dfs(a, b, l , r + 1);
        }

    }
    st[x][y] = false;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        cin >> borad[i];
    }
    if (borad[0][0] == '(')dfs(0, 0, 1, 0);
    cout << ans;

    return 0;
}


活动打卡代码 AcWing 2041. 干草堆

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

using namespace std;

int f[int(1e6 + 1)];

int main()
{
    int n,k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        f[a] ++;
        f[b + 1] --;
    }
    for (int i = 1; i <= n; i ++)
    {
        f[i] += f[i - 1];
    }
    nth_element(f + 1, f + n / 2 + 1, f + n + 1);
    printf("%d", f[n / 2 + 1]);
    return 0;
}


活动打卡代码 AcWing 2058. 笨拙的手指

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

inline int change(int model, string in)
{
    int res = 0;
    if (model == 2)
    {
        for (auto x : in)
        {
            res = res * 2 + x - '0';
        }
    }
    else if (model == 3)
    {
        for (auto x : in)
        {
            res = res * 3 + x - '0';
        }

    }
    return res;
}

int main()
{
    unordered_map<int, int> mp;
    string str1, str2;
    cin >> str1 >> str2;
    string str3;
    str3 = str1;
    for (int i = 0; i < str1.size(); i++)
    {
        if (str3[i] == '1')
        {
            str3[i] = '0';
            mp[change(2, str3)] ++;
            str3[i] = '1';
        }
        else
        {
            str3[i] = '1';
            mp[change(2, str3)] ++;
            str3[i] = '0';
        }
    }
    str3 = str2;
    for (int i = 0; i < str2.size(); i++)
    {
        if (str3[i] == '0')
        {
            str3[i] = '1';
            mp[change(3, str3)] ++;
            str3[i] = '2';
            mp[change(3, str3)] ++;
            str3[i] = '0';
        }
        else if (str3[i] == '1')
        {
            str3[i] = '2';
            mp[change(3, str3)] ++;
            str3[i] = '0';
            mp[change(3, str3)] ++;
            str3[i] = '1';
        }
        else
        {
            str3[i] = '1';
            mp[change(3, str3)] ++;
            str3[i] = '0';
            mp[change(3, str3)] ++;
            str3[i] = '2';
        }
    }
    for (auto x : mp)
    {
        if (x.second == 2)
        {
            cout << x.first;
            break;
        }
    }
    return 0;
}


活动打卡代码 AcWing 1996. 打乱字母

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    vector<string> start, low, high;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        string tmp;
        cin >> tmp;
        sort(tmp.begin(), tmp.end());
        start.push_back(tmp);
        low.push_back(tmp);
        reverse(tmp.begin(), tmp.end());
        high.push_back(tmp);
    }
    sort(high.begin(), high.end(), less());
    sort(low.begin(), low.end(), less());
    for (auto& x : start)
    {
        int a = lower_bound(high.begin(), high.end(), x) - high.begin() + 1;
        reverse(x.begin(), x.end());
        int b = upper_bound(low.begin(), low.end(), x) - low.begin();
        cout << a << ' ' << b << endl;
    }
    return 0;
}


新鲜事 原文

王俊吉
11天前
AcWing《寒假每日一题2022》拼团优惠!https://www.acwing.com/activity/content/introduction/88/group_buy/40899/


活动打卡代码 AcWing 1128. 信使

王俊吉
2个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

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

int h[N], ne[N], e[N], w[N], idx;
int dist[N];
bool st[N];

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

void dijkstra(int u)
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, u});
    dist[u] = 0;
    while (heap.size())
    {
        int id = heap.top().second;
        heap.pop();
        if (st[id] == true)continue;
        st[id] = true;
        for (int i = h[id]; ~i ; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[id] + w[i])
            {
                dist[j] = dist[id] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    memset(h, -1 , sizeof h);

    for (int i = 1; i <= m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    dijkstra(1);
    int ans = -1e9;
    for (int i = 2 ; i <= n ; i ++)
    {
        ans = max(ans, dist[i]);
    }
    if (ans == 0x3f3f3f3f)printf("-1");
    else printf("%d", ans);
    return 0;
}