上海市计算机学会月赛 2022年1月月赛丙组
发布时间
阅读量：
阅读量
上海市计算机学会月赛 2022年1月月赛丙组
-
- 三角形的判定
- 星号三角阵（一）
- 匹配括号的判定
- 走走跳跳
- 击鼓传花
三角形的判定
算法分析:
简单数学题，三角形两边之和大于第三边
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int a, b, c;
cin >> a >> b >> c;
if (a + b > c && b + c > a && a + c > b)
cout << "Valid";
else
cout << "Invalid";
return 0;
}星号三角阵（一）
算法分析：
找规律，每行的*都是以1递增的
#include <iostream>
using namespace std;
int n;
int main() {
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n ; ++i) {
for (int j = 1; j <= i; ++j)
cout << "*";
cout<<endl;
}
return 0;
}匹配括号的判定
算法分析：
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
string s;
stack<char> st;
int main()
{
ios::sync_with_stdio(false);
cin >> s;
for (int i = 0; i < s.size(); ++i)
{
if (s[i] == '(' || s[i] == '[')
st.push(s[i]);
else
{
if (st.empty())
{
cout << "Unbalanced";
return 0;
}
if ((s[i] == ')' && st.top() == '(') || (s[i] == ']' && st.top() == '['))
st.pop();
else
{
cout << "Unbalanced";
return 0;
}
}
}
if (st.empty())
cout << "Balanced";
else
cout << "Unbalanced";
return 0;
}走走跳跳
算法分析：
动态规划是一种解决最优化问题的有效方法。通过逆序递推的方式，我们可以计算起点的最大积分。状态转移方程也可以直观地看出（比较前一步的积分与跳步后的积分大小）。
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
long long i, n, a[100001], t[100000], dp[100001];
cin >> n;
for (i = 1; i <= n; ++i)
cin >> a[i];
for (i = 1; i < n; ++i)
cin >> t[i];
dp[n] = a[n];
for (i = n - 1; i >= 1; --i)
dp[i] = max(dp[i + 1], dp[t[i]]) + a[i];
cout << dp[1];
return 0;
}击鼓传花
算法分析：
这道题同样考察动态规划方法（逆向思维）。状态转移方程的核心问题在于：我应该选择取当前值还是不取？选择取的话，则当前值等于上一轮的分数；若选择不取，则当前值保持为花的数量。
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n, a[200010], dp[200010], sum[200010];
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
dp[n] = sum[n] = a[n];
for (int i = n - 1; i >= 1; --i)
{
sum[i] = sum[i + 1] + a[i];
dp[i] = max(dp[i + 1], sum[i] - dp[i + 1]);
}
cout << dp[i];
return 0;
}全部评论 (0)
还没有任何评论哟~