set

Zxsoul · 2021-06-19 18:17:01 · 个人记录

set 的正确打开方式

总结

1. 提高以下去重还是比较普及的，
2. 上难度的就是操作平衡术，或者老司机树
3. 或者那他当队列使

P2141 [NOIP2014 普及组] 珠心算测验

插入数组

set<int> se(a+1,a+n+1);

P1059 [NOIP2006 普及组] 明明的随机数

用set去重

int n;
int a[B];
set<int> se;
int ans;
int main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    set<int> se(a+1,a+n+1);
    set<int> find;
    set<int>::iterator it;
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
        {
            if ((it=se.find(a[i]+a[j])) != se.end())
            {
                find.insert(*it); 
            }
        }
    printf("%d",find.size());
}

用到二元组时，用 pair 才可以知道具体位置，结构体我试过了，不能调用，但是缺点是 pair 是按照第一关键字排序，只能在未重复的序列中找相应的位置

int x=read();
    set<pair<int,int> >::iterator it=se.lower_bound(make_pair(x,0));
    if (it->first==x) printf("%d\n", it->second);
    else printf("0\n");

P1918 保龄球

反例是：无法得知最先入队的编号，这个题P1540 [NOIP2010 提高组] 机器翻译

P5594 【XR-4】模拟赛

这题让我突然顿悟了set的一种作用，去重！给每一天都开一个set，记录需要考的次数，然后输出set大小就可

#include <set>
#define ll long long
using namespace std;

const int A = 1e7+10;
const int B = 1e6+10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
set<int> se[1009];
int n,m,k;
int main()
{
    n=read(),m=read(),k=read();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            int x=read();
            se[x].insert(j); 
        }
    }
    for (int i=1;i<=k;i++)
    {
        printf("%d ",se[i].size());
    }
}

P5318 【深基18.例3】查找文献

发现这个题跟P5022 [NOIP2018 提高组] 旅行 的建边思路相似，都是需要将边进行排序，从小开始枚举，对此我们有三种方法：

• 优先队列，每次都开一个优先队列，到时候直接出队即可，缺点是只能用一次，且时间空间开销大，不能实时调用

• vector，可以对vector 用sort 将每一个节点指向的儿子排序

  vector<int> pa[B];
  for (int i=1;i<=n;i++) sort(pa[i].begin(),pa[i].end()); 

• set，依旧每个点开一个set，插入后会自动排序，直接调用即可,这题就是这样操作的，常数可能大点

  se[u].insert(v); //建边
  
  set<int>::iterator it=se[u].begin();//遍历的操作
  for (it;it!=se[u].end();it++)
  {
  int v=*it;
  if (v==fa || vis[v]) continue;
  printf("%d ",v);
  vis[v]=1;
  dfs(v,u);
  }

#include <set>
using namespace std;

const int A = 1e6+10;
const int B = 1e5+10;

set<int> se[B];
int n;
int m;
int vis[B];
void dfs(int u,int fa)
{
    set<int>::iterator it=se[u].begin();
    for (it;it!=se[u].end();it++)
    {
        int v=*it;
        if (v==fa || vis[v]) continue;
        printf("%d ",v);
        vis[v]=1;
        dfs(v,u);
    }
}
queue<int>q;
int main()
{
    n=read(), m=read();
    for (int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        se[u].insert(v); 
    }
    vis[1]=1;
    printf("1 ");
    dfs(1,0);
    q.push(1);
    puts("");
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        printf("%d ",u);
        set<int>::iterator it=se[u].begin();
        for (it;it!=se[u].end();it++)
        {
            int v=*it;
            if (vis[v]) continue;
            vis[v]=1;
            q.push(v); 
        }
    }
}

CF975A Aramic script

又学到一种 STL ，unique 可以将字串重复的部分完美的放到后面

因为其原理是去除相邻位置重复，所以使用前需要排序

sort(a,a+strlen(a));
int len=unique(a,a+strlen(a))-a;//将重复的放在后面  

上面的len 表示的去重后容器中不重复序列的最后一个元素的下一个元素，我这里习惯从 0 开始存字符，因此 a[len] 就表示重复的第一个位置

set的新应用 set在插入字符时，长度以 \0 为标准，这样做

a[len]='\0';//结束符，使得后面被删去
se.insert(a);  

对于去重字符重复的部分，正常的操作为：

 str.erase(unique(str.begin(),str.end()),str.end());

用string可以直观的删除重复的部分，而对于char类型，可以 a[len]='\0' 即可

#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

const int A = 1e7+10;
const int B = 1e6+10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
char a[1009];
set<string> se;
int n;
int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        cin>>a;
        sort(a,a+strlen(a));
        int len=unique(a,a+strlen(a))-a;//将重复的放在后面
        a[len]='\0';//结束符，使得后面被删去
        se.insert(a);  
    }
    printf("%d",se.size());
}

P1781 宇宙总统

主要是string 的应用：

1. string 可以直接赋值
2. string 可以直接比较大小，即从左往右，挨个比较，方便的很 good

int n;
int id;
string bef;
string aft[B];
int main()
{
    n=read();
    cin>>aft[1];
    bef=aft[1];
    for (int i=2;i<=n;i++)
    {
        cin>>aft[i];
        if (aft[i].size()>bef.size() || (aft[i].size()==bef.size()&& aft[i]>bef)) 
        {
            bef=aft[i];
            id=i;   
        }
    }
    printf("%d\n",id);
    cout<<aft[id];
}

P1032 [NOIP2002 提高组] 字串变换

string 函数真奇妙！

substr（start,len） 取出从start开始的长度为len的字串，

利用set去重

vis.count(a)

#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

const int A = 1e7+10;
const int B = 1e6+10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
int cnt;
string a[100];
string b[100];
string s;
string t;
struct node
{
    string s;
    int step;
};
queue<node> q;
set<string>vis;
int main()
{
    cin>>s;
    cin>>t;
    while (cin>>a[cnt]>>b[cnt]) cnt++;
    q.push({s,0});
    if (s==t)
    {
        puts("0");
        return 0;
    }
    int flag=0;
    int ans=0;
    while (!q.empty())
    {
        node u=q.front();
        q.pop();
        string c=u.s;
        int len=c.size();
        if (u.step>=10) {flag=1; break;}
        if (c==t) {flag=2;ans=u.step;break;}
        for (int i=0;i<cnt;i++)
        {
            int zlen=a[i].size();
            for (int j=0;j+zlen<=len;j++)
            {
                string cmp=c.substr(j,zlen);
                if (cmp==a[i])
                {
                    string aft=c.substr(0,j)+b[i]+c.substr(j+zlen,len-(j+zlen));
                    if (vis.count(aft)) continue;
                    q.push((node){aft,u.step+1});
                    vis.insert(aft);    
                } 
            } 
        }
    } 
    if (flag==0 || flag==1) printf("NO ANSWER!");
    else printf("%d",ans);
}

P2286 [HNOI2004]宠物收养场

set 查前驱后记 利用lower_bound 的到前后位置即可

set<int>::iterator le, ri;
le=--se.lower_bound(x), ri=se.lower_bound(x);//这个地方完美的找到了前驱和后级  

/*
    那个多，那个选 
*/
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

const int A = 1e7+10;
const int B = 1e6+10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
set<int> se;
int c,p;
int ccnt,pcnt;
int a[B];
int n,ans;
int opt;
void work(int x)
{
    set<int>::iterator le, ri;
    le=--se.lower_bound(x), ri=se.lower_bound(x);
    if (x-*le<=*ri-x && *le!=-inf) //防止左边没有却可以去取到 
    {
        ans+=x-*le;
        se.erase(le); 
    }   
    else 
    {
        ans+=*ri-x;
        se.erase(ri);
    }
    ans%=1000000;
} 
int main()
{
    n=read();
    int cur=0;
    se.insert(inf),se.insert(-inf);  
    for (int i=1;i<=n;i++)
    {
        int opt=read(), x=read(); 
        if (se.size()==2)
        {
            cur=opt;
            se.insert(x); 
        }
        else if (cur==opt) se.insert(x);
        else work(x); 
    }
    printf("%d",ans);
}

P4305 [JLOI2011]不重复数字

考察set 的综合运用能力，我们发现set虽然能够去重，但是会自动排序，而题目不要求自动排序，况且去重函数也无法使用，因为必须排序，不符合题目性质，

我们用一个数组记录违被重复，但不改变顺序的数组，就相当于开了一个不会排序的set，至于判重，我就用set，最终答案用数组输出就可

其实也可以用map过，上面的操作其实就等价于map

set<int> se;
int t;
int n;
int a[B];
int now[B];
int cnt;
int main()
{
    t=read();
    while (t--)
    {
        n=read();
        se.clear();
        cnt=0;
        for (int i=1;i<=n;i++)
        {
            int x=read();
            if (se.count(x)) continue;
            else 
            {
                se.insert(x);
                now[++cnt]=x; 
            }
        }
        for (int i=1;i<=cnt;i++) printf("%d ",now[i]);
        puts(""); 
    }
} 

P1897 电梯里的爱情

简单的判重问题

set<int> se;
int n;
int ans=0;
int main()
{
    n=read();
    ans+=n;
    for (int i=1;i<=n;i++)
    {
        int x=read();
        if (se.count(x)) continue;
        else 
        {
            se.insert(x);
            ans+=5;//开门 
        }
    }
    set<int>::iterator it=se.end();
    it--;
    ans+=*it*10;
    printf("%d",ans); 
}

P3913 车的攻击

开两个set分别记录行和列所造成的数，考虑重合的部分，我们发现当两条线发生相交时有且仅有一个点，所以重合的部分就是行列个数乘积

set<int> x;
set<int> y;
int n,k;
main()
{
    n=read(),k=read();
    for (int i=1;i<=k;i++)
    {
        int a=read(),b=read();
        x.insert(a), y.insert(b);  
    }
    printf("%lld",x.size()*n-x.size()*y.size()+y.size()*n);
}

但是他 T 了

P2580 于是他错误的点名开始了

比较板子，开两个set记录即可

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
set<string> bef, now;
int n,m;
int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        string c;
        cin>>c;
        bef.insert(c); 
    }
    m=read();
    while (m--)
    {
        string c;
        cin>>c;
        if (bef.find(c)==bef.end()) printf("WRONG\n");
        else if (now.count(c)) printf("REPEAT\n");
        else 
        {
            now.insert(c);
            printf("OK\n"); 
        }
    }
}

P1056 [NOIP2008 普及组] 排座椅

排序

对行数列数计数，拍个序就好了，但是问题是要求将更改的编号按序输出，因此需要用set维护序列，

/*
    若只是知道改的编号，贪心排序就好
    但是要求对编号进行排序，就需要用set进行排序 
*/
#include <set>
using namespace std;

const int B = 1e6+10;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
struct node
{
    int val,id;
    inline bool operator <(const node &a) const 
    {
        return val>a.val;
    }
};
node hag[B];
node lie[B];
int n,m,l,k,s;
int main()
{
    n=read(),m=read(),l=read(),k=read(),s=read();
    for (int i=1;i<=n;i++) hag[i].id=i;
    for (int i=1;i<=m;i++) lie[i].id=i;
    for (int i=1;i<=s;i++)
    {
        int x1=read(),y1=read(), x2=read(),y2=read();
        if (x1==x2) lie[y1+y2>>1].val++;
        else hag[x1+x2>>1].val++; 
    }
    sort(hag+1,hag+1+n);
    sort(lie+1,lie+1+m);    
    set<int> se1;
    set<int> se2;
    for (int i=1;i<=l;i++) se1.insert(hag[i].id);
    for (int i=1;i<=k;i++) se2.insert(lie[i].id);
    set<int>:: iterator it;
    for (it=se1.begin();it!=se1.end();it++)
        printf("%d ",*it);
    puts("");
    for (it=se2.begin();it!=se2.end();it++)
        printf("%d ", *it);
    return 0;
}

P5250 【深基17.例5】木材仓库

二分查找！！！！新知识

二分的操作和宠物那个题很象，但是需要注意一点，set中的一些操作会造成re，lower_bound也是如此，其原因是下界越界，为了防止越界，我们先载入两个边界，其次，在取数时不能将边界取出，这样就不会re 了

main()
{
    n=read();
    se.insert(inf),se.insert(-inf);  
    for (int i=1;i<=n;i++)
    {
        int opt=read(),x=read();
        if (opt==1)
        {
            if (se.find(x)!=se.end()) printf("Already Exist\n");
            else se.insert(x); 
        }  
        else 
        {
            if (se.size()==2) printf("Empty\n");
            else 
            {   
                set<int>::iterator l=--se.lower_bound(x) ,r=se.lower_bound(x);
                if (x-*l<=*r-x && *l!=-inf)
                {
                    ans=*l;
                    se.erase(l); 
                } 
                else {ans=*r;se.erase(r);}
                printf("%lld\n",ans);
            } 
        }

    } 
} 

P1503 鬼子进村

平衡术

这个题发现用思维量，将摧毁的房子用set维护，在查明一个士兵可以通过的房子数量，就是set中该点位置的前驱和后级区间和，真奇妙。反向思考问题！

set<int> se;
set<int>::iterator p;
int n,m;
int cnt;
int tot[B];
int main()
{
    n=read(),m=read();
    se.insert(0), se.insert(n+1);
    while (m--)
    {
        char c;
        cin>>c;
        int x;
        if (c=='D')
        {
            x=read();
            se.insert(x);
            tot[++cnt]=x; 
        }
        else if (c=='R')
        {
            if (!cnt) continue;
            se.erase(tot[cnt]);
            cnt--; 
        }
        else
        {
            x=read();
            p=se.lower_bound(x);
            if (*p==x) {printf("0\n");continue;}
            else {int l=*p-(*--p);printf("%d\n",l-1);} 
        }
    }  
} 

P2161 [SHOI2009]会场预约

平衡术 struct 的作用

饲喂量+++，现在才懂结构体的作用，题目中要求删除重合区间，倘若我们的set的足够聪明，他会利用自己判重的特性，去删除他，

那么我们怎做到让set变聪明

struct 的作用，定义结构体并不能改变set的bst，即不能变他按第一关键字排序的特性，但是struct可以用于find，等函数

贪心的思想，先要重合的区间去重，就如同在同一时间内选择两节课，那么按照尾部排序，这样可以r<a.r 就是一个很明显得分割线，在线后就是重合的区间

struct node
{
    int l,r;
    inline bool operator <(const node &a) const
    {
        return r<a.l;
    }
};

完全不在同一区间内；

it=se.find({l,r});
while (it!=se.end())
{
cnt++;
se.erase(it);
it=se.find({l,r});  
} 
se.insert({l,r});

总能找到一个区间在区间包括l,r中的一个，突然感觉跟以前的贪心的思路很象

const int A = 1e7+10;
const int B = 1e6+10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
struct node
{
    int l,r;
    inline bool operator <(const node &a) const
    {
        return r<a.l;
    }
};//秒在 
set<node> se;
set<node>::iterator it;
int  n;
int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        char c; int l,r;
        cin>>c;
        if (c=='A')
        {
            int cnt=0;
            l=read(),r=read();
            it=se.find({l,r});
            while (it!=se.end())
            {
                cnt++;
                se.erase(it);
                it=se.find({l,r});  
            } 
            se.insert({l,r});
            printf("%d\n",cnt);
        }
        else 
        {
            printf("%d\n",se.size()); 
        }
    }
}