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;
}