上海市计算机学会2022年10月月赛丙组解题报告
上海市计算机学会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
分析
\bullet 勾股定理直接判断三个数是否满足直角三角形三边条件即可
#include <bits/stdc++.h>
using namespace std;
int a , b , c;
int main(){
cin >> a >> b >> c;
int ga = a * a , gb = b * b , gc = c * c;
if((ga + gb == gc) || (ga + gc == gb) || (gb + gc == ga))
cout << "Right Triangle" << endl;
else
cout << "No" << endl;
return 0;
}因子分解
题目描述
给定一个正整数 nn，请将它分解为素数的乘积。
例如 60=2\times2\times3\times5
输入格式
单个整数表示 n
输出格式
若干整数表示 n 的素因子，按照从小到大的顺序输出。
数据范围
2\leq n\leq 1,000,000,000
样例数据
输入:
60
输出:
2 2 3 5
输入:
3
输出:
3
分析
\bullet 依次枚举n 的因子直到相同为止最后输出n
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
for(int i = 2; i <= n; ++i)
while(n != i){
if(n % i == 0){
cout << i << " ";
n /= i;
}
else break;
}
cout << n << endl;
return 0;
}算式求值（一）
题目描述
给定一个由正整数、加号、减号构成的表达式，请计算表达式的值。
输入格式
输入一个由 正整数、+、- 构成的表达式
输出格式
单个整数：表示算式的值。
数据范围
数据保证
输入的字符串长度不超过 100000，
其中出现的整数不超过 10000。
样例数据
输入:
2+12-5
输出:
9
分析
\bullet 和一年普及组T2相似
\bullet while(cin) 读入每次读入一个符号和一个数字判断加减
代码
#include <bits/stdc++.h>
using namespace std;
string s;
char ch;
long long ans , n;
int main(){
cin >> ans;
while(cin >> ch >> n){
if(ch == '-')
ans -= n;
else
ans += n;
}
cout << ans << endl;
return 0;
}门禁记录
题目描述
小爱得到了某大楼一天内按时间顺序记录的nn条门禁出入记录，每条记录由两个字符串组成，第一个字符串为出入人员姓名，第二个字符串表示该人员进出状态、为 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，存在信息缺失
分析
\bullet map映射每个人名进出次数，如果进入就加一，离开就减一
\bullet 出现<0或者>2就是进入两次或者只有离开没有进入记录，数组记录字典序sort排序输出
代码
#include <bits/stdc++.h>
using namespace std;
map <string , int> mp;
string st , s[20010] , ss[20010] , s1 = "enter" , s2 = "exit";
int main(){
mp.clear();
int n , j = 0;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> s[i] >> st;
if(st == s1)
mp[s[i]]++;
else if(st == s2)
mp[s[i]]--;
if(mp[s[i]] < 0 || mp[s[i]] > 1)
ss[++j] = s[i];
}
int kk = j;
sort(ss + 1 , ss + j + 1);
for(int i = 1; i <= j; ++i)
if(mp[s[i]] != 0)
ss[++kk] = s[i];
sort(ss + 1 , ss + kk + 1);
for(int i = 1; i <= kk; ++i)
if(ss[i] != ss[i + 1])
cout << ss[i] << " ";
return 0;
}组队竞赛
题目描述
有nn同学想要参加小爱组建的一支信息学竞赛队伍，每位同学有能力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 \geq 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
分析
\bullet 定义两个数组 ， 读入后将能力值相同的直接复制到第二个数组中一起计算（此步骤可省略 ， 删去无影响）
\bullet 和一年普及组题目海港相似
\bullet 结构体读入sort排序 ， 从开头到结尾分成每个开始和结尾不同的区间每次遇到能力差大于X时 ， 区间开头变换 ， 同时计数总和减去所对应的热情度 ， 每次打擂台作比较输出最大值
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
struct nod{
int a , b;
}x[MAXN] , xx[MAXN];
bool cmp(nod p , nod q){
return p.a <= q.a;
}
int main(){
long long n , q;
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> x[i].a >> x[i].b;
cin >> q;
sort(x + 1 , x + 1 + n , cmp);
long long ans = 0 , maxs = 0;
long long minv = 1 , maxv = 1;
while(maxv <= n){
maxs += x[maxv].b;
while(x[maxv].a - x[minv].a > q){
maxs -= x[minv].b;
minv++;
}
maxv++;
ans = max(ans , maxs);
}
cout << ans << endl;
return 0;
}或把能力值相同的统计到同一数组
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
struct nod{
int a , b;
}x[MAXN] , xx[MAXN];
bool cmp(nod p , nod q){
return p.a <= q.a;
}
int main(){
long long n , q;
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> x[i].a >> x[i].b;
cin >> q;
sort(x + 1 , x + 1 + n , cmp);
int ii = 0;
for(int i = 1; i <= n; ++i){
if(x[i].a != xx[ii].a){
xx[++ii].a = x[i].a;
xx[ii].b = x[i].b;
}
else
xx[ii].b += x[i].b;
}
long long k = ii;
long long ans = 0 , maxs = 0;
long long minv = 1 , maxv = 1;
while(maxv <= k){
maxs += xx[maxv].b;
while(xx[maxv].a - xx[minv].a > q){
maxs -= xx[minv].b;
minv++;
}
maxv++;
ans = max(ans , maxs);
}
cout << ans << endl;
return 0;
}