AKSZ-贪心算法
2024-03-24 17:38:52
发布于:广东
第三课
1.贪心
英文:greedy
不从整体最优上考虑,算法得到的是某种意义上的局部最优解
贪心算法没有固定的模板,重要的是贪心策略的选择
结构体排序
struct node{
int p,h;
friend bool operator <(node a,node b){
return a.p<b.p;
}
}a[maxn];
bool cnp(node A,node B){
return A.p<B.p;
}
后效性
前面的贪心决策会影响后面的贪心决策
因此
没有后效性才能使用贪心算法
2.任意进制转十进制
x进制:abc.cde
结果:
3.位运算
1.按位与&
按位与&的运算规则,将两个二进制低位对齐,不足高位补零。对两个数字进行比较,只有当两个相应的二进制位都为1时,结果的相应位才为1,其余为0.
例如:计算7&10
0111&1010=0010
应用:x&(x-1)=0
是否为2的幂次
2.按位或|
按位或|的运算规则,将两个二进制低位对齐,不足高位补零。对两个数字进行比较,只有当两个相应的二进制位都为0时,结果的相应位才为0,其余为1.
例如:计算6|10
0110|1010=1110
3.按位非~
按位非·~的运算规则,将一个二进制每一位取反,0变1,1变0.
例如:计算~6
~0110=1001
注意:1.按位非运算会修改符号位,因此与实际结果不一致
2.~-1=0
4.按位异或^
按位异或^的运算规则,将两个二进制低位对齐,不足高位补零。对两个数字进行比较,当两个位相同时为0,不同时为1
5.按位右移>>
按位右移>>的运算规则,>>a就将二进制右移a位,高位丢弃,低位补零
相当于除二
6.按位左移<<
按位右移<<的运算规则,<<a就将二进制左移a位,高位丢弃,低位补零
相当于乘二
7.运算优先级
1.按位非~
2.左移右移
3.按位与&
4.按位异或^
5.按位或|
这里空空如也
有帮助,赞一个