[acwing周赛复盘] 第 69 场周赛20220917
[acwing周赛复盘] 第 69 场周赛20220917
- 一、本周周赛总结
- 二、4615. 相遇问题
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 三、4616. 击中战舰
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 四、4617. 解方程
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 六、参考链接
一、本周周赛总结
- T2卡半天很难受,赛后得知是9月6号下午茶原题,更难受了。
- T3位运算找纸笔找半天,很难受。
- 总之难受。
二、4615. 相遇问题
链接: 4615. 相遇问题
1. 题目描述
2. 思路分析
签到题,速度加起来计算时间。
最后乘回去判断整除。
3. 代码实现
import collections
import io
import os
import sys
from collections import deque
if sys.hexversion == 50923504:
sys.stdin = open('input.txt')
RI = lambda: map(int, input().split())
else:
input = sys.stdin.readline
input_int = sys.stdin.buffer.readline
RI = lambda: map(int, input_int().split())
RS = lambda: input().strip().split()
RILST = lambda: list(RI())
MOD = 10 ** 9 + 7
def solve(x,y,a,b):
# print(x,y,a,b)
ans = (y-x)//(a+b)
if ans * (a+b) == y-x:
print( ans)
return
print(-1)
if __name__ == '__main__':
t, = RI()
for _ in range(t):
x,y,a,b = RI()
solve(x,y,a,b)
三、4616. 击中战舰
链接: 4616. 击中战舰
1. 题目描述
2. 思路分析
CF原题
- 先扫描所有已经攻击过的位置,由于这些位置上都没有船,那么船都分布在空位中。
- 处理出所有空位,计算每个空位最多能放多少艘船,假设是c;现在已知有a艘船,那么这a艘船分布在这c个位置里。
- 每次打击的最优方案显然是每次覆盖一艘船,我们如果打c-a次,可能正好打不中,那么打hit = c-a+1次就可以了。
- 从空位中找hit个位置即可。
3. 代码实现
import collections
import io
import os
import sys
from collections import deque
from functools import lru_cache
if sys.hexversion == 50923504:
sys.stdin = open('input.txt')
RI = lambda: map(int, input().split())
else:
input = sys.stdin.readline
input_int = sys.stdin.buffer.readline
RI = lambda: map(int, input_int().split())
RS = lambda: input().strip().split()
RILST = lambda: list(RI())
MOD = 10 ** 9 + 7
def solve(n, a, b, s):
ks = [-1]
for i, v in enumerate(s):
if v == '1':
ks.append(i)
ks.append(n)
kong = []
c = 0
for i in range(1, k + 2):
d = ks[i] - ks[i - 1] - 1
c += d // b
kong.append((d, ks[i - 1], ks[i]))
hit = c - a + 1
print(hit)
ans = []
for d,i,j in kong:
while i+b< j:
i += b
ans.append(i)
if len(ans) == hit:
print(' '.join(map(lambda x: str(x + 1), ans)))
return
if __name__ == '__main__':
n, a, b, k = RI()
s, = RS()
solve(n, a, b, s)
四、4617. 解方程
链接: 4617. 解方程
1. 题目描述
2. 思路分析
这题找纸笔找半天,难受啊。
位运算知识。
- 这题涉及到异或,异或是个性质很特殊的运算:
- 通常如果搜索题出现异或,即状态转移通经过异或,则一般都需要遍历,因为很难有累计公式。
- 异或同时具有加法和减法的性质:不进位的加法/不借位的减法。
- 说回这题,由于题目给出的公式很难搞,我们先简单转化一下:a-x=a^x。
- 题目转化为,有多少个x满足被a-x=a^x。
- 即多少个x能满足:异或即减法
- 我们列一下01的异或组合发现:
- 1^0=1-0
- 1^1=1-1
- 0^1=1!=0-1
- 0^0=0-0
- 也就是说,当a的对应位是0的时候,x对应位只能是0,一种情况;
- 当a的对应位是1的时候,x对应位可以是1或者0,都满足减法等于异或。
3. 代码实现
import collections
import io
import os
import sys
from bisect import bisect_right
from collections import *
from itertools import accumulate
from math import inf
if sys.hexversion == 50923504:
sys.stdin = open('input.txt')
RI = lambda: map(int, input().split())
else:
input = sys.stdin.readline
input_int = sys.stdin.buffer.readline
RI = lambda: map(int, input_int().split())
RS = lambda: input().strip().split()
RILST = lambda: list(RI())
MOD = 10 ** 9 + 7
def solve(a):
# a = 1
# print(a)
c = bin(a).count('1')
# a.bit_count() py3.10以上才有
print(2**c)
if __name__ == '__main__':
t, = RI()
for _ in range(t):
a, = RI()
solve(a)
六、参考链接
- 无