24真题

1.相亲数

/*
1. 相亲数
在数学中，若彼此的约数之和（除去自身）等于另一方，则二者被称为亲和数。

例如：

220的约数和为1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
284的约数和为1 + 2 + 4 + 71 + 142 = 220

则220和284为一对亲和数。

输出10000以内的亲和数。
*/

#include <iostream>
#include <cmath>
using namespace std;
int sum(int n)
{
    int res=1;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0&&i<sqrt(n))res=res+i+n/i;
        else if(n%i==0)res+=i;
    }
    return res;
}

int main()
{
    int a,b;
    cin>>a>>b;

    for(int i=1;i<10000;i++)
    {
        int i_q=sum(i);
        if(i_q>i&&i_q<10000)
        {
            if(sum(i_q)==i)
            cout<<i<<" "<<i_q<<endl;
        }
    }
    return 0;
}

异位字符串

#include <iostream>
#include <cstring>
using namespace std;
int sa[26],sA[26];
int ta[26],tA[26];
int main()
{
    string s,t;
    cin>>s>>t;

    for(int i=0;i<s.size();i++)
    {
        if(s[i]>='A'&&s[i]<='Z')
        {
            sA[s[i]-'A']++;
        }
        else if(s[i]>='a'&&s[i]<='z')
        {
            sa[s[i]-'a']++;
        }
    }
    for(int i=0;i<t.size();i++)
    {
        if(t[i]>='A'&&t[i]<='Z')
        {
            tA[t[i]-'A']++;
        }
        else if(t[i]>='a'&&t[i]<='z')
        {
            ta[t[i]-'a']++;
        }
    }

    bool same=true;
    for(int i=0;i<26;i++)
    {
        if(sa[i]!=ta[i]||sA[i]!=tA[i])
        {
            same=false;
            break;
        }
    }
    if(same)puts("ture");
    else puts("flase");
    return 0;
}

/*
anagram
nagaram
*/

23真题

1.职工年龄

/*
1. 工龄排序
给定学校 N 名教师的工龄，要求按工龄增序输出每个工龄段有多少教师。
输入格式:
输入首先给出正整数 N（≤10^5），即教师总人数；随后给出 N 个整数，即每个教师的工龄，
范围在[0, 50]。
输出格式:
按工龄的递增顺序输出每个工龄的教师个数，格式为：“工龄:人数”。每项占一行。如果人数为 0 则不输出该项。要求时间复杂度为 O(N)。
输入样例:

8
10 2 0 5 7 2 5 2
输出样例:

0:1
2:3
5:2
7:1
10:1
*/

#include <iostream>
using namespace std;
int t[55];
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int ag;
        cin>>ag;
        t[ag]++;
    }
    for(int i=0;i<=50;i++)
    {
        if(t[i])printf("%d:%d\n",i,t[i]);
    }
    return 0;
}

2.二维前缀和

/*
2.二维前缀和
输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式
第一行包含三个整数 n，m，q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式
共 q 行，每行输出一个询问的结果。

数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21
*/

#include <iostream>
using namespace std;
const int N=1010;
int s[N][N];
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int a;
            cin>>a;
            s[i][j]=a+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }

    while(q--)
    {
       int a,b,x,y;
       cin>>a>>b>>x>>y;
       int ans=0;
       ans=s[x][y]-s[x][b-1]-s[a-1][y]+s[a-1][b-1];
       cout<<ans<<endl;
    }
}

3.机器人过障碍

/*
机器人一次可以绕过1或2个障碍。给定N(1≤N≤30)个障碍，求绕过这 N 个障碍的方案数。

输入格式:
第一行一个正整数 N。
输出格式:
一个正整数，表示方案数。
*/
#include <iostream>
using namespace std;
const int N=35;
int a[N];
int main()
{
    int n;
    cin>>n;
    a[1]=1,a[2]=2;
    for(int i=3;i<=n;i++)
    a[i]=a[i-1]+a[i-2];
    cout<<a[n];
    return 0;
}

22真题

1.无人机大靶

/*
题目描述
有 N支队伍参赛，每个队伍的无人机成绩为 S，
且每个无人机颜色被随机涂为蓝（b）、红（r）、绿（g）、紫（p）之一。

输入格式
第一行包含整数 N表示参加的队伍数目，即无人机数目。
接下来 N行，每行包含每支参赛队伍的无人机颜色和打靶成绩 S由空格分隔开。

输出格式
输出内容由两部分组成。
第一部分输出各种颜色对应的无人机数目。
第二部分根据按照成绩从大到小进行排序，输出无人机打靶成绩 S和对应的无人机颜色。

数据范围
1<=N<=30
1<=𝑁<=30
0<=S<=100
输入样例
5
b 80
p 95
b 85
g 90
r 90
输出样例
blue 2
green 1
purple 1
red 1

95 purple
90 green
90 red
85 blue
80 blue
*/

#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=35;

struct RO
{
    string c;
    int s;
    bool operator< (const RO&t)const
    {
        return s>t.s;
    }//顺序

    bool operator> (const RO&t)const
    {
        return  s<t.s;
    }//逆序
}ro[N];

int main()
{
    int n;
    cin>>n;
    int b=0,g=0,p=0,r=0;
    for(int i=0;i<n;i++)
    {
        char op;
        int a;
        cin>>op>>a;
        ro[i].s=a;
        if(op=='b'){ro[i].c="blue";b++;}
        else if(op=='g'){ro[i].c="green";g++;}
        else if(op=='p'){ro[i].c="purple";p++;}
        else {ro[i].c="red";r++;}
    }
    sort(ro,ro+n);
    for(int i=0;i<n;i++)
    {
        printf("%d %s\n",ro[i].s,ro[i].c.c_str());
    }
    sort(ro,ro+n,greater<RO>());
    printf("%s %d\n%s %d\n%s %d\n%s %d\n\n","blue",b,"green",g,"purple",p,"red",r);
    for(int i=0;i<n;i++)
    {
        printf("%d %s\n",ro[i].s,ro[i].c.c_str());
    }
}

2.顺子

/*
二、顺子
从扑克牌中抽取5张，其中A、J、Q、K分别表示 1、11、12、13，大小王用 0 表示,如果五张牌可以连成顺序则称为顺子，大小王可以表示任意数字。现在输入五张牌的牌面，判断是否为顺子。

算法思想
最大值 - 最小值 < 5 并且 除了大小王没重复的牌 → 是顺子
*/
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
vector<int> a;
int main()
{
    for(int i=0;i<5;i++)
    {
        string x;
        cin>>x;
        if(x>="0"&&x<="9")a.push_back(stoi(x));
        else if(x=="10")a.push_back(10);
        else if(x=="A")a.push_back(1);
        else if(x=="J")a.push_back(11);
        else if(x=="Q")a.push_back(12);
        else if(x=="K")a.push_back(13);
        else if(x=="W"||x=="w")a.push_back(0);
    }

    int maxx=a[0],minn=a[0];
    unordered_set<int> s;
    for(int x:a)
    {
        if(x==0)continue;
        else if(x>maxx)maxx=x;
        else if(x<minn)minn=x;
        if(s.count(x))return false;
        s.insert(x);
    }

    if((maxx-minn)<5)cout<<"是顺子";
    else cout<<"不是顺子";
}

3.递归实现指数型枚举

/*
三、递归实现指数型枚举
计算机视觉算法：检测获取一组候选物体，每个物体具有一个特征值，
其中 Wi 为正整数，现研究基于特征值选取物问题，
表示为< s, c >，s={W1, W2, …, Wn}，表示候选物体的特征值集合，
其中 Wi 为正整数，表示第 i 个物品的特征值；
C 为正整数，代表需达到目标特征值。
要求编程寻找 s 的子集，使子集中物体的特征值之和为 C.

程序输入模式：
第一行包括 2 个正整数 N 和 C，N 代表 S 中候选物体总数，
C 代表需要达到目标特征值；
第二行包括 N 个正整数（1≤N≤100），代表 S。

程序输出格式为：满足条件的 S 的子集（1 行 1 个）
或者当问题无解时，输出“None”。
*/

21真题

1.马鞍点

#include <iostream>
using namespace std;
const int N=15;
int a[N][N];
int mi[N],ma[N];
int cnt;

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];


    for(int i=1;i<=n;i++)
    {
        ma[i]=a[i][1];
       for(int j=1;j<=m;j++)
        {
            if(a[i][j]>ma[i])ma[i]=a[i][j];
        }
    }
    for(int j=1;j<=m;j++)
    {
        mi[j]=a[1][j];
       for(int i=1;i<=n;i++)
        {
            if(a[i][j]<mi[j])mi[j]=a[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==ma[i]&&a[i][j]==mi[j])
            {
                cnt++;
                printf("%d %d %d\n",i,j,a[i][j]);
            }
        }
    }
    if(cnt==0)puts("NO");

}