位运算

二进制中1的个数

给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 11 的个数。

输入格式

第一行包含整数 n。

第二行包含 n 个整数，表示整个数列。

输出格式

共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 11 的个数。

数据范围

1≤n≤100000
0≤数列中元素的值≤1e9

输入样例：

1
2
5
1 2 3 4 5

输出样例：

1
1 1 2 1 2

个人

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;cin>>n;
	for(int i=0;i<n;i++){
		int v;
		cin>>v;		
		int cnt = 0;
		while(v){
			cnt += v%2;
			v/=2;
		}
		printf("%d ",cnt);
	}
		
}
/*
5
1 2 3 4 5
*/

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int x, s = 0;
        scanf("%d", &x);

        for (int i = x; i; i -= i & -i) s ++ ;

        printf("%d ", s);
    }

    return 0;
}

位运算的应用：

  • 查看数字二进制表示的第K位是几？

    1
    2
    3
    4
    int res = (n>>k) & 1
    /*
    	本段代码都相当于把n的第k位数移动到个位与除各位外全是零的1进行与运算，将个位保留其余
    */

  • 查看二进制数字中有多少位1

    • lowbit函数：返回最后一位1。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      int lowbit(int x) {
      	return x&-x;
      }
      /*
      	对于某一个数的负数，进行取负操作一般定义为取反加一，那么
      	xxxxxxxxxxxx
      	yyyyyyyyyyyy
      	那么加上的那个一会进行传递到最近的零上零对应之前的1会变成零而 0之前的由于是取反导致也会被舍弃最终身下的是 0000001000000000 即末尾一的权值

      */

    • 对应得完整代码为

      1
      2
      3
      4
      5
      6
      7
      8
      int checkOne(int x) {
      	int cnt = 0;
      	while(x) {
      		x -= lowbit(x);
              cnt++;
      	}
      	return cnt;
      }

离散化

区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是 00。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 <l,r> 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式

共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围

−1e9≤x≤1e9,
1≤n,m≤1e5,
−1e9≤l≤r≤1e9,
−10000≤c≤10000

输入样例：

1
2
3
4
5
6
7
3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：

1
2
3
8
0
5

个人

1
无思路，对于这种超大空间的问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
vector<int>num;//记录所有的有意义的点
vector<pair<int,int>>allInsert;//记录所有增加的操作
vector<pair<int,int>>allQuery;//记录所有的查询操作
int sumV[300010];
//找到给定的位置 在查询的数组中同时我们可以设计一个空点即我们对所有得到的点都加一
//这样可以使 find的结果 从 0 - num.size  对于某一点的和a[x] x > 0
int find(int x) {
	int left = 0;
	int right = num.size() - 1;
	while(left <= right){
		int mid = (left + right) /2;
		if (num[mid] > x) {
			right = mid - 1; 
		} else if (num[mid] < x) {
			left = mid + 1;
		} else{
			return mid + 1;
		}
	}
}
int main() {
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		allInsert.push_back({a,b});
		num.push_back(a);
	}
	
	for(int i=0;i<m;i++){
		int l,r;
		scanf("%d %d",&l,&r);
		num.push_back(l);
		num.push_back(r);
		allQuery.push_back({l,r});
	}
//	需要先对num表进行去重排序的操作
	sort(num.begin(), num.end());
	num.erase(unique(num.begin(), num.end()),num.end());
	
//	对于啊a[i] 第i个有意义的数的值进行赋值
	for(auto x: allInsert) {
		int index = find(x.first);
		sumV[index] += x.second; 
	}
//	根据a中数据的长度为  num.size() 进行赋值
	for(int i=1;i<=num.size();i++){
		sumV[i] += sumV[i-1];
	}
	
	for(auto x: allQuery){
		int l = find(x.first);
		int r = find(x.second);
		printf("%d\n",sumV[r] - sumV[l-1]);
	}
	
	/*
		思想：本体的关键点是有太多对本体无意义的点，相应的先把真正有意义的点整合出来，（去离散化）
		对于整合好的数组我们先进性排序和去重保证以后算法的进行，对于其中的任何一个点我们只关注他在当前范围内的索引，因此我们可以借助这个索引建立一个int[]num其中存储的是每一个索引所对应的值（必须要去重）
		依次我们可以计算前缀和（ps,依靠前缀和可以方便的计算出我们想要的范围内的值，同时前缀和的要求是需要将数组内的元素进行排序的，）
		
        对数组进行去重
        将离散化的数据变得紧凑
        范围的划定（N）即为有意义的数的个数我们需要进行限定以方便进行前缀和的计算，3*100000
	*/
	
}
/*
3 3
1 2
3 6
7 5
1 3
4 6
7 8
*/

区间合并

给定 n 个区间 <l,r>要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：<1,3> 和 <2,6> 可以合并为一个区间 <1,6>。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1≤n≤100000,
−1e9≤li≤ri≤1e9

输入样例：

1
2
3
4
5
6
5
1 2
2 4
5 6
7 8
7 9

输出样例：

1
3

个人代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
// 声明了一个自定义的比较类型
bool cmp(pair<int,int>l, pair<int,int> r) {
	if (l.first == r.first) {
		return l.second > r.second;
	}
	return l.first<r.first;
}
int main() {
	int n;
	cin>>n;
	vector<pair<int,int>> num;
	for(int i=0;i<n;i++){
		int l,r;
		cin>>l>>r;
		num.push_back({l,r});
	}
	sort(num.begin(), num.end(),cmp);
	int cnt = 0;
	int right = num[0].second;
	
	for(int i=1;i<n;i++){
		auto now = num[i];
		if (now.first > right) cnt++;
		right = max(right,now.second);
		// 此处出现细节错误，忘记更换right的判断
	}
	cout<<cnt + 1<<endl;
	
	
}
/*
5
1 2
2 4
5 6
7 8
7 9



*/

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            // 对于非第一次我们的末端如果无法框定该数组那么就可以更换了
            st = seg.first, ed = seg.second;
            // 初始化赋值
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

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

    vector<PII> segs;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}

1
2
很荣幸能来到青软，在这里我将开始我为期一年半的学习，总的来说这里学习氛围和学校相比更好。在这里我主要进行了一下几方面的学习，因为个人偏向与java后端开发的岗位，所以会选择适当舍弃一些课程。
1.开始了我的算法学习，毫无疑问的是算法是da