蓝桥杯2019年第十届省赛真题-后缀表达式

题目

题目链接

题解

思维+数学（?）

说三点吧！

1. 后缀表达式就是无括号的中缀表达式，也就是我们平时的加减运算去掉括号、重新排序，且仍能保证运算（优先级）跟之前一样的表达式。中缀表达式可以通过加括号“随意”改变运算顺序，改变优先级，所以后缀表达式也是一样的，所以在理解的时候我们完全可以理解为一堆数进行排列，在这些数中插入若干个加若干个减，同时还可以加括号改变运算顺序，问结果最大是多少。

2. 结论： 相比于加号，减号的存在非常特殊！

   ① 如果全是加号，答案是所有数字直接相加； ② 如果存在减号， Ⅰ 如果全是正数，结果为全部数之和减去两倍的最小数； Ⅱ 如果全是负数，结果为全部数的绝对值之和减去两倍最小数的绝对值； Ⅲ 如果有正有负，结果为全部数的绝对值之和.

3. 分析存在符号的情况： 规定⊕表示剩下的正数之和，⊙表示剩下的负数之和，假设整个序列为±1,±2,±3,...

   全正：

   1个		⊕-1
   2个		-(1-⊕)
   3个		-(1-⊕-2)
   4个		-(1-⊕-2-3)
   

   全负：

   1个		(-1)-⊙
   2个		-(⊙-(-1))
   3个 		-(⊙-(-1))-(-2)
   4个		-(⊙-(-1))-(-2)-(-3)
   

   有正有负：

   1个														⊕-⊙
   ±1								+													-
   2个							⊕-(⊙-1)											⊕-⊙-(-1)
   ±2				+								-						+							-
   3个			⊕-(⊙-1-2)				      ⊕-(⊙-1)-(-2)		  ⊕-(⊙-2)-(-1)			⊕-⊙-(-1)-(-2)
   
   总结：最小的x为正数，x与⊙合并构成-(⊙-x)；最小的x为负数，x与⊕合并构成⊕-x。
   

算是找规律？我不会

代码

#include
using namespace std;
const int N = 2e5+10;
typedef long long LL;

int n, m;
LL ans;
LL a[N];

int main()
{
	cin >> n >> m;
	for(int i = 0;i > a[i];
	sort(a, a + n + m + 1);

	if (!m) {
		for (int i = 0;i