srm 538

发表于   |   分类于   |  

topcoder,srm538 题解

题外话

之前准备期末预习加上刚放假浪了一会= =没有补题，今天开始恢复补题。。

250

Description:

平面上给出$N$个点，整数坐标。从$(0,0)$出发，每次往上下左右四个垂直方向走，要求遍历所有点至少一次，最后回到给出的N个点中的某个点（不包括原点）。然后走过的距离是曼哈顿距离。给出一个数字代表要求走过的距离为奇还是为偶。问能否满足要求。

Solution

显然如果要求是偶的话只有全奇时无解，若有一个偶数，则可通过往返的方式访问其他点最后停留在偶数点，要求为奇数时同理

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
class EvenRoute {
        public:
        string isItPossible(vector <int> x, vector <int> y, int wantedParity) {
        	int n = x.size();
			bool even = 0, odd = 0;
			for (int i = 0; i < n; ++i) {
				if ((abs(x[i]) + abs(y[i])) & 1)	odd = 1;
				else even = 1;
			}
			return (odd && even) || (even && !wantedParity) || (odd && wantedParity) ? "CAN" : "CANNOT";
		}
};

450

Description

给出四种命令。左转多少度，右转多少度，前进多远，后退多远。先在顺序是打乱的。要求给出一种排列使得最终总的位移和最远。输出最远距离即可。

Solution

一个很明显的直观感受是尽量走直线会使得答案更大一些。这样就很简单了，不妨全向前，然后把调整角度放到后面，最后全向后即可。调整的角度背包求即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
vector<int> a, b;//ang back
int dp[60][360];
const double Pi = acos(-1.0);
class TurtleSpy {
	public:
        double maxDistance(vector <string> commands) {
   			int n = commands.size();
			double X = 0.0, Y = 0.0;
			for (int i = 0; i < n; ++i) {
				char s[10];
				int x;
				sscanf(commands[i].c_str(), "%s%d", s, &x);
				if (s[0] == 'f')	X += x;
				else if (s[0] == 'b')	Y += x;
				else if (s[0] == 'l')	a.pb(x);
				else	a.pb(360 - x);
			}
			dp[0][0] = 1;
			for (int i = 0; i < a.size(); ++i) {
				for (int j = 0; j < 360; ++j)
					if (dp[i][j])	dp[i + 1][(j + a[i]) % 360] = dp[i + 1][j] = 1;
			}
			double t = 0.0;
			for (int i = 0; i < 360; ++i) {
				if (dp[a.size()][i])	t = max(t, X * X + Y * Y - 2.0 * X * Y * cos(Pi * i / 180.0));
			}
			return sqrt(t);
		}
};