牛客刷题 - 2017百度春招(暴力 & 思维 & dp)

一共五道题，前三道没什么难度，暴力枚举就可以了。后两道需要想想，但是也不难(dp还是我的弱项啊)

---

Q1：

解题思路：这个没什么说的，随便都能过。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int main()
{
	int n;
	int pr[55];
	while (~scanf("%d",&n))
	{
		for (int i = 0 ; i < n ; i++)
			scanf("%d",&pr[i]);
		sort(pr, pr+n);
		int temp = pr[0];
		int cnt = 1;
		for (int i = 1 ; i < n ; i++)
		{
			if (pr[i] != temp)
			{
				temp = pr[i];
				cnt++;
				if (cnt == 3)
				{
					temp = pr[i];
					break;
				}
			}
		}
		printf("%d\n",cnt==3 ? temp : -1);
	}
	return 0;
}

---

Q2：

解题思路：直接枚举去掉每个点更新结果即可。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int main()
{
	int n;
	int pos[55];
	while (~scanf("%d",&n))
	{
		int all = 0;
		for (int i = 0 ; i < n ; i++)
		{
			scanf ("%d",&pos[i]);
			if (i >= 1)
				all += abs(pos[i]-pos[i-1]);
		}
		int ans = all;
		for (int i = 1 ; i < n-1 ; i++)
			ans = min(ans, all-abs(pos[i]-pos[i-1])-abs(pos[i+1]-pos[i])+abs(pos[i+1]-pos[i-1]));
		printf("%d\n",ans);
	}
	return 0;
}

---

Q3：

解题思路：分两种情况，同一个颜色和不同颜色的，然后遍历求面积就行，海伦公式~

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
struct Point
{
	double x,y,z;
};
double dis(Point a, Point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
double get_S(Point a, Point b, Point c)
{
	double da, db, dc;
	da = dis(b,c);
	db = dis(a,c);
	dc = dis(a,b);
	double k = (da+db+dc)/2;
	return sqrt(k*(k-da)*(k-db)*(k-dc));
}
int main()
{
	int n;
	while (~scanf("%d",&n))
	{
		vector<Point> R;
		vector<Point> G;
		vector<Point> B;
		Point tp;
		for (int i = 0 ; i < n ; i++)
		{
			char kind[4];
			scanf("%s %lf %lf %lf",kind,&tp.x,&tp.y,&tp.z);
			if (kind[0] == 'R')
				R.push_back(tp);
			else if (kind[0] == 'G')
				G.push_back(tp);
			else
				B.push_back(tp);
		}
		double ans = 0;
		//先枚举同一个颜色
		//R
		for (int i = 0 ; i < R.size() ; i++)
		{
			for (int j = i+1 ; j < R.size() ; j++)
			{
				for (int k = j+1 ; k < R.size() ; k++)
					ans = max(ans, get_S(R[i], R[j], R[k]));
			}
		}
		//G
		for (int i = 0 ; i < G.size() ; i++)
		{
			for (int j = i+1 ; j < G.size() ; j++)
			{
				for (int k = j+1 ; k < G.size() ; k++)
					ans = max(ans, get_S(G[i], G[j], G[k]));
			}
		}
		//B
		for (int i = 0 ; i < B.size() ; i++)
		{
			for (int j = i+1 ; j < B.size() ; j++)
			{
				for (int k = j+1 ; k < B.size() ; k++)
					ans = max(ans, get_S(B[i], B[j], B[k]));
			}
		}
		
		//再枚举三种颜色
		for (int i = 0 ; i < R.size() ; i++)
		{
			for (int j = 0 ; j < G.size() ; j++)
			{
				for (int k = 0 ; k < B.size() ; k++)
					ans = max(ans, get_S(R[i], G[j], B[k]));
			}
		}
		
		printf("%.5lf\n",ans);
	}
	return 0;
}

---

Q4：

解题思路：这道题得想想了，用稳定sort排序后，从最小开始看看有多长的序列是不用动的，例如样例中：19 7 8 25，可见7 8两个数字的位置是正确的，19位置就不正确了(19应该在8后面)，所以19后面的数字(19 25)都得操作一次。
再随便举个例子：2 3 45 46 47 48 49 15，从最小的数字往后看依次是2 3 15，然后再看45时发现位置不对了，所以大于等于45的都要操作。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
struct Num
{
	int order;
	int num;
};
bool cmp(Num a, Num b)
{
	if (a.num == b.num)
		return a.order < b.order;
	return a.num < b.num;
}
int main()
{
	int n;
	int num[55];
	int cp[55];
	while (~scanf("%d",&n))
	{
		vector<Num> d;
		Num temp;
		for (int i = 0 ; i < n ; i++)
		{
			scanf("%d",&temp.num);
			temp.order = i;
			d.push_back(temp);
		}
		sort(d.begin(), d.end(), cmp);
		//上个数字的位置 
		int pos = -1;
		//正确排序的数字数 
		int ok = 0;
		for (int i = 0 ; i < n ; i++)
		{
			if (d[i].order > pos)
			{
				pos = d[i].order;
				ok++;
			}
			else
				break;
		}
		printf("%d\n",n-ok);
	}
	return 0;
}

---

Q5：

解题思路：考虑用动态规划：dp[i][j]，i表示一共i个数，j表示有j个大于号(个人习惯，也可以表示小于号，其实都一样)。
下一个有i个数字、j个大于号时，考虑下面四种情况：
1.dp[i-1][j-1]状态，把i放在最前面，即可得到j个大于号，有dp[i-1][j-1]种情况。
2.dp[i-1][j-1]状态，需要增加一个大于号，把i插入小于号所在的位置时，可以多出一个大于号(例如：1<2，我们把3插入到小于号的位置上时，变成1<3>2)，即在dp[i-1][j-1]个状态中每个小于号都可以插入，有dp[i-1][j-1]*(i-1-j)种状态。
3.dp[i-1][j]状态，把j放在最后面，则不会增加大于号，有dp[i-1][j]种状态。
4.dp[i-1][j]状态，类似2的情况，这次可以在每个大于号的位置上插入数字i，有dp[i-1][j]*j种情况。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int dp[1005][1005];
int main()
{
	for (int i = 1 ; i <= 1000 ; i++)
	{
		dp[i][0] = 1;
		dp[i][i-1] = 1;
		for (int j = 1 ; j < i-1 ; j++)
			dp[i][j] = (dp[i-1][j-1] + dp[i-1][j-1]*(i-1-j) + dp[i-1][j] + dp[i-1][j]*j)%2017;
	}
	int n,m;
	while (~scanf("%d %d",&n,&m))
	{
		printf("%d\n",dp[n][n-1-m]);
	}
	return 0;
}