寒假Day28：[蓝桥杯2019初赛]后缀表达式+修改数组

 [蓝桥杯2019初赛]后缀表达式

题目链接：http://oj.ecustacm.cn/problem.php?id=1467

题目描述

给定N 个加号、M 个减号以及N + M + 1 个整数A1,A2,...,AN+M+1
小明想知道在所有由这N 个加号、M 个减号以及N + M +1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？
请你输出这个最大的结果。
例如使用1 2 3 + -，则“2 3 + 1 -” 这个后缀表达式结果是4，是最大的。

输入

第一行包含两个整数N 和M。
第二行包含N + M + 1 个整数A1,A2,...,AN+M+1
0<=N,M<=100000,-10^9<=Ai<=10^9

输出

输出一个整数，代表答案。

样例输入 Copy

1 1
1 2 3

样例输出 Copy

4

https://blog.csdn.net/ryo_218/article/details/89515960

https://blog.csdn.net/weixin_42765557/article/details/88914230

思路可以看一下上面两个博客，这俩博客的代码也存在问题，

由于我的代码没过完所有数据，暂不放思路。

网上的代码貌似都不对，无法过完全部数据，

我的代码（没有AC，待解决）：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N=100020;
typedef long long ll;

ll a[N],z[N],f[N];

bool cmp1(ll x,ll y)
{
    return x>y;
}

int main()
{
    ll n,m,sum=0,sum1=0,sum2=0;
    cin>>n>>m;
    int p=0,q=0;
    for(int i=0; i<n+m+1; i++)
    {
        cin>>a[i];
        sum+=a[i];
        if(a[i]>=0)
            z[p++]=a[i],sum1+=a[i];
        else
            f[q++]=a[i],sum2+=a[i];
    }
//    if(n==0)
//        cout<<(-1)*sum<<endl;
    if(m==0)
        cout<<sum<<endl;
    else
    {
        sum=0;
        sort(z,z+p);
        sort(f,f+q);
        if(m==q)
            sum=sum1+(-1)*sum2;
        else if(m<q)//负数比负号多
        {
            sum=0;
            ll ss=0;
            int s=1;
            for(int i=0;i<q;i++)
            {
                if(s<m)
                sum=sum+(-1)*f[i],s++;
                else
                    ss+=f[i];
            }
            sum=sum+(-1)*ss+sum1;
//            int s=0;
//            for(int i=0;i<q;i++)
//            {
//                if(s<m)
//                    sum-=f[i],s++;
//                else
//                    sum+=f[i];
//            }
//            sum+=sum1;
        }
        else if(m>q)//负号比负数多
        {
            int s=m-q;
            for(int i=0; i<p; i++)
            {
                if(s)
                    sum=sum-z[i],s--;
                else
                    sum+=z[i];
            }
            sum+=sum2*(-1);
        }
        cout<<sum<<endl;
    }
    return 0;
}

补充：

• 前缀表达式求值

例如前缀表达式“- × + 3 4 5 6”计算的步骤如下：

(1) 从右至左扫描，将6、5、4、3压入堆栈；
(2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈；
(3) 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈；
(4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

• 后缀表达式：又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。

后缀表达式计算：

例如：后缀表达式为“2 3 + 4 × 5 -”计算过程如下：
  （1）从左至右扫描，将 2 和 3 压入堆栈；
  （2）遇到 + 运算符，因此弹出 3 和 2（ 3 为栈顶元素，2 为次顶元素，注意与前缀表达式做比较），计算出 3+2 的值，得 5，再将 5 入栈；
  （3）将 4 入栈；
  （4）接下来是 × 运算符，因此弹出 4 和 5，计算出 4 × 5 = 20，将 20 入栈；
  （5）将 5 入栈；
  （6）最后是-运算符，计算出 20-5 的值，即 15，由此得出最终结果。

• 中缀表达式的话就是一般我们看到的那种正常表达式啦

[蓝桥杯2019初赛]不同子串

题意：判断原串中有多少不同字串

思路：暴力+set即可

AC代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
const int N=100020;
typedef long long ll;

set<string>s;

int main()
{
    string ss,a;
    a="0100110001010001";
    for(int i=0;i<a.length();i++)
    {
        ss.clear();
        ss+=a[i];
        s.insert(ss);
        for(int j=i+1;j<a.length();j++)
        {
             ss+=a[j];
             s.insert(ss);
        }
    }
    cout<<s.size()<<endl;
    return 0;
}

[蓝桥杯2019初赛]修改数组

给定一个长度为N 的数组A = [A1, A2,...,AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2,A3,..., AN。
当修改Ai 时，小明会检查Ai 是否在A1~ Ai-1 中出现过。
如果出现过，则小明会给Ai 加上1 ；
如果新的Ai 仍在之前出现过，小明会持续给Ai 加1 ，直到Ai 没有在A1~Ai-1中出现过。
当AN 也经过上述修改之后，显然A数组中就没有重复的整数了。
现在给定初始的A 数组，请你计算出最终的A 数组。

输入

第一行包含一个整数N(1<=N<=100000)
第二行包含N个整数A1,A2,...,AN(1<=Ai<=1000000)

输出

输出N个整数，依次是最终的A1,A2,...,AN

样例输入 

5
2 1 1 3 4

样例输出 

2 1 3 4 5

思路：一开始的想法，我用book把之前没有出现过的标记，出现过的while进行暴力，但会造成超时，拿不到全部的分数，貌似80%，感觉也没有什么新奇的思路，于是查了一下，有新奇的思路->并查集

参考博客：https://blog.csdn.net/weixin_42765557/article/details/89480557

如何引入和判断并查集关键：

    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        int x=getf(a[i]);
        a[i]=x;
        f[x]=getf(x+1);
    }

AC代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100020;
typedef long long ll;

int a[N],f[N];

int getf(int x)
{
    if(x==f[x])
        return x;
    return f[x]=getf(f[x]);
}

int main()
{
    for(int i=1; i<=N; i++)
        f[i]=i;
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        int x=getf(a[i]);
        a[i]=x;
        f[x]=getf(x+1);
    }
    for(int i=0; i<n-1; i++)
        cout<<a[i]<<" ";
    cout<<a[n-1]<<endl;
    return 0;
}

待解决：

• 蓝桥杯后缀表达式，原因写在上面题目之后了