头像

Mhbfy

洛阳单身程序猿基地




离线:1天前


最近来访(123)
用户头像
bline
用户头像
eric_f
用户头像
候默
用户头像
正能量的阿龙
用户头像
天天_13
用户头像
龙_12
用户头像
Txoon
用户头像
不拿牌牌不改名
用户头像
no_one
用户头像
incra
用户头像
ζ..懒灬猫①
用户头像
笨蛋1
用户头像
拉着飞仔
用户头像
江畔寻花
用户头像
2010
用户头像
垫底抽風
用户头像
谷谷
用户头像
史一帆
用户头像
cht
用户头像
雪王啦啦啦啦

活动打卡代码 AcWing 1144. 连接格点

Mhbfy
1天前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = N * N, K = 2 * N * N;

int n, m, k;
int ids[N][N];
struct Edge
{
    int a, b, w;
}e[K];
int p[M];

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

void get_edges()
{
    int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 }, dw[4] = { 1, 2, 1, 2 };

    for (int z = 0; z < 2; z++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                for (int u = 0; u < 4; u++)
                    if (u % 2 == z)
                    {
                        int x = i + dx[u], y = j + dy[u], w = dw[u];
                        if (x && x <= n && y && y <= m)
                        {
                            int a = ids[i][j], b = ids[x][y];
                            if (a < b) e[k++] = { a, b, w };
                        }
                    }
}

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

    for (int i = 1, t = 1; i <= n; i++)
        for (int j = 1; j <= m; j++, t++)
            ids[i][j] = t;

    for (int i = 1; i <= n * m; i++) p[i] = i;

    int x1, y1, x2, y2;
    while (cin >> x1 >> y1 >> x2 >> y2)
    {
        int a = ids[x1][y1], b = ids[x2][y2];
        p[find(a)] = find(b);
    }

    get_edges();

    int res = 0;
    for (int i = 0; i < k; i++)
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if (a != b)
        {
            p[a] = b;
            res += w;
        }
    }

    cout << res << endl;

    return 0;
}



活动打卡代码 AcWing 1134. 最短路计数

Mhbfy
2天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1e5 + 10, M = 4e5 + 10, mod = 100003;

int n, m;
int e[M], ne[M], idx, h[N];
int dist[N], cnt[N];

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

void bfs()
{
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    cnt[1] = 1;

    q.push(1);

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + 1)
            {
                dist[j] = dist[t] + 1;
                cnt[j] = cnt[t];
                q.push(j);
            }
            else if (dist[j] == dist[t] + 1)
                cnt[j] = (cnt[j] + cnt[t]) % mod;
        }
    }
}

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

    memset(h, -1, sizeof h);

    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;

        add(a, b), add(b, a);
    }

    bfs();

    for (int i = 1; i <= n; i++)
        cout << cnt[i] << endl;

    return 0;
}



Mhbfy
3天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>

using namespace std;

const int N = 1e5 + 10, M = 2e6 + 10;

typedef long long LL;

int n, m, mod;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int scc_cnt, Size[N], id[N];
int f[N], g[N];

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

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        int y;
        scc_cnt++;

        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt]++;
        } while (y != u);
    }
}

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

    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);

    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;

        add(h, a, b);
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);

    unordered_set<LL> S;

    for(int i=1;i<=n;i++)
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            LL hash = a * 1000000ll + b;

            if (a != b&&!S.count(hash))
            {
                add(hs, a, b);
                S.insert(hash);
            }
        }

    for (int i = scc_cnt; i; i--)
    {
        if (!f[i])
        {
            f[i] = Size[i];
            g[i] = 1;
        }
        for (int j = hs[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            if (f[k] < f[i] + Size[k])
            {
                f[k] = f[i] + Size[k];
                g[k] = g[i];
            }
            else if (f[k] == f[i] + Size[k])
                g[k] = (g[k] + g[i]) % mod;
        }
    }

    int maxf = 0, sum = 0;
    for (int i = 1; i <= scc_cnt; i++)
        if (f[i] > maxf)
        {
            maxf = f[i];
            sum = g[i];
        }
        else if (f[i] == maxf) sum = (sum + g[i]) % mod;

    cout << maxf << endl;
    cout << sum << endl;

    return 0;
}


活动打卡代码 AcWing 831. KMP字符串

Mhbfy
22天前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int ne[N];
char s[M], p[N];
int n, m;

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}


活动打卡代码 AcWing 367. 学校网络

Mhbfy
1个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;

int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt;
int din[N], dout[N];

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

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++scc_cnt;
        int y;
        do {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
        } while (y != u);
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++)
    {
        int t;
        while (cin >> t, t) add(i, t);
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);

    for (int i = 1; i <= n; i++)
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b)
            {
                dout[a] ++;
                din[b] ++;
            }
        }

    int a = 0, b = 0;
    for (int i = 1; i <= scc_cnt; i++)
    {
        if (!din[i]) a++;
        if (!dout[i]) b++;
    }

    printf("%d\n", a);
    if (scc_cnt == 1) puts("0");
    else printf("%d\n", max(a, b));

    return 0;
}



活动打卡代码 AcWing 1174. 受欢迎的牛

Mhbfy
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10, M = 5e5 + 10;

int n, m;
int stk[N], top;
int e[M], ne[M], h[N], idx;
int dfn[N], low[N], timestamp;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N];

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

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt]++;
        } while (y != u);
    }
}

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

    memset(h, -1, sizeof h);

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

        add(a, b);
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);

    for(int i=1;i<=n;i++)
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) dout[a]++;
        }

    int zeros = 0, sum = 0;
    for(int i=1;i<=scc_cnt;i++)
        if (!dout[i])
        {
            zeros++;
            sum += Size[i];
            if (zeros > 1)
            {
                sum = 0;
                break;
            }
        }

    cout << sum << endl;

    return 0;
}


活动打卡代码 AcWing 840. 模拟散列表

Mhbfy
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 3;

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

void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;

    return false;
}

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

    memset(h, -1, sizeof h);

    while (n--)
    {
        char op[2];
        int x;

        scanf("%s%d", op, &x);

        if (*op == 'I') insert(x);
        else
        {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}


活动打卡代码 AcWing 893. 集合-Nim游戏

Mhbfy
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int s[N], f[N];

int sg(int x)
{
    if (f[x] != 1) return f[x];

    unordered_set<int> S;

    for (int i = 0; i < m && s[i] <= x; i++)
        S.insert(sg(x - s[i]));

    for (int i = 0;; i++)
        if (!S.count(i))
            return f[x] = i;
}

int main()
{
    while (cin >> m, m)
    {
        for (int i = 0; i < m; i++) cin >> s[i];

        sort(s, s + m);

        int k;
        cin >> k;

        while (k--)
        {
            memset(f, -1, sizeof f);

            int res = 0;
            cin >> n;

            for (int i = 0; i < n; i++)
            {
                int x;
                cin >> x;

                res ^= sg(x);
            }

            if (res) cout << "W";
            else cout << "L";
        }

        cout << endl;
    }

    return 0;
}



Mhbfy
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e3 + 10, INF = 0x3f3f3f3f;

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

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;
        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    return res;
}

int main()
{
    memset(g, 0, sizeof g);

    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;

        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;
}


活动打卡代码 AcWing 3596. a+b

Mhbfy
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1e5 + 10;

vector<int> state;

vector<int>add(vector<int>& A, vector<int>& B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;

    for (int i = 0; i < A.size(); i++)
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

int main()
{
    string a, b;
    while (cin >> a >> b)
    {
        vector<int> A, B;
        for (int i = a.size()-1; i >= 0; i--) A.push_back(a[i] - '0');
        for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

        auto C = add(A, B);

        for (int i = C.size() - 1; i >= 0; i--) cout << C[i];

        cout << endl;
    }
    return 0;

}