头像

不会算法的小菜鸡




离线:6小时前


最近来访(3)
用户头像
现代修士o_O
用户头像
rech
用户头像
SIMPLIFY


自己对离散化的一些理解

离散化适用于题目要求空间很大,但实际使用空间较小的题,类似于这题,题目空间是1e-9~1e9,而实际只使用了1e5的空间

本题核心 本题如何离散化

  1. 先排序
  2. 在去重
  3. 利用元素的位置来离散化他的空间 例如在 1 5 100 1000这四个位置插入元素,则可离散化为 1-0,5-1, 100-2, 1000-3,就凡是在1000位置上插入一个数,实际实在a[3]里插入一个数, 求[l,r]区间同理,l和r进行离散化,只要求离散化后区间的前缀和,例如求1,100之间的和,则只需要求0,2的前缀和

unique函数的实现

思路
1. 第一个元素肯定唯一
2. 当前元素于前一个元素不同 a[i] != a[i+1]

vectror:iterator unique(vector &a)
{
    int j=0;
    for(int i=0;i<a.size();i++)
    {
        while(!i || a[i]!=a[i+1])
         a[j++] = a[i];
    }
    return j+a.begin();
}

题目代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 300000+10;
typedef pair<int,int> PII;
vector<int> alls;
vector<PII> add,query;
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()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int x,c;
        cin>>x>>c;
        alls.push_back(x);
        add.push_back({x,c});
    }
    for(int i=0;i<m;i++) 
    {
        int l,r;
        cin>>l>>r;
        alls.push_back(l);
        alls.push_back(r);
        query.push_back({l,r});
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(auto i : add) 
    {
        int x = find(i.first);
        a[x] += i.second;
    }

    for(int i=1;i<=alls.size();i++) s[i] = s[i-1] + a[i];

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


活动打卡代码 AcWing 842. 排列数字

#include<iostream>
using namespace std;
const int N=7+10;
int path[N];
int n;
bool s[N];
void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;i++) printf("%d ",path[i]);
        printf("\n");
        return ;
    }

    for(int i=1;i<=n;i++)
    {
        if(!s[i])
        {
            path[u]=i;
            s[i]=true;
            dfs(u+1);
            s[i]=false;
            path[u]=0;

        }
    }
}
int main(){
 scanf("%d",&n);
 dfs(0);
}



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

#include<iostream>
#include<cstdio>
const int N=50000+10;
int p[N],d[N],n,m;

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()
{
    int res=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {p[i]=i; d[i]=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{
                    p[px] = py;
                    d[px] = d[y]-d[x];
                }
            }
            else if(t==2) {
                if(px==py && (d[x]-d[y]-1)%3) res++;
                else{
                    p[px]=py;
                    d[px]=d[y]-d[x]+1;
                }
            }
        }
    }
        printf("%d",res);
        return 0;
}



C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned long long ULL;
const int N=100003,P=131;
int h[N],p[N],n,m;
string str;
ULL query(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];// 已知h[l]和h[r]求l~r 将l右移h-r+1 然后相减即使l~r的值
}
int main()
{
    int l1,r1,l2,r2;
    cin>>n>>m;
    cin>>str;
    h[0]=0;
    p[0]=1;
    for(int i=0;i<n;i++)
    {
        p[i+1] = p[i]*P;  //p代表是多少位,代表要到i要乘多少个p    
        h[i+1] = h[i]*P +str[i]; //构造哈希前缀和
    }
    while(m--)
    {
        cin>>l1>>r1>>l2>>r2;
        if(query(l1,r1)==query(l2,r2)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;

}

`



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

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100003,null=0xf3f3f3f3;
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()
{
    int n,x,k;
    char ch;
    cin>>n;
    memset(h,0xf3,sizeof(h));
    while(n--)
    {
        cin>>ch>>x;
        k=find(x);
        if(ch=='I') h[k]=x;
        else
        {
            if(h[k]==x) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}


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

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
int a[N],n,m,si=0;
void down(int t)
{
    int u=t;
    if(2*u<=si&&a[t]>a[2*u]) t=2*u;
    if(2*u+1<=si&&a[t]>a[2*u+1]) t=2*u+1;
    if(u!=t)
    {
        swap(a[t],a[u]);
        down(t);
    }
}
void up(int t)
{
    int u=t;
    while(u/2&&a[u/2]>a[t])
    {
        swap(a[u/2],a[t]);
        t=u/2;
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    si=n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);//堆必须从1开始
    for(int i=n/2;i>=1;i--) down(i);
    while(m--)
    {
        printf("%d ",a[1]);
        a[1]=a[si];
        si--;
        down(1);
    }
    return 0;
}



#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
int q[N],si[N],idx,n,m;
int find(int x)
{
    if(q[x]!=x) q[x]=find(q[x]);
    return q[x];
}
void merge(int a,int b)
{
    if(find(a)!=find(b))
    {
        si[find(b)]=si[find(a)]+si[find(b)];
        q[find(a)]=find(b);

    }
}
bool query(int a,int b)
{
    return find(a)==find(b);
}
int main()
{
    int a,b;
    cin>>n>>m;
    for(int i=i;i<=n;i++)
    {
        q[i]=i;
        si[i]++;
    }
    string op;
    while(m--)
    {
        cin>>op;
        if(op=="C")
        {
            cin>>a>>b;
            merge(a,b);
        }
        else if(op=="Q1")
        {
            cin>>a>>b;
            if(query(a,b)) printf("Yes\n");
            else printf("No\n");
        }
        else
        {
            cin>>a;
            printf("%d\n",si[find(a)]);
        }

    } 
    return 0;

}


活动打卡代码 AcWing 836. 合并集合

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
int q[N],idx;
//查询所在集合
int find(int x)
{
    if(q[x]!=x) q[x]=find(q[x]);
    return q[x];
}
int main()
{
    int n,m,a,b;
    char  ch;
    cin>>n>>m;
    for(int i=1;i<+n;i++) q[i]=i;
    for(int i=1;i<=m;i++)
    {
      scanf(" %c %d %d",&ch,&a,&b);
      if(ch=='M')
      {
          if(find(a)!=find(b));
          q[find(a)]=find(b);
      }
      else
      {
          if(find(a)==find(b))
          printf("Yes\n");
          else 
          printf("No\n");
      }
    }
    return 0;
}


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

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010*31;
int a[100010],son[N][2],idx=1;
void insert(int x)
{
    int p=0;
    for(int i=31;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=31;i>=0;i--)
    {
        int u=x>>i&1;
        if(son[p][!u]) 
        {
            p=son[p][!u];
            res=res*2+1;
        }
        else{
            p=son[p][u];
            res=res*2+0;
        }

    }
    return res;
}
int main()
{
    int n,res=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        insert(a[i]);
    }
    for(int i=0;i<n;i++)
    {
        res=max(res,query(a[i]));
    }
    printf("%d",res);
}~


活动打卡代码 AcWing 835. Trie字符串统计

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
int son[N][26],cnt[N],idx;
void insert(char str[])
{
     int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
int  query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    char ch,op[N];
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>ch;
        if(ch=='I')
        {
            cin>>op;
            insert(op);
        }
        else
        {
            cin>>op;
            printf("%d\n",query(op));
        }
    }
    return 0;
}