2024春算法训练3——数组与字符串

一、题解

1、A-[NOIP2013]记数问题_2024春算法训练3——数组与字符串 (nowcoder.com)

直接暴力用一个哈希表存每个数出现的次数，最坏的时间时间复杂度为7*10^7（实际上比这个数要小）；代码如下：

#include<iostream>
using namespace std;
int ha[10];

int  main()
{
    int r,q;
    cin>>r>>q;
    
    for(int i=1;i<=r;i++)
    {
        int t=i;
        while(t)
        {
            ha[t%10]++;
            t/=10;
        }
    }
    
    cout<<ha[q]<<endl;
    
    return 0;
}

2、B-[NOIP2005]校门外的树_2024春算法训练3——数组与字符串 (nowcoder.com)

这题我只知道两个时间复杂度不同的解法，一个是线性时间复杂度的，一个是O(nm)的；

首先说一下第二种，其实就是直接模拟，每次从起点到终点减去1，如果一颗树没有被挖掉，那么它的值为0，反之小于0；代码如下：

#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 solve()
{
    int n,m;
    cin>>n>>m;
    
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        for(int i=x;i<=y;i++)a[i]--;
    }
    
    int cnt=0;
    for(int i=0;i<=n;i++)if(a[i]==0)cnt++;
    cout<<cnt<<endl;
}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    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;
}

3、C-比较月亮大小_2024春算法训练3——数组与字符串 (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;
}

4.D-求逆序数_2024春算法训练3——数组与字符串 (nowcoder.com)

本题根据数据范围判断可以有两种解法，第一种是根据题目暴力枚举O(n^2),二是利用归并排序的特性求得O(nlogn);

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

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

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

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

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

1.两个数都在左边

2.两个数都在右边

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

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

注意退出循环时还有一个数组肯定是有一个数组没有枚举完的所以，那个数组剩下的数一定要记得加进临时数组

代码如下：

#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);
    for(int i=0;i<n;i++)
        for(int j=i;j<n;j++)
            if(a[i]>a[j])ans++;
    
    cout<<ans<<endl;
    
    return 0;
}

5.E-F课程满意度计算_2024春算法训练3——数组与字符串 (nowcoder.com)

用一个哈希表记录每门课程的人数，看其是否等于总人数

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

const int N=1010;
int a[N][N],ha[N];

void solve()
{
    int n,m;
    cin>>n>>m;
    
    int d=n;
    while(d--)
    {
       int x;
        cin>>x;
        while(x--)
        {
            int y;
            cin>>y;
            ha[y]++;
        }
    }
    int cnt=0;
    for(int i=1;i<=m;i++)if(ha[i]==n)cnt++;
    cout<<cnt<<endl;
}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    return 0;
}

6.F-有序序列合并_2024春算法训练3——数组与字符串 (nowcoder.com)

普通排序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

const int N=200010;
int a[N];

bool cmp(int a,int b)
{
    return a<b;
}

void solve()
{
    int n,m;
    cin>>n>>m;
    n+=m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    return 0;
}

7.G-[NOIP2015]扫雷游戏_2024春算法训练3——数组与字符串 (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;
}

8.H-数独合理吗？_2024春算法训练3——数组与字符串 (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;
}

9、I-回型矩阵_2024春算法训练3——数组与字符串 (nowcoder.com)

这题用四个while循环代表四个方向，这四个循环终止的条件是撞到边界或者其他已经被填充的数字。代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

const int N=2010;
int a[N][N];

void solve()
{
    int n;
    cin>>n;
    
    int sum=n*n,cnt=1;
    int i=1,j=1;
    a[1][1]=1;
    while(cnt<sum)
    {
         while(++j<=n&&!a[i][j])a[i][j]=++cnt;j--;//右
         while(++i<=n&&!a[i][j])a[i][j]=++cnt;i--;//下
         while(--j&&!a[i][j])a[i][j]=++cnt;j++;//左
         while(--i&&!a[i][j])a[i][j]=++cnt;i++;//上
    }
    
   for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++)
    {
        cout<<a[i][j]<<" ";
    }
       cout<<endl;
   }
}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    return 0;
}

10、J-蛇形矩阵_2024春算法训练3——数组与字符串 (nowcoder.com)

按照canor表划分层数的方式一样，我们将n*n的矩阵分为2*n-1层，每层的元素横纵坐标之和等于层数加一，所以我们只要确定每一层起始或者终止的点的横(纵)坐标即可，我是枚举的纵坐标。记得分奇偶讨论。

代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

const int N=1010;
int a[N][N];

void solve()
{
    int n;
    cin>>n;
    
    int cnt=1;
    /*上半段*/
    for(int i=1;i<=n;i++)
    {
        int x=i+1;
        if(i%2==0) for(int j=i;j>=1;j--)a[x-j][j]=cnt++;
        else for(int j=1;j<=i;j++) a[x-j][j]=cnt++;
    }
    //下半段
    
    for(int i=n+1;i<=2*n-1;i++)
    {
        int x=i+1;
        if(i%2!=0)for(int j=x-n;j<=n;j++)a[x-j][j]=cnt++;
        else for(int j=n;j>=x-n;j--)a[x-j][j]=cnt++;
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
            
}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    return 0;
}

11、K-[NOIP2006]明明的随机数_2024春算法训练3——数组与字符串 (nowcoder.com)

这题可以利用stl的vector自带的erase函数以及<algorithm>的sort和unique函数或者用数组记录重复出现的数字。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

const int N=200010;
int a[N];

void solve()
{   
    int n;
    cin>>n;
    
    vector<int >ans(n);
    
    for(int i=0;i<n;i++)cin>>ans[i];
    sort(ans.begin(),ans.end());
    ans.erase(unique(ans.begin(),ans.end()),ans.end());
    
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    return 0;
}

12、L-[NOIP2009]分数线划定_2024春算法训练3——数组与字符串 (nowcoder.com)

按题意排序找到最低分数，然后看有多少人达到了最低分数

#include<iostream>
#include<algorithm>
using namespace std;
const int N=5050;
double rate=1.5;

struct infor
{
    int identity,score;
}queue[N];

bool cmp(struct infor a,struct infor b)
{
    if(a.score!=b.score)return a.score<b.score;
    else return a.identity>b.identity;
}

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        queue[i]={a,b};
    }
    
    int stan=m*rate;

    sort(queue+1,queue+1+n,cmp);
    
    cout<<queue[n-stan+1].score<<" ";
    stan=queue[n-stan+1].score;
    
    int l=1,r=n;
    while(l<r)
    {
        int mid=l+r>>1;
        if(stan<=queue[mid].score)r=mid;
        else l=mid+1;
    }
    cout<<n-l+1<<endl;
    
    for(int i=n;i>=l;i--)cout<<queue[i].identity<<" "<<queue[i].score<<endl;
       
    return 0;
}

13、M-[NOIP2007]奖学金_2024春算法训练3——数组与字符串 (nowcoder.com)

这题考察多元素排序，要根据优先级在结构内部定义一个重载符进行运算，注意学号是从大到小排序，代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

const int N=200010;
int a[N];

struct students
{
    int sum,c,e,m,h;
    
    bool operator <(const students &A)
    {
        if(sum!=A.sum)return sum<A.sum;
        else if(c!=A.c)return c<A.c;
        else return h>A.h;
    }
}s[N];

void solve()
{
    int n;
    cin>>n;
    
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        int d=a+b+c;
        s[i]={d,a,b,c,i};
    }
    
    sort(s+1,s+1+n);
    
    for(int i=n;i>=n-4;i--)cout<<s[i].h<<" "<<s[i].sum<<endl;
}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    return 0;
}

14、N-[NOIP2003]乒乓球_2024春算法训练3——数组与字符串 (nowcoder.com)

这道题是一道模拟题，但是考察乒乓球的知识（去搜索引擎搜），就是当有一方有11（21）分后他和对手的分差是要大于2的，这是正常的分出胜负的情况，然而还有一种另外特殊情况就是打着打着局数满了，如果此时双方还没有分出胜负也必须强行终止那么最后就不用输出第二次，这种情况用flag特判。如果是因为局数满了而终止的对局，其结果就不需要在最后输出了。输入用getchar()  （感觉getchar是真好用) 代码如下：

#include<iostream>
using namespace std;
const int N=10000000;
char result[N];

int main()
{
    int cnt=0;char ch;
    while((ch=getchar())!='E')if(ch!='\n')result[++cnt]=ch;
    
    /*11分制*/
    int a=0,b=0;
    bool flag=false;
    for(int i=1;i<=cnt;i++)
    {
       if(result[i]=='W')a++;
       else b++;
        
       if(a==11||b==11)
       {
            while(abs(a-b)<2&&i<=cnt)
            {
                i++;
                if(result[i]=='W')a++;
                else if(result[i]=='L')b++;
            }
           if(i>cnt)flag=true;
           cout<<a<<":"<<b<<endl;
           a=b=0;   
       }
    }
    if(!flag)cout<<a<<":"<<b<<endl;
    
    cout<<endl;
    a=b=0;
    /*21分制*/
    flag=false;
    for(int i=1;i<=cnt;i++)
    {
       if(result[i]=='W')a++;
       else b++;
        
       if(a==21||b==21)
       {
            while(abs(a-b)<2&&i<=cnt)
            {
                i++;
                if(result[i]=='W')a++;
                else if(result[i]=='L')b++;
            }
           if(i>cnt)flag=true;
           cout<<a<<":"<<b<<endl;
           a=b=0;
       }
    }
    if(!flag)cout<<a<<":"<<b<<endl;

    return 0;
}

15、O-简写单词_2024春算法训练3——数组与字符串 (nowcoder.com)

getchar() yyds!! 一开始设flag为true,因为这里没有特殊说明默认第一个字符为一个字母。遇到第一个或者空格后的第一个字母,输出其大写形式即可。代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

const int N=200010;
int a[N];

void solve()
{
    char ch;
    bool f=true;
    
    while((ch=getchar())!=EOF)
    {
        if(ch==' ')f=true;
        else if(f==true){if(ch>='a'&&ch<='z')ch+='A'-'a';cout<<ch;f=false;}
    }
}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    return 0;
}

16、P-[NOIP2008]笨小猴_2024春算法训练3——数组与字符串 (nowcoder.com)

用数组记录所有出现过的字母的次数，排序得到答案，再判断质数（本题认为0不是质数）

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

const int N=200010;
int ha[27];

bool isprime(int x)
{
    if(x==1||x==0)return false;
    
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)return false;
    }
    
    return true;
}

bool cmp(int a,int b)
{
    return a<b;
}

void solve()
{
    string a;
    cin>>a;
    
    for(int i=0;i<a.size();i++)ha[a[i]-'a'+1]++;
    sort(ha+1,ha+27,cmp);
    
    int x=1,y=26,w,z;
    while(!ha[x])x++;
    w=ha[x];
    while(!ha[y])y--;
    z=ha[y];
    if(isprime(z-w))cout<<"Lucky Word"<<endl<<z-w;
    else cout<<"No Answer"<<endl<<0;
}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    return 0;
}

17、Q-[NOIP2000]计算器的改良_2024春算法训练3——数组与字符串 (nowcoder.com)

这题的数据好像与其题目描述的不一样，但是洛谷的原题又没有这个限制：最后一个数据点是真的恶心，程序输出的是-0.00，答案是0.00还不给过。所以这个点需要特判一下。其他的按照思路写就可以，我自己是按照分左右两边分别计算未知数系数和常数写的，好像有点长（能力有限）。推荐去洛谷看一下题解。还是给出我的代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
double eps=1e-9;
const int N=200010;
int a[N];

void solve()
{
    string a;
    cin>>a;
    
    char unknown;int mid;;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]>='a'&&a[i]<='z')unknown=a[i];
        if(a[i]=='=')mid=i;  
    }
   
    //标准：常数项归到等式右边，带有未知数的项归到等式左边
    int xi=0,chang=0;
    //首先讨论等式左边的情况
    for(int i=mid-1;i>=0;i--)
    {
         //等号前面要么是带有未知数的多项式要么是常数项
         if(a[i]==unknown)
         {
                i--;
                int ret=0,temp=1;
                while(a[i]!='+'&&a[i]!='-'&&i>=0)
                {
                    ret+=(a[i]-'0')*temp;
                    i--;
                    temp*=10;
                }
                if(ret==0)ret=1;
                if(i==-1&&a[i]!='+'&&a[i]!='-')xi+=ret;
                else if(a[i]=='+')xi+=ret;
                else xi-=ret;
             
         }else
         {
                int ret=0,temp=1;
                while(a[i]!='+'&&a[i]!='-'&&i>=0)
                {
                    ret+=(a[i]-'0')*temp;
                    i--;
                    temp*=10;
                }
                 if(i==-1&&a[i]!='+'&&a[i]!='-')chang-=ret;   
                 else if(a[i]=='+')chang-=ret;
                 else chang+=ret;
         }
    }
    /*然后讨论等式右边的情况*/
    for(int i=a.size()-1;i>=mid+1;i--)
    {
        /*方程最后一个元素同样只有两种情况要么是带有未知数的想要么是常数项*/
              if(a[i]==unknown)
             {
                    i--;
                    int ret=0,temp=1;
                    while(a[i]!='+'&&a[i]!='-'&&i>mid)
                    {
                        ret+=(a[i]-'0')*temp;
                        i--;
                        temp*=10;
                    }
                     if(ret==0)ret=1;
                     if(i==mid&&a[i]!='+'&&a[i]!='-')xi-=ret;
                     else if(a[i]=='+')xi-=ret;
                     else xi+=ret;
             }else
             {
                    int ret=0,temp=1;
                    while(a[i]!='+'&&a[i]!='-'&&i>mid)
                    {
                        ret+=(a[i]-'0')*temp;
                        i--;
                        temp*=10;
                    }
                     if(i==mid&&a[i]!='+'&&a[i]!='-')chang+=ret;   
                     else if(a[i]=='+')chang+=ret;
                     else chang-=ret;
             }   
    }
    double ans=chang*1.0/xi;
    if(fabs(ans)<eps)ans*=-1;
    printf("%c=%.3f",unknown,ans);

}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    return 0;
}

18、R-[NOIP2011]统计单词数_2024春算法训练3——数组与字符串 (nowcoder.com)

这题要注意的有几个点：1、所有字母都换成小写

2、记录首次出现的位置（我用的flag判断）

3、用到一个临时字符串存储当前的单词，遇到空格则清空。

#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

char pa[100000];
int main()
{
    string mod,p="";
    cin>>mod;   
    
    int cnt=0,loc=0,c=0;
    
    for(int i=0;i<mod.size();i++)if(mod[i]<'a')mod[i]=mod[i]+'a'-'A';
    
    char ch;
    bool flag=true;
    getchar();
    while((ch=getchar())!=EOF)
    {
        
        if(ch!=' ')
        {
            if(ch<'a')ch+='a'-'A';
            p+=ch;
        }else
        {
            if(p==mod&&flag)cnt++,flag=false;
            else if(p==mod&&!flag)cnt++;
            p="";
            if(flag)loc=c+1;
        }
        c++;/*计数*/
    }
    
    if(!cnt)cout<<-1<<endl;
    else cout<<cnt<<" "<<loc<<endl;

    return 0;
}

19、S-[NOIP2017]图书管理员_2024春算法训练3——数组与字符串 (nowcoder.com)

开一个辅助数组存放求对应长度后缀所需要的数

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

const int N=200010;
int a[N];

int dx[]={1,10,100,1000,10000,100000,1000000,10000000};
struct re
{
    int len,x;
}b[N];

bool cmp(int a,int b)
{
    return a<b;
}

void solve()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n,cmp);
    for(int j=1;j<=m;j++)cin>>b[j].len>>b[j].x;

    for(int i=1;i<=m;i++){
        bool flag=true;
        for(int j=1;j<=n;j++)
        {
            if(a[j]%dx[b[i].len]==b[i].x&&flag)cout<<a[j]<<endl,flag=0;
        }
        if(flag)cout<<-1<<endl;
    }
}

int main()
{
    int _;
    _=1;
    while(_--)
    {
        solve();
    }
    return 0;
}

20、T-[NOIP2012]Vigenère 密码_2024春算法训练3——数组与字符串 (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)

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/509751.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

SSL安全证书多少钱?

SSL安全证书多少钱?

SSL安全证书多少钱&#xff1f;单域名、多域名与通配符SSL证书的全面对比与价格分析。SSL&#xff08;Secure Sockets Layer&#xff09;证书作为一种加密技术&#xff0c;能够确保网站数据传输的安全性和可靠性&#xff0c;对于提升网站信誉和保护用户隐私具有至关重要的作用。…
阅读更多...
niushop单商户V5多店版源码分享三端uniapp打包方法包括PC端_小程序或h5端打包_收银端打包_APP端打包_商户端

niushop单商户V5多店版源码分享三端uniapp打包方法包括PC端_小程序或h5端打包_收银端打包_APP端打包_商户端

目前多店版有四端uniapp&#xff0c;包括PC端uniapp&#xff0c;商家端uniapp&#xff0c;收银端uniapp&#xff0c;门店手机端uniapp&#xff0c;下面我总结下这些端的打包流程希望能帮助到大家&#xff0c;需要交流的可以看我昵称或者点我头像关注我分享代码和教程 一.niush…
阅读更多...
kettle介绍-参数变量

kettle介绍-参数变量

ETL中为什么使用参数变量 实现ETL的复用D,Q,P环境不同,使用变量方便发布有的条件需要外部传入增量ETL灵活性强 kettle中参数变量种类 Environment VariablesKettle VariablesInternal VariablesTransformation中的变量Job中的变量 Environment Variables 通过Set Environm…
阅读更多...
QT - 日志：qDebug/qInfo/qWarning/qCritical

QT - 日志：qDebug/qInfo/qWarning/qCritical

篇一、日志打印函数 头文件&#xff1a; #include <QDebug> 代码&#xff1a;qDebug()<<"hello world!"; 其他打印级别&#xff1a; qInfo(): 普通信息 qDebug(): 调试信息 qWarning(): 警告信息 qCritical(): 严重错误 qFatal(): 致命错误 1. qDebug…
阅读更多...
FSH6罗德与施瓦茨FSH6频谱分析仪

FSH6罗德与施瓦茨FSH6频谱分析仪

181/2461/8938产品概述&#xff1a; R&S FSH6频谱分析仪坚固耐用、方便易用&#xff0c;专为野外使用而设计。它重量轻、操作简单、设计合理且具有大量测量功能&#xff0c;是任何需要高效测量仪器进行户外工作的人不可或缺的工具。 R&S FSH6是一款手持式频谱分析仪&…
阅读更多...
Jupyter Notebook启动及其常用快捷键

Jupyter Notebook启动及其常用快捷键

添加图片注释&#xff0c;不超过 140 字&#xff08;可选&#xff09; 1.JupyterNotebook 第一种启动方式 点击 windows 电脑左下角开始 > 搜索 Anaconda > 点击 Anaconda Prompt 添加图片注释&#xff0c;不超过 140 字&#xff08;可选&#xff09; 在命令行窗口输入&…
阅读更多...
华盛顿大学撰文反驳微软，我们无法删除大模型关于哈利波特的记忆

华盛顿大学撰文反驳微软，我们无法删除大模型关于哈利波特的记忆

在人工智能的发展过程中&#xff0c;一个引人入胜的议题是机器学习模型是否能够被训练以忘记其曾经学到的信息。近期&#xff0c;Ronen Eldan和Mark Russinovich在其研究“谁才是哈利波特&#xff1f;”[1]中提出了一种创新技术&#xff0c;声称能够从LLMs中“抹去”特定数据集…
阅读更多...
城市交通视频视频联网系统实施方案

城市交通视频视频联网系统实施方案

目录 1.需求调研 2.系统设计 3.技术分析 4.技术开发 5.系统平台环境要求 6.网络要求 7.安全要求 8.项目交付和验收 8.1交付准备 8.2系统安装、培训 8.2.1系统验收 8.2.2项目进度计划 附录&#xff1a;交通监控设备情况调研表 1.需求调研 从SZ市交通运输局、以及下…
阅读更多...
opencv使用问题记录一二

opencv使用问题记录一二

opencv介绍 opencv是一个计算机视觉处理软件库&#xff0c;拥有强大的功能和高效的性能。 但是由于早期版本的原因&#xff0c;存在一些与目前主流使用不兼容的问题 问题与解决 RGB通道顺序 一般图片处理类库的通道顺序就是RGB&#xff0c;但是opencv的是反过来的&#xf…
阅读更多...
如何改写出优质文案，AI写作工具有方法

如何改写出优质文案，AI写作工具有方法

在当今数字化时代&#xff0c;内容创作已成为企业和个人在市场竞争中脱颖而出的关键因素。而写作优质文案是吸引读者注意力、传达信息以及促使行动的重要手段之一。然而&#xff0c;对许多人来说&#xff0c;写作可能是一项具有挑战性的任务。幸运的是&#xff0c;随着人工智能…
阅读更多...
书生·浦语大模型开源体系（二）笔记

书生·浦语大模型开源体系（二）笔记

&#x1f497;&#x1f497;&#x1f497;欢迎来到我的博客&#xff0c;你将找到有关如何使用技术解决问题的文章&#xff0c;也会找到某个技术的学习路线。无论你是何种职业&#xff0c;我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章&#xff0c;也欢…
阅读更多...
【Vscode】无法将“python，pip，node，npm等”识别为cmdlet...问题

【Vscode】无法将“python，pip，node，npm等”识别为cmdlet...问题

问题出现场景 新换个电脑&#xff0c;然后重新安装了软件&#xff0c;又复现一次又一次“老生常谈”的问题。 解决方法 网络答案吧五花八门&#xff0c;我采取一个我的场景解决可行的方案&#xff0c; 首先我的场景是&#xff0c;环境变量&#xff0c;配置路径都是没有问题…
阅读更多...
super关键字的使用总结

super关键字的使用总结

一、super关键字的使用1. 为什么需要super&#xff1f;举例1&#xff1a;子类继承父类以后&#xff0c;对父类的方法进行了重写&#xff0c;那么在子类中&#xff0c;是否还可以对父类中被重写的方法进行调用&#xff1f; 可以&#xff01;举例2&#xff1a;子类继承父类以后&a…
阅读更多...
ice-06 运用Burp-Suite进行暴力破解（攻防世界）

ice-06 运用Burp-Suite进行暴力破解（攻防世界）

ice-06 步骤一&#xff1a;点击超链接&#xff0c;发现只有报表中心才有用。 步骤二&#xff1a;点进去发现输入日期范围没有用 步骤三&#xff1a;使用Burp Suite进行抓包&#xff0c;把值传到Action到Intruder中 步骤四&#xff1a;如图所示进行配置 步骤五&#xff1a;攻击…
阅读更多...
13.2k star, 高生产力的低代码开发平台 lowcode-engine

13.2k star, 高生产力的低代码开发平台 lowcode-engine

13.2k star, 高生产力的低代码开发平台 lowcode-engine 分类 开源分享 项目名: lowcode-engine -- 高生产力的低代码研发平台 Github 开源地址&#xff1a; GitHub - alibaba/lowcode-engine: An enterprise-class low-code technology stack with scale-out design / 一套面…
阅读更多...
【滤波器基础】卡尔曼滤波器

【滤波器基础】卡尔曼滤波器

滤波器基础 为了进一步抑制高频噪声&#xff0c;科研人员也会采用一些高阶低通滤波器来对电流采样信号的高频噪声进行抑制&#xff0c;常用的一种滤波器为&#xff1a;巴特沃兹滤波器。除了这种滤波器&#xff0c;也存在如贝塞尔、切比雪夫滤波器等。 巴特沃斯滤波器 在线性控…
阅读更多...
【御控物联】JavaScript JSON结构转换（15）：对象To数组——转换映射方式

【御控物联】JavaScript JSON结构转换（15）：对象To数组——转换映射方式

文章目录 一、JSON结构转换是什么&#xff1f;二、术语解释三、案例之《JSON对象 To JSON数组》四、代码实现五、在线转换工具六、技术资料 一、JSON结构转换是什么&#xff1f; JSON结构转换指的是将一个JSON对象或JSON数组按照一定规则进行重组、筛选、映射或转换&#xff0…
阅读更多...
服务器托管让服务器管理更轻松高效

服务器托管让服务器管理更轻松高效

在信息化飞速发展的今天&#xff0c;服务器作为企业数据处理和信息存储的核心设备&#xff0c;其管理的重要性日益凸显。服务器托管&#xff0c;作为一种高效、专业的服务器管理方式&#xff0c;正逐渐成为众多企业的首选。那么&#xff0c;服务器托管究竟是如何让服务器管理更…
阅读更多...
10个最佳3D角色下载站

10个最佳3D角色下载站

每个人都喜欢免费的东西。 无论是免费的 3D 角色还是游戏资产&#xff0c;我们都喜欢它们。 以下是可以为你的游戏获取免费 3D 角色的前 10 个网站的列表。 你可以将它们用于多种用途&#xff0c;例如 3D 打印或动画剪辑。 如果需要将下载的3D角色转化为其他格式&#xff0c;可…
阅读更多...
面具下的flag【杂项】

面具下的flag【杂项】

知识点&#xff1a; binwalk 检测文件是否合并binwalk -e 文件名 将文件进行剥离&#xff0c;自动解压出压缩包中的文件vmdk文件是可以进行解压的 7z x 文件 -o./vmdk是linux文件&#xff0c;需要在linux中进行解压&#xff0c;看了别人的wp发现在window中解压是没有关键信息…
阅读更多...
最新文章

Copyright @ 2022~2023