上海市计算机学会月赛 2022年1月月赛丙组

上海市计算机学会月赛 2022年1月月赛丙组"/>

上海市计算机学会月赛 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";elsecout << "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;
}