第二周学习C++

01/26 10:59
阅读数 50

一.位运算
1.基本知识
(1).与 (&&):两者皆是1即为1;其余为0;
或(||) :一方为1皆为1;其余为0;
非 (!) :!x,所得即为不是x;
异或(^) :两者相同皆为0;不同为1;
(2).左移:1<<x (即为二进制中左移一位,其实就是扩大2倍)
右移:1>>x (即为二进制中右移一位,其实就是除以2)
(3).判断奇偶性
奇数的二进制最低位是1;
偶数的二进制最低位是0;









2.位运算典型的应用
(1)求模运算
例如:a乘b对p求模;a的b次方对p求模;等等
一般就是取模运算:a % p(或a mod p),表示a除以p的余数。比如给定一个正整数p,任意一个整数n,一定存在等式 :n = kp + r ;其中 k、r 是整数,且 0 ≤ r < p,则称 k 为 n 除以 p 的商,r 为 n 除以 p 的余数。取模运算的规则如下:
1、(a + b) % p = (a % p + b % p) % p 。
2、(a - b) % p = (a % p - b % p) % p 。
3、(a * b) % p = (a % p * b % p) % p 。
4、a ^ b % p = ((a % p)^b) % p 。
一般就是会用快速幂=二分+拆分来减少计算, 一般快速幂 a的b次方,如3的7次方: 7=111(2) 3^7=3* 3^2 3^4.也就是ans=ansa,a每次在b右移一位后平方。对于a乘b,化为加法,3x7:=3+3x2+3x4,也就是ans=ans+a,a每次在b右移一位后乘以2.。









while(b)
{
   
   
   if(b&1){
   
   
    ans=ans*1lla%p;(有时范围大会转化为长整形long long ,会加个1ll)
    }
    a=a*1lla%p;
    b>>=1;
   }

``

while(b > 0){
   
   
		if(b & 1){
   
   
			ans = (ans + a) % p;
		}
		a = 2 * a % p;
		b >>= 1;
	}

二. 整数二分和浮点二分
1.二分一般就是用来查找的,整数二分用的比较多吧,有两种模板
(1).找中间点
所以中间点应为mid=(l+r+1)/2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时,其更新操作是r = mid - 1或者l = mid;,此时为了防止死循环,计算mid时需要加1。



(2).中间点 mid=(l+r)/ 2
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时,其更新操作是r = mid或者l = mid + 1;,计算mid时不需要加1。

//(1)
```while(l<r)
{
   
   
	int mid=(l+r+1)/2; 
	if(x<=a[mid])
	{
   
   
		l=mid;
	}
	else r=mid-1;
}
cout<<l<<endl;
return 0;
}
 

//(2)

```while(l<r)
{
   
   
   int mid=(l+r)/2;
   if(a[mid]>=x)
   {
   
   
   	r=mid;
   }
   else l=mid+1;
}
cout<<r<<endl;
return 0;
}

``

2.浮点数二分
浮点数的模板比较简单,以一个题说明(数的三次方根)
给定一个浮点数n,求它的三次方根。

输入格式

共一行,包含一个浮点数n。

输出格式

共一行,包含一个浮点数,表示问题的解。

注意,结果保留6位小数。

数据范围

−10000≤n≤10000−10000≤n≤10000
输入样例:
在这里插入图片描述
输出样例:
在这里插入图片描述
在这里插入图片描述
说明: 当r-l足够小时,我们就假定已经找完, 用公式表示r-l<1e-6,此时有个精度问题如果要求保留6位小数则r-l<1e-8,总要比保留的小数多两位。





三.前缀和与差分
1.前缀和
一般就是一维前缀和二维前缀,就是求一列数的在哪个区间他们的和,也是有模板的。
一维的给定长度为n的序列a1,a2…an,则sum[i]=a1+…+ai=sum[i-1]+a[i],求每个区间的和的话,
`



    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=1;i<=n;i++)
        s[i] = s[i-1] + a[i];
    while (m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<s[r] - s[l-1]<<endl;
    }
    return 0;
}
      

// 有些是让每个数都加上c,以下是写的函数
void s(int l, int r, int c)
{
   
   
   b[l] += c;
   b[r + 1] -= c;
}

//`二维前缀和就是如给定一个矩阵s[i][j],sum[i][j]是矩阵的和。 

```for(int i=1;i<=n;i++)

 for(int j=1;j<=m;j++)

  sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];

有些二维矩阵求区间的和

`ans=sum[x2][y2]-sum [x1-1][y2]-sum [x2][y1-1]+sum [x1-1][y1-1];
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部