一.位運算
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]；
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252209.html
標籤：其他