2022/2/1模拟、枚举和贪心自学

本文主要是介绍2022/2/1模拟、枚举和贪心自学，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

听课部分：（9:00~15:00）

例17：Flip Game
先考虑结论：若按一个按钮两次则无意义
思路：枚举第一行的按法，共2^4种按法并往下推由于下一行只能去影响上一行所以下一行的按法唯一。
如何存放？用int就可以存放所谓的二进制数字串
位运算
<<左移，>>右移，|或，&与，~取反，^异或
在例17中，利用左移，右移和异或即可完成开关的操作
要注意的是，比较运算符的优先级高于位运算符，所以两者同时出现时必须要打括号。

加强版

有N*M个灯泡(N<=10,M<=100)

思路：枚举N，所以总复杂度为M*(2^N)

位运算基础练习

1.去掉最后一位：x>>1

2.在最后加一个0：x<<1

3.在最后加一个1：(x<<1)+1     (x<<1|1)

4.把最后一位变成1：x|1

5.把最后一位变成0：(x|1)-1     (x>>1)<<1

6.最后一位取反：x^1

7.把右数第k位变成1：x|(1<<(k-1))

8.把右数第k位变成0：(x|(1<<(k-1)))^(1<<(k-1))     x&(~(1<<(k-1)))

9.右数第k位取反：x^(1<<(k-1))

例19：点名

已知n个同学的学号，现在有一场活动，来了n-1个同学，他们每个人都把自己的学号写了下来，告诉你这n-1个同学的学号，问哪个同学没来。

思路

n小，学号小：开数组用下标哈希

n小，学号比较大：sort两个数组，从左往右遍历，到第一个不一样的为止

n大，学号比较大：开longlong将所有同学的学号相加，减去n-1个同学的学号剩余的即是没来的

n大，学号非常大：开高精（？）呸呸呸。先开一个longlong，利用异或两个相同的数会还原的思想即可

如果有两个同学没来怎么办？

先开longlong，求出总异或和再还原为两个没来的同学的异或和，由于不存在两个学号相同的同学，必然不可能该异或和全为0；对于异或和为1的某一位，必然有两个同学该位不同（在2进制下），据此可以把所有同学分为两堆，分别是该位为0的和该位为1的。之后，两堆中每堆就只有一个没来的同学，就回归到了在一堆中求一个没来同学的问题了。

例18：NC110113 CF333E Summer Earings

N个点，任选其中三个作为圆心画三个半径相同的圆，圆不能相交，求能画圆的最大的半径为多少(N<=3000)

说实话挺难的，本新手基本听不懂

这篇关于2022/2/1模拟、枚举和贪心自学的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！