D-Link with Game Glitch)
有 $n$ 种物品,$m$ 种转换,每 $ka_i$ 个 $b_i$ 类物品可以换 $w\times kc_i$ 个 $d_i$ 类物品 $(1\le i\le m, k\in \R_+)$,求最大的 $0\le w\le 1$ 使得不存在一种转换方式可以得到无限多的某类物品。($n\le 1000, m \le 2000)$
二分答案,判负环。
如何建图:
由 $b_i$ 向 $d_i$ 连边,边权定义为转化的效率 $\dfrac{wc_i}{a_i}$,每一个 $b_i$ 可以换 $\dfrac{wc_i}{a_i}$ 个 $d_i$。题目中的“无限多”实际上在图中是一个环,这个环从 $b_i$ 开始,转一圈如果可以换出大于 $1$ 个 $b_i$,那么我们就可以无限换下去,也就是说环上的边权乘积一定要小于 $1$。显然 $w$ 越大,环边权乘积会越大。
原问题转化成:将图中所有边权乘上 $w$,图中不存在边权乘积 $\ge 1$ 的环。
二分答案 $w$,找到最大的满足上述条件的 $w$。
原来是要边权取 $-log$ 的,这样乘积 $\ge 1$ 就等价于和 $\lt 0$,相当于判负环。
但是我用 long double 莽过去了。
复杂度 $O(n^2log(二分精度))$
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class graph {
public:
struct edge {
int from;
int to;
T cost;
};
vector<edge> edges;
vector<vector<int>> g;
int n;
graph(int _n) : n(_n) {
g.resize(n);
}
virtual int add(int from, int to, T cost) = 0;
};
template <typename T>
class digraph : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
digraph(int _n) : graph<T>(_n) {}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int)edges.size();
g[from].push_back(id);
edges.push_back({from, to, cost});
return id;
}
digraph<T> reverse() const {
digraph<T> rev(n);
for (auto &e : edges) {
rev.add(e.to, e.from, e.cost);
}
return rev;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
digraph<long double> g(n);
for (int i = 0; i < m; i++) {
double a, c;
int b, d;
cin >> a >> b >> c >> d;
b--; d--;
g.add(b, d, (long double)c / a);
}
auto spfa = [&](long double w) -> bool {
vector<long double> dist(n, 1);
vector<int> cnt(n);
vector<bool> vis(n, true);
vector<int> que(n);
iota(que.begin(), que.end(), 0);
for (int i = 0; i < (int) que.size(); i++) {
int u = que[i];
vis[u] = false;
for (int id : g.g[u]) {
auto &e = g.edges[id];
int to = e.from ^ e.to ^ u;
if (dist[to] < dist[u] * e.cost * w) {
dist[to] = dist[u] * e.cost * w;
cnt[to] = cnt[u] + 1;
if (cnt[to] > n) {
return false;
}
if (!vis[to]) {
vis[to] = true;
que.push_back(to);
}
}
}
}
return true;
};
long double l = 0, r = 1;
while (fabs(r - l) > 1e-12) {
long double mid = (l + r) * 0.5;
if (!spfa(mid)) {
r = mid;
} else {
l = mid;
}
}
cout << fixed << setprecision(12) << l << '\n';
return 0;
}
L-Link with Level Editor I
有 $n$ 个世界,每个世界是一张简单有向图。从这些世界中选择一个子段进行游戏,规则为从 $1$ 出发,每个世界可以原地不动或经过一条边,然后就会进入另一个世界,到达点 $m$ 即为胜利。
要求选出一个尽可能短的子段,使得存在至少一种方案可以胜利
$dp(i, j)$ 表示到达第 $i$ 个世界的 $j$ 点最晚需要从第几个世界出发。
转移时考虑如何到达 $j$ 号点,假设当前世界有一条边 $u\rightarrow j$ 有两种情况
- 上一个世界可以通过在 $j$ 点原地不动到达,$dp(i-1, j)$
- 上一个世界可以到达 $j$ 的入边的顶点,$dp(i-1,u)$
日常压掉第一维
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> dp(m + 1, -1);
dp[0] = 0;
int ans = n + 1;
for (int i = 0; i < n; i++) {
auto new_dp = dp;
new_dp[0] = i + 1;
int k;
cin >> k;
while (k--) {
int u, v;
cin >> u >> v;
u--; v--;
new_dp[v] = max({new_dp[v], dp[u], dp[v]});
}
if (new_dp[m - 1] != -1) {
ans = min(ans, i + 1 - new_dp[m - 1]);
}
swap(dp, new_dp);
}
if (ans > n) ans = -1;
cout << ans << '\n';
return 0;
}
J-Link with Arithmetic Progression
给定一个数列 $a$ ,将其修改为一个等差数列 $b$,代价为 $\sum\limits_{i=1}^n(a_i − b_i)^2$ 最小化代价。
这是个 Linear Progression
$$
标函数=\sum(观测值-理论值)^2
$$
用最小二乘法拟合。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
namespace GTI {
char gc(void) {
const int S = 1 << 16;
static char buf[S], *s = buf, *t = buf;
if (s == t)
t = buf + fread(s = buf, 1, S, stdin);
if (s == t)
return EOF;
return *s++;
}
int read(void) {
int a = 0, b = 1, c = gc();
for (; !isdigit(c); c = gc())
b ^= (c == '-');
for (; isdigit(c); c = gc())
a = a * 10 + c - '0';
return b ? a : -a;
}
} // namespace GTI
using GTI::read;
class LeastSquare {
double a, b;
public:
LeastSquare(const vector<double> &x, const vector<double> &y) {
long double t1 = 0, t2 = 0, t3 = 0, t4 = 0;
for (int i = 0; i < x.size(); ++i) {
t1 += x[i] * x[i];
t2 += x[i];
t3 += x[i] * y[i];
t4 += y[i];
}
a = (t3 * x.size() - t2 * t4) / (t1 * x.size() - t2 * t2);
// b = (t4 - a*t2) / x.size();
b = (t1 * t4 - t2 * t3) / (t1 * x.size() - t2 * t2);
}
long double getY(const double x) const { return a * x + b; }
};
int main() {
int tt = read();
while (tt--) {
int n = read();
vector<double> y(n);
for (int i = 0; i < n; i++) {
y[i] = read();
}
vector<double> x(n);
iota(x.begin(), x.end(), 0);
LeastSquare line(x, y);
double ans = 0;
for (int i = 0; i < n; i++) {
ans += (y[i] - line.getY(i)) * (y[i] - line.getY(i));
}
printf("%.12lf\n", ans);
}
return 0;
}
K - Link with Bracket Sequence I
已知括号序列 $a$ 是一个长度为 $m$ 的合法括号序列 $b$ 的子序列,求可能的序列 $b$ 的数量。
$$
dp(i, j, k):= b的前i个匹配了a的前j个,剩下k个左括号未被匹配
$$
转移时考虑在 $b$ 后面加一个左括号会转移到哪里,加一个右括号会转移到哪里。
在 $b$ 后面加左括号:
-
如果 $a_{j+1}$ 是左括号: $dp(i, j, k) \rightarrow dp(i + 1, j + 1, k + 1)$
-
如果 $a_{j+1}$ 是右括号:$dp(i, j, k)\rightarrow dp(i + 1, j, k + 1)$
在 $b$ 后面加右括号:
-
如果 $a_{j+1}$ 是左括号: $dp(i, j, k) \rightarrow dp(i + 1, j, k - 1)$
-
如果 $a_{j+1}$ 是右括号:$dp(i, j, k)\rightarrow dp(i + 1, j + 1, k - 1)$
答案是 $dp(m, n, 0)$
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, m;
cin >> n >> m;
string s;
cin >> s;
vector dp(m + 1, vector<Mint>(m + 1));
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
vector new_dp(m + 1, vector<Mint>(m + 1));
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= i; k++) {
new_dp[j + (s[j] == '(')][k + 1] += dp[j][k];
if (k > 0) {
new_dp[j + (s[j] == ')')][k - 1] += dp[j][k];
}
}
}
swap(dp, new_dp);
}
cout << dp[n][0] << '\n';
}
return 0;
}