头像

xyzzyx


访客:906

离线:11小时前


活动打卡代码 AcWing 846. 树的重心

xyzzyx
12小时前

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

const int N = 100010,M=2*N;

int n;
int h[N],e[M],ne[M]; /// 链表的头结点 结点 下一个结点索引
int idx=0;
bool st[N];
int ans=N;

//// 将b 插入到以a为表头的链表中
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
};

/// 树的深度优先遍历框架
int dfs(int u)       //dfs过程寻找根的连通的点
{
   int size=0;    //存放连通块中点的个数的最大值
   st[u]=true;  //  该点已经走过
   int sum=0;       //sum用于记录根子树的个数
   for(int i=h[u];i!=-1;i=ne[i])
   {
       int j=e[i];
       if(!st[j])
       { 
            int s=dfs(j); /// 子树的联通分量个数
            size=max(size,s); 
            sum+=s;
       }
   }
   size=max(size,n-sum-1);  // 在树中 除了该结点和其子树所组成的结点以外的结点个数 求最大值
   ans=min(ans,size); // 将这些最大值求个最小值
   return sum+1;        //return sum+1 是因为sum初始化为0 而当前这个点即根也算是该连通块内的一点
}


int main(){

    memset(h,-1,sizeof(h));
    scanf("%d",&n);

    int a,b;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        add(a,b); /// 添加双向边
        add(b,a);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}













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

xyzzyx
4天前

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int p = 131; /// 码值
typedef unsigned long long ULL; /// 用这个类型存储相当于将结果mod 2的64次方
int h[N],P[N];

int n,m;

ULL gethash(int l,int r){ /// 哈希函数 
    return h[r]-h[l-1]*P[r-l+1];
};

char str[N];
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(gethash(l1,r1)==gethash(l2,r2)){
            puts("Yes");
        }else{
            puts("No");
        }
    }
    return 0;
}




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

xyzzyx
4天前

拉链法寻址: 将大范围的数通过哈希函数映射到小范围的区间中
解决哈希冲突: 将元素插入到 结果链表 的头结点
实际上就是单链表的操作 只不过头结点也是由数组维护的 相当于有很多的单链表


#include<iostream>
#include<cstring>

using namespace std;

const int N = 100003; ///质数
int h[N],e[N],ne[N];
int n,idx;

void insert(int x){
    int k = ((x%N)+N)%N; // 哈希函数
    //// 将元素插入到链表头
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx;
    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(){

    memset(h,-1,sizeof(h));
    scanf("%d",&n);

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


开放寻址法
通过哈希函数查找元素的位置 如果没有找到 则移动到下一个坑位
如果坑位里面没有元素 则返回这个坑位的索引 否则继续移动到下一个坑位
就像是模拟人上厕所的过程


#include<iostream>
#include<cstring>

using namespace std;

const int N = 200003; ///质数
int h[N];
int n;
int count =0; //指循环的次数 如果查找了一圈都没有找到 通过这个计数器来跳出循环 否则会死循环

int  find(int x){ // 查找x应该存放的坑位
    int k = ((x%N)+N)%N;
    while(h[k]!=x && h[k]!= 0x3f3f3f3f && (count<2)){
        k++;
        if(k==N){
            k=0;
            count++;
        }
    }
    return k;
};


int main(){

    memset(h, 0x3f3f3f3f,sizeof(h)); // 初始化的时候 里面的元素无穷大
    scanf("%d",&n);

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

       int k = find(x);
       if(*op=='I'){
           h[k]=x; // 插入就是直接赋值
       }else{
           if(h[k]!= 0x3f3f3f3f){
               printf("Yes\n");
           }else{
               printf("No\n");
           }
       }
    }
    return 0;
}



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

xyzzyx
4天前
/**
  在并查集里面 根据距离 根结点的高度 划分成3种区域
  天敌域 捕食域 同类域 这些结点分别与跟结点的距离取模
  得到的余数是 1 2 0

**/


#include<iostream>
using namespace std;
const int N = 50010;

int p[N],d[N]; /// 父节点/到父节点的距离
int n,k;

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,&k);

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

    int res =0;
    while(k--){

        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);

        if(x>n || y>n){
            res++;
        }else{
            int px = find(x);
            int py = find(y);
            if(t==1){
                if(px==py){ //// 如果在同一个并查集里面
                    int dx = d[x];
                    int dy = d[y];
                    if((dx-dy)%3!=0){ //// 不是同类 说明这句话是假的
                        res+=1;
                    }
                }else{
                    p[px]=py; //不同的并查集里面
                    d[px]=d[y]-d[x]; /// 使得这句话成立的条件
                }
            }else{
                if(px==py){
                    int dx = d[x];
                    int dy = d[y];
                    if((dx-dy-1)%3!=0){
                        res+=1;
                    }
                }else{
                    p[px]=py;
                    d[px]=d[y]+1-d[x];
                }
            }
        }
    }

    printf("%d",res);
    return 0;
}




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

xyzzyx
5天前

#include<iostream>
using namespace std;
const int N = 100010, M = 1000010;

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

int n,m;
int main(){

    cin>>n>>(p+1);
    cin>>m>>(s+1);

    ///寻找ne的过程
    //// ne[j]是以j为终点的线段 前缀线段和后缀线段完全相等的最大的长度
    //// 这个过程只与p字串有关

    for(int i=2,j=0;i<=n;i++){
        while(j && p[i]!=p[j+1]){
            j=ne[j]; /// j向前移动的最小步伐
        }

        if(p[i]==p[j+1]){
            j++;
        }
        ne[i]=j;
    }

    ////kmp匹配的过程 
    //// 其实和上面是一样的
    /// 只不过这个时候是与两个字串相关

    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){
            cout<<i-n<<" ";
            j=ne[j];
        }
    }
    return 0;
}




分享 下围棋

xyzzyx
8天前

我感觉 学算法和下围棋差不多。
自己评估一下你现在处在什么段位?
刷题是有必要的 就像打棋谱。
打棋谱多了 水平也就提高了。
但有时也要去野狐多下下网棋,积累实战经验。
打棋谱是有必要的 但这并不代表着 打完棋谱 你的水平就一定能提高。
事在人为啊。



活动打卡代码 AcWing 802. 区间和

xyzzyx
10天前

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
const int N = 300010;


typedef pair<int,int> PII;

int n,m;

vector<PII> adds;
vector<PII> querys;
vector<int> alls; // 将所有可能的下标存入一个数组里
int a[N],s[N];


int find(int x) // 查找在数组中的下标索引来映射
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}


int main(){

    cin>>n>>m;

    for(int i=0;i<n;i++){
        int x,c;
        cin>>x>>c;
        adds.push_back({x,c});
        alls.push_back(x); ///所有获取的横坐标
    }

    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        querys.push_back({l,r});
        alls.push_back(l); ///所有获取的横坐标
        alls.push_back(r); ///所有获取的横坐标
    }

    /// 将数组中的元素排序去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    ////////// 离散化
    for(auto item:adds){
        int index = find(item.first);
        a[index]+=item.second;
    }

    /////// 转化成求前缀和的问题
    for(int i=1;i<=alls.size();i++){
        s[i]=s[i-1]+a[i];
    }

    for(auto item:querys){
        int l = find(item.first);
        int r = find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }

    return 0;
}



活动打卡代码 AcWing 798. 差分矩阵

xyzzyx
11天前
二维差分

#include<iostream>

using namespace std;
const int N = 1010;
int n,m,q;

int a[N][N],b[N][N];

void update(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main(){

    scanf("%d%d%d",&n,&m,&q);

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

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            update(i,j,i,j,a[i][j]);
        }
    }


    while(q--){
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        update(x1,y1,x2,y2,c);
    }

    // 计算i,j 的前缀和
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=b[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }


    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) printf("%d ", a[i][j]);
        puts("");
    }

    return 0;
}




活动打卡代码 AcWing 797. 差分

xyzzyx
11天前
//通过构造差分数组的操作来求出
//对原数组操作的结果

#include<iostream>
using namespace std;
const int N = 100010;
int q[N];
int b[N];
int n,m;

// 对差分数组进行操作 
void insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}

int main(){

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

   for(int i=1;i<=n;i++){
       insert(i,i,q[i]);
   }

   while(m--){
       int l, r, c;
       scanf("%d%d%d",&l,&r,&c);
       insert(l,r,c);
   }

   /// 通过差分数组求出原数组 
   /// 原数组是差分数组的前缀和
   for(int i=1;i<=n;i++){
       q[i]=q[i-1]+b[i];
   }

   ///输出原数组
   for(int i=1;i<=n;i++){
       printf("%d ",q[i]);
   }

   return 0;
}



活动打卡代码 AcWing 794. 高精度除法

xyzzyx
11天前
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

/// 计算除数 r是商 
vector<int> div(vector<int> &A,int b,int& r){

    vector<int> res;
    for(int i=A.size()-1;i>=0;i--){
        r=r*10+A[i];
        res.push_back(r/b);
        r=r%b;
    }

    reverse(res.begin(),res.end());
    //去除多余的0
    while(res.size()>1 && res.back()==0){
        res.pop_back();
    }
    return res;
};

int main(){

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

    int r=0;
    vector<int> res = div(A,b,r);
    for(int i=res.size()-1;i>=0;i--){
        cout<<res[i];
    }
    cout<<endl<<r<<"";
    return 0;
}