A.小田的宝石镇

---

难度：⭐

思路

有2种路线：

（1）走11条$a$。

（2）先一条$a$下来，再走五条$b$。

比大小即可。

代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    freopen("gem.in", "r", stdin);
    freopen("gem.out", "w", stdout);
    long long a,b;
    cin>>a>>b;
    cout<<min(a*11,a+b*5);
    return 0;
}

要点

• 没有想到更加简单的直接比较，而是写了更加复杂的算法✅

---

B.小田的好数组

---

难度：⭐⭐

思路

有2种情况：

（1）有序，怎么选都不行，结果为0。

（2）无序，全选即可，结果为$n$。

代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    freopen("hsz.in", "r", stdin);
    freopen("hsz.out", "w", stdout);
    int n,f=0;
    cin>>n;
    int r=-1;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x<r){
            f=n;
        }
        r=x;
    }
    cout<<f;
    return 0;
}

要点

• 没有想到分类讨论，想的角度不够多，这种难度的题目应该优先思考分类讨论🧾

---

C.小田的数字合并

---

难度：⭐⭐

思路

跟最大值与最小值没有关系，每个数都有可能是当时的最大值或最小值。

合并的数一定是一个子串，因为：

假设最优合并的最小值为$a_i$,那么$a_i$一定不会被合并，不是合并左边的所有就是合并右边的所有。如果一边大，那么合并另一边就没有意义；如果相等，任意一边即可。

由于我们不知道最优合并的最小值，所以需要遍历枚举；两边的子串和用前缀和与后缀和求得。

取其最小值即可。

代码

#include<bits/stdc++.h>
using namespace std;
long long sq[200005],sh[200005],a[200005];
int main() {
    freopen("num.in", "r", stdin);
    freopen("num.out", "w", stdout);
    long long n,mx=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sq[i]=sq[i-1]+a[i];
    }
    for(int i=n;i>=1;i--){
        sh[i]=sh[i+1]+a[i];
        long long q=sq[i-1]-a[i];
        long long h=sh[i+1]-a[i];
        long long nowmx=max(q,h);
        mx=max(mx,nowmx);
    }
    cout<<mx;
    return 0;
}

要点

• 单单从“最大值”与“最小值”的方面去想了，结果就是一个点一直想不出来，后来才发现这个思路有问题。优化时想思路时可以一直想，因为这个框架是对的。但是核心思路不对，一直想会越想越复杂，这种情况下应该及时想一想另外的思路，看看是否想得通（最好打个草稿"存档“）💡

---

D.化学式的原子数

---

难度：⭐⭐⭐

思路

类似于表达式求值，用栈和哈希（map）来解。

栈的作用：存放map，遍历的时候就不用找这个找那个，会轻松许多。

map的作用：存放表达式里面各项原子的个数（括号里面单独在栈里存一个新的map)。

先来遍历字符串：

如果遇到“（”，建立一个新的map，入栈（具体代码：q.push({}）)。

如果遇到“）”，合并栈底的第一个和第二个map。

否则，用$getnum$和$getstr$函数将原子名称和原子数量提取，存入栈底的map。

最后合并栈里剩下的map，输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
int i=0;
string s;
stack<map<string,int>> st;
map<string,int> mp;
int getnum(){
    int num=0;
    while(s[i]>='0'&&s[i]<='9'&&i<s.size()){
        num=num*10+(s[i]-'0');
        i++;
    }
    if(num==0){
        num=1;
    }
    return num;
}
string getstr(){
    string s2="";
    while(((s[i]>='a'&&s[i]<='z')||s2=="")&&i<s.size()){
        s2+=s[i];
        i++;
    }
    return s2;
}
int main(){
    freopen("atom.in", "r", stdin);
    freopen("atom.out", "w", stdout);
    cin>>s;
    st.push({});
    while(i<s.size()){
        if(s[i]=='('){
            st.push({});
            i++;
        }else if(s[i]==')'){
            i++;
            int v=getnum();
            map<string,int> mp2=st.top();
            st.pop();
            for(auto j:mp2){
                j.second*=v;
                st.top()[j.first]+=j.second;
            }
        }else{
            string t=getstr();
            int v=getnum();
            st.top()[t]+=v;
        }
    }
    while(!st.empty()){
        
        for(auto idx:st.top()){
            mp[idx.first]+=idx.second;
        }
        st.pop();
    }
    for(auto idx:mp){
        cout<<idx.first<<' '<<idx.second<<endl;
    }
    return 0;
}

要点

• 做的时候看到直接放弃，但复现赛写的时候却一下就过了，思路也很简单，骗分也很容易，不应该看一眼就放弃🙋‍♂️
• 写的时候许多语法不会用，代码积累还不够多📖

---

E .小W挖宝藏

---

难度：⭐⭐

思路

DFS+记忆化。

看到题目很容易能想到DFS，但是数据范围确实冷酷无情，所以还要加上记忆化缓缓关系。

用一个记忆化数组$b$,$b_{x,y}$表示从$(x,y)$开始搜索最多可以走几格，如果某一次搜索搜到$(x,y)$且$b_{x,y}$有数就直接返回$b_{x,y}$，$b_{nowx,nowy}$在这一次往四周搜索返回的值更新。最后返回$b{x,y}$

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,ans;
int a[110][110];
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
long long f[110][110];
long long dfs(int x,int y){
    if(f[x][y]>0){
        return f[x][y];
    }
    for(int i=0;i<4;i++){
        int nowx=dx[i]+x;
        int nowy=dy[i]+y;
        if(!(nowx>=1&&nowx<=n&&nowy>=1&&nowy<=m)){
            continue;
        }
        if(a[x][y]<=a[nowx][nowy]){
            continue;
        }
        long long t=dfs(nowx,nowy)+1;
        f[x][y]=max(f[x][y],t);
    }
    return f[x][y];
}
int main(){
    freopen("treasure.in", "r", stdin);
    freopen("treasure.out", "w", stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(dfs(i,j)+1>ans){
                ans=dfs(i,j)+1;
                x=i;
                y=j;
            }
        }
    }
    cout<<x<<' '<<y<<endl;
    cout<<ans;
    return 0;
}

要点

• DFS记忆化不够彻底，只想到了在DFS外面更新$b$,没有更加深入想🔍

---

F.小z的等待时间

---

难度：⭐⭐⭐

思路

用线性DP来解。

通过样例可以发现，如果第$i$朵花是最后一朵或者比第$i+1$朵花更高，那么第$i$朵花高度变为0的时间为$h_i$。如果$i$朵花比第$i+1$朵花更低，那么它需要等前一朵花的高度比自己低才会变低，高度变为0的时间为前一朵花的时间+1。

由此可得状态转移方程：

$if(f_i≤f_{i+1}) f_i=f_{i+1}+1$

$if (f_i>f_{i+1}) f_i=h_i$

求完$f$取其最大值即可。

代码

#include<bits/stdc++.h>
using namespace std;
int f[100005];
int main(){
    freopen("flowers.in", "r", stdin);
    freopen("flowers.out", "w", stdout);
    int n;
    int ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>f[i];
    }
    for(int i=n;i>=1;i--){
        if(f[i]<=f[i+1]){
            f[i]=f[i+1]+1;
        }
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}

要点

• 没有推导出状态转移方程的原因纯属没有想到DP，说明对DP掌握不够熟练，这道题要重点复习🖋

---