problem1 link
暴力枚举即可。
problem2 link
一共有24小时，所以最多有24个顾客。设$f[x][y][z]$表示还剩下$x$把刀，现在时间是$y$,以及来过的顾客集合为$z$可以获得的最大值。
那假设第$y$小时来的顾客为$t$，来的概率为$p$,有三种情况：
（1）之前它来过，那么$f[x][y][z]=f[x][y+1][z]$
（2）之前没来过，现在也没来，$f[x][y][z]=(1-p)*f[x][y+1][z]$
（3）之前没来过，现在来了。可以选择买给他一把刀，$c_{1}=f[x-1][y+1][z|2^{t}]+v_{y}$;或者不卖给他,$c_{2}=f[x][y+1][z|2^{t}]$，所以$f[x][y][z]=max(c_{1},c_{2})*p$
另外，假设一个人第一次，第二次来的概率分别为0.2和0.4。那么上面使用的$p$是假设他之前没来过。如果第一次没来，那么第二次来的概率为$\frac{0.4}{1-0.2}$
problem3 link
首先枚举字母'R'和‘F’的位置$p_{1},p_{2}$。然后计算和其他所有‘L’的答案。
首先，对于每个位置$(x,y)$,计算其函数值$g(x,y)=distance(p_{1},p_{x,y})+distance(p_{2},p_{x,y})$
然后新建一系列节点$S_{0},S_{1},S_{2},...$。
对于每个$(x,y)$，设$t=g(x,y)$。那么节点$S_{t-1}$向点$(x,y)$连有向边。
另外节点$S_{i}$到$S_{i+1}$有一条有向边。每个点$(x,y)$向四周的格子有四条有向边。
所有边的长度均为1.然后从节点$S_{0}$开始进行bfs，计算到达每个点的距离。每个‘L’字母计算的距离就是选择$p_{1},p_{2}$和该位置的答案。
code for problem1
class RotatedClock {
public:
string getEarliest(int hourHand, int minuteHand) {
for (int i = 0; i < 12; ++i) {
for (int j = 0; j < 60; j += 2) {
for (int k = 0; k < 12; ++k) {
if (Check(i, j, k, hourHand, minuteHand)) {
return ToString(i) + ":" + ToString(j);
}
}
}
}
return "";
}
string ToString(int x) {
stringstream ss;
if (x < 10) {
ss << "0" << x;
} else {
ss << x;
}
return ss.str();
}
bool Check(int h, int m, int b, int hHand, int mHand) {
return GetHourHand(h, m, b) == hHand && GetMinuteHand(m, b) == mHand;
}
int GetHourHand(int h, int m, int b) {
int result = 0;
if (h >= b) {
result = (h - b) * 30 + m / 2;
} else {
result = 360 - (b - h) * 30 + m / 2;
}
return result;
}
int GetMinuteHand(int m, int b) {
b *= 5;
if (m >= b) {
return (m - b) * 6;
}
else {
return 360 - (b - m) * 6;
}
}
};
code for problem2
double cache[25][24][1 << 12];
int visited[25][24][1 << 12]; class NewItemShop {
public:
double getMaximum(int swords, vector<string> customers) {
Init(customers);
memset(visited, 0, sizeof(visited));
return dfs(swords, 0, 0);
} double dfs(int swords, int hour, int mask) {
if (swords == 0 || hour == 24) {
return 0;
}
if (visited[swords][hour][mask] != 0) {
return cache[swords][hour][mask];
}
visited[swords][hour][mask] = 1;
if (!hour_[hour].inited_) {
return cache[swords][hour][mask] = dfs(swords, hour + 1, mask);
} int cMask = hour_[hour].mask();
double p = hour_[hour].probility_;
int val = hour_[hour].value_; if ((mask & cMask) > 0) {
return cache[swords][hour][mask] = dfs(swords, hour + 1, mask);
} cache[swords][hour][mask] = (1 - p) * dfs(swords, hour + 1, mask); double c0 = dfs(swords, hour + 1, mask | cMask);
double c1 = dfs(swords - 1, hour + 1, mask | cMask) + val; cache[swords][hour][mask] += max(c0, c1) * p; return cache[swords][hour][mask];
} private: struct HourInfo {
bool is_multiple_times_;
int multiple_index_;
double probility_;
int value_; bool inited_; HourInfo():inited_(false) {} int mask() const {
if (!is_multiple_times_) {
return 0;
}
return 1 << multiple_index_;
} }hour_[24]; void Init(const vector<string>& customers) {
for (int i = 0; i < 24; ++ i) {
hour_[i].inited_ = false;
}
int multiple_num = 0;
for (int i = 0; i < (int)customers.size(); ++ i) {
const vector<int> a = Split(customers[i]);
const int n = (int)a.size();
const int idx = n > 3 ? multiple_num ++ : 0;
double cur = 1.0;
for (int j = 0; j < n; j += 3) {
int h = a[j];
int v = a[j + 1];
double p = a[j + 2] / 100.0 / cur;
cur -= a[j + 2] / 100.0;
if (n > 3) {
hour_[h].is_multiple_times_ = true;
hour_[h].multiple_index_ = idx;
}
else {
hour_[h].is_multiple_times_ = false;
}
hour_[h].probility_ = p;
hour_[h].value_ = v;
hour_[h].inited_ = true;
}
}
} std::vector<int> Split(const std::string& s) {
std::vector<int> result;
const int len = (int)s.length();
int idx = 0;
while (idx < len) {
while (idx < len && !IsDigit(s[idx])) {
++ idx;
}
if (idx >= len) {
break;
}
int x = 0;
while (idx < len && IsDigit(s[idx])) {
x = x * 10 + s[idx++] - '0';
}
result.push_back(x);
}
return result;
} static bool IsDigit(char c) {
return '0' <= c && c <= '9';
}
};
code for problem3
class MeetInTheMaze {
public:
string getExpected(vector<string> maze) {
Initialize(maze);
std::vector<std::pair<int, int>> all_f_positions;
std::vector<std::pair<int, int>> all_r_positions;
int l_number = 0;
for (int i = 0; i < height_; ++i) {
for (int j = 0; j < width_; ++j) {
char ch = maze_[i][j];
if (ch == 'F') {
all_f_positions.push_back(std::make_pair(i, j));
} else if (ch == 'R') {
all_r_positions.push_back(std::make_pair(i, j));
} else if (ch == 'L') {
++l_number;
}
}
}
int total = 0;
for (auto f : all_f_positions) {
for (auto r : all_r_positions) {
int t = Calculate(f.first, f.second, r.first, r.second);
if (t == -1) {
return "";
}
total += t;
}
}
int d = (int)all_f_positions.size() * (int)all_r_positions.size() *
l_number;
int g = Gcd(total, d);
total /= g;
d /= g;
std::stringstream ss;
ss << total << "/" << d;
return ss.str();
}
~MeetInTheMaze() { delete[] distance_; }
private:
int Calculate(const int f_x, const int f_y, const int r_x, const int r_y) {
std::vector<std::vector<std::pair<int, int>>> new_graph(
(width_ + height_) << 1);
for (int i = 0; i < height_; ++i) {
for (int j = 0; j < width_; ++j) {
if (maze_[i][j] != '#') {
int d1 = GetDistance(f_x, f_y, i, j);
int d2 = GetDistance(r_x, r_y, i, j);
if (d1 == -1 || d2 == -1) {
continue;
}
int d = d1 + d2;
if (d > (int)new_graph.size()) {
new_graph.resize(d);
}
new_graph[d - 1].push_back(std::make_pair(i, j));
}
}
}
const int nodes = (int)new_graph.size();
std::vector<int> dist(height_ * width_ + nodes, -1);
dist[height_ * width_] = 0;
std::queue<int> a_queue;
a_queue.push(height_ * width_);
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
while (!a_queue.empty()) {
const int start = a_queue.front();
a_queue.pop();
if (start < width_ * height_) {
const int sx = start / width_;
const int sy = start % width_;
for (int i = 0; i < 4; ++i) {
int x = sx + dx[i];
int y = sy + dy[i];
if (0 <= x && x < height_ && 0 <= y && y < width_) {
if (maze_[x][y] == '#') {
continue;
}
if (dist[x * width_ + y] == -1) {
dist[x * width_ + y] = dist[start] + 1;
a_queue.push(x * width_ + y);
}
}
}
} else {
const int new_graph_index = start - width_ * height_;
for (auto son : new_graph[new_graph_index]) {
int x = son.first;
int y = son.second;
int key = x * width_ + y;
if (dist[key] == -1) {
dist[key] = dist[start] + 1;
a_queue.push(key);
}
}
if (new_graph_index + 1 < nodes) {
dist[start + 1] = dist[start] + 1;
a_queue.push(start + 1);
}
}
}
int total = 0;
for (int i = 0; i < height_; ++i) {
for (int j = 0; j < width_; ++j) {
if (maze_[i][j] == 'L') {
if (dist[i * width_ + j] == -1) {
return -1;
}
total += dist[i * width_ + j];
}
}
}
return total;
}
int Gcd(int x, int y) { return y == 0 ? x : Gcd(y, x % y); }
void Initialize(const std::vector<std::string> &maze) {
maze_ = maze;
height_ = (int)maze_.size();
width_ = (int)maze_[0].size();
const int total_size = width_ * width_ * height_ * height_;
distance_ = new int[total_size];
memset(distance_, -1, sizeof(int) * total_size);
}
int GetDistance(int start_x, int start_y, int end_x, int end_y) {
if (start_x > end_x || (start_x == end_x && start_y > end_y)) {
std::swap(start_x, end_x);
std::swap(start_y, end_y);
}
int key = GetKey(start_x, start_y, end_x, end_y);
if (distance_[key] == -1) {
CalculateDistanceFrom(start_x, start_y);
}
return distance_[key];
}
void CalculateDistanceFrom(const int start_x, const int start_y) {
std::queue<std::pair<int, int>> a_queue;
a_queue.push(std::make_pair(start_x, start_y));
distance_[GetKey(start_x, start_y, start_x, start_y)] = 0;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
while (!a_queue.empty()) {
const int sx = a_queue.front().first;
const int sy = a_queue.front().second;
a_queue.pop();
const int from_key = GetKey(start_x, start_y, sx, sy);
for (int i = 0; i < 4; ++i) {
int x = sx + dx[i];
int y = sy + dy[i];
if (0 <= x && x < height_ && 0 <= y && y < width_) {
if (maze_[x][y] == '#') {
continue;
}
int key = GetKey(start_x, start_y, x, y);
if (distance_[key] != -1) {
continue;
}
distance_[key] = distance_[from_key] + 1;
a_queue.push(std::make_pair(x, y));
}
}
}
}
int GetKey(int x1, int y1, int x2, int y2) const {
return x1 * width_ * height_ * width_ + y1 * height_ * width_ +
x2 * width_ + y2;
}
int width_;
int height_;
std::vector<std::string> maze_;
int *distance_;
};