一、上机打卡1.1 FJ的字符串1.1.1 题目FJ在沙盘上写了这样一些字符串A1 “A”A2 “ABA”A3 “ABACABA”A4 “ABACABADABACABA”… …你能找出其中的规律并写所有的数列AN吗仅有一个数N ≤ 20。请输出相应的字符串AN以一个换行符结束。输出中不得含有多余的空格或换行、回车符。输入范例3输出范例ABACABA1.1.2 总结这个算法通过观察字符串序列的构造规律发现每一个字符串都是由前一个字符串、一个新的大写字母以及再次重复的前一个字符串拼接而成的。由于程序只需要按顺序打印字符而无需在内存中维护庞大的中间字符串这种直接输出的递归策略能有效节省空间开销在有效的时间复杂度内完成任务。当递归深度降至 1 时直接输出字符 A否则先递归调用函数输出前缀部分随后通过字符偏移计算输出当前层级的核心字符最后再次递归调用完成后缀拼接。1.1.3 代码#include iostream using namespace std; // 递归生成并直接输出AN序列 void solve(int n) { if (n 1) { cout A; return; } // 递归输出左侧部分 solve(n - 1); // 输出中间的字母n2时为Bn3时为C以此类推 cout (char)(A n - 1); // 递归输出右侧部分 solve(n - 1); } int main() { int n; if (cin n) { solve(n); cout endl; } return 0; }1.2 3000米排名预测1.2.1 题目3000米长跑时围观党们兴高采烈地预测着最后的排名。因为他们来自不同的班对所有运动员不一定都了解于是他们分别对自己了解的一些运动员的实力作出了评估即对部分运动员做了相对排名的预测并且告诉了可怜留守的班长。因为无聊于是他们就组团去打Dota去了。比赛结束后他们向班长询问最后的排名但班长不记得了只记得他们中哪些人的预测是正确的哪些人的预测是错误的。他们想知道比赛的排名可能是什么。第一行两个整数n mn为运动员数量m为围观党数量。运动员编号从0到n-1。接下来m行每行为一个围观党的相对排名预测。每行第一个数c表示他预测的人数后面跟着c个0~n-1的不同的数表示他预测的运动员相对排名最后还有一个数0表示这个预测是错误的1表示是正确的。数据规模和约定1n10, 2cn, 1m10保证数据合法且答案中排名可能数不超过20000。对于一个排名序列一个预测是正确的当且仅当预测的排名的相对顺序是排名序列的一个子序列。一个预测是错误的当且仅当这个预测不正确。第一行一个数k为有多少种排名的可能。下面k行每行一个0~n-1的排列为某一个可能的排名每个数字后有一个空格即行尾也有一个空格。所有排名按字典序依次输出。比如输入3 22 0 1 12 2 1 0则输出10 1 2输入范例3 22 0 1 12 1 2 0输出范例20 2 12 0 11.2.2 总结该算法通过全排列枚举与子序列匹配相结合的策略解决排名预测问题。考虑到运动员数量最多为 10总的可能排名数量即 10 的阶乘约为三百六十万种在给定的时间限制内可以通过暴力搜索结合高效剪枝完成。首先利用递归函数生成所有可能的运动员排名全排列。对于每一种生成的排列依次校验所有围观党的预测。校验的核心在于判断预测序列是否为当前排名序列的子序列。具体实现时针对每个预测在排名序列中按顺序寻找预测的每一个运动员若能依次找齐则该预测在当前排名下为真。最后将所有预测的实际真假情况与班长记忆中的对错标记进行对比只有全部吻合的排名才是合法结果。由于需要按字典序输出且总数受限算法直接在生成全排列的过程中进行实时过滤并存储结果确保了输出的有序性和时空效率。1.2.3 代码#include iostream #include vector #include algorithm using namespace std; struct Predict { int c; vectorint p; int result; // 1为正确0为错误 }; int n, m; vectorPredict predicts; vectorvectorint results; // 检查预测在当前排列下是否成立即是否为子序列 bool checkSubsequence(const vectorint order, const Predict pred) { int current 0; for (int athlete : order) { if (athlete pred.p[current]) { current; } if (current pred.c) return true; } return false; } int main() { if (!(cin n m)) return 0; for (int i 0; i m; i) { Predict pred; cin pred.c; for (int j 0; j pred.c; j) { int athlete; cin athlete; pred.p.push_back(athlete); } cin pred.result; predicts.push_back(pred); } // 生成初始排列 0, 1, ..., n-1 vectorint order(n); for (int i 0; i n; i) order[i] i; // 枚举所有全排列字典序从小到大 do { bool isValid true; for (const auto pred : predicts) { bool isCorrect checkSubsequence(order, pred); // 如果实际对错与班长记忆不符则该排列无效 if ((isCorrect ? 1 : 0) ! pred.result) { isValid false; break; } } if (isValid) { results.push_back(order); } } while (next_permutation(order.begin(), order.end())); // 输出结果 cout results.size() endl; for (const auto res : results) { for (int x : res) { cout x ; } cout endl; } return 0; }1.3 芯片测试1.3.1 题目有n2≤n≤20块芯片有好有坏已知好芯片比坏芯片多。每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时会随机给出好或是坏的测试结果即此结果与被测试芯片实际的好坏无关。给出所有芯片的测试结果问哪些芯片是好芯片。输入数据第一行为一个整数n表示芯片个数。第二行到第n1行为n*n的一张表每行n个数据。表中的每个数据为0或1在这n行中的第i行第j列1≤i, j≤n的数据表示用第i块芯片测试第j块芯片时得到的测试结果1表示好0表示坏ij时一律为1并不表示该芯片对本身的测试结果。芯片不能对本身进行测试。按从小到大的顺序输出所有好芯片的编号输入范例31 0 10 1 01 0 1输出范例1 31.3.2 总结算法的具体实现逻辑如下遍历每一列即统计每一块芯片被其他所有芯片测试的结果。对于第 j块芯片我们计算所有其他芯片i对它的测试结果中 1 的总数。如果第 j 块芯片是好的那么所有好的芯片都会给它投 1而好芯片的数量已经超过了总数的一半。因此只要第 j 列中 1 的个数大于或等于 n/2或者更稳妥地判断为大于坏芯片可能产生的最大干扰数就可以断定该芯片为好芯片。这种基于纵向统计的方法避开了坏芯片随机结果的干扰直接利用好芯片的多数优势锁定目标。1.3.3 代码#include iostream #include vector using namespace std; int main() { int n; if (!(cin n)) return 0; // 存储测试矩阵data[i][j] 表示第 i 块芯片测试第 j 块的结果 vectorvectorint data(n, vectorint(n)); for (int i 0; i n; i) { for (int j 0; j n; j) { cin data[i][j]; } } bool first true; // 纵向遍历每一列统计每块芯片被评价为“好”的次数 for (int j 0; j n; j) { int count 0; for (int i 0; i n; i) { if (data[i][j] 1) { count; } } // 核心逻辑因为好芯片比坏芯片多 // 那么所有好芯片都会给真芯片投1投1的总数必然大于 n/2 if (count n / 2) { if (!first) cout ; cout j 1; // 题目通常输出编号注意是否从1开始 first false; } } cout endl; return 0; }二、翻译打卡P1用于玩电脑游戏的设备包括索尼的PlayStation、任天堂的Wii和微软的Xbox。它们具有强大的处理能力和出色的图形但它们通常用于专门的游戏和流视频而不是运行应用程序软件。P2媒体播放器如iPod Touch通过为消费者提供可以存储和播放数千首歌曲的便携式设备彻底改变了音乐行业。这些设备由触摸屏或简单的点击轮机构控制。P3手表和时钟是首批数字化设备之一。20世纪70年代这些手表大规模生产价格低至10美元仅限于时间和日期功能。2013年三星、谷歌和高通公司推出了一种新型数字手表。这些多功能设 备被称为智能手表可以包括照相机、温度计、指南针、计算器、手机、GPS、媒体播放器和健身追踪器。一些智能手表的功能是内置在设备中的而其他功能则需要访问互联网或佩戴者的智能手机。三、单词打卡