problem1 link
对于每一个，找到其在目标串中的位置，判断能不能移动即可。
problem2 link
如果最后的$limit$为$11=(1011)_{2}$,那么可以分别计算值为$(1011)_{2},(1010)_{2},(100x)_{2},(0xxx)_{2}$的答案数，$x$位置表示可以为任意。也就是可以忽略这些位。
当答案固定时，可以用高斯消元求解。
problem3 link
令$d(i,j)$表示点 $i$到点$j$的距离。
使用最小割求解。将每个点拆成$n$个点，第$i$个点拆成$p(i,0),p(i,1),...,p(i,n-1)$.其中$p(i,j)$如果与源点在一个割集，说明$d(0,i)\leq j$为假，与汇点在一个割集说明$d(0,i)\leq j$为真。
所以，如果一个割产生在边$p(i,j-1)\rightarrow p(i,j)$说明最后$d(0,i)=j$.其中边$p(i,j-1)\rightarrow p(i,j)$的代价为$(want[i]-j)^{2}$
有以下边：
（1）对于0点来说,$p(0,0)$与汇点的边流量为无穷大，说明，最后它与汇点在一个割集，所以$d(0,0)\leq 0$为真;
（2）对于$1\leq i < n$号点来说，源点到$p(i,0)$为无穷大（一定不可能），$p(i, n-1)$到汇点为无穷大（一定为真); $p(i,j-1)\rightarrow p(i,j),1\leq j < n)$为$(want[i]-j)^{2}$
(3)如果原来存在边$i\rightarrow j$,那么$p(i,k)\rightarrow p(j,k-1)$为无穷大，表示如果$d(0,i)>k$,那么一定有$d(0,j)>k-1$
code for problem1
#include <string>
class FoxAndChess {
public:
std::string ableToMove(const std::string &begin, const std::string &target) {
int n = static_cast<int>(begin.size());
int idx = 0;
for (int i = 0; i < n; ++i) {
if (begin[i] == 'L' || begin[i] == 'R') {
while (idx < n && target[idx] == '.') {
++idx;
}
if (idx == n || begin[i] != target[idx] ||
(begin[i] == 'L' && i < idx) || (begin[i] == 'R' && i > idx)) {
return "Impossible";
}
++idx;
}
}
while (idx < n && target[idx] == '.') {
++idx;
}
if (idx != n) {
return "Impossible";
}
return "Possible";
}
};
code for problem2
#include <vector>
class XorCards {
public:
long long numberOfWays(const std::vector<long long> &number,
long long limit) {
const int n = 52;
const int m = static_cast<int>(number.size());
long long result = 0;
auto GetBit = [](long long t, int b) -> int {
return (t & (1ll << b)) != 0 ? 1 : 0;
};
{
std::vector<std::vector<int>> g(n, std::vector<int>(m + 1, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
g[i][j] = GetBit(number[j], i);
}
g[i][m] = GetBit(limit, i);
}
result += Gauss(g);
}
for (int i = 0; i < n; ++i) {
if (GetBit(limit, i) == 0) {
continue;
}
std::vector<std::vector<int>> g(n, std::vector<int>(m + 1, 0));
for (int j = i; j < n; ++j) {
for (int k = 0; k < m; ++k) {
g[j][k] = GetBit(number[k], j);
}
if (j > i) {
g[j][m] = GetBit(limit, j);
}
}
result += Gauss(g);
}
return result;
}
private:
long long Gauss(std::vector<std::vector<int>> &g) {
int n = static_cast<int>(g.size());
int m = static_cast<int>(g[0].size()) - 1;
int col = 0;
auto HasBit = [&](int start, int col) {
for (int i = n - 1; i >= start; --i) {
if (g[i][col] != 0) return i;
}
return -1;
};
int row_number = 0;
for (int i = 0; i < n && col < m; ++i) {
int row = HasBit(i, col);
while (row == -1 && col + 1 < m) {
row = HasBit(i, ++col);
}
if (row == -1) {
break;
}
if (row != i) {
std::swap(g[i], g[row]);
}
for (int idx = 0; idx < n; ++idx) {
if (idx != i && g[idx][col] != 0) {
for (int k = 0; k <= m; ++k) {
g[idx][k] ^= g[i][k];
}
}
}
++col;
++row_number;
}
for (int i = row_number; i < n; ++i) {
if (g[i][m] != 0) {
return 0;
}
}
if (m < row_number) {
return 0;
}
return 1ll << (m - row_number);
}
};
code for problem3
#include <limits>
#include <unordered_map>
#include <vector> template <typename FlowType>
class MaxFlowSolver {
static constexpr FlowType kMaxFlow = std::numeric_limits<FlowType>::max();
static constexpr FlowType kZeroFlow = static_cast<FlowType>(0);
struct node {
int v;
int next;
FlowType cap;
}; public:
int VertexNumber() const { return used_index_; } FlowType MaxFlow(int source, int sink) {
source = GetIndex(source);
sink = GetIndex(sink); int n = VertexNumber();
std::vector<int> pre(n);
std::vector<int> cur(n);
std::vector<int> num(n);
std::vector<int> h(n);
for (int i = 0; i < n; ++i) {
cur[i] = head_[i];
num[i] = 0;
h[i] = 0;
}
int u = source;
FlowType result = 0;
while (h[u] < n) {
if (u == sink) {
FlowType min_cap = kMaxFlow;
int v = -1;
for (int i = source; i != sink; i = edges_[cur[i]].v) {
int k = cur[i];
if (edges_[k].cap < min_cap) {
min_cap = edges_[k].cap;
v = i;
}
}
result += min_cap;
u = v;
for (int i = source; i != sink; i = edges_[cur[i]].v) {
int k = cur[i];
edges_[k].cap -= min_cap;
edges_[k ^ 1].cap += min_cap;
}
}
int index = -1;
for (int i = cur[u]; i != -1; i = edges_[i].next) {
if (edges_[i].cap > 0 && h[u] == h[edges_[i].v] + 1) {
index = i;
break;
}
}
if (index != -1) {
cur[u] = index;
pre[edges_[index].v] = u;
u = edges_[index].v;
} else {
if (--num[h[u]] == 0) {
break;
}
int k = n;
cur[u] = head_[u];
for (int i = head_[u]; i != -1; i = edges_[i].next) {
if (edges_[i].cap > 0 && h[edges_[i].v] < k) {
k = h[edges_[i].v];
}
}
if (k + 1 < n) {
num[k + 1] += 1;
}
h[u] = k + 1;
if (u != source) {
u = pre[u];
}
}
}
return result;
} MaxFlowSolver() = default; void Clear() {
edges_.clear();
head_.clear();
vertex_indexer_.clear();
used_index_ = 0;
} void InsertEdge(int from, int to, FlowType cap) {
from = GetIndex(from);
to = GetIndex(to);
AddEdge(from, to, cap);
AddEdge(to, from, kZeroFlow);
} private:
int GetIndex(int idx) {
auto iter = vertex_indexer_.find(idx);
if (iter != vertex_indexer_.end()) {
return iter->second;
}
int map_idx = used_index_++;
head_.push_back(-1);
return vertex_indexer_[idx] = map_idx;
} void AddEdge(int from, int to, FlowType cap) {
node p;
p.v = to;
p.cap = cap;
p.next = head_[from];
head_[from] = static_cast<int>(edges_.size());
edges_.emplace_back(p);
} std::vector<node> edges_;
std::vector<int> head_; std::unordered_map<int, int> vertex_indexer_;
int used_index_ = 0;
}; #include <string> class FoxAndCity {
public:
int minimalCost(const std::vector<std::string> linked,
const std::vector<int> want) {
constexpr int kMaxCapacity = 1000000;
int n = static_cast<int>(linked.size());
MaxFlowSolver<int> solver;
auto Index = [&](int u, int k) { return u * n + k; };
int source = -1;
int sink = -2;
for (int i = 0; i < n; ++i) {
if (i == 0) {
solver.InsertEdge(Index(i, 0), sink, kMaxCapacity);
continue;
} solver.InsertEdge(source, Index(i, 0), kMaxCapacity);
solver.InsertEdge(Index(i, n - 1), sink, kMaxCapacity);
for (int j = 1; j < n; ++j) {
solver.InsertEdge(Index(i, j - 1), Index(i, j),
(want[i] - j) * (want[i] - j));
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (linked[i][j] == 'Y') {
for (int k = 1; k < n; ++k) {
solver.InsertEdge(Index(i, k), Index(j, k - 1), kMaxCapacity);
}
}
}
}
return solver.MaxFlow(source, sink);
}
};