头像

Jesus

无组织!无纪律!




离线:5小时前


最近来访(18)
用户头像
im0use
用户头像
torus
用户头像
一个人的巴黎
用户头像
ふぇありぃあい
用户头像
wuli.遇
用户头像
傻瓜_4
用户头像
意难平_6
用户头像
csr
用户头像
11111151
用户头像
阿杰-


Jesus
22小时前


活动打卡代码 AcWing 841. 字符串哈希

Jesus
1天前

2.png
1.png

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];
ULL Q = (ULL)1 << 63 ; //  2的64次方

ULL get(int l, int r)
{
    return (h[r] - h[l - 1] * p[r - l + 1]) % Q; // 可以不取余Q,返回值类型是ULL就行
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * P + str[i]; //看图片公式
        p[i] = p[i - 1] * P;  //保存下P对应所有次方的数,方便下标直接使用
    }

    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;
}



活动打卡代码 AcWing 839. 模拟堆

Jesus
2天前
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt ++ ;
            m ++ ;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt -- ;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }

    return 0;
}




活动打卡代码 AcWing 143. 最大异或对

Jesus
5天前
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010, M = 31 * N + 10;

int n;
int a[N], son[M][2], idx;

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 () {
    cin >> 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);
    }

    cout << res;
    return 0;
}


活动打卡代码 AcWing 240. 食物链

Jesus
5天前

/* 
(d[x] - d[y]) % 3  (由于有负数的可能直接d[x]和d[y]分别取余结果是不正确的,这里需要使用取模)
就用第一种同类举例 d [ x ] + ? = d [ y ] ,d [ y ] 就和 d [ x ] 是同类
当 d [ x ] = -1 ,d [ y ] = 2 时 x,y是同类
但是 -1 % 3 != 2 % 3

C/C++和java %是取余   python是取模

例1.计算:-7 Mod 4
那么:a = -7;b = 4;
第一步:求整数商c:
①进行求模运算c = [a/b] = -7 / 4 = -2(向负无穷方向舍入),
②进行求余运算c = [a/b] = -7 / 4 = -1(向0方向舍入);
第二步:计算模和余数的公式相同,但因c的值不同,
①求模时:r = a - c*b =-7 - (-2)*4 = 1,
②求余时:r = a - c*b = -7 - (-1)*4 =-3。
*/

#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N];

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

    }
    return p[x];
}

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

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

    int res = 0;
    while (m -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        if (x > n || y > n) res ++ ;
        else
        {
            int px = find(x), py = find(y);
            if (t == 1)
            {
                if (px == py && (d[x] - d[y]) % 3) res ++ ;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;
}





Jesus
5天前
#include <iostream>
#include <cstdio>


using namespace std;
const int N = 1e5 + 10;
int p[N], cnt[N]; //size变量名会冲突


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




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

    for (int i = 0; i < n; i++) {
        p[i] = i;
        cnt[i] = 1;
    }

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

        if (op == "C")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b)
            {
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }

    }

    return 0;
}



Jesus
2个月前

https://mp.weixin.qq.com/s?__biz=MjM5NTY1MjY0MQ==&mid=2650853887&idx=4&sn=8bc8a0ae10131ed7ba8c9b6d71a83ed4&chksm=bd0144b18a76cda77f904b23a05818ea3db6ac58910eca05e8d844bef7e9b44e119281cbb8b9&mpshare=1&scene=23&srcid=06111rCJYTgEAZJQjMjqX0TY&sharer_sharetime=1654940817042&sharer_shareid=21b047d30a12b4dea3199d43fe677347#rd

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

using namespace std;

const int N = 100010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

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

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

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

    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }

    int t = kruskal();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}




Jesus
2个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[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], g[t][j]);
    }

    return res;
}


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

    memset(g, 0x3f, sizeof g);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}



活动打卡代码 AcWing 854. Floyd求最短路

Jesus
2个月前
#include <iostream>
#include <cstdio>

using namespace std;
const int N = 210;


int INF = 1E9, n, m, q;
int dis[N][N];

int Floyd() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) {
                dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
            }
}

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j) dis[i][j] = 0;
            else dis[i][j] = INF;

    while (m--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        dis[a][b] = min(dis[a][b], c);
    }

    Floyd();

    while (q--) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (dis[a][b] > INF / 2) cout << "impossible" << endl;
        else cout << dis[a][b] << endl;
    }


    return 0;
}


活动打卡代码 AcWing 852. spfa判断负环

Jesus
2个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], w[N], idx;
int n, m;
int dis[N], st[N], cnt[N];

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

int spfa() {
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    queue<int> q;
    for (int i = 1; i <= n; i++) q.push(i); 

    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dis[j] > dis[t] + w[i]) {
                dis[j] = dis[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof(h));

    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
    }

    if (spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;


    return 0;
}