T1 扑克牌

查看答案与解析
题目给出已有的牌,要求计算最少需要补充多少张牌才能凑齐一副完整的扑克牌(52张)。给出的扑克牌可能包含重复的牌(即花色和点数都相同的牌),因此需要去重后计算缺失的牌数。
T1 扑克牌

题目给出已有的牌,要求计算最少需要补充多少张牌才能凑齐一副完整的扑克牌(52张)。给出的扑克牌可能包含重复的牌(即花色和点数都相同的牌),因此需要去重后计算缺失的牌数。
T2 地图探险

需要的变量 / 数组
描述机器人状态需要的3个变量:
x:位置。
y:位置。
d:朝向(0~3)。
vis数组:
当机器人走过[x, y],vis[x][y] = true。
dir数组:
dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}。
[x + dir[d][0], y + dir[d][1]]表示当机器人朝向为d时往前走一步之后的位置。
d = 0: 右 (0, 1)。
d = 1: 下 (1, 0)。
d = 2: 左 (0, -1)。
d = 3: 上 (-1, 0)。
核心思想
vis[x][y] = true;
while (k--) {
int nx = x + dir[d][0], ny = y + dir[d][1]; // 计算下一步的位置
if (!(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.')) { // 是否能走
d = (d + 1) % 4; // 若不能走 右转
continue;
}
x = nx, y = ny; // 若能走 更新
vis[nx][ny] = true;
}
T3 小木棍

拼出0~9分别需要的木棍数量:

求解思想:
因为拼出8所需的木棍最多(7根),所以用8,可以使位数更少
在保证位数最少的前提下,还要尽可能把高位的数字变小(必须保证位数最小)
按照思想,可以找到这样的规律:

T4 接龙

解题思路
本文的解题思想为dp。
dp[r][x]:接龙 r 轮、以 x 结尾的状态:
dp[r][x] = -1:不可实现。
dp[r][x] = i(一个自然数):可以通过词库 i 实现(最后一次接龙操作使用的是词库 i 中的某个连续子序列)。
dp[r][x] = -2:可以通过多个词库实现。
代码解析
完整的求解部分:
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
dp[0][1] = -2;
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i;
else if (dp[r][tmp] != i)
dp[r][tmp] = -2;
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;
}
}
}
return dp;
}逐行分析
mx:所有词库中的最大值,用于构建dp的第二个维度。
dp的大小为R(最大轮数) * mx(所有词库中的最大值)。
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));dp[0][1] = -2:作为虚拟起点,使得第一次接龙可以从数字 1 开始。
dp[0][1] = -2;
r:轮数。
i:尝试让第 i 个人接龙。
j:第 i 个人词库中第 j 个词语。
lst:当前序列 i 中最近一个满足接龙条件的起始位置(可以以lst为起点开始接龙)。
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
}
}
}获取当前人员 i 的词库中第 j 个词语。
如果当前词库中有一个合适的起点可以开始接龙,并且长度合适:
那么选择子序列[lst, j]开始接龙。
更新当前状态。
如果上一轮接龙不是 i 在接龙,并且可以以tmp结束,那么这一轮也可以从tmp开始接龙。
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i; // 首次发现路径则记录序列i
else if (dp[r][tmp] != i)
dp[r][tmp] = -2; // 若已有其他序列可达则标记为多路径(-2)
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;