T1小田的宝石镇(暴力)
思路
如图可知我们必须要走一个A到其它的点去拿宝石，比如我们先到3点，接下来如果想到其它的点（假设要到2），则有两条路：
3 -->2 3-->1-->2
明显可知，想到旁边的点要么走2个A，要么走1个B，所以比较大小即可
附AC代码：
#include<bits/stdc++.h>
using namespace std;
long long ans;
int main()
{
freopen("gem.in","r",stdin);
freopen("gem.out","w",stdout);
long long a,b;
cin>>a>>b;
ans=a;
if(a*2<b)
{
ans+=a*2*5;
}
else
{
ans+=b*5;
}
cout<<ans;
return 0;
}
** T2 小田的好数组（暴力，分类讨论）**
思路
题目看似很难，要枚举每一种可能性，但数据1≤𝑛≤2×10^5，而暴力是n^2，所以肯定有更好的方法
对于一个数组a[]只有两种可能：
1.a[]完全有序（升序），则怎么选都无法找出任何一个“好数组”，答案为0 2.a[]非升序排列，则整个数组就是一个“好数组”，答案为n
分类讨论后就很简单了
附AC代码
#include<bits/stdc++.h>
using namespace std;
int ans;
int n,a[200010];
int main()
{
freopen("hsz.in","r",stdin);
freopen("hsz.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
if(n==1)
{
cout<<0;
return 0;
}
for(int i=1;i<n;i++)
{
if(a[i]>a[i+1])
{
cout<<n;
return 0;
}
}
cout<<0;
return 0;
}
T3 小田的数字合并(暴力枚举)
思路
这道题也是优先考虑暴力，我们可以枚举一个分界点i，i满足1<i<n，对于一个i，我们可以求出一个以i为分界点的极差
$$ans=max(abs((a[1]+a[2]+...+a[i-1])-(a[i+1]+a[i+2]+...+a[n])),ans)$$用此式即可求出这个数组的极差，但还有一个很大的问题，每一次循环都要求一次数组之和，还要求n次，时间是，,时间肯定超了 但是求一个数组内若干个区间之和，可以用前缀和来优化时间就能A了 附Ac代码
#include<bits/stdc++.h>
using namespace std;
long long n,a[200010],qz[200010],hz[200010],ans;
int main()
{
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
qz[i]=qz[i-1]+a[i];
ans=max(qz[i-1]-a[i],ans);
}
for(int i=n;i>=1;i--)
{
hz[i]=hz[i+1]+a[i];
ans=max(hz[i+1]-a[i],ans);
}
cout<<ans;
return 0;
}
T4 化学式的原子数(数据结构)
思路
这道题要用哈希栈分类讨论一下就很简单了(虽然但是我没做出来)
我们先定义两个函数分别用来取到数字和原子
stack<map<string,int> > res;
int i,n;
string a;
int qs()
{
if(i==n||!isdigit((a[i]))) return 1;
int ans=0;
while(isdigit(a[i])&&i<n)
{
ans=ans*10+a[i]-'0';
i++;
}
return ans;
}
string qy()
{
string b;
b+=a[i++];
while(i<n&&a[i]>='a'&&a[i]<='z') b+=a[i++];
return b;
}
接下来就可以分类讨论了
如果遇到 "("就在栈顶创建一个新哈希表，遇到 ")"就将栈顶哈希表拿出并和当前栈顶合并（乘括号外数字），不然就取一遍原子和数字存入数组就行了
附AC代码
#include<bits/stdc++.h>
using namespace std;
stack<map<string,int> > res;
int i,n;
string a;
int qs()
{
if(i==n||!isdigit((a[i]))) return 1;
int ans=0;
while(isdigit(a[i])&&i<n)
{
ans=ans*10+a[i]-'0';
i++;
}
return ans;
}
string qy()
{
string b;
b+=a[i++];
while(i<n&&a[i]>='a'&&a[i]<='z') b+=a[i++];
return b;
}
int main()
{
freopen("atom.in","r",stdin);
freopen("atom.out","w",stdout);
cin>>a;
n=a.size();
res.push({});
while(i<n){
if(a[i]=='('){
i++;
res.push({});
}
else if(a[i]==')'){
i++;
int s=qs();
auto sh=res.top();
res.pop();
for(auto &j:sh) res.top()[j.first]+=j.second*s;
}
else{
string yz=qy();
res.top()[yz]+=qs();
}
}
for(auto &j:res.top()) cout<<j.first<<" "<<j.second<<endl;
return 0;
}
T5 小W挖宝藏（dfs）
总结（自己）
dfs没加记忆化[哭]，40还是我一道题最高的分数[哇哇大哭]，下次要看时间范围啊啊啊
思路
明显一道dfs搜索摆在这里只要解决个落点的时间复杂度就行
但还是先想朴素算法 个落点每次要走次， 的时间复杂度但是肯定还会有常数所以会超时间，要用记忆化剪枝来优化时间
我们可以用一个数组记录走过的位置，一个数组记录以当前格子为起点可以获取的最大宝藏数，如果当前下一个要走的格子走过，就只要和当前的步数取个max再更新即可
附AC代码
#include<bits/stdc++.h>
using namespace std;
int zs[10][2]={{1,0},{-1,0},{0,-1},{0,1}};
int n,m,a[110][110],dx,dy,ans;
int z[110][110],bs[110][110];
int bfs(int b,int x,int y)
{
z[x][y]=1;
for(int i=0;i<4;i++)
{
int zx=x+zs[i][0],zy=y+zs[i][1];
if(zx<1||zy<1||zy>n||zx>m) continue;
if(a[x][y]>a[zx][zy])
{
if(z[zx][zy]==0)
{
int t=bfs(b+1,zx,zy);
bs[x][y]=max(bs[x][y],t+1);
}
else
{
bs[x][y]=max(bs[zx][zy]+1,bs[x][y]);
}
}
}
return bs[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++)
{
int l=bfs(0,i,j);
if(l>ans)
{
dx=i;
dy=j;
ans=l;
}
}
}
cout<<dx<<" "<<dy<<endl<<ans+1;
return 0;
}
T6小z的等待时间（dp）
总结（自己）
没时间（~有时间也不会~）第一天对dp没那么熟练（~甚至是现在dp简单的那类~），还是多打点草稿可能就会了
思路
这题是道dp（~考试甚至没看出来~），要按照dp三要素来想
f[i]定义：将i吹为0所需时间(没什么思考过程)
初始化：f[i]=a[i]（最好情况）
dp式：
如果 那么就不存在遮挡的情况，答案就是(已初始化)，不用处理
如果那么想吹f[i]必须要把f[i+1]吹到f[i]-1 所以在f[i+1]变成0后，f[i]是1 f[i]要用f[i+1]+1
附AC代码
#include<bits/stdc++.h>
using namespace std;
int f[100010],n;
int main()
{
freopen("flowers.in","r",stdin);
freopen("flowers.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>f[i];
}
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;
}
三克油
