记录

zhangqin123 · 2021-07-11 18:44:30 · 个人记录

不知名外出培训

2021.7.11

优先队列 +结构体 + 排序

priority_queue<node>q;
struct node
{
    int r,id;
    bool operator <(const node &b) const
    {
        return b.r<r; // 栈顶为最小 小根堆
    }
};

结构体+排序

int cmp(const Node &a,const Node &b)
{
    return a.l<b.l;
}

2021.7.12

建议：非常妙

二分整数区域上

求满足条件的最大值：

while(l<r)
{
    mid=(l+r)/2+1;
   if(满足条件) l=mid;
   else r=mid-1;
}

求满足条件的最小值

while(l<r)
{
    mid=(l+r)/2;
    if(满足条件) r=mid;
    else l=mid+1;
}

求大于等于 k 的最小下标


while(l<=r)     //注意二分 
{
    int mid=(l+r)>>1;
    if(a[mid]+>=k) r1=mid-1;
    else l1=mid+1;
}

2021.7.13

字符串与数字之间的转化

    //sscanf(s,"%d",&n);  将字符串s 转化成数字n 
    //sprintf(s,"%d",n);  将数字n 转化成字符串 s

string::npos参数 —— npos 是一个常数，用来表示不存在的位置

例如，有两个字符串a、b，判断a字符串是否包含b字符串

//如果字符串不存在包含关系，那么返回值就一定是npos

if(a.find(b)!=string::npos)
{
   cout<<"yes"<<endl;
}
else
{
   cout<<"no"<<endl;
}

2021.7.14

trie 字典树题型：字典树与异或

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,tot; // tot=0，开始，则下面 c=0
int ans;   // tot=1，开始，则下面 c=1
int s[1000001],ch[3000001][2];
void add(int x)
{
    int p=0;
    for(int i=31;i>=0;i--)
    {
        int x2=((x>>i)&1);  // 从 最高位 开始 建边 
        if(!ch[p][x2]) ch[p][x2]=++tot;
        p=ch[p][x2];
    }
}
void query(int x)
{
    int p=0;
    ans=0;
    for(int i=31;i>=0;i--)
    {
        /*if((x>>i)&1)
        int x2=0;
        else int x2=1; */
        int x2=((x>>i)&1)==1 ? 0:1;  // 如果 第 i 位上有 1，则寻找  第i位上没有 1 的 往下便历 
        if(ch[p][x2])  // 含有 最高位上是 0 的 
        ans+=(1<<i); 
        else x2=((x>>i)&1); // 最高位上全是1 则向下便历 
        p=ch[p][x2];
        /*int s=x>>i & 1;
        if(ch[p][!s])
        {
            ans+=(1<<i);
            p=ch[p][!s];
         } 
         else p=ch[p][s];*/
    }
}
int main()
{

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        add(s[i]);
    }
    int an=0;
    for(int i=1;i<=n;i++)
    {
        query(s[i]);
        an=max(ans,an);
    }
    printf("%d",an);
 }

2021.7.15

离散化

第一种

const int N=1e5+7;
int t[N],a[N];
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>a[i],t[i]=a[i];
  sort(t+1,t+n+1);
  m=unique(t+1,t+n+1)-t-1;  //去重
  for(int i=1;i<=n;i++)
    a[i]=lower_bound(t+1,t+m+1,a[i])-t;
}

第二种

const int N=1e5+7;
struct Node{
  int v,id;
  bool operator < (const Node a)const
  {
    return v<a.v;}//排序用
}a[N];
int n,rank[N];
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i].v;
    a[i].id=i;}
  sort(a+1,a+n+1);
  for(int i=1;i<=n;i++)
    rank[a[i].id]=i;
}

v: 3 6 5 10 8 --> v: 3 6 5 10 8

id :1 2 3 4 5 --> rk:1 3 2 5 4

2021.7.16

差分约束

7.17-7.20

中间太懒

2021.7.21

状压DP
对于一个二进制数
通过
来枚举子集

for(int i=1;i<(1<<n);i++)
    for(int j=(i-1)&i;j;j=(j-1)&i)  //j=（j-1）&i就是其子集

记录