位运算
原码
原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:
其中，第一位为1是负数
[+1] = [0000 0001]原
[-1] = [1000 0001]原
因此，8位二进制数的取值范围：[-127,127]
补码
正数的补码是其本身
负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1(即在其反码的基础上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补
反码
正数的反码是其本身
负数的反码是在其原码的基础上，符号位不变，其余各个位取反
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
技巧
memset(a, 0x3f, sizeof(a)) 给数组赋值 0x3f3f3f3f
赋值正无穷 INF = 0x3f3f3f3f 或者 INF = 0x3f
移位运算
左移：n << x = n*2^x
右移：n >> x = n/2^x (在C++中右移为算数右移，即移出去的位丢弃，空缺位用“符号位”来填充)
快速幂
原理解释：
代码模板：
int qmi(int m, int k, int p)
{
int res = 1 % p, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}例题：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
int main()
{
ll a,b,p;
cin>>a>>b>>p;
ll res = 1;
while(b)
{
if(b&1) res = res * a % p;
a *= a;
a %= p;
b >>= 1;
}
cout<<res % p<<endl;
return 0;
}与快速幂原理相同，将一个乘数分解成二进制来表示，然后再相乘，防止溢出。
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
int main()
{
ll a,b,p,res = 0;
cin>>a>>b>>p;
while(b)
{
if(b&1)res = (res + a) % p;
b >>= 1;
a = 2 * a % p;
}
cout<<res%p<<endl;
return 0;
}递推与递归
例题
位运算解法：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
int main()
{
int n;
cin >> n;
n = pow(2, n);
for (int i = 0;i < n; i++)
{
int temp = i, cnt = 1;
while (temp)
{
if (temp & 1) cout << cnt << " ";
cnt++;
temp >>= 1;
}
if (temp == 0) cout << " " << endl;
else cout << endl;
}
return 0;
}递归解法：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
int n;
vector<int> res;
void solve(int x)
{
if (x == n + 1)
{
for (int i = 0;i < res.size();i++)
{
cout << res[i] << " ";
}
cout << endl;
return ;
}
solve(x + 1);
res.push_back(x);
solve(x + 1);
res.pop_back();
}
int main()
{
cin >> n;
solve(1);
return 0;
}需要剪枝
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int m,n;
vector<int> res;
bool vis[30];
void solve(int cnt)
{
if (res.size() + n - res.back() + 1 < m) return ;
if (cnt == m)
{
for (int i = 1; i < res.size(); i++)
{
cout << res[i] << " ";
}
cout << endl;
return ;
}
for (int i = 1; i <= n; i++)
{
if (vis[i] == 0 && res.back() < i)
{
res.push_back(i);
vis[i] = 1;
solve(cnt+1);
vis[i] = 0;
res.pop_back();
}
}
}
int main()
{
cin >> n >> m;
res.push_back(0);
solve(0);
return 0;
}在上一题的基础上修改一部分代码就行
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int n;
vector<int> res;
bool vis[30];
void solve(int cnt)
{
//if (res.size() + n - res.back() + 1 < n) return ;
if (cnt == n)
{
for (int i = 0; i < res.size(); i++)
{
cout << res[i] << " ";
}
cout << endl;
return ;
}
for (int i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
res.push_back(i);
vis[i] = 1;
solve(cnt+1);
vis[i] = 0;
res.pop_back();
}
}
}
int main()
{
cin >> n;
//res.push_back(0);
solve(0);
return 0;
}前缀和与差分
二维前缀和
根据容斥原理，可以推导出二维前缀和：s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int sum[5050][5050];
int n,r;
int main()
{
cin >> n >> r;
int x, y, w;
for (int i = 0; i < n; i++)
{
cin >> x >> y >> w;
x++,y++;
sum[x][y] += w;//读数据，位置相同的点权值相加
}
for (int i = 1; i <= 5001; i++)
for (int j = 1; j <= 5001; j++)
sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];//以(0,0)为左下角的矩形求二维前缀和
int ans = 0;
for (int i = r; i <= 5001; i++)
for (int j = r; j <= 5001; j++)
ans = max(ans, sum[i][j] - sum[i][j-r] - sum[i-r][j] + sum[i-r][j-r]);//因为炸弹影响r*r矩形的范围，根据容斥原理同样可以推导出ans=sum[i][j]-sum[i][j-r]-sum[i-r][j]+sum[i][j]，最后再取一个最大值就行
cout << ans <<endl;
return 0;
}简单的差分题，注意去重
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int d[10005], res[10005];
set<pair<int, int> > vis;
int main()
{
int n, p, h, m, a, b;
cin >> n >> p >> h >> m;
while (m--)
{
cin >> a >> b;
int l = min(a, b), r = max(a, b);
if (vis.count({l, r})) continue;
vis.insert({l, r});
d[l + 1] --;
d[r] ++;
}
res[0] = h;
for (int i = 1; i <= n; i++)
{
res[i] = res[i - 1] + d[i];
cout << res[i] << endl;
}
return 0;
}二分
二分出平均值，然后再用前缀和找出该平均值条件下的最大子段和，在利用这个最大子段和来确定二分方向
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 50;
typedef long long ll;
int n, f;
double s[maxn], a[maxn], l, r, mid, ans, min_value;
int main()
{
cin >> n >> f;
for (int i = 1; i <= n; i++) cin >> a[i];
l = -3000, r = 3000;
while (r - l > eps)
{
mid = (l + r) / 2;
for (int i = 1; i <= n; i++) // 前缀和
s[i] = s[i - 1] + a[i] - mid;
ans = -1e8, min_value = 1e8;
for (int i = f; i <= n; i++)
{
min_value = min(min_value, s[i - f]);
ans = max(ans, s[i] - min_value);
}
if (ans >= 0) l = mid;
else r = mid;
}
cout << (int)(r * 1000) << endl;
return 0;
}
.png)