上海市计算机学会竞赛平台 5月月赛 丙组
T1 三角形的分类
题目描述
给定三个角度 a ， b 及 c 。请判断这三个角在平面上能组成什么样的三角形：
若无法构成三角形，则应返回 Error
若能构成等边三角形，则输出 Equilateral
若能构成等腰直角三角形，则输出 Isosceles right
若能构成等腰三角形，则输出 Isosceles
若能构成直角三角形，则输出 Right
若能构成不等边三角形，则输出 Scalene
输入格式
第一行：第一个角度的大小为 a
第二行：第二个角度的大小为 b
第三行：第三个角度的大小为 c
输出格式
根据题目要求输出对应的文字
数据范围
1≤a,b,c≤180
样例数据
输入:
60
60
60
输出:
Equilateral
分析
虽然直接可以用if语句嵌套来解决这个问题，但这种做法可能会遗漏一些特殊情况。如果不加以限制的话，则可能出现将等腰直角三角形误认为是等腰或直角三角形的情形。
代码
#include <bits/stdc++.h>
using namespace std;
int a, b, c;
int main(){
cin >> a >> b >> c;
if (a < b) swap(a, b);
if (b < c) swap(b, c);
if (a < b) swap(a, b);
//将abc从大到小排序，方便判断
if (a + b + c != 180) printf("Error");
else if (a == 60 && b == 60 && c == 60)
printf("Equilateral");
else if (a == 90 && b == c)
printf("Isosceles right");
else if (a == b || a == c || b == c)
printf("Isosceles");
else if (a == 90)
printf("Right");
else
printf("Scalene");
return 0;
}T2 区间最大公约数
题目描述
设L和R是两个给定的正整数，在区间[L, R]内共有若干个整数可供选择。你可以从这些整数中任取两个不同的数x和y（其中L≤x<y≤R），计算它们的最大公约数值是多少？
输入格式
输入共一行，两个正整数表示L,R
输出格式
输出共一个整数，表示所求答案
数据范围
对于30%的数据，1≤L<R≤100
对于60%的数据，1≤L<R≤10^3
对于100%的数据，1≤L<R≤5×10^5
样例数据
输入:
23 29
输出:
4
说明:
选(24,28)时，取到最大值为 4
输入:
32768 32769
输出:
1
分析
已知条件中给出两个数为a\times c和a \times (c-1)，其中a一定是他们的公因数。如果这两个数位于区间l至r之间，则由此可知a就是它们的公因数。进而我们可以枚举所有可能解。
代码
#include <bits/stdc++.h>
using namespace std;
int l, r, ans = 1;
int main(){
cin >> l >> r;
for (int i = 2; i <= r; i++){
int x = r / i * i;
if (x - i >= l) ans = i;
}
cout << ans << endl;
return 0;
}T3 滑雪训练
题目描述
最近小爱对滑雪产生了浓厚的兴趣。该滑雪场提供了n条不同难度设置的雪道，在熟练掌握了第i条雪道的技术后，并非直接就可以进入第i+1条雪道的学习与训练阶段。
假设在初次滑雪第i条雪道时，必须先投入a_i分钟的学习阶段，并接着花费b_i分钟才能完成该雪道的学习任务。如果随后再次滑雪第i条雪道，则只需花费b_i分钟就能再次完成。
小爱共有 T 分钟时间，请问如何安排才能使他能滑的圈数最多？
输入格式
开头一行给出两个正整数值 n, T
随后有n个部分
每个部分包含两个正整数a_i, b_i
分别代表第i条雪道的学习时间和滑雪时长
输出格式
输出一个正整数，表示小爱最多可以滑的圈数。
数据范围
针对30%的数据集进行测试；针对60%的数据集进行验证；在全部数据情况下完成算法设计与实现
样例数据
投入三个小时进行专业技能培训
分析
这题可以通过研究不同赛道的学习效果来确定最佳选择。
首先我们来分析总时间T如何分配为学习时间和滑雪时间（分别用a_i和b_i表示）。其中b必须是学完后的最后一段赛道这样才能够使他在滑行过程中获得最多的圈数。一旦a已经确定下来那么$b也随之确定它就是你在完成所有课程之后所剩下的最后一段练习机会因为如果你当前耗时最少的并不是最后一条那么从这条开始往后都不应该再进行学习否则会导致整体效率低下所以这种情况下就不可能是最优解而只有当这个方案经过验证并证明其最优性才会被采用。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
long long n, t, b[MAXN], tim[MAXN];
int main(){
cin >> n >> t;
memset(tim, 0, sizeof(tim));
for (int i = 1; i <= n; i++){
int a;
cin >> a >> b[i];
tim[i] = tim[i - 1] + a + b[i]; //记录学习到第i条所需的时间
if (tim[i] > t){//数据最大时会爆long long，进行判断
n = i - 1;
break;
}
}
long long ans = 0;
for (int i = 1; i <= n; i++){
long long a = t - tim[i];
ans = max(ans, a / b[i] + i);//比较圈数
}
cout << ans << endl;
return 0;
}T4 混乱的文本
题目描述
小爱正在使用一种文本编辑器输入文字。文本编辑器的工作机制如下：
当用户输入一个 [时，在当前光标位置直接定位到整个文本的第一个字符之前的位置。
当用户输入一个 ]时，在当前光标位置直接定位到最后一个字符之后的位置。
任意字符被输入时，在当前光标位置插入该字符，并使光标移动至字符之后的位置。
根据给定的一系列输入字符，请确定最终生成的文字内容。
输入格式
一个字符序列：表示键入的字符序列。
输出格式
一个字符序列：表示最后获得的文本。
数据范围
设 nn 表示输入字符序列的长度
约3成的数据满足条件。
其中约6成的数据满足条件。
全部数据均满足条件。
样本数据：
输入:
abc[xyz]efg
输出:
xyzabcefg
分析1
我在最初尝试解决这个问题时，首先想到了字符串内置了insert函数，并且仅需使用一个变量来标记光标的位置，并通过特定的符号（如[和]）来调整其位置。
代码1
#include <bits/stdc++.h>
using namespace std;
string s, ans;
int k = 0;
int main(){
cin >> s;
int l = s.size();
int len = 0;
for (int i = 0; i < l; i++){
string ss = "";
ss += s[i];
if (s[i] == '[') k = 0;//改变位置
else if (s[i] == ']') k = len;
else {
len++;
ans.insert(k, ss);
k++;
}
}
cout << ans << endl;
return 0;
}不知道insert函数的时间复杂度，初测100，复测80，两个点超时。
分析2
将给定的字符串分割为 [ ] 的部分进行处理。每当遇到 [ ，将其对应的另一个字符串保存到指定的位置；当遇到 ] 时，在第一个数组之后追加对应的元素；最后按逆序排列输出结果
代码2
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
string s, ans[MAXN];
int num = 1, n = 1;//num是当前是第几个字符串，n是一共多少字符串
int main(){
cin >> s;
int l = s.size();
int len = 0;
for (int i = 0; i < l; i++){
if (isalpha(s[i])){
ans[num] += s[i];
}else{
if (s[i] == '['){
n++;
num = n;
}else{
num = 1;
}
}
}
for (int i = n; i >= 1; i--)
cout << ans[i];
cout << endl;
return 0;
}T5 最大子阵和
题目描述
设有n \times n个整数组成一个方阵a_{i,j}。请确定存在这样一个k \times k的子矩阵，并使该子矩阵内部元素的总和达到全局最大值，并输出该最大值。
输入格式
第一行：两个整数 n 与 k
第二行到第 n+1 行：每行 n 个整数表示 a_{i,j}
输出格式
单个整数：表示最大的 k\times k 的子方阵的数字之和。
数据范围
30% 的数据，1\leq k\leq n\leq 30
60% 的数据，1\leq k\leq n\leq 300
100% 的数据，1\leq k\leq n\leq 2500
0\leq a_{i,j}\leq 1,000,000
样例数据
输入:
3 2
1 2 3
3 1 2
0 2 4
输出:
9
说明:
右下角最大
分析1：枚举
枚举子阵的左上角的位置（a_{1,1}到a_{n-k+1,n-k+1}），循环将子阵和求出并比较。
代码1
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[3010][3010];
int main(){
cin >> n >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
int ans = -1;
for (int i = 1; i <= n - k + 1; i++){
for (int l = 1; l <= n - k + 1; l++){
int an = 0;
for (int j = 0; j < k; j++){
for (int q = 0; q < k; q++)
an += a[i + j][l + q];
}
ans = max(ans, an);
}
}
cout << ans << endl;
return 0;
}时间复杂度O(n^4),应该30分，但初测复测都是60
分析2：前缀和
在解决字段大小问题时，默认可用前缀和方法；但本题则突破传统思路，在单维度拓展至双维度场景下应用前缀和算法。
对于上图，将a[x,y]的值转化为它的面积，那么
a_{x,y}=a_{x,y-1}+a_{x-1,y}-a_{x-1,y-1}+m
根据存好的数组求出对应的子阵和，进行比较
所以对于点a[x,y]，当其作为子阵右下角的点时：
S=a_{x,y}-a_{x-k,y}-a_{x,y-k}+a_{x-k,y-k}
假设n的最大值为2500，则意味着约需输入6,250,00个数值。使用标准输入方法（如cin$和scanf$）进行处理将导致程序运行超时。即便关闭流同步优化措施，在某些情况下仍需依赖运气因素来完成计算。
代码2
#include <bits/stdc++.h>
using namespace std;
long long n, k, ans;
long long x[2560][2560];
int main(){
std::ios::sync_with_stdio(false);
memset(x, 0, sizeof(x));
cin >> n >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++){
int num;
cin >> num;
x[i][j] = x[i - 1][j] + x[i][j - 1] - x[i - 1][j - 1] + num;
}
for (int i = k; i <= n; i++){
for (int j = k; j <= n; j++){
long long v = x[i][j] - x[i - k][j] - x[i][j - k] + x[i - k][j - k];
ans = max(ans, v);
}
}
cout << ans << endl;
return 0;
}