CCF CAT- 全国算法精英大赛（2024第二场）往届真题练习 3 | 珂学家
前言
这是2024年第一场CCF初赛的题， 其实整场比赛，感觉不是特别难，就是码量大，偏模拟和数学。
对于A题，摩斯密码，很容易抄错，我一直在想有什么好办法可以规避它，是真的苦涩。
真题
摩斯密码
思路: 模拟题
真的太容易错了
from collections import defaultdict
mp = defaultdict(str)
mp['.-'] = 'A'
mp['-...'] = 'B'
mp['-.-.'] = 'C'
mp['-..'] = 'D'
mp['.'] = 'E'
mp['..-.'] = 'F'
mp['--.'] = 'G'
mp['....'] = 'H'
mp['..'] = 'I'
mp['.---'] = 'J'
mp['-.-'] = 'K'
mp['.-..'] = 'L'
mp['--'] = 'M'
mp['-.'] = 'N'
mp['---'] = 'O'
mp['.--.'] = 'P'
mp['--.-'] = 'Q'
mp['.-.'] = 'R'
mp['...'] = 'S'
mp['-'] = 'T'
mp['..-'] = 'U'
mp['...-'] = 'V'
mp['.--'] = 'W'
mp['-..-'] = 'X'
mp['-.--'] = 'Y'
mp['--..'] = 'Z'
mp['.----'] = '1'
mp['..---'] = '2'
mp['...--'] = '3'
mp['....-'] = '4'
mp['.....'] = '5'
mp['-....'] = '6'
mp['--...'] = '7'
mp['---..'] = '8'
mp['----.'] = '9'
mp['-----'] = '0'
mp['..--..'] = '?'
mp['-..-.'] = '/'
mp['-.--.-'] = '()'
mp['-....-'] = '-'
mp['.-.-.-'] = '.'
arr = input().split('.')
res = []
for s in arr:
s = s.replace('1', '-')
s = s.replace('0', '.')
#print (mp[s])
res.append(mp[s])
print(''.join(res))
光线折射
光线映射，引入方向，然后模拟之。
我在想，是不是可以用初中物理那种做法，然后映入坐标映射转换。
w, h = list(map(int, input().split()))
dirs = [(1, 1), (-1, 1), (-1, -1), (1, -1)]
x, y = 0, 0
d = 0
for _ in range(3):
if d == 0:
dy, dx = h - y, w - x
if dy == dx:
y, x = h, w
d = 2
elif dy > dx:
y, x = y + (w - x), w
d = 1
else:
y, x = h, x + (h - y)
d = 3
elif d == 1:
dy, dx = abs(y - h), abs(x)
if dy == dx:
y, x = h, 0
d = 3
elif dy > dx:
y, x = y + x, 0
d = 0
else:
y, x = h, x - dy
d = 2
elif d == 2:
dy, dx = y, x
if dy == dx:
y, x = 0, 0
d = 0
elif dy > dx:
y, x = y - dx, 0
d = 3
else:
y, x = 0, x - dy
d = 1
elif d == 3:
dy, dx = y, w - x
if dy == dx:
y, x = 0, w
d = 1
elif dy > dx:
y, x = y - dx, w
d = 2
else:
y, x = 0, x + dy
d = 0
print (x, y)
多项式还原
思路: n+1进制
诈骗题，如果能提取到关键的信息，其实就能快速秒了这题。
这题核心就是 n+1 进制构造
n, m = list(map(int, input().split()))
res = []
i = 0
while m > 0:
r = m % (n + 1)
if r > 0:
res.append((r, i))
i += 1
m = m // (n + 1)
rs = []
for (k, v) in reversed(res):
s = ""
if k > 1:
s += str(k)
if v > 1:
s += "x^" + str(v)
elif v == 1:
s += "x"
else:
if v > 1:
s += "x^" + str(v)
elif v == 1:
s += "x"
else:
s += str(1)
rs.append(s)
print('+'.join(rs))
开心消消乐
经典的回溯问题，很游戏向的一道题
其实蛮折磨人的一道题，即考察dfs又考察bfs。
n, m = list(map(int, input().split()))
grid = []
for _ in range(n):
row = list(map(int, input().split()))
grid.append(row)
from collections import deque
def bfs(chess, r, c, vis):
res = []
h, w = len(chess), len(chess[0])
deq = deque()
deq.append((r, c))
vis[r][c] = True
res.append((r, c))
while len(deq) > 0:
y, x = deq.popleft()
for (dy, dx) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
ty, tx = y + dy, x + dx
if 0 = 0:
while ty2 >= 0 and nchess[ty2][tx] == 0:
ty2 -= 1
if ty2
等式
思路: 质数筛 + 分子分解
偏数论的一道题
要做好优化，不然容易TLE
大概是预处理筛表
O
(
n
)
O(n)
O(n)+
m
n
,
m
为
n
以内的质数个数
m \sqrt {n}, m为n以内的质数个数
mn
,m为n以内的质数个数
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
boolean[] vis = new boolean[n + 1];
Arrays.fill(vis, true);
vis[0] = vis[1] = false;
List primes = new ArrayList();
List primes2 = new ArrayList();
for (int i = 2; i
if (vis[i]) {
primes.add(i);
if (i n / i) continue;
primes2.add(i);
for (int j = i * i; j
vis[j] = false;
}
}
}
long res = 0;
for (int v: primes) {
if (n
if (cn
写在最后
