摘要
Title: Acwing 第 44 场周赛
Tag: BFS、质因子分解

第 44 场周赛

A AcWing 4317. 不同正整数的个数

题意

给定 n 个非负整数 a1,a2,…,an。
请你计算其中共有多少个不同的正整数。
思路

直接放进set即可

代码

'''
Author: NEFU AB-IN
Date: 2022-03-26 18:53:57
FilePath: \ACM\Acwing\44\a.py
LastEditTime: 2022-03-26 19:01:13
'''
n = int(input())
s = set()
a = list(map(int, input().split()))

for i in a:
    if i > 0: s.add(i)
print(len(s))

B AcWing 4318. 最短路径

题意

见原题
思路

几步步骤：
* 首先判断是否终点与起点相同
* 判断是否有环
* 判断这条路径是不是最短路径，用BFS将能走的路径跑一遍即可

代码

'''
Author: NEFU AB-IN
Date: 2022-03-26 18:54:01
FilePath: \ACM\Acwing\44\b.py
LastEditTime: 2022-03-27 19:51:54
'''
from collections import Counter, deque

N = 550
B = N // 2
g = [[0] * N for _ in range(N)]
s = input()
d = Counter(s)

if d['L'] == d['R'] and d['U'] == d['D']:  #判断是否起点终点相同
    print("NO")
    exit(0)

x1, y1 = B, B  #起点
g[x1][y1] = 1

#判断是否有环
for i in s:
    if i == 'L': x1 -= 1
    if i == 'R': x1 += 1
    if i == 'U': y1 += 1
    if i == 'D': y1 -= 1
    if g[x1][y1]:
        print("NO")
        exit(0)
    g[x1][y1] = 1

#BFS
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
q = deque()
q.appendleft([B, B, 0])
while q:
    x, y, cnt = q.pop()
    if x == x1 and y == y1:
        break
    for i in range(4):
        x2 = x + dx[i]
        y2 = y + dy[i]
        if g[x2][y2] == 1:
            q.appendleft([x2, y2, cnt + 1])
            g[x2][y2] = 0

if cnt != len(s):
    print("NO")
    exit(0)

print("YES")

C AcWing 4319. 合适数对

题意

给定一个长度为 n 的正整数数列 a1,a2,…,an 和一个正整数 k。
请你判断共有多少个数对 (l,r) 同时满足：
1≤l<r≤n
存在一个整数 x 使得 al×ar=xk 成立
思路

将所有数x质因子分解，记录一个数为x的互补数，每次判断前面是否有互补数即可

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int cnt[N];

int power(int a, int b)
{
    LL res = 1;
    while (b -- )
    {
        res *= a;
        if (res >= N) res = 0;
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    LL res = 0;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        LL y = 1, z = 1;
        for (int i = 2; i * i <= x; i ++ )
            if (x % i == 0)
            {
                int s = 0;
                while (x % i == 0) x /= i, s ++ ;
                s %= m;
                if (s) 
                {
                    y *= power(i, s);
                    z *= power(i, m - s);
                }
            }

        if (x > 1) y *= x, z *= power(x, m - 1);
        if (z >= N) z = 0;

        res += cnt[z];
        cnt[y] ++ ;
    }

    printf("%lld\n", res);
    return 0;
}

第 44 场周赛

A AcWing 4317. 不同正整数的个数

题意

思路

代码

B AcWing 4318. 最短路径

题意

思路

代码

C AcWing 4319. 合适数对

题意

思路

代码