T1小田的四则运算（暴力）
总结（自己）
水题没总结
思路
就把几个可能出现答案的式子取个max就行
附AC代码
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main()
{
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
cin>>a>>b>>c;
if(a==0) cout<<max(b+c,b*c);
cout<<max(max(a*b*c,a+b+c),(a+b)*c);
return 0;
}
T2小田的gcd构造（数学？）
总结（自己）
没想到取题目最大值，以为是道数学又想不出来
思路
答案可以是所以用一个最大值减最小值，不行就-1可以就输出
附AC代码
#include<bits/stdc++.h>
using namespace std;
long long x,y,z;
int main()
{
freopen("gcd.in","r",stdin);
freopen("gcd.out","w",stdout);
cin>>x>>y>>z;
long long a=5*(long long)(1e18)/z*z;
cout<<z<<" "<<a;
return 0;
}
T3小田的山峰数组（双指针）
总结（自己）
双重循环时间超了
思路
双指针枚举两个分界点，前一个找第一个山峰数组（左边就不是了），答案就可以加 ，然后将i增加即可
附AC代码
#include<bits/stdc++.h>
using namespace std;
long long qz[200010],ans,n,a[200010];
int main()
{
freopen("mountain.in","r",stdin);
freopen("mountain.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
qz[i]=qz[i-1]+a[i];
}
for(int i=1,j=2;i<n-1;i++)
{
if(qz[i]>=qz[n]-qz[i]) break;
while(qz[i]>=qz[j]-qz[i]||qz[j]-qz[i]<=qz[n]-qz[j]) j++;
// cout<<i<<" "<<j<<" "<<qz[i-1]<<" "<<qz[j]-qz[i]<<" "<<qz[n]-qz[j]<<endl;
ans+=n-j;
}
cout<<ans;
return 0;
}
T4Dota2参议院（单调栈）
总结（自己）
没有用草稿纸分类讨论 没有考虑到第二轮的情况
思路
定义两个栈，分别存两个阵营的发言顺序 每次先发言的禁言对方栈顶即可
附AC代码
#include<bits/stdc++.h>
using namespace std;
string a;
int tt1=-1,tt2=-1,hh1,hh2,r[20010],d[20010];
int main()
{
freopen("dota.in","r",stdin);
freopen("dota.out","w",stdout);
int t;
cin>>t;
while(t--)
{
tt1=tt2=-1;
hh1=hh2=0;
cin>>a;
int n=a.size();
for(int i=0;i<n;i++){
if(a[i]=='R')
r[++tt1]=i;
else
d[++tt2]=i;
}
while(tt1>=hh1&&tt2>=hh2){
if(r[hh1]<d[hh2]) r[++tt1]=r[hh1]+n;
else d[++tt2]=d[hh2]+n;
hh1++;
hh2++;
}
if(tt1<hh1) cout<<"Dire"<<endl;
else cout<<"Radiant"<<endl;
}
return 0;
}
T5小W走迷宫(搜索)
总结（自己）
搜索还掌握的不熟练 没有一次对
思路
搜索模版题，加个记忆化就行
附AC代码
#include<bits/stdc++.h>
using namespace std;
char a[110][110];
int qx,qy,f[5][2]={{0,0},{-1,0},{0,-1},{1,0},{0,1}};
int b[110][110],n,m;
void dfs(int x,int y,int bs)
{
if(a[x][y]=='*')
{
return;
}
for(int i=1;i<=4;i++)
{
int nx=x+f[i][0],ny=y+f[i][1];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&b[nx][ny]>bs+1&&a[nx][ny]!='#')
{
b[nx][ny]=bs+1;
dfs(nx,ny,bs+1);
}
}
}
int main()
{
freopen("mg.in","r",stdin);
freopen("mg.out","w",stdout);
memset(b,0x3f,sizeof(b));
cin>>n>>m;
int zx,zy;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='@')
{
qx=i;
qy=j;
}
if(a[i][j]=='*')
{
zx=i;
zy=j;
}
}
}
b[qx][qy]=0;
dfs(qx,qy,0);
if(b[zx][zy]==0x3f3f3f3f)
{
cout<<-1;
}
else
{
cout<<b[zx][zy];
}
return 0;
}
T6小W去旅游（搜索）
总结（自己）
还是对搜索不够熟练 只拿了70分
思路
图的搜索而已 dfs秒了
附AC代码
#include<bits/stdc++.h>
using namespace std;
int q,z,n,m,a,c,l,b[110];
int x[110][110];
void dfs(int d,int bs)
{
if(d==z)
{
return;
}
for(int i=1;i<=n;i++)
{
if(x[d][i]!=-1&&i!=d&&bs+x[d][i]<b[i])
{
b[i]=bs+x[d][i];
dfs(i,bs+x[d][i]);
}
}
}
int main()
{
freopen("city.in","r",stdin);
freopen("city.out","w",stdout);
memset(x,-1,sizeof(x));
memset(b,0x3f,sizeof(b));
cin>>n>>m;
for(int i=1;i<=n;i++)
{
x[i][i]=0;
}
for(int i=1;i<=m;i++)
{
cin>>a>>c>>l;
x[a][c]=l;
x[c][a]=l;
}
cin>>q>>z;
b[q]=0;
dfs(q,0);
if(b[z]==0x3f3f3f3f)
{
cout<<"No path";
}
else
{
cout<<b[z];
}
return 0;
}
