牛客周赛91题解
<h1 id="牛客周赛91">牛客周赛91</h1><p>https://ac.nowcoder.com/acm/contest/108038#question</p>
<h3 id="awhile">A.while</h3>
<p>https://ac.nowcoder.com/acm/contest/108038/A</p>
<p>签到题：只需要判断当前字符串与<code>while</code>有多少个位置上的字符不相同即可。</p>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;cin>>s;
int ans=0;
if(s!='w') ans++;
if(s!='h') ans++;
if(s!='i') ans++;
if(s!='l') ans++;
if(s!='e') ans++;
cout<<ans;
return 0;
}
</code></pre>
<h3 id="btoken">B.token</h3>
<p>https://ac.nowcoder.com/acm/contest/108038/B</p>
<p>签到题，用前缀和解决即可。</p>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{
int n;cin>>n;
vector<LL> a(n+1,0),s(n+1,0);
for(int i=1;i<=n;i++) cin>>a,s=s+a;
LL ans=0;
for(int i=1;i<=n;i++){
if(i<=9) ans=max(ans,s);
else ans=max(ans,s-s);
}
cout<<ans;
return 0;
}
</code></pre>
<h3 id="c小苯的逆序对和">C.小苯的逆序对和</h3>
<p>https://ac.nowcoder.com/acm/contest/108038/C</p>
<p>思路：预处理出前i个数中最大的数的值<code>p</code>，然后枚举下标<span class="math inline">\(i\)</span>，若<code>p>a</code>，也就是说，下标i前面的值有>a的部分，那么可以构成逆序对，因为要求最大的<code>a+a</code>，故而我们处理出前i个数中最大的值即可。</p>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;cin>>n;
//预处理前i个数中的最大值
vector<int> a(n+1,0),p(n+1,0);
for(int i=1;i<=n;i++){
cin>>a;
p=max(p,a);
}
int ans=0;
for(int i=1;i<=n;i++){
if(p>a) ans=max(p+a,ans);
}
cout<<ans<<"\n";
}
int main()
{
int t=1;cin>>t;
while(t--) solve();
return 0;
}
</code></pre>
<h3 id="d数组40">D.数组4.0</h3>
<p>https://ac.nowcoder.com/acm/contest/108038/D</p>
<p>思路：将数组中的元素进行排序以后，计算“段数”，那么答案就是“段数”-1，怎么计算段数呢？当我们以一个数<code>x</code>新开一段时，意味着<code>x-1</code>在数组中必然不存在，那么我们只需要用<code>map</code>来存储每个数出现的频率，（至于为什么用map，不用set，后面有解释。）如果<code>x-1</code>出现的频率为0，那么就新开一段。</p>
<p>那么为什么我们使用<code>map</code>而不使用<code>set</code>呢？我们有一种特殊情况，类似下列样例：</p>
<p><code></code>这个样例，我们需要在<code>2,4</code>之间连接一条边，也需要在<code>4,4</code>和<code>4-6</code>之间连一条边，也就是说：当<code>x+1</code>在数组中不存在时，我们需要将所有的x之间连接起来，将所有x连接起来的代价是：<code>x出现的频率-1</code>；</p>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;cin>>n;
map<int,int> mp;
for(int i=1;i<=n;i++){
int x;cin>>x;
mp++;
}
int ans=0;
for(auto & : mp){
//x-1不存在，就新开一段
if(!mp.count(x-1)){
ans++;
//若x+1不存在，那么需要将所有的x自行连接起来...
if(!mp.count(x+1)) ans+=y-1;
}
}
//答案为“段数”-1;
cout<<ans-1<<"\n";
}
int main()
{
int t=1;cin>>t;
while(t--) solve();
return 0;
}
</code></pre>
<h3 id="e小苯的矩阵反转">E.小苯的矩阵反转</h3>
<p>https://ac.nowcoder.com/acm/contest/108038/E</p>
<p>思路：如果给我们一个01矩阵，让我们判断是否能变成全0矩阵，这样或许有点麻烦，有很多种情况需要讨论，那么我们不妨反过来思考，给我们一个全0矩阵，经过这几种操作之后，能够变成什么样的矩阵，然后将这个矩阵和我们原本的01矩阵进行匹配，如果匹配成功，那么就输出<code>YES</code>，否则输出<code>NO</code>;<br>
那么给我们一个01矩阵，进行这几种操作以后，可以有四种情况：</p>
<ol>
<li>选择全0的一行（列）进行翻转两次，得到的矩阵还是全0矩阵</li>
<li>选择全0的两行（这两行不同）分别翻转一次，得到的矩阵是：只有两行全是1，其余行都是0；</li>
<li>选择全0的两列（这两列不同）分别翻转一次，得到的矩阵是：只有两列全是1，其余列都是0；</li>
<li>选择一行和一列进行操作，翻转一次。那么得到的会是一个十字架类型的图形，除了交叉点，其余点都是1；</li>
</ol>
<p>那么如何写代码进行判断呢？</p>
<ol>
<li>
<p>全0的情况很容易判断，只需要数字符1的个数<code>c1</code>，若<code>c1==0</code>，那么这个01矩阵原本就是全0矩阵</p>
</li>
<li>
<p>选择两行进行翻转，那么翻转以后，得到的矩阵中的1的个数必然为<code>m*2</code>，并且其他行都是0，我们只需要用一个变量<code>Cr</code>来记录全是0是行的个数，若<code>Cr==2 && c1==m*2</code>，那么就符合我们这种情况。</p>
</li>
<li>
<p>选择两列翻转，与第二条同理。我们用<code>Cc</code>来记录 全0的列数的个数，若<code>Cc==2 && c1==n*2</code>，那么就符合情况</p>
</li>
<li>
<p>十字架类型的图形，这种情况，因为交点是0，那么我们只需要枚举0的位置，假设当前行列的位置分别为<code>i,j</code>。那么我们只需要判断<code>第i行中1的个数是否为m-1</code>以及<code>第j列中1的个数是否为n-1</code>，以及<code>字符1的个数为n+m-2</code>；如果三条都满足，那么就符合这种情况。在这里我们需要用<code>r</code>来记录第i行中1的个数，还需要用<code>c</code>来记录第j列中1的个数</p>
</li>
</ol>
<pre><code class="language-cpp">//正难则反
//考虑四种情况
//1.原本就是全0
//2.有两列/行为1
//3.有一个十字架型的形状(除了交点以外都是1);
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n,m;cin>>n>>m;
vector<string> a(n);
//r表示第i行中1的个数,..c表示第i列中1的个数
vector<int> r(n),c(m);
for(int i=0;i<n;i++) cin>>a;
//算1的个数
int c1=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a=='1'){
c1++;
//第i行，第j列
r++;
c++;
}
}
}
//计算全是1的行数的个数
int Cr = 0;
for(int i = 0; i < n; i++) {
Cr += (r == m);
}
//计算全为0的列数的个数
int Cc = 0;
for(int i = 0; i < m; i++) {
Cc += (c == n);
}
//还有类似十字架的图形,枚举0的位置..那么那行的1的个数为m-1,那一列的1的个数为n-1..且总的1的个数为n+m-2;
bool flag=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a=='1') continue;
if(r==m-1&&c==n-1&&c1==n+m-2) flag=true;
}
}
//满足一种情况,那么就输出YES,否则为NO;
if(c1==0||(c1==2*m && Cr==2)||(c1==2*n && Cc==2)||flag) cout<<"YES\n";
else cout<<"NO\n";
}
int main()
{
int t=1;cin>>t;
while(t--) solve();
return 0;
}
</code></pre>
<h3 id="f小苯的因子查询">F.小苯的因子查询</h3>
<p>https://ac.nowcoder.com/acm/contest/108038/F</p>
<p>有待更新....</p><br><br>
来源：https://www.cnblogs.com/Tomorrowland/p/18853293
頁:
[1]