前言

这是2024年第一场CCF初赛的题， 其实整场比赛，感觉不是特别难，就是码量大，偏模拟和数学。

对于A题，摩斯密码，很容易抄错，我一直在想有什么好办法可以规避它，是真的苦涩。

真题

摩斯密码

思路: 模拟题

真的太容易错了

from collections import defaultdictmp = 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, 0d = 0for _ 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 = 0print (x, y)

多项式还原

思路: n+1进制

诈骗题，如果能提取到关键的信息，其实就能快速秒了这题。

这题核心就是 n+1 进制构造

n, m = list(map(int, input().split()))res = []i = 0while 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 dequedef 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 <= ty < h and 0 <= tx < w and not vis[ty][tx] and chess[ty][tx] == chess[r][c]: vis[ty][tx] = True res.append((ty, tx)) deq.append((ty, tx)) return res# 经典的DFS回溯问题def dfs(chess): score = 0 h, w = len(chess), len(chess[0]) vis = [[False] * w for _ in range(h)] for i in range(h): for j in range(w): if not vis[i][j] and chess[i][j] != 0: cs = bfs(chess, i, j, vis) if len(cs) >= 3: nchess = [chess[x][:] for x in range(h)] for (ty, tx) in cs: nchess[ty][tx] = 0 for tx in range(w): ty = h - 1 ty2 = h - 1 while ty >= 0: while ty2 >= 0 and nchess[ty2][tx] == 0: ty2 -= 1 if ty2 < 0: nchess[ty][tx] = 0 else: nchess[ty][tx] = nchess[ty2][tx] ty -= 1 ty2 -= 1 r1 = dfs(nchess) score = max(score, r1 + len(cs)) return scoreres = dfs(grid)print (res)

等式

思路: 质数筛 + 分子分解

偏数论的一道题

要做好优化，不然容易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<Integer> primes = new ArrayList<>(); List<Integer> primes2 = new ArrayList<>(); for (int i = 2; i <= n; i++) { if (vis[i]) { primes.add(i); if (i > n / i) continue; primes2.add(i); for (int j = i * i; j <= n; j += i) { vis[j] = false; } } } long res = 0; for (int v: primes) { if (n <= v) break; int r = 1; int cn = n - v; if (vis[cn]) continue; for (int u: primes2) { if (cn < u) break; if (u > cn / u) break; if (cn % u == 0) { int t = 0; while (cn % u == 0) { t++; cn /= u; } r = r * (t + 1); } } if (cn > 1) r = r * 2; res += r; } System.out.println(res); }}

写在最后