题解 P1603 斯诺登的密码
<img src="https://imayx.top/key-to-p1603/cover.jpg" alt="Featured image of post 题解 P1603 斯诺登的密码" /><p>题面来自<a class="link" href="https://www.luogu.com.cn/problem/P1603" target="_blank" rel="noopener"
>洛谷</a>,根据我的个人喜好有小修改</p>
<h2 id="题目背景">题目背景</h2>
<p>根据斯诺登事件出的一道水题</p>
<h2 id="题目描述">题目描述</h2>
<p>2013 年 X 月 X 日,俄罗斯办理了斯诺登的护照,于是他混迹于一架开往委内瑞拉的飞机。但是,这件事情太不周密了,因为 FBI 的间谍早已获悉他的具体位置——但这不是最重要的——最重要的是如果要去委内瑞拉,那么就要经过古巴,而经过古巴的路在美国的掌控之中。</p>
<p>丧心病狂的奥巴马迫降斯诺登的飞机,搜查时却发现,斯诺登杳无踪迹。但是,在据说是斯诺登的座位上,发现了一张纸条。纸条由纯英文构成:<code>Obama is a two five zero.</code>(以 <code>.</code> 结束输出,只有 6 个单词+一个句号,句子开头如没有大写亦为合法)这句话虽然有点无厘头,但是警官陈珺骛发现这是一条极其重要的线索。他在斯诺登截获的一台笔记本中找到了一个 C++ 程序,输入这条句子后立马给出了相对应的密码。陈珺鹜高兴得晕了过去,身为警官的你把字条和程序带上了飞机,准备飞往曼哈顿国际机场,但是在飞机上检查的时候发现——程序被粉碎了!飞机抵达华盛顿只剩5分钟,你必须在这 5 分钟内编写(杜撰)一个程序,免受上司的 10000000000%10 大板。破译密码的步骤如下:</p>
<p>(1)找出句子中所有用英文表示的数字($\leq 20$),列举在下:</p>
<p>正规:<code>one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen twenty</code></p>
<p>非正规:<code>a both another first second third</code>。为避免造成歧义,<code>another</code> 算作 $1$ 处理。</p>
<p>(2)将这些数字平方后对 $100$ 取模,如 $00,05,11,19,86,99$。</p>
<p>(3)把这些两位数按数位排成一行,组成一个新数,如果开头为 $0$,就去 $0$。</p>
<p>(4)找出所有排列方法中最小的一个数,即为密码。</p>
<p>// 数据已经修正 By absi2011 如果还有问题请联系我</p>
<h2 id="输入格式">输入格式</h2>
<p>一个含有 6 个单词的句子。</p>
<h2 id="输出格式">输出格式</h2>
<p>一个整型变量(密码)。如果没有符合要求的数字出现,则输出 0。</p>
<h2 id="输入输出样例">输入输出样例</h2>
<p>输入 #1</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt">1
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-fallback" data-lang="fallback"><span class="line"><span class="cl">Black Obama is two five zero .
</span></span></code></pre></td></tr></table>
</div>
</div><p>输出 #1</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt">1
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-fallback" data-lang="fallback"><span class="line"><span class="cl">425
</span></span></code></pre></td></tr></table>
</div>
</div><h2 id="分析">分析</h2>
<p><del>数据咋骂人呢</del></p>
<p>先一个个输入单词与题目给出的 <code>26</code> 个单词匹配,<code>string</code> 类型可以直接使用逻辑运算符 <code>==</code> 进行判断(C++ 选手谁闲着没事用 <code>char</code> 数组啊);</p>
<p>由于已经知道单词数量是 $6$ 个并不需要用到 while 循环(输入字符串的情况下 cin 的返回值情况我也不清楚)</p>
<h2 id="一些问题">一些问题</h2>
<h3 id="为什么样例输出不是-245-或者-254-">为什么样例输出不是 <code>245</code> 或者 <code>254</code> ?</h3>
<blockquote>
<p>25和4组成的最小数不是254吗,为什么样例给的425?</p>
</blockquote>
<blockquote>
<p>Black Obama is <strong>two five</strong> zero .</p>
</blockquote>
<h4 id="zero-是不算数的"><code>zero</code> 是不算数的!</h4>
<p>因此我们从六个单词中只能提取出两个:<code>two</code> 和 <code>five</code>。</p>
<p>转换成数字就是 $2$ 和 $5$。</p>
<p>然后我们算出它们的平方。</p>
<p>$2^2=4$</p>
<p>$5^5=25$</p>
<p>对 $100$ 取模后结果是 $04$ 和 $25$,因为题目说</p>
<blockquote>
<p>把这些 <code>两位数</code> 按数位排成一行</p>
</blockquote>
<p>并且给出了 <code>00,05</code> 这两个例子</p>
<p>有两种排列方法,因为 $0425$ 开头为 $0$,去掉开头的 $0$ 之后就是 $425$,比另一个排列 $2504$ 小</p>
<p>所以这个所有排列方法中最小的一个数是 $425$,而不是 $2504$。</p>
<blockquote>
<p>把这些两位数<code>按数位</code>排成一行,组成一个新数</p>
</blockquote>
<p>我感觉中间那三个字是多余的…不仅不能帮助理解反而可能误导选手</p>
<h3 id="只能得-20-分">只能得 <code>20</code> 分?</h3>
<p>放一下我下载的测试点#2 的数据(<del>请勿用于打表</del>):</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt">1
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-fallback" data-lang="fallback"><span class="line"><span class="cl">You are a three eight pig .
</span></span></code></pre></td></tr></table>
</div>
</div><div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt">1
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-fallback" data-lang="fallback"><span class="line"><span class="cl">10964
</span></span></code></pre></td></tr></table>
</div>
</div><p>我得了 <code>20</code> 分的程序在这个测试点上给出的答案是 <code>1964</code>,也就是忽略了所有 <code>0</code>,但实际上只能忽略开头那个。</p>
<blockquote>
<p>如果<code>开头</code>为 0,就去 0。</p>
</blockquote>
<p>记得排序。</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt">1
</span><span class="lnt">2
</span><span class="lnt">3
</span><span class="lnt">4
</span><span class="lnt">5
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="line"><span class="cl"><span class="k">if</span><span class="p">(</span><span class="n">num</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span> <span class="n">cout</span><span class="o"><<</span><span class="n">num</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
</span></span><span class="line"><span class="cl"><span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">cnt</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
</span></span><span class="line"><span class="cl"> <span class="k">if</span><span class="p">(</span><span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">></span><span class="mi">10</span><span class="p">)</span> <span class="n">cout</span><span class="o"><<</span><span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
</span></span><span class="line"><span class="cl"> <span class="k">else</span> <span class="n">cout</span><span class="o"><<</span><span class="sc">'0'</span><span class="o"><<</span><span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span>
</span></span></code></pre></td></tr></table>
</div>
</div><h3 id="忘了没有任何单词匹配的情况">忘了没有任何单词匹配的情况</h3>
<p><del>可能就我没看清题?</del></p>
<h4 id="直接输出-0-后结束程序即可">直接输出 <code>0</code> 后结束程序即可。</h4>
<p>其实不结束也啥都输出不出来,浪费点时间而已。</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt">1
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="line"><span class="cl"><span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">cnt</span><span class="p">)</span> <span class="n">cout</span><span class="o"><<</span><span class="mi">0</span><span class="p">,</span><span class="n">exit</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
</span></span></code></pre></td></tr></table>
</div>
</div><h5 id="冷知识虽然-return-0-不能写在逗号后面用于结束程序无法通过编译但是-exit0-可以">冷知识,虽然 <code>return 0;</code> 不能写在逗号后面用于结束程序(无法通过编译),但是 <code>exit(0);</code> 可以</h5>
<h2 id="完整代码">完整代码</h2>
<h3 id="仅供学习参考使用">仅供学习参考使用</h3>
<p>抄袭、复制题解,以达到刷 AC 率/AC 数量或其他目的的行为,在洛谷是严格禁止的。</p>
<p>洛谷非常重视<strong>学术诚信</strong>。此类行为将会导致您成为<em>作弊者</em>。 具体细则请查看<a class="link" href="https://www.luogu.com.cn/blog/luogu/social-rules" target="_blank" rel="noopener"
>洛谷社区规则</a>。</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre tabindex="0" class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span><span class="lnt">29
</span><span class="lnt">30
</span><span class="lnt">31
</span><span class="lnt">32
</span><span class="lnt">33
</span><span class="lnt">34
</span><span class="lnt">35
</span><span class="lnt">36
</span><span class="lnt">37
</span><span class="lnt">38
</span><span class="lnt">39
</span><span class="lnt">40
</span><span class="lnt">41
</span><span class="lnt">42
</span><span class="lnt">43
</span><span class="lnt">44
</span><span class="lnt">45
</span><span class="lnt">46
</span><span class="lnt">47
</span><span class="lnt">48
</span><span class="lnt">49
</span></code></pre></td>
<td class="lntd">
<pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="line"><span class="cl"><span class="cp">#include<bits/stdc++.h>
</span></span></span><span class="line"><span class="cl"><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"><span class="n">string</span> <span class="n">tmp</span><span class="p">,</span><span class="n">dic</span><span class="p">[</span><span class="mi">27</span><span class="p">]</span><span class="o">=</span><span class="p">{</span><span class="s">""</span><span class="p">,</span><span class="s">"one"</span><span class="p">,</span><span class="s">"two"</span><span class="p">,</span><span class="s">"three"</span><span class="p">,</span><span class="s">"four"</span><span class="p">,</span><span class="s">"five"</span><span class="p">,</span><span class="c1">//并不会出现zero
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="s">"six"</span><span class="p">,</span><span class="s">"seven"</span><span class="p">,</span><span class="s">"eight"</span><span class="p">,</span><span class="s">"nine"</span><span class="p">,</span><span class="s">"ten"</span><span class="p">,</span><span class="c1">//但是这里我为了前20个数下标对应数值把0空着
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="s">"eleven"</span><span class="p">,</span><span class="s">"twelve"</span><span class="p">,</span><span class="s">"thirteen"</span><span class="p">,</span><span class="s">"fourteen"</span><span class="p">,</span><span class="s">"fifteen"</span><span class="p">,</span>
</span></span><span class="line"><span class="cl"><span class="s">"sixteen"</span><span class="p">,</span><span class="s">"seventeen"</span><span class="p">,</span><span class="s">"eighteen"</span><span class="p">,</span><span class="s">"nineteen"</span><span class="p">,</span><span class="s">"twenty"</span><span class="p">,</span>
</span></span><span class="line"><span class="cl"><span class="s">"a"</span><span class="p">,</span><span class="s">"both"</span><span class="p">,</span><span class="s">"another"</span><span class="p">,</span><span class="s">"first"</span><span class="p">,</span><span class="s">"second"</span><span class="p">,</span><span class="s">"third"</span><span class="p">};</span>
</span></span><span class="line"><span class="cl"><span class="kt">int</span> <span class="n">num</span><span class="p">[</span><span class="mi">6</span><span class="p">],</span><span class="n">cnt</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"><span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span>
</span></span><span class="line"><span class="cl"> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="mi">6</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
</span></span><span class="line"><span class="cl"> <span class="n">cin</span><span class="o">>></span><span class="n">tmp</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">i</span><span class="o">&&</span><span class="n">tmp</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">>=</span><span class="sc">'A'</span><span class="o">&&</span><span class="n">tmp</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o"><=</span><span class="sc">'Z'</span><span class="p">)</span> <span class="n">tmp</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">+=</span><span class="sc">'a'</span><span class="o">-</span><span class="sc">'A'</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o"><=</span><span class="mi">26</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">){</span>
</span></span><span class="line"><span class="cl"> <span class="k">if</span><span class="p">(</span><span class="n">tmp</span><span class="o">==</span><span class="n">dic</span><span class="p">[</span><span class="n">j</span><span class="p">]){</span>
</span></span><span class="line"><span class="cl"> <span class="k">if</span><span class="p">(</span><span class="n">j</span><span class="o"><=</span><span class="mi">20</span><span class="p">){</span> <span class="c1">//在下标1-20匹配即对应1-20
</span></span></span><span class="line"><span class="cl"><span class="c1"></span> <span class="n">num</span><span class="p">[</span><span class="n">cnt</span><span class="o">++</span><span class="p">]</span><span class="o">=</span><span class="n">j</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"> <span class="k">break</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"> <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl"> <span class="k">switch</span><span class="p">(</span><span class="n">j</span><span class="p">){</span>
</span></span><span class="line"><span class="cl"> <span class="k">case</span> <span class="mi">21</span><span class="o">:</span> <span class="k">case</span> <span class="mi">23</span><span class="o">:</span> <span class="k">case</span> <span class="mi">24</span><span class="o">:</span> <span class="c1">//21、23、24对应1
</span></span></span><span class="line"><span class="cl"><span class="c1"></span> <span class="n">num</span><span class="p">[</span><span class="n">cnt</span><span class="o">++</span><span class="p">]</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="k">break</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"> <span class="k">case</span> <span class="mi">22</span><span class="o">:</span> <span class="k">case</span> <span class="mi">25</span><span class="o">:</span> <span class="c1">//22、25对应2
</span></span></span><span class="line"><span class="cl"><span class="c1"></span> <span class="n">num</span><span class="p">[</span><span class="n">cnt</span><span class="o">++</span><span class="p">]</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span><span class="k">break</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"> <span class="k">case</span> <span class="mi">26</span><span class="o">:</span> <span class="c1">//26对应3
</span></span></span><span class="line"><span class="cl"><span class="c1"></span> <span class="n">num</span><span class="p">[</span><span class="n">cnt</span><span class="o">++</span><span class="p">]</span><span class="o">=</span><span class="mi">3</span><span class="p">;</span><span class="k">break</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"> <span class="p">}</span>
</span></span><span class="line"><span class="cl"> <span class="k">break</span><span class="p">;</span><span class="c1">//switch 语句内的 break 仅能跳出 switch 而对外面的循环没有影响,
</span></span></span><span class="line"><span class="cl"><span class="c1"></span> <span class="c1">//因此必须在跳出 switch 后再 break 一次以确保跳出循环(其实继续遍历应该
</span></span></span><span class="line"><span class="cl"><span class="c1"></span> <span class="c1">//也没事,不会成功匹配只是浪费点时间)
</span></span></span><span class="line"><span class="cl"><span class="c1"></span> <span class="p">}</span>
</span></span><span class="line"><span class="cl"> <span class="p">}</span>
</span></span><span class="line"><span class="cl"> <span class="p">}</span>
</span></span><span class="line"><span class="cl"> <span class="p">}</span>
</span></span><span class="line"><span class="cl"> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">cnt</span><span class="p">)</span> <span class="n">cout</span><span class="o"><<</span><span class="mi">0</span><span class="p">,</span><span class="n">exit</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span><span class="c1">//冷知识,虽然 return 0 不能写在逗号后面用于结束程序但是
</span></span></span><span class="line"><span class="cl"><span class="c1"></span> <span class="c1">// exit(0) 可以
</span></span></span><span class="line"><span class="cl"><span class="c1"></span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">cnt</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
</span></span><span class="line"><span class="cl"> <span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">*</span><span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
</span></span><span class="line"><span class="cl"> <span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">%=</span><span class="mi">100</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"> <span class="p">}</span>
</span></span><span class="line"><span class="cl"> <span class="n">sort</span><span class="p">(</span><span class="n">num</span><span class="p">,</span><span class="n">num</span><span class="o">+</span><span class="n">cnt</span><span class="p">);</span>
</span></span><span class="line"><span class="cl"> <span class="k">if</span><span class="p">(</span><span class="n">num</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span> <span class="n">cout</span><span class="o"><<</span><span class="n">num</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
</span></span><span class="line"><span class="cl"> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o"><</span><span class="n">cnt</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
</span></span><span class="line"><span class="cl"> <span class="k">if</span><span class="p">(</span><span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">></span><span class="mi">10</span><span class="p">){</span>
</span></span><span class="line"><span class="cl"> <span class="n">cout</span><span class="o"><<</span><span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
</span></span><span class="line"><span class="cl"> <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl"> <span class="n">cout</span><span class="o"><<</span><span class="sc">'0'</span><span class="o"><<</span><span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
</span></span><span class="line"><span class="cl"> <span class="p">}</span>
</span></span><span class="line"><span class="cl"> <span class="p">}</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span>
</span></span></code></pre></td></tr></table>
</div>
</div><p>编辑记录</p>
<p>修复了最后一个解释不通的地方</p>
<p>2023-10-28 11:37:00</p>
<p>修复数学公式渲染</p>
<p>2021-08-06 18:39:00</p>
<p>暂时移除的段落:</p>
<blockquote>
<p>我得了 <code>20</code> 分(过了测试点#1)之后重读题面的理解是<code>把数字的每一位拆分排序</code>,而<a class="link" href="https://www.luogu.com.cn/discuss/show/293285" target="_blank" rel="noopener"
>这个帖子</a>的<a class="link" href="https://www.luogu.com.cn/user/434215" target="_blank" rel="noopener"
>楼主</a>的想法则是 <code>25</code> 和 <code>4</code> 的两种组合 <code>425</code> 和 <code>254</code> 中 <code>254</code> 更小。</p>
</blockquote>