小田的宝石（暴力）
思路
通过计算，我们可以知道最短距离就是从“都走”与“走一段，然后都走”中选更小那个即可。
且注意数据范围：对于所有测试数据，有：。所以一定要开 !!!
代码
#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;
if(a+a<b){
cout <<11*a;
}else{
cout <<a+5*b;
}
return 0;
}
小田的好数组（暴力）
思路
当数组中不是升序，就可以选择整个数组，输出；
如果数组是升序的，那么就无法选择任何一段，输出。
代码
#include <bits/stdc++.h>
using namespace std;
const int tt=2*1e5+10;
int a[tt];
int main(){
freopen("hsz.in","r",stdin);
freopen("hsz.out","w",stdout);
int n;
cin >>n;
for(int i=0;i<n;i++){
cin >>a[i];
}
if(n==1){
cout <<"0";
return 0;
}
int ans=0;
int cnt=1;
for(int i=1;i<n;i++){
if(a[i]>=a[i-1]){
cnt++;
}
}
if(cnt==n){
cout <<"0";
}else{
cout <<n;
}
return 0;
}
小田的数字合并（前缀和）
思路没想到的原因
没有想到“前缀和”这个方向，但想到了分别计算数字左边和右边的“所有数字的”与“这个数字的差”。
下次要联想以前学过的知识来做题。
思路
最大值一定是最小值左边或者右边的所有数字全部合并得来的。
用前缀和来帮助我们求出区间和，然后枚举每个数字，
分别计算数字左边和右边的“所有数字”与“这个数字的差”，取这个差的最大值。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
long long f[N],t[N];
int main(){
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
int n;
cin >>n;
for(int i=1;i<=n;i++){
cin >>f[i];
t[i]=f[i];
}
long long mx=-1;
for(int i=n;i>=2;i--){
f[i]+=f[i+1];
mx=max(mx,abs(f[i]-f[i-1]));
}
for(int i=1;i<n;i++){
t[i]+=t[i-1];
mx=max(mx,abs(t[i]-t[i+1]));
}
cout <<mx;
return 0;
}
化学式的原子数（栈&哈希）
思路没想到的原因
没有想到栈&哈希相关的东西。
思路
对于遍历所有到的字符：
- 如果是左括号，一个空哈希表到栈中
- 如果是右括号，说明当前层遍历完了，若括号右侧有数字，取出该数，否则视为括号右侧为，然后将栈顶哈希表出，并将弹出的原子数乘上取出的数字，加到上一层的哈希表中。
- 不是括号则为原子，取出原子，若后面还有数字，则取出数字，否则视作数字为，然后将 原子：数字 键值对添加到哈希表中。
代码
#include <bits/stdc++.h>
using namespace std;
stack<map<string,int>> stk;
string s;
int i,len;
int get_num(){
if(i==len||!isdigit((s[i]))) return 1;
int num=0;
while(isdigit(s[i])&&i<len){
num=num*10+s[i]-'0';
i++;
}
return num;
}
string get_atom(){
string atom;
atom+=s[i++];
while(i<len&&s[i]>='a'&&s[i]<='z') atom+=s[i++];
return atom;
}
int main(){
freopen("atom.in","r",stdin);
freopen("atom.out","w",stdout);
cin >>s;
len=s.size();
stk.push({});
while(i<len){
char ch=s[i];
if(ch=='('){
i++;
stk.push({});
}
else if(ch==')'){
i++;
int num=get_num();
auto atom_num=stk.top();
stk.pop();
for(auto &it:atom_num){
string k=it.first;
int v=it.second;
stk.top()[k]+=v*num;
}
}else{
string atom=get_atom();
int num=get_num();
stk.top()[atom]+=num;
}
}
auto atn=stk.top();
for(auto &it:atn){
string k=it.first;
int v=it.second;
cout <<k<<" "<<v<<endl;
}
return 0;
}
小W挖宝藏（dfs深搜）
思路没想到的原因
想到了，但忘记了判断边界，所以以后要把所有的情况都考虑到。
思路
这道题所有的点都有可能成为起点，所以我们每个点都要，最后取次数的最大值。
部分判断这个方向是否在地图范围内，当然还要判断这个点是否能爬到，也就是高度要比前一个低 。
因为低的不可能到高的，所以我们不需要再开一个数组去记录这个点是否走过。
接下来，就要往四个方向搜索，取四个方向中距离最长的，然后，这就是这个点的结果了。
但是我们从数据的范围可以发现，直接会。
那么就需要记忆化来判断这个点到终点的距离。每次搜索一次记忆一次即可。
代码
#include <bits/stdc++.h>
using namespace std;
int a[110][110],b[110][110];
int n,m;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int dfs(int x,int y){
if(b[x][y]>0) return b[x][y];
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[x][y]>a[nx][ny]){
int t=dfs(nx,ny);
b[x][y]=max(b[x][y],t+1);
}
}
return b[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];
}
}
int x,y,ans=-1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int t=dfs(i,j);
if(t+1>ans){
x=i;
y=j;
ans=dfs(i,j)+1;
}
}
}
cout <<x<<" "<<y<<endl;
cout <<ans;
return 0;
}
小z的等待时间（线性DP）
思路没想到的原因
没求出递推公式，以后要养成打草稿的好习惯，这对我以后考试有很大的用处。
思路
做的题，就要找到“状态表示”与“状态计算”，具体见下：
状态表示：来表示第朵花高度变成所需要的时间。
状态计算：要为，那么考虑和的关系，如果的话，那么就是我们要找的递推公式。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n;
long long f[N],a[N];
int main(){
freopen("flowers.in","r",stdin);
freopen("flowers.out","w",stdout);
cin >>n;
for(int i=1;i<=n;i++){
cin >>a[i];
}
f[n]=a[n];
for(int i=n-1;i>=1;i--){
if(f[i]<=f[i+1]){
f[i]=f[i+1]+1;
}
}
cout <<f[1];
return 0;
}
谢谢
