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