ACWING基础算法（三）

　　双指针算法。

　　相向双指针，指的是在算法的一开始，两根指针分别位于数组/字符串的两端，并相向行走。

　　ACWING 的一道裸题（不知道为啥进不去404）：最长连续不重复子序列

　　输入

　　1 2 2 3 5

　　输出

　　　　需要两个指针，指针范围为不重复自序列，i，j为其两端。j为左边，i为右边。a【】数组记录原数组，s【】数组记录数字出现次数。怎么搞呢，举个例子，对于样例1 ：

　　1　　　2　　2　　3　　5

　　0　　 1 2　　3 　 4

　　首先j=0,i=0。。如果当前没有出现某个数的出现次数>1,那么i++,j不变。当 j=0,i=2时，出现了s[2]>1，2出现了2次，很明显不符题意了。那么需要移动指针了。根据常识，我们需要从当前出现两次的数重新开始计了，即从i=2,j=2开始，我们可以看到，i没变,j移动了，总结：出现次数大于1的数，i不变，j右移，直到i==j。但是既然要重新计，那么记录次数的s[]数组肯定要清一下，所以s[a[j]]--，在j右移的过程中逐步清掉s[]数组，由于出了s[i]==2以外s[j]==1，所以可以把他们都清为s[a[j]]==0,而顺便把重复数s[a[ i ]]==1，重新开始计。

　　有点啰嗦了，代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn =  1e5;
int a[maxn],s[maxn];
int main()
{
    int n;
    cin>>n;
    for(int i = 0 ;i < n ;i++)
        cin>>a[i];
    int maxx=-1 ;
    for(int i= 0 ,j=0;i< n;i++)
    {
        s[a[i]]++;
        while(s[a[i]]>1)
        {
            s[a[j]]--;
            j++;
        }
        maxx=max(i-j+1,maxx);
    }
    cout<<maxx<<endl;                
}

　　ACWING800

　　给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。请你求出满足A[i] + B[j] = x的数对(i, j)。

　　　　　本来写了一个双指针，结果超时了，j每次清0的操作实在花了好多无用功。因为题目中给的两个数组，均为升序排列。所以，用 i 代表a[]数组，j 为b[]数组。j从右往左滑，i往右划。

由于是升序排列，所以j并不需要清成m-1,因为比如：i 在 1位置+j在2位置 ==x,那么下一次 i 右移，j不会再往右移，如果往右移接下来的a+b一定>x，没必要再算了。j不能从左往右滑，不再解释，还是因为升序数组。

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn =  1e5+10;
int a[maxn],b[maxn];//     
int main()
{
    int n ,m ,x;
    cin>>n>>m>>x;
    for(int i= 0 ;i < n ; i++)
         cin>>a[i];
    for(int i = 0 ;i< m; i++)
        cin>>b[i];
    int ans=0;
    for(int i = 0 ,j = m-1 ; i < n && j>=0;    i++)
    {    
        while(a[i]+b[j]>x&&j>=0)
        {
            j--;         
        }
        if(a[i]+b[j]==x) 
            cout<<i<<" "<<j<<endl; 
    }
}

　　　　位运算 :

　　　　1:　　n的二进制表示中第k位是几？　　n > > k & 1

　　　　模板：表示N的二进制

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn =  1e5+10;
int a[maxn],b[maxn];//     
int main()
{
     int n;
     while(cin>>n)
     {
         for(int k=9 ;k>=0; k-- )
             cout<<(n>>k&1);
             cout<<endl;
    }
}

　　　　2：返回x（二进制）的最后一位1的位置

　　　　x & （-x）==x & (x取反+1)

　　　　ACWING

　　　　二进制中1的个数

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn =  1e5+10;
int a[maxn],b[maxn];//     
int lowbit(int a)
{
    return a&(-a);
}
int main()
{
     int n;
     cin>>n;
     for(int i=1;i<=n;i++)
     {
         int x;
         int ans=0;
         cin>>x;
         while(x)
         {
             ans++;
             x-=lowbit(x);　　//每次减去x的最后一位
        }
        cout<<ans<<' ';
     }    
}

　　离散化：整数离散化：

　　　　要点：　　1：重复元素的去重。2：如何算离散化值　　　

　　//排序加去重

void quchong()
{
    vector<int>alls;    //存储所有待离散化的值
    sort(alls.begin(),alls.end());    //将所有值排序
    alls.erase(unique(alls.begin(),alls.end()),alls.end());    //去掉重复元素 
}

//二分法求出x对应的离散化的值 
int find(int x)    //找到第一个大于等于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;  //映射 
}

　　ACWING　　区间和

　　　　　　10^9,不能用前缀和了。分析一下，n+2*m个坐标==3*10^5，用得着的也就这么些坐标了，其他的没必要看，所以可以用离散化来做。

　　ACWING 区间合并

　　vector的不会做，自己写的代码

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;
struct node
{
    int l,r;
}st[maxn];
bool cmp(node a,node b)
{
    return a.l<b.l;
}
int main()
{
    int n ; 
    cin>>n;
    for(int i= 0 ; i < n; i++)
    {
        cin>>st[i].l>>st[i].r;
    }
    sort(st,st+n,cmp);
    int sum = 1 ;
    for(int i= 0;i < n ;i++)
    {
        if(st[i].r<st[i+1].l)
        {
            sum++;
        //    cout<<st[i].l<<"  "<<st[i].r<<" -"<<st[i+1].l<<" "<<st[i+1].r<<endl;
        }
        else
        {
            if(st[i].r>st[i+1].r)
            {
                st[i+1].r=st[i].r;
            }
        }
    }
    cout<<sum<<endl;
}