小田的四则运算（暴力）

思路

先从小到大排序。有几种特判，具体如下：

• 都是$1$,输出$3$；
• 只有一个$1$，输出$（a[0]+a[1]）*a[2]$；
• 其他输出$a[0]*a[1]*a[2]$。

代码

#include <bits/stdc++.h>
using namespace std;

int a[10];

int main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	cin >>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	if(a[0]==1&&a[2]==1&&a[2]==1){
		cout <<"3";
		return 0;
	}
	if(a[0]==1||a[1]==1||a[2]==1){
		cout <<(a[0]+a[1])*a[2];
	}else{
		cout <<a[0]*a[1]*a[2];
	}
	return 0;
}

小田的gcd构造（数学）

思路没想到的原因

公式推错了，看成和差问题了。以后要多想一想。

思路

我们要构造出一个最小值和最大值，最小值是$z$，最大值题目说了：最大值$=5*10^{18}$。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	long long x,y,z;
	cin >>x>>y>>z;
	cout <<z<<" "<<(long long)5e18/z*z;
	return 0;
}

小田的山峰数组（双指针）

思路没想到的原因

没有写，当时想的是用模拟，老师讲完才知道要用双指针。以后要加强熟练度。

思路

双指针来指向$i$与$j$，还有两种特判：

• 如果$s[i]>=s[n]-s[i]$,那么退出当前循环；
• 当$s[j]-s[i]<=s[i]$或者$s[j]-s[i]<=s[n]-s[j]$，$j$指针$++$。（要用$while!!!$）

代码

#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;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;
	return 0;
}

Dota2参议院（队列）

思路没想到的原因

当时感觉太简单了，只需写几个特判就行了。但实际要用队列。以后要多刷题，分清题目。

思路

每次第一位删离$ta$最近且阵营相反。最后队列为$0$的，输出相反阵营。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=2e4+10;
int q1[tt],q2[tt];
int hh1=0,hh2=0,tt1=-1,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;
		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"<<endl;
		}else{
			cout <<"Dire"<<endl;
		}
	}
	return 0;
}

小W走迷宫（dfs深搜）

思路

用$dfs$来搜，遇到"."前进，记得判断边界！！！

代码

#include <bits/stdc++.h>
using namespace std;

char g[110][110];
int dis[110][110];
int m,n,sx,sy,ex,ey;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

void dfs(int x,int y,int d){
	dis[x][y]=d; 
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>=1&&nx<=m&&ny>=1&&ny<=n&&g[nx][ny]=='.'&&d+1<dis[nx][ny]){
			dfs(nx,ny,d+1);
		}
	}
}

int main(){
	freopen("mg.in","r",stdin);
	freopen("mg.out","w",stdout);
	int cnt=0;
	memset(dis,0x3f,sizeof dis);
	cin >>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin >>g[i][j];
			if(g[i][j]=='@'){
				sx=i,sy=j;
			}
			if(g[i][j]=='*'){
				ex=i,ey=j;
				g[i][j]='.';
			}
		}
	}
	dfs(sx,sy,0);
	if(dis[ex][ey]==0x3f3f3f3f) cout <<"-1";
	else cout <<dis[ex][ey]; 
	return 0;
}

小W去旅游（Dijkstra最短路）

思路没想到的原因

用了$Dijkstra$算法，但是我没有把模板有向图换成无向图。以后要加强理解与运用。

思路

$Dijkstra$算法模板题，只需把有向图换成无向图，并且如果$arr[x][y]!=0x3f3f3f3f$与$dist[x]+arr[x][y]<dist[y]$成立，那么$dist[y]=dist[x]+arr[x][y]$。

代码

#include <bits/stdc++.h>
using namespace std;

int arr[1010][1010];
int dist[1010];
bool v[1010];
int n,m,ans,s,e;

int f(){
    memset(dist,0x3f,sizeof(dist));
    memset(v,0,sizeof(v));
    dist[s]=0;
    for(int i=1;i<=n;i++){ 
        int x=-1;
        for(int j=1;j<=n;j++){
            if(!v[j]&&(x==-1||dist[j]<dist[x])){
            	x=j;
			}
        }
        v[x]=1;
        for(int y=1;y<=n;y++){
            if(arr[x][y]!=0x3f3f3f3f&&dist[x]+arr[x][y]<dist[y]){
            	dist[y]=dist[x]+arr[x][y];
			}
        }  
    }  
    if(dist[e]==0x3f3f3f3f){
    	return -1;
	}
	return dist[e];
}  
int main(){
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
    cin >>n>>m;
    memset(arr,0x3f,sizeof(arr));
    for(int i=1;i<=n;i++) arr[i][i]=0;
    for(int i=1;i<=m;i++){ 
        int x,y,z;
        cin >>x>>y>>z;
        arr[x][y]=min(arr[x][y],z);
		arr[y][x]=min(arr[y][x],z);
    } 
    cin>>s>>e;
    ans=f();
    if(ans==-1){ 
    	cout <<"No path";
	}
    else cout <<ans;
    return 0;  
}

谢谢