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

• • 三角形的判定
  • 星号三角阵（一）
  • 匹配括号的判定
  • 走走跳跳
  • 击鼓传花

算法分析:
简单数学题，三角形两边之和大于第三边

#include 
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 
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< 
匹配括号的判定 
算法分析：
 这道题考数据结构-栈，先进后出。如果是），栈首肯定有一个（，然后（出栈，反之不匹配。
 
#include 
#include 
#include 
using namespace std;
string s;
stack 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 
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 
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;
}