第二届ACC(AcWing Cup)全国联赛
摘要
Title: 第二届ACC(AcWing Cup)全国联赛
Tag: 进制、BFS
Powered by:NEFU AB-IN
第二届ACC(AcWing Cup)全国联赛
-
A AcWing 4941. 凑数
-
题意
https://www.luogu.com.cn/problem/CF579A
略
-
思路
其实就是数这个数的二进制位中有多少个1
（当时想的是，把dp方程写了出来，发现可以一直除以二，直到奇数就减一，再一直除以二） -
代码
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/*
* @Author: NEFU AB-IN
* @Date: 2023-04-02 18:49:27
* @FilePath: \Acwing\ACC2\a\a.cpp
* @LastEditTime: 2023-04-02 19:15:54
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
signed main()
{
IOS;
int n, ans = 0;
cin >> n;
while (n)
{
if (n % 2 == 0)
n /= 2;
else
{
n--;
ans++;
}
}
cout << ans;
return 0;
}
-
-
B AcWing 4942. 砝码称重
-
题意
https://www.luogu.com.cn/problem/CF552C
能否通过n的幂次的加减得到m
-
思路
可以发现m可以表示成这样的进制类型的式子，p可以取-1 0 1三个值
现在m除余n，就会得到，m除以n之后，再除余n，就会得到… 一直做下去，如果p取了它们三个中的其他值，就是无解 -
代码
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90'''
Author: NEFU AB-IN
Date: 2023-04-02 19:23:42
FilePath: \Acwing\ACC2\b\b.py
LastEditTime: 2023-04-06 19:46:18
'''
# import
import sys, math, os
from io import BytesIO, IOBase
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from typing import *
# Fast Read
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
BUFSIZE = 4096
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
# Final
N = int(1e3 + 10)
INF = int(2e9)
# Define
sys.setrecursionlimit(INF)
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
read = lambda: map(int, input().split())
# —————————————————————Division line ————————————————————————————————————————
def check(n, m):
while m:
r = m % n
if r != 0 and r != 1 and r != n - 1:
return False
if r > 1:
r = -1
m = (m - r) // n
return True
n, m = read()
print("YES" if check(n, m) else "NO")
-
-
C AcWing 4943. 方格迷宫
-
题意
https://www.luogu.com.cn/problem/CF877D
给一个n^2的矩阵，有空地有陷阱，需要从起点走到终点，每一次可以往四个方向其中一个走最多k步，问最少走几次
-
思路
非正常BFS，需要剪枝（代码中有注释）
正常的BFS：每个点只更新一次，因为每次只走一步，代价为1；但这个的话，每次能走k步，代价还是为1；所以某个点可能会被四周的点多次更新，所以可以采取最短路的策略写，因为BFS本质就是路程为1的最短路问题，也就是双端队列广搜的模板，只不过去掉了st数组，因为每个点会被走到多次 -
代码
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87/*
* @Author: NEFU AB-IN
* @Date: 2023-04-02 18:49:27
* @FilePath: \Acwing\ACC2\c\c.cpp
* @LastEditTime: 2023-04-06 22:13:53
*/
// #pragma GCC optimize(1)
// #pragma GCC optimize(2) // 先开优化
// #pragma GCC optimize(3, "Ofast", "inline")
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 10, INF = 0x3f3f3f3f;
int n, m, k;
struct sa
{
int x, y;
} s[N];
int sx, sy, ex, ey;
int dist[N][N];
char g[N][N];
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int bfs()
{
queue<sa> q;
q.push({sx, sy});
memset(dist, 0x3f, sizeof dist);
dist[sx][sy] = 0;
while (SZ(q))
{
auto t = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
for (int j = 1; j <= k; ++j)
{
int x = t.x + j * dir[i][0];
int y = t.y + j * dir[i][1];
if (x < 1 || x > n || y < 1 || y > m || g[x][y] == '#')
break;
if (dist[x][y] < dist[t.x][t.y] + 1)
// 在一个方向上枚举时，如果到达点的最短步数(dist[x][y])小于等于当前点(dist[t.x][t.y])的位置，就立马
// break 掉
// 因为到达点的距离就不用目前点更新，所以目前点就可以直接break
break;
if (dist[x][y] > dist[t.x][t.y] + 1)
{
dist[x][y] = dist[t.x][t.y] + 1;
if (x == ex && y == ey) // 直接判断，防止多循环一次
return dist[x][y];
q.push({x, y});
}
}
}
}
return -1;
}
signed main()
{
// IOS;
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i)
{
cin >> (g[i] + 1);
}
cin >> sx >> sy >> ex >> ey;
if (sx == ex && sy == ey)
cout << "0\n";
else
cout << bfs() << '\n';
return 0;
}
-