题目传送门🚀️ 🚀️ 🚀️ 🚀️ 🚀️

A 小田的四则运算

B 小田的gcd构造

C 小田的山峰数组

D Dota2参议院

E 小W走迷宫

F 小W去旅游

T1小田的四则运算😄

思路❤️

1.如果a,b,c都是1，那么输出3 2.如果a是1或a和b都是1，那么输出(a+b)c 3.其他的cout<<ab*c;

🎉️ 代码

#include<bits/stdc++.h>
using namespace std;
long long a[10];
int main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	cin>>a[0]>>a[1]>>a[2];
	if(a[0]==1&&a[1]==1&&a[2]==1){cout<<3;return 0;}
	if(a[0]==1)a[1]+=a[0],a[0]=1;
	cout<<a[0]*a[1]*a[2];
}

T2 小田的gcd构造😄 😄

😕 错的地方

1.公式推错了，以后要推好点，思维也要加强，这样才能做出这类题

❤️ 思路

要满足gcd(a,b)=x，那么其中一个数就是x就行了,为了和差超过x,y，我们看到a,b的范围比x,y大，我们就能在a,b的范围中选z最大倍数

代码🎉️

#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;
	cout<<z<<' '<<(long long)5e18/z*z;
}

T3 小田的山峰数组😄 😄

错的地方😕

1.双指针没用好，以后要加强代码熟练度，争取每一个算法都过关

思路❤️

先求一个前缀和，再循环枚举i,j,如果1~i比其他数的和都大，大么结束循环，在枚举到第一个可行的j的位置,计数变量+=n-j;

🎉️

#include<bits/stdc++.h>
using namespace std;
long long n,a[200010],s[200010],l=0;
int main(){
	freopen("mountain.in","r",stdin);
	freopen("mountain.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	for(int i=1,j=2;i<n-1;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++;
		l+=n-j;
	}
	cout<<l;
}

T4 Dota2参议院😄 😄

😕 错的地方

1.把题目看的太简单了，不能轻题,这样才能发挥自己的最大实力

❤️ 思路

我们可以用队列模拟，先把每个阵营的入队，每次轮到一个人是，让他禁言对方第一个人，最后那个队有剩余的就输出哪个阵营

代码 🎉️

#include<bits/stdc++.h>
using namespace std;
int q1[20010],q2[200010],hh1=0,tt1=-1,hh2=0,tt2=-1;
int main(){
	freopen("dota.in","r",stdin);
	freopen("dota.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		hh1=hh2=0;
		tt1=tt2=-1;
		string s;
		cin>>s;
		int n=s.size();
		for(int i=0;i<n;i++){
			if(s[i]=='R')q1[++tt1]=i;
			else q2[++tt2]=i;
		}
		while(hh1<=tt1&&hh2<=tt2){
			if(q1[hh1]<q2[hh2])q1[++tt1]=q1[hh1]+n;
			else q2[++tt2]=q2[hh2]+n;
			hh1++,hh2++;
		}
		if(hh1>tt2)cout<<"Radiant";
		else cout<<"Dire";
		cout<<"\n";
	}
}

T5 小W走迷宫😄 😄

错的地方😕

1.搜索忘优化，要加强对优化写法的掌握度，不能看算法熟悉就轻视

❤️ 思路

我们可以再暴力搜索的基础上，用上记忆化优化，才能保证不超时

🎉️ 代码

#include <bits/stdc++.h>
using namespace std;
char a[110][110];
int f[110][110];
int m,n,x,y,xx,yy;
int dx[10]={0,1,0,-1};
int dy[10]={1,0,-1,0};
void dfs(int ii,int jj,int b){
	f[ii][jj]=b; 
	for(int i=0;i<4;i++){
		int xxx=ii+dx[i];
		int yyy=jj+dy[i];
		if(xxx>=1&&xxx<=m&&yyy>=1&&yyy<=n&&a[xxx][yyy]!='#'&&b+1<f[xxx][yyy])dfs(xxx,yyy,b+1);
	}
}
int main(){
	freopen("mg.in","r",stdin);
	freopen("mg.out","w",stdout);
	memset(f,0x3f,sizeof f);
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			if(a[i][j]=='@')x=i,y=j;
			if(a[i][j]=='*')xx=i,yy=j;
		}
	}
	dfs(x,y,0);
	if(f[xx][yy]==0x3f3f3f3f)cout<<"-1";
	else cout <<f[xx][yy]; 
	return 0;
}

T6小W去旅游😄

思路❤️

有两种写法,第一种深搜，可以枚举这个点到下一个点图中的路径，而且每个点相连的边只有一条，就可以搜 还可以用最短路作，在模版上改一下即可

🎉️ 代码

#include<bits/stdc++.h>
using namespace std;
int a[22][22],p[22],l=0;
int n,m;
int s,z;
int mi=10000;
void dfs(int c,int h){
	if(c==z){
		l=1;
		mi=min(mi,h);
		return ;
	}
	for(int i=1;i<=n;i++){
		if(a[c][i]&&!p[i]){
			p[i]=1;
			dfs(i,h+a[c][i]);
			p[i]=0;
		}
	}
}
int main(){
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
	
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int aa,bb,l;
		cin>>aa>>bb>>l;
		a[aa][bb]=l;
		a[bb][aa]=l;
	}
	cin>>s>>z;
	dfs(s,0);
	if(!l){cout<<"No path";return 0;}
	cout<<mi;
}

图论背模版就行了不想写了