当前位置:网站首页>cf:H. Maximal AND【位运算练习 + k次操作 + 最大And】
cf:H. Maximal AND【位运算练习 + k次操作 + 最大And】
2022-07-06 00:38:00 【白速龙王的回眸】
分析
and就是只要有一个0这个位置还是0
所以我们统计31个bit的含1的个数
然后贪心,从最高位看起,只要有在k以内的我们就加到ans中(加2 ** i)
这个就是位运算展开成dict,然后从最高位贪心下来
只要得到某一个高位,就是赚了
所以从高位开始贪心
ac code
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
bitDict = {
}
for i in range(31):
bitDict[i] = 0
for aa in a:
#print(bin(aa)[2:].zfill(31))
bin_str = (bin(aa)[2:].zfill(31))[::-1]
for i in range(31):
if bin_str[i] == '1':
bitDict[i] += 1
ans = 0
# greedy
for i in range(30, -1, -1):
# normal add 1
if k >= n - bitDict[i]:
ans += 2 ** i
k -= n - bitDict[i]
print(ans)
总结
位运算 + and + 贪心
边栏推荐
- Pointer - character pointer
- [simple implementation of file IO]
- 猿桌派第三季开播在即,打开出海浪潮下的开发者新视野
- How to solve the problems caused by the import process of ecology9.0
- Lone brave man
- AtCoder Beginner Contest 254【VP记录】
- anconda下载+添加清华+tensorflow 安装+No module named ‘tensorflow‘+KernelRestarter: restart failed,内核重启失败
- 数据分析思维分析方法和业务知识——分析方法(二)
- STM32 key chattering elimination - entry state machine thinking
- Model analysis of establishment time and holding time
猜你喜欢
notepad++正则表达式替换字符串
[groovy] JSON serialization (jsonbuilder builder | generates JSON string with root node name | generates JSON string without root node name)
Analysis of the combination of small program technology advantages and industrial Internet
Atcoder beginer contest 254 [VP record]
SAP Spartacus home 页面读取 product 数据的请求的 population 逻辑
Model analysis of establishment time and holding time
LeetCode 1598. Folder operation log collector
Anconda download + add Tsinghua +tensorflow installation +no module named 'tensorflow' +kernelrestart: restart failed, kernel restart failed
Go learning - dependency injection
Multithreading and high concurrency (8) -- summarize AQS shared lock from countdownlatch (punch in for the third anniversary)
随机推荐
Folding and sinking sand -- weekly record of ETF
Spark DF增加一列
Start from the bottom structure and learn the introduction of fpga---fifo IP core and its key parameters
For a deadline, the IT fellow graduated from Tsinghua suddenly died on the toilet
Analysis of the combination of small program technology advantages and industrial Internet
Lone brave man
How spark gets columns in dataframe --column, $, column, apply
An understanding of & array names
[designmode] Decorator Pattern
STM32 key chattering elimination - entry state machine thinking
MySQL存储引擎
Spark SQL空值Null,NaN判断和处理
About the slmgr command
Idea远程提交spark任务到yarn集群
curlpost-php
The third season of ape table school is about to launch, opening a new vision for developers under the wave of going to sea
Promise
Global and Chinese market of valve institutions 2022-2028: Research Report on technology, participants, trends, market size and share
Global and Chinese markets for hinged watertight doors 2022-2028: Research Report on technology, participants, trends, market size and share
Extracting profile data from profile measurement