zhangas

Pay more attention

0%

Veröffentlicht am Bearbeitet am

利用vector存储映射的一组数据 

1
2
typedef pair<int,int> PII; 
vector<PII> add,query;//add是添加操作 query是查询操作

①先排序 再去重

1
2
unique函数的原型:
iterator unique(iterator it_1,iterator it_2);

返回值指向去重后容器中不重复序列的最后一个元素的下一元素

1
2
sort(all.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());

②二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int find(int x){
	int l=0,r=alls.size()-1;
	while(l<r){
		int mid=l+c>>1;
		if(alls[mid]>=x){
			r=mid;
		}
		else{
			l=mid+1;		
		}
	}
	//return l;//映射到0,1,2,3...
	return r+1;//映射到1,2,3,4s... 
        //在计算a的前缀和时 不需要考虑边界问题 s[i]=s[i-1]+a[i];
    
}

遍历add容器和求数组a的前缀和s

1
2
3
4
5
6
7
for(auto it:add){
		int x=find(it.first);
		a[x]+=it.second;
	} 
for(int i=0;i<=alls.size();i++){
    s[i]=s[i-1]+a[i];
}

遍历query容器输出

1
2
3
4
5
for(auto it:query){
    int l=find(it.first);
    int r=find(it,second);
    cout<<s[r]-s[l-1]<<endl;
}

Veröffentlicht am Bearbeitet am

位运算概览

1
2
3
4
5
6
7
符号 描述	 运算规则
&	 与	    两个位都为1时，结果才为1
|	 或	    两个位都为0时，结果才为0
^	 异或	两个位相同为0，相异为1
~	 取反	0变1，1变0
<<	 左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	 右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

求n的二进制第k位是多少

1
cout<<(n>>k&1);

这里&1判断n是否为奇数
①n为奇数时,对应的二进制数最低位一定为1,&1的结果就是1.
②n为偶数时,相应的最低位为0,n&1的结果就是0.
这里等价于 (n>>k)%2

统计n的二进制中有多少个1

x&-x
(-x)=~x+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
假设x==42
原码  x  (101010)
反码 ~x  (010101)
补码 ~x+1(010110)
   x&-x  (000010)
*/
int lowbit(int x){
	return x&-x;
} 
int cnt=0;
	while(a){
		a-=lowbit(a);//减去最右侧第一个1到末尾的部分
		cnt++;
	}
	cout<<cnt;

Veröffentlicht am Bearbeitet am

模板

对于一个序列 借助两个指针维护一个区间(i与j有单调关系)

1
2
3
4
5
6
7
for(int i=0;i<n;i++){
    j=i;
    while(j<n&&check(i,j)){
        j++;
    }
    //每道题的具体逻辑
}

可将暴力两层嵌套循环O(n^2)优化到O(n)

799. 最长连续不重复子序列

找出最长的不包含重复数字的连续子序列[l,c]的长度
input 1 2 2 3 5
output 3

1
2
3
4
5
6
7
8
9
int res=0;
for(int r=0,l=0;r<n;r++){
	cnt[a[r]]++;//计时器的作用
	while(l<r&&s[a[r]]>1){//当出现重复的数字j向前移动一位直到不再重复
		cnt[a[l]]--;
		l++;	
	}
	res=max(res,r-l+1);
}

实现unique函数

1
2
3
4
5
6
7
8
9
10
vector<int>::iterator unique(vector<int> &a){
	int j=0;
	for(int i=0;i<a.size();i++){
		if(!i||a[i]!=a[i-1]){//第一个或满足不与前一个数相同 
			a[j]=a[i];
			j++;
		}
	}
	return a.begin()+j;//返回值必须是迭代器
}

调用实现去重操作

1
2
sort(a.begin(),a.end());
a.erase(unique(a),a.end());

Veröffentlicht am Bearbeitet am

对于一维数组a和数组b
a[i]=b[1]+b[2]+…+b[i];

b[1]=a[1]
b[2]=a[2]-a[1]
··· ···
b[n]=a[n]-a[n-1]
称数组a是数组b的前缀和 数组b是数组a的差分

若将一维数组a的[l,r]区间加上c 且时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void insert(int l,int r,int c){//数组b是数组a的差分 b[i]=a[i]-a[i-1] 
	b[l]+=c;
	b[r+1]-=c;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m,n;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(i,i,a[i]);//将数组a转变成它的差分数组b
	}
	while(m--){
		int l,r,c;
		cin>>l>>r>>c;
		insert(l,r,c);
	}
	for(int i=1;i<=n;i++){
		b[i]=b[i]+b[i-1];//将数组b变成数组b的前缀和并输出
		cout<<b[i]<<" ";
	}

对于二维数组a和数组b
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];

b[1][1]=a[1][1]-a[1][0]-a[0][1]+a[0][0]
b[2][2]=a[2][2]-a[2][1]-a[1][2]+a[1][1]
··· ···
b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
称数组a是数组b的前缀和 数组b是数组a的差分

若将二维数组a的[(x1,y1),(x2,y2)]子矩阵加上c 且时间复杂度为O(n^2)

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
void insert(int x1,int y1,int x2,int y2,int c){//这样变化后只有含有加上c的子矩阵元素的前缀和才会改变 
	b[x1][y1]+=c;
	b[x1][y2+1]-=c;
	b[x2+1][y1]-=c;
	b[x2+1][y2+1]+=c;
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			insert(i,j,i,j,a[i][j]);
			
		}
	}
	while(q--){
		int x1,y1,x2,y2,c;
		cin>>x1>>y1>>x2>>y2>>c;
		
		insert(x1,y1,x2,y2,c);//b[x1][y1]和b[x2+1][y2+1]符号为正 b[x1][y2+1]和b[x2+1][y1]符号为负
	}
	//将数组b化为数组b的前缀和 并输出 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
			cout<<b[i][j]<<" ";
		}
		cout<<endl;
	}

Veröffentlicht am Bearbeitet am

通过

1
2
3
ios::sync_with_stdio(false);
cin.tie(0)；
cout.tie(0);

取消cin和stdin的同步,解除cin与cout的绑定,加快执行速度.

但不可再使用scanf()或printf() ！！！

puts()也不可用

Veröffentlicht am Bearbeitet am 
1
2
3
4
struct node{
	int data;
	struct node *next;
};//创建结构体 表示链表的节点类型

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct node *head,*p,*q,*t;
	int n,a;
	cin>>n;
	head=NULL;//头指针初始化为空 
	for(int i=0;i<n;i++){
		cin>>a;//input 
		
		p=(struct node*)malloc(sizeof(struct node));//动态申请一个空间 用来存放一个节点 
		//并将临时节点p指向这块内存
		 
		p->data=a;//将a存储在这个节点的data域中 
		p->next=NULL;//将当前节点的后继指针指向空 
		if(head==NULL){
			head=p;//如果是是第一个节点 将头指针指向这个节点 
		}
		else{ 
			q->next=p;//如果不是第一个节点 将上一节点的后继指针指向当前的节点 
		}

		q=p;//更新上一节点 
		p=NULL;//将临时节点p变为空指针 
	}

插入

注意:

如果这个链表很长，且每个节点的值相同
再插一个相同的值进去会遍历整个链表然后插入到链表尾部 浪费了时间
将大于号改为大于等于

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   cin>>a; //输入插入的数字 
t=head;//从头指针开始遍历 
while(t!=NULL){
	if(t->next==NULL||t->next->data>=a){//如果是在最后一个数字 下一节点指向空或者下一集结点的data域的大小比新插入的数字要大 
		p=(struct node*)malloc(sizeof(struct node));//动态申请一个空间 存放新增节点 
		p->data=a;//将新节点的data域更新为插入的值 
		p->next=t->next;//将新节点的下一节点于t节点的下一节点相连 
		t->next=p;//将t节点的下一节点更新为新节点p 
		p=NULL;//初始化临时指针p 
		break;
	}
	t=t->next;//向下一节点遍历 
}

输出

1
2
3
4
5
6
7
   t=head;
while(t!=NULL){
	cout<<t->data<<" ";//从头节点开始输出 
	t=t->next;//向下一节点遍历 
}
free(t);//清空t指针指向的内存 
t=NULL;//t初始化为空指针

Veröffentlicht am Bearbeitet am

lower_bound() 时间复杂度为O(n)

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

函数作用

在升序的情况下，返回指向第一个值不小于val的位置，即返回第一个大于等于val值的位置。（通过二分查找）
借助数组实现 从a[0]到a[n]

1
cout<<a[lower_bound(a,a+n,val)-a];

输出第一个大于或等于val的数

nth_element() 时间复杂度为O(n)

称第 n 个元素为升序序列中”第n大”的元素
例如

1
2 4 6 8 10

2为第1小 8为第4小

默认升序

1
2
3
void nth_element (RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last);

自定义cmp排序

1
2
3
4
void nth_element (RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last，
                  Compare cmp);

函数作用

1
nth_element(a,a+n,a+k);//使第k小整数就位

Veröffentlicht am Bearbeitet am

加法 A+B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> add(vector<int> &a,vector<int> &b){//默认字符串a的长 
	vector<int>c;//加上引用不用拷贝整个数组 可以加快效率 
	if(a.size()<b.size()){
		return add(b,a);
	}
	int t=0;//处理进位问题 
	for(int i=0;i<a.size();i++){
		t+=a[i];
		if(i<b.size()){
			t+=b[i];
		}
		c.push_back(t%10);
		t/=10;
	}
	if(t){//若最高位向前进了1 则添加到c中
		c.push_back(t);
	}
	return c;
}

减法 A-B

需要判断读入A和B的大小

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
//比较A和B的大小 
bool cmp(vector<int>&a,vector<int>&b){
	if(a.size()!=b.size()){
		return a.size()>b.size();
	}
	//长度相同 
	for(int i=a.size()-1;i>=0;i--){
		if(a[i]!=b[i]){
			return a[i]>b[i];
		}
	}
	return true;	
}
vector<int> subtraction(vector<int>&a,vector<int>&b){
	vector<int>c;//计算A-B 
	for(int i=0,t=0;i<a.size();i++){
		t=a[i]-t;
		if(i<b.size()){//判断b是不是已经越界了 
			t-=b[i];
		}
		c.push_back((t+10)%10);
		//等价于判断t<0时候 t+=10 t<10时 直接在尾部添加t
		t=t<0?1:0;//更新t 若借一 t在下次循环要减去一
	}
	while(c.size()>1&&c.back()==0){//例如123-120=3 容器c的长度和a一样 返回的应该是003
		c.pop_back();//删除容器尾部元素
	}
	return c;
	
}

乘法 A*b

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> multiple(vector<int>a,int b){
	vector<int>c;
	int t=0; 
	for(int i=0;i<a.size();i++){
		t+=a[i]*b;		
		c.push_back(t%10);
		t/=10;
	}
	if(t){//t不为零时 可以加到c的最高位上 
		c.push_back(t);
	}
	return c;
}

除法