2018头条春招笔试题解 怼烎@ 2022-05-29 13:27 157阅读 0赞 原文链接:[https://www.nowcoder.com/discuss/70299?type=2&order=0&pos=9&page=2][https_www.nowcoder.com_discuss_70299_type_2_order_0_pos_9_page_2] 头条题目: [ https://blog.csdn.net/flushhip/article/details/79685488][https_blog.csdn.net_flushhip_article_details_79685488] 头条测试: [https://blog.csdn.net/flushhip/article/details/79562199][https_blog.csdn.net_flushhip_article_details_79562199] 第一题: 双指针: <table> <tbody> <tr> <td> <div> <br> </div> <div> <br> </div></td> <td> <div> <div> <code>#include <bits/stdc++.h></code> </div> <div> <code>using</code> <code>namespace</code> <code>std;</code> </div> <div> <code>typedef</code> <code>long</code> <code>long</code> <code>ll;</code> </div> <div> <code>const</code> <code>int</code> <code>N = 1e6+7;</code> </div> <div> <code>int</code> <code>a[N];</code> </div> <div> <code>int</code> <code>main()</code> </div> <div> <code>{ </code> </div> <div> <code> </code> <code>int</code> <code>n,k;</code> </div> <div> <code> </code> <code>scanf</code> <code>(</code> <code>"%d%d"</code> <code>,&n,&k);</code> </div> <div> <code> </code> <code>for</code> <code>(</code> <code>int</code> <code>i=0;i<n;++i) </code> <code>scanf</code> <code>(</code> <code>"%d"</code> <code>,&a[i]);</code> </div> <div> <code> </code> <code>sort(a, a+n);</code> </div> <div> <code> </code> <code>n = unique(a, a+n) -a;</code> </div> <div> <code> </code> <code>int</code> <code>r = 0, ans=0;</code> </div> <div> <code> </code> <code>for</code> <code>(</code> <code>int</code> <code>l=0; l<n;++l)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>while</code> <code>(r<n&&a[r]-a[l]<k) ++r;</code> </div> <div> <code> </code> <code>if</code> <code>(r==n) </code> <code>break</code> <code>;</code> </div> <div> <code> </code> <code>if</code> <code>(a[r]-a[l] == k) ++ans;</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>printf</code> <code>(</code> <code>"%d\n"</code> <code>, ans);</code> </div> <div> <code> </code> <code>return</code> <code>0;</code> </div> <div> <code>}</code> </div> <div> </div> <div> <code> </code> </div> </div></td> </tr> </tbody> </table> 第二题: BFS <table> <tbody> <tr> <td> <div> <br> </div></td> <td> <div> <div> <code>#include <bits/stdc++.h></code> </div> <div> <code>using</code> <code>namespace</code> <code>std;</code> </div> <div> <code>typedef</code> <code>pair<</code> <code>int</code> <code>,</code> <code>int</code> <code>> pii;</code> </div> <div> <code>map<pair<</code> <code>int</code> <code>,</code> <code>int</code> <code>> , </code> <code>int</code> <code>> mp;</code> </div> <div> <code>int</code> <code>main()</code> </div> <div> <code>{ </code> </div> <div> <code> </code> <code>int</code> <code>n;</code> </div> <div> <code> </code> <code>scanf</code> <code>(</code> <code>"%d"</code> <code>,&n);</code> </div> <div> <code> </code> <code>queue<pii> q;</code> </div> <div> <code> </code> <code>q.push(make_pair(1, 1));</code> </div> <div> <code> </code> <code>mp[make_pair(1,1)]=0;</code> </div> <div> <code> </code> <code>while</code> <code>(!q.empty())</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>pii pr = q.front();q.pop();</code> </div> <div> <code>// printf("%d %d\n",pr.first, pr.second);</code> </div> <div> <code> </code> <code>if</code> <code>(pr.first == n)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>printf</code> <code>(</code> <code>"%d\n"</code> <code>, mp[pr]);</code> </div> <div> <code> </code> <code>exit</code> <code>(0);</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>pii t=pr;</code> </div> <div> <code> </code> <code>t.second = t.first; t.first*=2;</code> </div> <div> <code> </code> <code>if</code> <code>(!mp.count(t))</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>q.push(t);</code> </div> <div> <code> </code> <code>mp[t] = mp[pr]+1;</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>t=pr;</code> </div> <div> <code> </code> <code>t.first=t.first+t.second;</code> </div> <div> <code> </code> <code>if</code> <code>(!mp.count(t))</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>q.push(t);</code> </div> <div> <code> </code> <code>mp[t] = mp[pr]+1;</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>return</code> <code>0;</code> </div> <div> <code>}</code> </div> <div> </div> <div> <code> </code> </div> </div></td> </tr> </tbody> </table> 第三题: 模拟。 <table> <tbody> <tr> <td> </td> <td> <div> <div> <code>#include <bits/stdc++.h></code> </div> <div> <code>using</code> <code>namespace</code> <code>std;</code> </div> <div> <code>typedef</code> <code>long</code> <code>long</code> <code>ll;</code> </div> <div> <code>char</code> <code>s[107];</code> </div> <div> <code>char</code> <code>G[5][10][8] = { </code> </div> <div> <code> </code> <code>{ </code> <code>"66666"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"6...6"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>},</code> </div> <div> <code> </code> <code>{ </code> <code>"6...6"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"6...6"</code> <code>, </code> <code>"6...."</code> <code>, </code> <code>"6...."</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"6...6"</code> <code>, </code> <code>"6...6"</code> <code>},</code> </div> <div> <code> </code> <code>{ </code> <code>"6...6"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>},</code> </div> <div> <code> </code> <code>{ </code> <code>"6...6"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"6...."</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"6...6"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"6...6"</code> <code>, </code> <code>"....6"</code> <code>},</code> </div> <div> <code> </code> <code>{ </code> <code>"66666"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"....6"</code> <code>, </code> <code>"66666"</code> <code>, </code> <code>"66666"</code> <code>}</code> </div> <div> <code>};</code> </div> <div> <code>ll cal()</code> </div> <div> <code>{ </code> </div> <div> <code> </code> <code>int</code> <code>n = </code> <code>strlen</code> <code>(s);</code> </div> <div> <code> </code> <code>ll sum=0, cur=0, prd=1;</code> </div> <div> <code> </code> <code>for</code> <code>(</code> <code>int</code> <code>i=0; i<n; ++i)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>if</code> <code>(</code> <code>isdigit</code> <code>(s[i])) cur=cur*10+s[i]-</code> <code>'0'</code> <code>;</code> </div> <div> <code> </code> <code>else</code> <code>if</code> <code>(s[i] == </code> <code>'-'</code> <code>)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>sum+=prd*cur;</code> </div> <div> <code> </code> <code>cur=0;</code> </div> <div> <code> </code> <code>prd=-1;</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>else</code> <code>if</code> <code>(s[i] == </code> <code>'+'</code> <code>)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>sum+=prd*cur;</code> </div> <div> <code> </code> <code>cur=0;</code> </div> <div> <code> </code> <code>prd=1;</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>else</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>prd*=cur;</code> </div> <div> <code> </code> <code>cur=0;</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>return</code> <code>sum+prd*cur;</code> </div> <div> <code>}</code> </div> <div> <code>int</code> <code>main()</code> </div> <div> <code>{ </code> </div> <div> <code> </code> <code>int</code> <code>T;</code> </div> <div> <code> </code> <code>scanf</code> <code>(</code> <code>"%d"</code> <code>,&T);</code> <code>while</code> <code>(T--)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>scanf</code> <code>(</code> <code>"%s"</code> <code>, s);</code> </div> <div> <code> </code> <code>ll ans = cal();</code> </div> <div> <code> </code> <code>for</code> <code>(</code> <code>int</code> <code>i=0; i<5; ++i)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>vector<</code> <code>int</code> <code>> v;</code> </div> <div> <code> </code> <code>ll tmp = ans;</code> </div> <div> <code> </code> <code>while</code> <code>(tmp) v.push_back(tmp%10),tmp/=10;</code> </div> <div> <code> </code> <code>reverse(v.begin(), v.end());</code> </div> <div> <code> </code> <code>if</code> <code>(v.empty()) v.push_back(0);</code> </div> <div> <code> </code> <code>for</code> <code>(</code> <code>int</code> <code>j=0; j<v.size(); ++j)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>printf</code> <code>(</code> <code>"%s%s"</code> <code>,G[i][v[j]], j+1==v.size()?</code> <code>"\n"</code> <code>:</code> <code>".."</code> <code>);</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>return</code> <code>0;</code> </div> <div> <code>}</code> </div> </div></td> </tr> </tbody> </table> <table> <tbody> <tr> <td> <div> 1 </div></td> <td> <div> <div> </div> </div></td> </tr> </tbody> </table> 第四题: 只能从均值大的集合往均值小的集合里放。 取数只能取出现次数等于1的数 放数只能放没出现过的数 从小的数开始放可以使均值小的集合均值上升慢,均值大的集合均值上升快,这样最优。 <table> <tbody> <tr> <td> </td> <td> <div> <div> <code>#include <bits/stdc++.h></code> </div> <div> <code>using</code> <code>namespace</code> <code>std;</code> </div> <div> <code>typedef</code> <code>long</code> <code>long</code> <code>ll;</code> </div> <div> <code>set<</code> <code>int</code> <code>> sa,sb;</code> </div> <div> <code>ll suma, sumb;</code> </div> <div> <code>const</code> <code>long</code> <code>double</code> <code>eps = 1e-14;</code> </div> <div> <code>inline</code> <code>int</code> <code>cmp(</code> <code>long</code> <code>double</code> <code>a, </code> <code>long</code> <code>double</code> <code>b)</code> </div> <div> <code>{ </code> </div> <div> <code> </code> <code>if</code> <code>(</code> <code>fabs</code> <code>(a-b) <= eps) </code> <code>return</code> <code>0;</code> </div> <div> <code> </code> <code>return</code> <code>a>b?1:-1;</code> </div> <div> <code>}</code> </div> <div> <code>inline</code> <code>long</code> <code>double</code> <code>jz(ll k, </code> <code>int</code> <code>m)</code> </div> <div> <code>{ </code> </div> <div> <code> </code> <code>return</code> <code>(</code> <code>long</code> <code>double</code> <code>)k/m;</code> </div> <div> <code>}</code> </div> <div> <code>int</code> <code>main()</code> </div> <div> <code>{ </code> </div> <div> <code> </code> <code>int</code> <code>n,m;</code> </div> <div> <code> </code> <code>scanf</code> <code>(</code> <code>"%d%d"</code> <code>,&n,&m);</code> </div> <div> <code> </code> <code>for</code> <code>(</code> <code>int</code> <code>i=0; i<n;++i)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>int</code> <code>t;</code> </div> <div> <code> </code> <code>scanf</code> <code>(</code> <code>"%d"</code> <code>,&t);</code> </div> <div> <code> </code> <code>sa.insert(t);</code> </div> <div> <code> </code> <code>suma+=t;</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>for</code> <code>(</code> <code>int</code> <code>i=0;i<m;++i)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>int</code> <code>t;</code> </div> <div> <code> </code> <code>scanf</code> <code>(</code> <code>"%d"</code> <code>,&t);</code> </div> <div> <code> </code> <code>sb.insert(t);</code> </div> <div> <code> </code> <code>sumb+=t;</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>if</code> <code>(cmp(jz(suma, n), jz(sumb, m))==-1)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>swap(suma, sumb);</code> </div> <div> <code> </code> <code>swap(n, m);</code> </div> <div> <code> </code> <code>sa.swap(sb);</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>int</code> <code>mx =n;</code> </div> <div> <code> </code> <code>int</code> <code>ans = 0;</code> </div> <div> <code> </code> <code>for</code> <code>(auto k : sa)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>if</code> <code>(cmp(k, jz(suma, n)) >= 0) </code> <code>break</code> <code>;</code> </div> <div> <code>// printf("%d %d\n",n, k);</code> </div> <div> <code> </code> <code>if</code> <code>(!sb.count(k)&&cmp(k, jz(sumb, m))>0)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>++ans;</code> </div> <div> <code> </code> <code>sumb+=k;</code> </div> <div> <code> </code> <code>suma-=k;</code> </div> <div> <code> </code> <code>sb.insert(k);</code> </div> <div> <code> </code> <code>--n;++m;</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>printf</code> <code>(</code> <code>"%d\n"</code> <code>, ans);</code> </div> </div></td> </tr> </tbody> </table> 第五题:BFS <table> <tbody> <tr> <td> </td> <td> <div> <div> <code>#include <bits/stdc++.h></code> </div> <div> <code>using</code> <code>namespace</code> <code>std;</code> </div> <div> <code>const</code> <code>int</code> <code>N = 1e5+1000;</code> </div> <div> <code>typedef</code> <code>pair<</code> <code>int</code> <code>, </code> <code>int</code> <code>> pii;</code> </div> <div> <code>bool</code> <code>vis[N];</code> </div> <div> <code>int</code> <code>a[N];</code> </div> <div> <code>int</code> <code>main()</code> </div> <div> <code>{ </code> </div> <div> <code> </code> <code>int</code> <code>n,k,h;</code> </div> <div> <code> </code> <code>scanf</code> <code>(</code> <code>"%d%d%d"</code> <code>,&n,&k,&h);</code> </div> <div> <code> </code> <code>for</code> <code>(</code> <code>int</code> <code>i=0;i<n;++i)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>int</code> <code>t;</code> </div> <div> <code> </code> <code>scanf</code> <code>(</code> <code>"%d"</code> <code>,&t);</code> </div> <div> <code> </code> <code>a[t]=1;</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>queue<pii> q;</code> </div> <div> <code> </code> <code>q.push({0,0});</code> </div> <div> <code> </code> <code>int</code> <code>ans = 0;</code> </div> <div> <code> </code> <code>while</code> <code>(!q.empty())</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>pii p = q.front(); q.pop();</code> </div> <div> <code> </code> <code>if</code> <code>(p.second>k) </code> <code>break</code> <code>;</code> </div> <div> <code> </code> <code>ans = max(ans, p.first);</code> </div> <div> <code> </code> <code>for</code> <code>(</code> <code>int</code> <code>i=1; i<=h; ++i)</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>if</code> <code>(a[p.first + i]&&!vis[p.first+2*i])</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>vis[p.first+2*i]=</code> <code>true</code> <code>;</code> </div> <div> <code> </code> <code>q.push(make_pair(p.first+2*i, p.second+1));</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>if</code> <code>(p.first-2*i>0&&a[p.first-i]&&!vis[p.first-2*i])</code> </div> <div> <code> </code> <code>{ </code> </div> <div> <code> </code> <code>vis[p.first-2*i]=</code> <code>true</code> <code>;</code> </div> <div> <code> </code> <code>q.push(make_pair(p.first-2*i, p.second+1));</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>}</code> </div> <div> <code> </code> <code>printf</code> <code>(</code> <code>"%d\n"</code> <code>, ans);</code> </div> <div> <code> </code> <code>return</code> <code>0;</code> </div> <div> <code>}</code> </div> <div> </div> </div></td> </tr> </tbody> </table> [https_www.nowcoder.com_discuss_70299_type_2_order_0_pos_9_page_2]: https://www.nowcoder.com/discuss/70299?type=2&order=0&pos=9&page=2 [https_blog.csdn.net_flushhip_article_details_79685488]: https://blog.csdn.net/flushhip/article/details/79685488 [https_blog.csdn.net_flushhip_article_details_79562199]: https://blog.csdn.net/flushhip/article/details/79562199
还没有评论,来说两句吧...