2024级新生数组字符串专题题解

一、题解：

1.A-[NOIP2005]校门外的树_24级新生数组字符串训练题· (nowcoder.com)

这题常见的解法有两种：

第一种是这道题我们可以直接按照题目意思枚举

#include<bits/stdc++.h>
#define int long long 
using namespace std;int road[10010];signed main()
{int l,m;cin>>l>>m;for(int i=1;i<=m;i++){int l,r;cin>>l>>r;for(int i=l;i<=r;i++)road[i]=1;}int ans=0;for(int i=0;i<=l;i++)if(!road[i])ans++;cout<<ans;return 0;
}

第二种用了差分算法，这个算法与前缀和算法互逆关于算法的知识可以看一下这个视频：

STUACM-算法入门-前缀和与差分(含二维)_哔哩哔哩_bilibili

代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;const int N=200010;
int a[N],b[N];void insert(int x,int y)
{b[x]--;b[y+1]++;
}void solve()
{int n,k;cin>>n>>k;while(k--){int x,y;cin>>x>>y;insert(x,y);}int ans=0;for(int i=1;i<=n;i++)b[i]+=b[i-1];for(int i=0;i<=n;i++)if(b[i]<0)ans++;cout<<n+1-ans<<endl;
}int main()
{int _;_=1;while(_--){solve();}return 0;
}

2、B-比较月亮大小_24级新生数组字符串训练题· (nowcoder.com)

如果只有一天的话只能判断0和15这两个特殊元素,其他的都不能判断，如果有两天以上的话只用看最后两天可以了（这种情况只有14,15需要特判）。代码如下：

#include<iostream>
using namespace std;int temp[1000];int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>temp[i];if(n<=1){if(temp[n]==15)cout<<"DOWN"<<endl;else if(temp[n]==0)cout<<"UP"<<endl;else cout<<-1<<endl;}else if(temp[n]==15&&temp[n-1]==14)cout<<"DOWN"<<endl;else if(temp[n]>temp[n-1])cout<<"UP"<<endl;else if(temp[n]<temp[n-1])cout<<"DOWN"<<endl;return 0;
}

3、C-数列下标_24级新生数组字符串训练题· (nowcoder.com)

方法一：按照题目意思模拟，用数组存储答案；

#include<bits/stdc++.h>
#define int long long 
using namespace std;int a[10010],b[10010];signed main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){int temp=0;//判断是否有满足条件的数for(int j=i;j<=n;j++){if(a[j]>a[i]){b[i]=j;break;}}}for(int i=1;i<=n;i++)cout<<b[i]<<" ";return 0;
}

方法二：可以用单调栈的方法写，有兴趣的同学可以自己去了解。

4、D-求逆序数_24级新生数组字符串训练题· (nowcoder.com)

本题根据数据范围判断可以有两种解法，第一种是根据题目暴力枚举O(n^2)；

二是利用归并排序的特性求得O(nlogn);

第二种做法采用了分治的思想，非常经典，首先看归并排序的流程：

1.划分区间 [l,mid] ,[ mid+1,r];

2.递归排序(不断减小问题的规模)

3.归并，将左右两个区间合二为一；

一个逆序对是指一对数，其中前面的元素严格大于后面的数；那么根据归并排序的过程我们可以将逆序对分成三类：

1.两个数都在左边

2.两个数都在右边

3.两个数分别在左右两边 

其实质就是计算第三种逆序对，因为左右两边的逆序对随着递归最终都会分解成第三种情况。

方法二为基本归并排序算法

方法一代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;int a[10010];signed main()
{int n,ans=0;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(a[i]>a[j])ans++;}}cout<<ans;return 0;
}

方法二代码:

#include<iostream>
using namespace std;
int ans=0;int temp[2010],a[2022];void merge_sort(int q[],int l,int r)
{if(l>=r)return ;int mid=(l+r)>>1;merge_sort(q,l,mid);merge_sort(q,mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(q[i]>=q[j])ans+=mid-i+1,temp[k++]=q[j++];else temp[k++]=q[i++];}while(i<=mid)temp[k++]=q[i++];while(j<=r)temp[k++]=q[j++];for(int i=0,j=l;j<=r;j++,i++)q[j]=temp[i];
}int main()
{int n;cin>>n;for(int i=0;i<n;i++)cin>>a[i];merge_sort(a,0,n-1);cout<<ans<<endl;return 0;
}

5、E-[NOIP2015]扫雷游戏_24级新生数组字符串训练题· (nowcoder.com)

注意要判断八个方向

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;const int N=110;
char f[N][N];int dx[]={-1,0,1,0,1,1,-1,-1},dy[]={0,1,0,-1,1,-1,1,-1};void check(int x,int y)
{int cnt=0;for(int i=0;i<8;i++){int xx=x+dx[i],yy=dy[i]+y;if(f[xx][yy]=='*')cnt++;}f[x][y]='0'+cnt;
}void solve()
{int a,b;cin>>a>>b;for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)cin>>f[i][j];for(int i=1;i<=a;i++){    for(int j=1;j<=b;j++){if(f[i][j]!='*')check(i,j);printf("%c",f[i][j]);}cout<<endl;}
}int main()
{int _;_=1;while(_--){solve();}return 0;
}

6、A-[NOIP2008]笨小猴_24级新生数组字符串训练题 (nowcoder.com)

用数组记录所有出现过的字母的次数，排序得到答案，再判断质数（0不是质数）注意看清题目，只有是的时候输出答案，否则一律输出0；

#include<bits/stdc++.h>
#define int long long 
using namespace std;int num[29];bool isprime(int x)
{if(!x||x==1)return false;for(int i=2;i<=x/i;i++){if(x%i==0)return false;}return true;
}signed main()
{string s;cin>>s;int maxn=0,minn=1e12;for(int i=0;i<s.size();i++){if(s[i]>='A'&&s[i]<='Z')s[i]+='a'-'A';num[s[i]-'a']++;}for(int i=0;i<=25;i++){maxn=max(maxn,num[i]);if(num[i])minn=min(minn,num[i]);}int ans=maxn-minn;if(!isprime(ans)) cout<<"No Answer"<<endl<<0;else  cout<<"Lucky Word"<<endl<<ans;return 0;
}

7、B-数独合理吗？_24级新生数组字符串训练题 (nowcoder.com)

简单模拟，用一个数组记录数字出现的次数即可，记得每次检查前要初始化这个数组，代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;const int N=10;
int shu[N][N],ha[10];
bool flag1=1,flag2=1,flag3=1;void init()
{for(int i=1;i<=10;i++)ha[i]=0;
}bool check3(int x,int y)
{for(int i=x;i<=x+2;i++)for(int j=y;j<=y+2;j++){ha[shu[i][j]]++;if(ha[shu[i][j]]>1)return false;}return true;
}void check1()
{for(int i=1;i<=9;i++){init();for(int j=1;j<=9;j++){ha[shu[i][j]]++;if(ha[shu[i][j]]>1)flag1=false;}}   for(int i=1;i<=9;i++){init();for(int j=1;j<=9;j++){ha[shu[j][i]]++;if(ha[shu[j][i]]>1)flag2=false;}}
}void check2()
{for(int i=1;i<=9;i+=3)for(int j=1;j<=9;j+=3){init();if(!check3(i,j))flag3=false;}    
}void solve()
{for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)cin>>shu[i][j];/*检查行和列*/check1();/*检查宫*/check2();if(flag1&&flag2&&flag3)cout<<"YES"<<endl;else cout<<"NO"<<endl;
}int main()
{int _;_=1;while(_--){solve();}return 0;
}

8、珂朵莉的假toptree (nowcoder.com)

c++有个to_string函数很方便

#include<bits/stdc++.h>
#define int long long
using namespace std;signed main()
{int n;cin>>n;string s="";int cnt=0;for(int i=1;i<=1000;i++){s+=to_string(i);}cout<<s[n-1];return 0;
}

9、D-[NOIP2012]Vigenère 密码_24级新生数组字符串训练题 (nowcoder.com)

首先按照题目初始化密码表，然后根据规则去翻译即可。代码如下：

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;char map[26][26];
char key[110],text[1010];void init()
{for(int i=0;i<26;i++){char base='A'+i;for(int j=0;j<26;j++){char now=base+j;if(now-'A'>=26)now-=26;map[i][j]=now;}}
}int main()
{init();cin>>key>>text;int l=strlen(key),ll=strlen(text);for(int i=0;i<ll;i++){char a=key[i%l];char b=text[i];if(a>='a'&&a<='z')a+='A'-'a';if(b>='a'&&b<='z')b+='A'-'a';char ans;for(int j=0;j<26;j++)if(map[j][a-'A']==b)ans=j+'A';if(text[i]>='a'&&text[i]<='z')ans+='a'-'A';printf("%c",ans);}return 0;
}

有兴趣的同学还可以去试一下这道题：潜伏者 (nowcoder.com)

10、E-上三角矩阵判定_24级新生数组字符串训练题 (nowcoder.com)

设行数为i,那么要满足题目意思的话只要每行前i-1个元素全为0即可，否则不满足条件。

#include<bits/stdc++.h>
using namespace std;int f[11][11];signed main()
{int n;cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>f[i][j];bool ff=1;for(int i=1;i<=n;i++)for(int j=1;j<=i-1;j++){if(f[i][j])ff=0;}if(ff)cout<<"YES";else cout<<"NO";return 0;
}