[acwing周赛复盘] 第 64 场周赛20220813

一、本周周赛总结

• 本周4题，前两题一道A+B，一道endswith水题就不放了。
• T4不会做鸽了。
• 就放个T3吧
• 另外这什么版本的python前缀和竟然不支持initial参数，得换个写法：pre = [0] + list(accumulate(a, func=xor))
• 

二、 4507. 子数组异或和

链接: 4507. 子数组异或和

1. 题目描述

2. 思路分析

异或的性质比较特殊，这里用到了前缀异或和+哈希。
通常这种区间计数问题又需要O(n)复杂度，都是这种套路优化

• 两个数如果相等的话，异或和是0，因此想到可以用前缀和来做。
• 如果pre[j+1] xor pre[i] == 0（pre[j+1]= pre[i]）,代表[i,j]本段异或和是0，而如果这段内异或和是0的话，对这段无论怎么切割，切出来的两段的异或和a,b必相等，因为a xor b = 0。

3. 代码实现

import io
import os
import sys
from collections import deque, Counter
from itertools import accumulate
from operator import xor

if sys.hexversion == 50923504:
    sys.stdin = open('input.txt')
else:
    input = sys.stdin.readline
MOD = 10 ** 9 + 7


def sovle(n, a):
    pre = [0] + list(accumulate(a, func=xor))
    # print(pre)
    c = Counter()
    ans = 0
    for i, v in enumerate(pre):
        ji = i & 1
        ans += c[(ji, v)]
        c[(ji, v)] += 1

    print(ans)


if __name__ == '__main__':

    if False:
        n = int(input())
        m, n = map(int, input().split())
        s = list(map(int, input().split()))

    n = int(input())
    x = list(map(int, input().split()))
    sovle(n, x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

三、4508. 移动的点

链接: 4508. 移动的点

1. 题目描述

2. 思路分析

这题不会，等大佬讲解再补吧。

• 看了题解，补上。
• 对2个点来说，他们的相对速度是可以计算出来的vx12=vx1-vx2,vy12=vy1-vy2。
• 一开始所有点都共线y=ax+b,那么如果两个点过去/未来能相撞，那么它们相对速度的方向一定是沿着共线的方向，即斜率为a。
• 那么我们整理一下公式
• 
• 用哈希表记录下来每个斜率有多少个点即可。
• 但是我们发现会有平行点的情况，需要另开一个哈希表，记录每种相同速度的点有多少个，减去这种情况。

3. 代码实现

import io
import os
import sys
from collections import deque, Counter
from itertools import accumulate
from operator import xor

if sys.hexversion == 50923504:
    sys.stdin = open('input.txt')
else:
    input = sys.stdin.readline
MOD = 10 ** 9 + 7


def sovle(n, a, b, xs):
    c = Counter()
    d = Counter()
    ans = 0
    for _, vx, vy in xs:
        k = vy - a * vx
        ans += c[k] - d[(vx, vy)]
        c[k] += 1
        d[(vx, vy)] += 1

    print(ans * 2)


if __name__ == '__main__':

    if False:
        n = int(input())
        m, n = map(int, input().split())
        s = list(map(int, input().split()))

    n, a, b = map(int, input().split())
    xs = []
    for _ in range(n):
        xs.append(list(map(int, input().split())))
    sovle(n, a, b, xs)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40