[acwing周赛复盘] 第 69 场周赛20220917

[acwing周赛复盘] 第 69 场周赛20220917

    • 一、本周周赛总结
    • 二、4615. 相遇问题
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 三、4616. 击中战舰
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 四、4617. 解方程
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 六、参考链接

一、本周周赛总结

  • T2卡半天很难受,赛后得知是9月6号下午茶原题,更难受了。
  • T3位运算找纸笔找半天,很难受。
  • 总之难受。 [acwing周赛复盘] 第 69 场周赛20220917_第1张图片

[acwing周赛复盘] 第 69 场周赛20220917_第2张图片

二、4615. 相遇问题

链接: 4615. 相遇问题

1. 题目描述

[acwing周赛复盘] 第 69 场周赛20220917_第3张图片

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. 题目描述

[acwing周赛复盘] 第 69 场周赛20220917_第4张图片

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. 题目描述

[acwing周赛复盘] 第 69 场周赛20220917_第5张图片

2. 思路分析

这题找纸笔找半天,难受啊。

位运算知识。

  • 这题涉及到异或,异或是个性质很特殊的运算:
    • 通常如果搜索题出现异或,即状态转移通经过异或,则一般都需要遍历,因为很难有累计公式。
    • 异或同时具有加法和减法的性质:不进位的加法/不借位的减法。
  • 说回这题,由于题目给出的公式很难搞,我们先简单转化一下:a-x=a^x。
  • 题目转化为,有多少个x满足被a-x=a^x。
  • 即多少个x能满足:异或即减法
  • 我们列一下01的异或组合发现:
    1. 1^0=1-0
    2. 1^1=1-1
    3. 0^1=1!=0-1
    4. 0^0=0-0
  • 也就是说,当a的对应位是0的时候,x对应位只能是0,一种情况;
  • 当a的对应位是1的时候,x对应位可以是1或者0,都满足减法等于异或。
    [acwing周赛复盘] 第 69 场周赛20220917_第6张图片

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)



六、参考链接

你可能感兴趣的