A. 小田的四则运算
题目类型：分类讨论
思路
-
若最大值==1，输出3。
-
若最小值==1中，最大值等于a，输出a*(b+c)，最大值等于b，输出b*(a+c),最大值等于c，输出c*(a+b).
-
否则输出a与b和c的积。
代码
#include<bits/stdc++.h> using namespace std; int main(){ freopen("math.in","r",stdin); freopen("math.out","w",stdout); int a,b,c; cin>>a>>b>>c; int ma=max(a,max(b,c)); if(ma==1) cout<<3; else if(min(a,min(b,c))==1){ if(ma==a) cout<<a*(b+c); else if(ma==b) cout<<b*(a+c); else cout<<c*(a+b); } else cout<<a*b*c; return 0; }
这道题我在写的时候将
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
写成
//freopen("math.in","r",stdin);
//freopen("math.out","w",stdout);
了。 所以下次要仔细检查，一定不能再犯这种低级的错误了。
B. 小田的gcd构造
题目类型：数学
思路
列出式子我们即可知道c的最小倍数是它本身，而在5e18以内c的倍数即是5e18/c*c，只是在输出答案时要转化成long long类型即可。
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("gcd.in","r",stdin);
freopen("gcd.out","w",stdout);
long long a,b,c;
cin>>a>>b>>c;
cout<<c<<" "<<(long long)5e18/c*c;
return 0;
}
这道题我在写的时候想成了和差问题，写到最后推出来了原来的式子，于是就放弃了，下次应该再想一下。
C. 小田的山峰数组
题目类型：前缀和与双指针
思路
- 通过元素之和可知需要用前缀和，再看，因双层循环会超时，所以要用双指针，若s[i]>=s[j]-s[i]||s[j]-s[i]<=s[n]-s[j]，j++，最后输出答案。
- 注意：ans要开long long类型。
代码
#include<bits/stdc++.h>
using namespace std;
long long a[200010],s[200010];
int main(){
freopen("mountain.in","r",stdin);
freopen("mountain.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
long long ans=0;
for(int i=1,j=2;i<=n;i++){
if(s[i]>=s[n]-s[i]) break;
while(s[j]-s[i]<=s[i]||s[j]-s[i]<=s[n]-s[j]) j++;
ans+=n-j;
}
cout<<ans;
return 0;
}
这题在写的时候用了双层循环和int类型的ans，所以RE了，下次要注意数据范围。
D. Dota2参议院
题目类型：队列
思路
通过参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利可知，可以用队列来做，因参议员一定会让另一位参议员在这一轮和随后的几轮中丧失所有的权利，所以可以将丧失所有的权利的参议员踢出队列，再将参议员丧失所有的权利的参议员踢出队列，再排到队列末尾，相等于等待下一轮发言，最后根据队列是否为空来输出答案。
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("dota.in","r",stdin);
freopen("dota.out","w",stdout);
int t;
cin>>t;
while(t--){
queue<int> a,b;
string s;
cin>>s;
for(int i=0;i<s.size();i++){
if(s[i]=='R') b.push(i);
else a.push(i);
}
for(int i=0;b.size()&&a.size();i+=2){
if(a.front()>=b.front()){
int c=b.front();
b.push(c+s.size());
}
else{
int c=a.front();
a.push(c+s.size());
}
b.pop(),a.pop();
}
if(b.empty()) cout<<"Dire"<<endl;
else cout<<"Radiant"<<endl;
}
return 0;
}
这题在写的时候写成枚举了，所以RE了，下次要再仔细看一下题目。
E. 小W走迷宫
题目类型：搜索
思路
这道题目其实就是DFS模版改一下即可，只不过需要改一下四种a[i][j]的判断，以及最后的判断。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct P{
int x,y,step;
};
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
queue<P> q;
int vis[50][50],mp[50][50];
int n,m,s1,s2,b1,b2;
void bfs(){
vis[s1][s2]=1;
q.push(P{s1,s2,0});
while(q.size()){
P now=q.front();
q.pop();
if(now.x==b1&&now.y==b2){
cout<<now.step;
return;
}
for(int i=0;i<4;i++){
int nx=now.x+dx[i],ny=now.y+dy[i];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(vis[nx][ny]||mp[nx][ny]) continue;
q.push(P{nx,ny,now.step+1});
vis[nx][ny]=1;
}
}
cout<<-1;
return;
}
signed main(){
freopen("mg.in","r",stdin);
freopen("mg.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char a;
cin>>a;
if(a=='.') mp[i][j]=0;
if(a=='#') mp[i][j]=1;
if(a=='@') s1=i,s2=j;
if(a=='*') b1=i,b2=j;
}
}
bfs();
}
这道题在写的时候模版写出来了，但有一个地方没有改，下一次还是要根据题目做出改变。
F. 小W去旅游
题目类型：最短路
思路
这道题目其实就是最短路模版改一下即可，将有向图换成无向图，mp[x][y]=min(mp[x][y],mp[x][i]+mp[i][y])。
代码
#include<bits/stdc++.h>
using namespace std;
int d[30][30],mp[30][30],n,m,a,b,l,x,y;
void dijkstra(){
memcpy(mp,d,sizeof mp);
for(int i=1;i<=n;i++){
for(int x=1;x<=n;x++){
for(int y=1;y<=n;y++){
mp[x][y]=min(mp[x][y],mp[x][i]+mp[i][y]);
}
}
}
}
int main(){
freopen("city.in","r",stdin);
freopen("city.out","w",stdout);
memset(d,0x3f,sizeof d);
cin>>n>>m;
while(m--){
cin>>a>>b>>l;
d[a][b]=l;
d[b][a]=l;
}
dijkstra();
cin>>x>>y;
if(mp[x][y]>=0x3f3f3f3f-5e6){
cout<<"No path";
return 0;
}
cout<<mp[x][y];
return 0;
}
这道题没有时间写了，下一次考试的时候一定要有明确的时间规划。
