上海市计算机学会2022年10月月赛丙组试题
第一题 直角三角形判定
题目描述
给定三个正整数表示三角形的三条边，请判定它是否为直角三角形。
输入格式
第一行：三个整数 a，b 与 c
输出格式
若可以构成一个直角三角形，输出 Right Triangle
否则，输出 No
数据范围
1\leq a, b, c\leq 1000
样例输入1:
3 4 5
样例输出1:
Right Triangle
样例输入2:
3 3 3
样例输出2:
NO
分析
简单的分支结构判断，先将最大值交换到 c 中，再用勾股定理判断就行了。
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b, c;
cin >> a >> b >> c;
if (a > b) swap(a, b);
if (b > c) swap(b, c);
if (a * a + b * b == c * c)
cout << "Right Triangle" << endl;
else
cout << "No" << endl;
return 0;
}
AI写代码第二题 因子分解
题目描述
给定一个正整数 nn，请将它分解为素数的乘积。
例如 60=2\times2\times3\times5
输入格式
单个整数表示 n
输出格式
若干整数表示 n 的素因子，按照从小到大的顺序输出。
数据范围
2\leq n\leq 1,000,000,000
样例输入1:
60
样例输出1:
2 2 3 5
样例输入2:
3
样例输出2:
3
问题分析
- 考虑枚举 n 的因子，用 n 除它，直到不能整除，这样找到的因子一定是素因子。
for (int i = 2; i <= n; ++i)
while (n % i == 0){
cout << i << " ";
n /= i;
}
AI写代码算法是O(n)，超时。
- 结论：整数 n 大于 \sqrt n 的素因子可能有 0 或 1个。（
反证法容易证明)
因此，只需要枚举到 \sqrt n，如果最后原数还未变成 1，则该数一定是唯一的大于 \sqrt n 的素因子。时间复杂度：O(\sqrt n)。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n;
m = n;
for (int i = 2; i * i <= n; ++i){
while (m % i == 0){
cout << i << " ";
m /= i;
}
}
if (m != 1) cout << m << endl;
return 0;
}
AI写代码第三题 算术求值（一）
题目描述
给定一个由正整数、加号、减号构成的表达式，请计算表达式的值。
输入格式
输入一个由 正整数、+、- 构成的表达式
输出格式
单个整数：表示算式的值。
数据范围
数据保证输入的字符串长度不超过 100,000，其中出现的整数不超过 10000。
样例数据:
2+12-5
样例输出:
9
问题分析
简单模拟题
#include <bits/stdc++.h>
using namespace std;
int main(){
char op = '+';
long long ans = 0, t;
while (op != ' '){
cin >> t;
if (op == '+')
ans += t;
else
ans -= t;
op = ' ';
cin >> op;
}
cout << ans << endl;
return 0;
}
AI写代码第四题 门禁记录
题目描述
小爱得到了某大楼一天内按时间顺序记录的 n 条门禁出入记录，每条记录由两个字符串组成，第一个字符串为出入人员姓名，第二个字符串表示该人员进出状态、为 enter 或 exit 中一项，其中 enter 为进入， exit 为离开。
小爱发现，部分人员的门禁信息存在错误，即某人在没有进入记录时便有了离开记录，或是某人有进入记录但没有离开记录。
已知在第一条记录前及最后一条记录后，大楼内均没有任何人员。请你根据门禁记录，来分析哪些人员的门禁信息存在错误？
输入格式
输入第一行，一个正整数 n
接下来 n 行，每行两个字符串，以空格隔开，其中第 i + 1 行的两字符串分别表示第 i 条记录的人员姓名与出入信息。
输出格式
按字典序输出所有出入信息存在错误的人员姓名，按空格隔开
数据范围
对于30\%的数据，1 \leq n \leq 10
对于60\%的数据，1 \leq n \leq 10^3
对于100\%的数据，1 \leq n \leq 2\times10^4 ，且人员姓名字符串长度不超过10。
样例输入:
5
Xiaoai enter
Bob exit
Xiaoai exit
Alice exit
Alice enter
样例输出:
Alice Bob
说明:
Bob只有exit数据，存在信息缺失
Alice的exit数据前不存在enter，而在最后一条enter后也没有exit，存在信息缺失
问题分析
模拟题。
用map<string, string>标记每个人的状态，如果冲突就存储到set集合中。最后输出set中的名字即可。
#include <bits/stdc++.h>
using namespace std;
int main(){
map<string, string> mp;
int n;
string s, t;
set<string> ans;
cin >> n;
while (n--){
cin >> s >> t;
if (t == "enter"){
if (mp.find(s) != mp.end() && mp[s] == "enter")
ans.insert(s);
else
mp[s] = t;
}
else {
if (mp.find(s) == mp.end() || mp[s] == "exit"){
ans.insert(s);
} else {
mp[s] = t;
}
}
}
map<string, string>::iterator it;
for (it = mp.begin(); it != mp.end(); it++){
if (it->second != "exit") ans.insert(it->first);
}
for (set<string>::iterator it = ans.begin(); it != ans.end(); ++it)
cout << *it << " ";
cout << endl;
return 0;
}
AI写代码第五题 组队竞赛
题目描述
有 n 同学想要参加小爱组建的一支信息学竞赛队伍，每位同学有能力值 a_i 与热情度b_i 。
小爱认为，如果队伍当中，能力值最大与能力值最小选手之间，能力差值大于给定 X，会导致能力差距过大、不利于团队的学习与凝聚力。因此，请你帮助小爱计算下，如何选择队伍的选手，才能使所有选手的能力差值小于等于 X，且热情度最大。
输入格式
输入第一行，一个正整数 n，表示有 n 位选手
接下来 n 行，每行两个正整数a_i,b_i 表示每位选手的能力值与热情度。
最后一行，一个正整数 X，表示小爱希望的能力差值上限
输出格式
输出一个整数，表示满足条件的情况下，最大热情度的值
数据范围
对于30\%的数据，1 \leq n \leq 100
对于60\%的数据，1 \leq n \leq 10^4
对于100\%的数据，1 \leq n \leq 10^5,1 \leq d \leq 10^9,1 \leq a_i,b_i \leq 10^9
样例输入:
5
10 21
20 34
30 27
40 89
50 54
20
样例输出:
170
说明:
选第3、4、5个选手。
能力值分别为30、40、50，不超过50-30=20给定的能力差值上限20
此时热情度为27+89+54=170
问题分析
求能力值差不超过 x, 最大热情度的和。
- 枚举最小能力值，O(n)查找大于等于该能力值并且差值不大于X的热情度和，打擂台求最大值。时间复杂度：O(n^2).
- 按能力值排序，问题变成
能力值差不大于 X 的最大热情度区间和。指针 l 指向第一个人，r 向后移动找到能力值差值不大于 X的最远的人，维护区间内热情度的和，得到左端点为 1 的最大区间和。l每次向后移动， r 向后找能力值差值不大于X的最远的人，维护区间热情度和，打擂台求最大值即可。 当 r = n 循环结束，即可找到解。时间复杂度：O(n\log n)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1E5 + 10;
struct nod{
int a, b;
};
bool cmp(nod p, nod q){
return p.a < q.a;
}
nod c[MAXN];
int n, x;
int main(){
cin >> n;
for (int i = 0; i < n; ++i)
cin >> c[i].a >> c[i].b;
cin >> x;
sort(c, c + n, cmp);
long long ans = 0, s2 = 0;
int l = 0, r = 0;
while (r < n){
while (r < n && c[r].a - c[l].a <= x){
s2 += c[r].b;
r++;
}
ans = max(ans, s2);
s2 -= c[l].b;
l++;
}
cout << ans << endl;
return 0;
}
AI写代码