头像

ChaseAug_0




离线:5小时前



ChaseAug_0
6小时前
#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;//res记录最小生成树的树边权重之和,cnt记录的是全部加入到树的集合中边的数量(可能有多个集合)
    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)
        {
            /*
        具体可以参考连通块中点的数量,如果a和b已经在一个集合当中了,说明这两个点已经被一种方式连接起来了,
        如果加入a-b这条边,会导致集合中有环的生成,而树中不允许有环生成,所以一个连通块中的点的数量假设
        为x,那么里面x个节点应该是被串联起来的,有x-1条边,所以只有当a,b所属的集合不同时,才能将a-b这条
        边加入到总集合当中去
        */
            p[a] = b;//将a,b所在的两个集合连接起来
            res += w;//加入到集合中的边的权重之和
            cnt ++;//因为加入的是a-b的这一条边,将a,b所在的两个集合连接之后,全部集合中的边数加1
        }
    }
    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;
}


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

ChaseAug_0
15小时前
全称字符串前缀哈希法,把字符串变成一个p进制数字(哈希值),实现不同的字符串映射到不同的数字。
对形如 X1X2X3⋯Xn−1XnX1X2X3⋯Xn−1Xn 的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值。

映射公式 (X1×Pn−1+X2×Pn−2+⋯+Xn−1×P1+Xn×P0)modQ(X1×Pn−1+X2×Pn−2+⋯+Xn−1×P1+Xn×P0)modQ
注意点:
1. 任意字符不可以映射成0,否则会出现不同的字符串都映射成0的情况,比如A,AA,AAA皆为0
2. 冲突问题:通过巧妙设置P (131 或 13331) , Q (264)(264)的值,一般可以理解为不产生冲突。

问题是比较不同区间的子串是否相同,就转化为对应的哈希值是否相同。
求一个字符串的哈希值就相当于求前缀和,求一个字符串的子串哈希值就相当于求部分和。

前缀和公式 h[i+1]=h[i]×P+s[i]h[i+1]=h[i]×P+s[i] i∈[0,n−1]i∈[0,n−1] h为前缀和数组,s为字符串数组
区间和公式 h[l,r]=h[r]−h[l−1]×Pr−l+1h[l,r]=h[r]−h[l−1]×Pr−l+1
区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样,只差两位,
乘上P的二次方把 ABC 变为 ABC00,再用 ABCDE - ABC00 得到 DE 的哈希值。


#include<iostream>
using namespace std;

typedef unsigned long long ULL;//由于前缀值的值会很大 所以应该将数组中的数据定义为ULL型
const int N = 100010, P = 131; //P为权重
                               //131为经验值 即P=131或13331时 哈希冲突的可能性最小

int n,m;
char str[N];
ULL h[N],p[N];//h[]存放字符串的前缀值
              //p[]存放各个位数的相应权值

ULL get(int l,int r)
{
    return h[r] - h[l-1] * p[r - l + 1]; //这步其实是将h[l-1]左移
                                        //其目的事实上是为了将h[l-1]的高位与h[r]相对齐从而才可以完成计算
}
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;           //计算每个位上的相应权值
    }

    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 840. 模拟散列表

ChaseAug_0
17小时前
//开放寻址法
#include<cstring>
#include<iostream>
using namespace std;

const  int N = 200003,null = 0x3f3f3f3f;
int h[N];

int find(int x)
{
    int k = (x%N+N) % N;
    while(h[k]!= null && h[k] != x)
    {
        k ++;
        if(k == N) k = 0;
    }
    return k;
}
int main()
{
    memset(h,0x3f,sizeof h);
    int n;
    scanf("%d",&n);

    while(n --)
    {
        char op[2];
        int x;
        scanf("%s%d",op,&x);

        int k = find(x);
        if(op[0] == 'I') h[k] = x;
        else
        {
            if(h[k] == null) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

//拉链法
#include<iostream>
#include<cstring>
using namespace std;

const int N = 100003;
int h[N],e[N],ne[N],idx;//h[]是哈希函数的一维数组//e[]是链表中存的值//ne[]是指针存的指向的地址//idx是当前指针

void insert(int x)
{
    int k = (x % N + N) % N; //为了让负数在整数有映射,负数的取模还是负数,加上maxn后为正,再%即可
    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;
    scanf("%d",&n);

    memset(h,-1,sizeof h);//所有槽都清空,对应的是单链表的头(head)[注:head存的是地址,详见单链表的课]指针为-1

    while(n --)
    {
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(op[0] == 'I') insert(x);
        else
        {
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}


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

这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
从而我们需要对应到原先第K个堆中元素
如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换
h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响

#include<iostream>
using namespace std;

const int N = 100010;
int n;
int h[N],ph[N],hp[N],cnt;//ph存放第k个插入点得下标
//hp存放堆中插入点的插入次序

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

    if(t != u) 
    {
        heap_swap(u,t);
        down(t);
    }
}
void up(int u)
{
    if(u/2 && h[u/2] > h[u])
    {
        heap_swap(u,u/2);
        up(u/2);
    }
}
int main()
{
    cin >> n;
    int m = 0;
    while(n --)
    {
        string op;
        cin >> op;
        int k,x;
        if(op == "I")
        {
            cin >> x;
            m ++;
            h[++ cnt] = x;
            ph[m] = cnt;
            hp[cnt] = m;
            up(cnt);
            //down(cnt);
        }
        else if(op == "PM") cout << h[1] << endl;
        else if(op == "DM")
        {
            heap_swap(1,cnt);
            cnt --;
            down(1);
        }
        else if(op == "D")
        {
            cin >> k;
            int u = ph[k];
            heap_swap(u,cnt);
            cnt --;
            up(u);
            down(u);
        }
        else
        {
            cin >> k >> x;
            int u = ph[k];
            h[u] = x;
            down(u);
            up(u);
        }
    }
    return 0;
}


活动打卡代码 AcWing 838. 堆排序

分析

i为什么从n/2开始down?

首先要明确要进行down操作时必须满足左儿子和右儿子已经是个堆。

开始创建堆的时候,元素是随机插入的,所以不能从根节点开始down,而是要找到满足下面三个性质的结点:

1.左右儿子满足堆的性质。

2.下标最大(因为要往上遍历)

3.不是叶结点(叶节点一定满足堆的性质)

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
int n,m,cnt;
int h[N];

void down(int u) 
{
    int t = u;
    if(2*u <= cnt && h[2*u] < h[t]) t = 2*u;
    if(2*u + 1 <= cnt && h[2*u+1] < h[t]) t = 2*u+1;
    if(u != t)
    {
        swap(h[u],h[t]);
        down(t);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i ++) scanf("%d",&h[i]);
    cnt = n;

    for(int i = n/2 ;i ;i --) down(i); //i = n也能AC
    while(m --)
    {
        cout << h[1] << ' ';
        h[1] = h[cnt];
        cnt --;
        down(1);
    }
    return 0;
}


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

距离的含义
x吃y表示y到x的距离为1. y是第0代,吃y的x是第1代,吃x的是第2代…根节点是第0代
三种关系:用点到根节点之间的距离表示其余根节点之间的关系
mod 3 = 1:可以吃根节点
mod 3 = 2:可以被根节点吃
mod 3 = 0:和根节点同类
把集合中所有的点划分为上述三类。

#include<iostream>
using namespace std;

const int N = 100010;
int n,k;
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;//x节点也压缩到树根
    }
    return p[x];
}
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) p[i] = i;

    int res = 0;
    while(k --)
    {
        int t,x,y;
        cin >> t >> x >> y;
        if(x > n || y > n) res ++;
        else
        {
            int px = find(x),py = find(y);//分别表示x集合和y集合的祖总结点
            if(t == 1)
            {
                //假话
                if(px == py && (d[x] - d[y])%3 ) res ++; // d[i] 是到父亲结点的距离
                //真话
                else if(px != py)
                {
                    p[px] = py;//当前不在同一集合中,无法判定为假。故为真,应加入同一集合表示存在同类关系
                    d[px] = d[y] - d[x];//(d[x]+d[rx]-d[y])%3 = 0,由于判断时都针对mod 3,故3可省略
                }
            }
            else  // x吃y
            {
                if(px == py && (d[x] - d[y] - 1)%3) res ++; //C++中负数取模得非正数,需要注意别写错
                else if(px != py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }

    }
    cout << res << endl;

    return 0;
}



#include<iostream>
using namespace std;

int p[100010],n,m;
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int size[100010];
    cin >> n >> m;
    for(int i = 0; i < n ; i++)
    {
        p[i] = i;
        size[i] = 1;
    }
    while(m --)
    {
        char op[2];
        int a,b;
        cin >> op;
        if(op[0] == 'C')
        {
            cin >> a >> b;
            if(find(a) == find(b)) continue;
            size[find(b)] += size[find(a)];
            p[find(a)] = find(b);
        }
        else if(op[1] == '1')
        {
            cin >> a >> b;
            if(find(a) == find(b)) cout << "Yes" <<endl;
            else cout << "No" <<endl;
        }
        else 
        {
            cin >> a;
            cout << size[find(a)] << endl;
        }
    }
    return 0;
}



模运算法则

  1. (a + b) % p = (a % p + b % p) % p
  2. (a - b) % p = (a % p - b % p) % p
  3. (a * b) % p = (a % p * b % p) % p
  4. (a^b) % p = ((a % p)^b) % p


活动打卡代码 AcWing 104. 货仓选址

与中位数的差之和

#include<iostream>
#include<algorithm>
using namespace std;

int n,A[100010],res;
int main()
{
    cin >> n;
    for(int i = 0 ;i < n ;i ++) cin >> A[i];
    sort(A,A+n);

    int x = A[n/2];
    for(int i = 0;i < n;i ++)
    {
        res += abs(A[i] - x);
    }
    cout << res << endl;
    return 0;
}

利用不等式的性质
∑i=0n−1|ai−an2|=∑i=0n−1ai−ai2

#include<iostream>
#include<algorithm>
using namespace std;

int n,A[100010],res;
int main()
{
    cin >> n;
    for(int i = 0 ;i < n ;i ++) cin >> A[i];
    sort(A,A+n);

    for(int i = 0;i < n;i ++)
    {
        res += abs(A[i] - A[n/2]);//res += abs(A[i] - A[i/2]);
    }
    cout << res << endl;
    return 0;
}


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

ChaseAug_0
1个月前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010,M = 3100010;  
int n;
int a[N],s[M][2],idx;
//M代表一个数字串二进制可以到多长

void insert(int x)
{
    int p = 0; //根节点
    for(int i = 30 ; ~i; i --)
    {
        int u = x >> i & 1; // x的第i位二进制数
        int &q = s[p][u];
        if(!q) q = ++ idx; // 若没有不存在子节点,则创建一个子节点
        p = q; //指针指向下一层
    }
}

int query(int x)
{
    int p = 0,res = 0;
    for(int i = 30 ; ~i; i --)
    {
        int q = x >> i & 1;
        if(s[p][!q]) 
        {
            res += 1 << i;
            p = s[p][!q];
        }
        else p = s[p][q];
    }
    return res;
}
int main()
{
    cin.tie(0);
    cin >> n;
    for(int i = 0 ;i < n ; i++)
    {
        cin >> a[i];
        insert(a[i]);
    }
    int res = 0;
    for(int i = 0 ; i < n; i ++) res = max(res,query(a[i]));
    cout << res << endl;

    return 0;
}