目录T1. 冠军魔术思路分析T2. 找座位思路分析T3. 英语老师小助手思路分析T4. 奇葩楼层思路分析T5. 小偷踩点思路分析T1. 冠军魔术题目链接SOJ D12722018 年 FISM世界魔术大会近景总冠军简纶廷的表演中有一个情节以桌面上一根带子为界当他将纸牌从带子的一边推到另一边时纸牌会变成硬币把硬币推回另一边会变成纸牌。这里我们假设纸牌会变成等量的硬币而硬币变成纸牌时纸牌的数量会加倍。那么给定纸牌的初始数量当他来回推了N NN次来 / 回各算一次后手里拿的是纸牌还是硬币数量是多少时间限制1 s内存限制64 MB输入输入在一行里给出两个正整数分别是纸牌的初始数量和魔术师推送的次数。这里假设初始状态下魔术师手里全是纸牌。输出如果最后魔术师手里是纸牌输出0 00和纸牌数量如果是硬币则输出1 11和硬币数量。数字间须有1 11个空格。题目保证结果数值不超出整型范围即2 31 − 1 2^{31}-1231−1。样例输入 13 7样例输出 11 24样例输入 28 4样例输出 20 32思路分析此题考查顺序结构属于基础题。魔术师如果推了偶数次最终手里一定是纸牌否则手里一定是硬币因此第一问输出n % 2 n\%2n%2即可。由于纸牌变成硬币数量不变硬币变成纸牌数量翻倍因此⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋就是数量翻倍的次数于是最终数量为a × 2 ⌊ n / 2 ⌋ a\times 2^{\lfloor n/2 \rfloor}a×2⌊n/2⌋。/* * Name: T1.cpp * Problem: 冠军魔术 * Author: Teacher Gao. * DateTime: 2025/01/14 21:30 */#includeiostreamusingnamespacestd;intmain(){inta,n;cinan;coutn%2 (a(n/2))endl;return0;}T2. 找座位题目链接SOJ D1273组织一场考试时监考老师手里会有一份签到表按座位号的顺序列出学生。但学生要根据这份表找到自己的座位编号就很麻烦了。本题就要求你编写程序帮助学生快速找到他们的座位号。时间限制1 s内存限制64 MB输入输入第一行给出一个不超过10 3 10^3103的正整数N NN是参加考试的学生数。以下N NN行第i ii行给出座位号为i ii的学生的学号i 1 , . . , N i1, .. , Ni1,..,N。学号是一个不超过8 88位、完全由数字组成的字符串。输入保证每个学生只分配一个座位。接下来一行给出一个不超过10 5 10^5105的正整数M MM是待查询的学生数。以下M MM行每行给出一个待查询的学生的学号。输出对每一个待查询的学生如果他在考场里有座位则在一行中输出其座位号否则输出NAN o t A v a i l a b l e \tt Not\ AvailableNotAvailable的缩写表示座位号不存在。样例输入5 100013 200233 100001 520077 886759 4 520077 000000 100013 999999样例输出4 NA 1 NA思路分析此题考查字符串查找属于入门题。由于学号可能存在前导零为了方便查找将学号以字符串的形式存储到数组中。对于输入的每个学号字符串在数组中依次查找即可若匹配成功则输出对应下标否则输出NA。用m a p \tt mapmap存储每个学生的座位号可以达到O ( log ⁡ n ) O(\log n)O(logn)的查找时间复杂度或者用u n o r d e r e d _ m a p \tt unordered\_mapunordered_map可以达到O ( 1 ) O(1)O(1)的查找时间复杂度。示例代码用m a p \tt mapmap实现。/* * Name: T2.cpp * Problem: 找座位 * Author: Teacher Gao. * DateTime: 2025/01/14 21:35 */#includebits/stdc.husingnamespacestd;intmain(){intn,m;string x;mapstring,intmp;cinn;for(inti1;in;i){cinx;mp[x]i;}cinm;for(inti1;im;i){cinx;if(mp.find(x)!mp.end()){coutmp[x]\n;}else{coutNA\n;}}return0;}T3. 英语老师小助手题目链接SOJ D1274英语老师要求学生按照如下规则写一串字母规则1 11如果写了某个大写字母下一个就必须写同个字母的小写或者写字母表中前一个字母的大写规则2 22如果写了某个小写字母下一个就必须写同个字母的大写或者写字母表中下一个字母的小写。例如zZzZYXWwxyYX就是一个合法的字母串而wVUuvUTsR就是非法的。现在面对全班学生交上来的作业老师请你写个程序自动批改。时间限制5 s内存限制64 MB输入输入在第一行给出一个不超过100 100100的正整数N NN。随后N NN行每行给出一位学生的作业即仅由英文字母组成的非空字母串长度不超过2 × 10 6 2×10^62×106。输出对每位学生的作业如果正确就在一行中输出Y否则输出N。样例输入2 zZzZYXWwxyYX wVUuvUTsR样例输出Y N思路分析此题考查字符串遍历属于入门题。对于输入的每个字符串按照题目中的两个规则进行相邻字符的检测即可。/* * Name: T3.cpp * Problem: 英语老师小助手 * Author: Teacher Gao. * DateTime: 2025/01/14 21:38 */#includebits/stdc.husingnamespacestd;intmain(){intn;string s;cinn;for(inti1;in;i){cins;string ansY\n;for(intj0;js.size()-1;j){if(s[j]Zs[j1]!s[j]-1s[j1]!s[j]32){ansN\n;break;}elseif(s[j]as[j1]!s[j]1s[j1]!s[j]-32){ansN\n;break;}}coutans;}return0;}T4. 奇葩楼层题目链接SOJ D1275几乎每个国家都有自己忌讳的数字有的大楼在给楼层编号的时候会刻意跳过含有不吉利数字的编号。比如中国人比较忌讳4 44有的大楼就没有第4 44层、第14 1414层等等这样楼层的编号就会是1 11、2 22、3 33、5 55、… 即编号为5 55的楼层实际是第4 44层。那么在去掉了忌讳数字之后最高楼层编号为n nn的大楼实际上有多少层呢时间限制1 s内存限制64 MB输入输入在一行中给出2 22个整数依次为大楼最高层的编号n nn1 n ≤ 1000 1 n ≤ 10001n≤1000和某国人民忌讳的数字d dd0 ≤ d ≤ 9 0 ≤ d ≤ 90≤d≤9。题目保证n nn中不包含d dd。输出在一行中输出该大楼的实际楼层数。样例输入50 4样例输出36思路分析此题考查循环结构和数位分离属于基础题。定义变量t o t tottot记录不存在的楼层数量对1 ∼ n 1\sim n1∼n之间的每一个整数进行数位分离若检测到其中某一位为d dd则该楼层不存在将t o t tottot加1 11最终输出n − t o t n-totn−tot即可。/* * Name: T4.cpp * Problem: 奇葩楼层 * Author: Teacher Gao. * DateTime: 2025/01/14 22:16 */#includeiostreamusingnamespacestd;intmain(){intn,d,tot0;cinnd;for(inti1;in;i){intti;while(t){if(t%10d){tot;break;}t/10;}}coutn-totendl;return0;}T5. 小偷踩点题目链接SOJ D1276俗话说不怕贼偷就怕贼惦记。小偷在作案前有时会在居民家的门、墙上做一些标记每一种记号代表一个含义一般人看不懂但同行一看便知道这个家庭的情况。不过派出所干警也不是吃素的很快破译了这些记号的含义如上图并且在辖区内广为张贴告知居民。随后小偷们又改变了方法将这些记号从1 11到N NN编号然后将这些编号按照某种规则重新打乱再做标记标记变成了一串数字。不过这种新的编号方法又被破译了干警们发现这些数字的规律可以用一个二维矩阵来表示矩阵有10 1010列顺序对应数字0 00到9 99矩阵一般不超过10 1010行每行对应一个0 00到9 99之间的数字这些数字保证不重复。小偷的新标记由若干个两位数组成每个数字的十位对应行、个位对应列而对应位置上的数字就是原始标记的编号。如上图40 4040种标记从上到下、从左到右顺序编号后按下图所示的规律打乱则如果我们看到标记71 7171就是行标记为7 77列标记为1 11的单元格对应的数字11 1111对应原始标记中第11 1111个即 “很有钱”。那么标记71 78 57 71\ 78\ 57717857就表示原始标记的第11 1111、8 88、7 77号意思是 “很有钱”、“没有防范”、“计划行动”。本题就请你编写程序自动破译小偷的新标记。时间限制1 s内存限制64 MB输入输入第一行给出2 22个正整数N NN≤ 100 ≤ 100≤100为小偷的原始标记个数M MM≤ 10 ≤ 10≤10为新标记对照矩阵的行数。随后N NN行第i ii行给出第i ii个标记的解释由不超过100 100100个英文字母和空格组成。接下来一行给出M MM个数字为0 00到9 99之间的数字保证不重复其中第i ii个数对应矩阵第i ii行。接下来M MM行每行给出10 1010个数字或者是1 11到N NN之间的一个编号或者是− 1 -1−1表示没有对应的编号。最后一行给出小偷留在墙上的数字标记格式为k t [ 1 ] . . . t [ k ] k\ t[1] ... t[k]kt[1]...t[k]其中k kk是数字个数不超过N NN后面跟着k kk个数字。输出对小偷留下的每个数字在一行中输出其对应的意义顺序与输入顺序相同。如果没有对应的意义则在对应行中输出?。样例输入10 2 jia li you ren kong fang zi jia you e gou dan shen hen you qian xiao xin lin ju you bao jing qi jin kuai dong shou xia ci zai lai bu bi jin ru 6 2 -1 6 5 1 -1 10 3 4 -1 9 2 4 7 -1 3 -1 5 -1 8 2 5 20 64 61 22 13样例输出kong fang zi ? xiao xin lin ju you bao jing qi ?思路分析此题考查二维数组属于基础题。题目读起来比较绕不过理解清楚之后还是比较简单的代码写起来稍微有些复杂。首先我们需要将所有字符串按顺序存储起来示例代码中的h hh数组即按照原始编号存储由于字符串带空格所以输入时要格外小心使用g e t l i n e \tt getlinegetline函数时要注意第一行末尾尚未处理的换行符。输入的行号也要存起来示例代码中的r o w rowrow数组为了查询速度更快建立一个稍微大一点的二维数组示例代码中的m p mpmp数组确保第r o w i row_irowi​行可以立即访问而无需遍历这样就可以将新旧标记对照表存储到m p r o w i , j mp_{row_i, j}mprowi​,j​处。然后以新标记的十位和个位分别作为行标和列标即m p x / 10 , x % 10 mp_{x/10, x\%10}mpx/10,x%10​查询对应的旧编号即可可以将m p mpmp数组初始化为− 1 -1−1这样只要查询到− 1 -1−1就说明无意义。此题也可以用m a p \tt mapmap或u n o r d e r e d _ m a p \tt unordered\_mapunordered_map将新标记即r o w i × 10 j row_i \times 10 jrowi​×10j直接映射到旧标记对应的字符串中输入理解清楚之后该方法的代码较为简单感兴趣可自行实现。/* * Name: T5.cpp * Problem: 小偷踩点 * Author: Teacher Gao. * DateTime: 2025/01/14 22:43 */#includebits/stdc.husingnamespacestd;intmain(){intn,m,k,x;string h[105];intmp[15][15],row[15];memset(mp,-1,sizeof(mp));scanf(%d%d ,n,m);for(inti1;in;i)getline(cin,h[i]);for(inti1;im;i)cinrow[i];for(inti1;im;i)for(intj0;j10;j)cinmp[row[i]][j];cink;for(inti1;ik;i){cinx;if(mp[x/10][x%10]!-1){couth[mp[x/10][x%10]]\n;}else{cout?\n;}}return0;}