AtCoder Grand Contest 036 题解
Visits: 369
Triangle
考虑 $\triangle (0,0)(x,n)(n,y)$ 的面积为 $n^2 – xy$，找到最小的 $n$ 满足 $n^2 \ge S$，设 $k = n^2 – S$，有 $0 \le k \le 2n-1$。
若 $k < n$，则 $\triangle (0,0)(k,n)(n,1)$ 满足条件，否则 $\triangle (0,0)(k-n,n-1)(n,1)$ 满足条件。
注意可能会有精度误差，要简单调一下。
inline void out(ll x, ll y) {
print(x, ' '), print(y, ' ');
}
int main() {
ll s;
rd(s);
ll n = sqrt(s);
while (n * n >= s) --n;
while (n * n < s) ++n;
ll k = n * n - s;
if (k < n) out(0, 0), out(k, n), out(n, 1);
else out(0, 0), out(k - n, n - 1), out(n, 1);
return 0;
}
Do Not Duplicate
考虑对于每个 $i$ 求出以 $a_i$ 开始的情况下需要多少步会清空，清空后下一个填的数。
设步数为 $d_i$，填的数为 $t_i$，连一条 $(i,t_i,d_i)$ 的有向边，则会形成一个 $n$ 个点的基环内向边带权森林。
整个过程会从起点开始，走到环上之后，绕环若干圈，最后再走不到整环的一段。
模拟就好了，时间复杂度 $\mathcal O(n)$。
const int N = 2e5 + 7;
int n, a[N<<1|1], b[N<<1|1], t[N], d[N], p[N];
ll k, s[N];
bool v[N];
inline void work(int &o, ll &k, int ed = 0) {
while (o != ed && k >= d[o])
k -= d[o], o = t[o];
}
int main() {
rd(n), rd(k), k *= n;
rda(a, n);
for (int i = 1; i <= n; i++) a[i+n] = a[i];
for (int i = n << 1; i; i--) b[i] = p[a[i]], p[a[i]] = i;
for (int i = 1; i <= n; i++)
t[i] = b[i] % n + 1, d[i] = b[i] - i + 1;
int o = 1;
v[o] = 1;
while (!v[t[o]]) {
v[t[o]] = 1;
s[t[o]] = s[o] + d[o];
o = t[o];
}
ll g = s[o] + d[o] - s[t[o]];
int x = t[o];
o = 1;
work(o, k, x);
k %= g;
work(o, k);
for (int i = 1; i <= n; i++) v[i] = 0;
vi ans;
while (k--) {
if (o == n + 1) o = n;
int w = a[o++];
if (v[w]) while (v[w]) v[ans.back()] = 0, ans.pop_back();
else ans.pb(w), v[w] = 1;
}
for (int x : ans) print(x, ' ');
return 0;
}
GP 2
满足条件的序列等价于（从 $1$ 开始编号）：
- $a_i \le 2m$。
- $\sum_{i=1}^n a_i = 3m$。
- $\sum_{i=1}^n \lfloor \frac {a_i}2 \rfloor \ge m$。
枚举 $\sum_{i=1}^n \lfloor \frac {a_i}2 \rfloor$ 的值，剩下就是一个多重集组合数，容斥一下发现计算量是常数，时间复杂度 $\mathcal O(n)$。
int n, m;
modint ans;
int main() {
rd(n, m), init(n + 3 * m / 2);
for (int k = m; k <= 3 * m / 2; k++) {
int b = 3 * m - 2 * k, a = n - b;
if (a < 0 || b < 0) continue;
ans += binom(n, a) * (binom(n + k - 1, n - 1) - a * binom(n + k - m - 2, n - 1) - b * binom(n + k - m - 1, n - 1));
}
print(ans);
return 0;
}
Negative Cycle
题意
- 有一张 $n$ 个点的有向图，点的编号为 $0 \sim n – 1$。
- 一开始有 $n-1$ 条边，对于 $i\in [0,n-2]$，有边 $(i,i+1,0)$。
- 另外若 $i<j$，加边 $(i,j,-1)$；若 $i>j$，加边 $(i,j,1)$。这些边都可以删除，边 $(i,j)$ 删除的代价为 $a_{i,j}$。
- 你希望用最小的代价删除某些边，使得图中不存在负环。
- $n \le 500$，$a_{i,j} \le 10^9$。
题解
考虑差分约束模型，图中不存在负环等价于存在一组合法的差分约束的解。
将每个节点作为一个变量，第 $i$ 个节点对应的变量为 $x_i$。因为初始的边不能删去，所以一定有 $x_i \ge x_{i + 1}$。
令 $q_i = x_i – x_{i + 1}$，有 $q_i \ge 0$。
假设保留了一条边权为 $-1$ 的 $i \to j(i < j)$ 的边，有 $x_i – 1 \ge x_j$，即 $x_i – x_j \ge 1$，即 $q_i + q_{i + 1} + \cdots + q_{j – 1} \ge 1$；假设保留了一条边权为 $1$ 的 $i \to j(i>j)$ 的边，有 $x_i + 1 \ge x_j$，即 $x_j – x_i \le 1$，即 $q_j + q_{j + 1} + \cdots + q_{i – 1} \le 1$。
反过来想，如果确定了所有的 $q_i$，那么每一条边就应该尽可能地保留下来，这样代价最小。
对于边权为 $-1$ 的边，是区间和 $\ge 1$ 才能保留，也就是说如果区间和 $= 0$ 就必须删除；对于边权为 $1$ 的边，是区间和 $\le 1$ 才能保留，也就是说如果区间和 $\ge 2$ 就必须删除。
也就是说，对于一种 $q$ 的取值方案，$q_i = 0$ 的每个连续段，都对应着一系列的边权为 $-1$ 的边的删除，而区间和 $\ge 2$ 的区间也对应着边权为 $1$ 的边的删除。
可以发现如果出现了 $q_i \ge 2$，不如把它变成 $1$，这样一定更优，所以只需要考虑 $q$ 的取值为 $0/1$ 的情况。
考虑 DP，设 $f_{i,j}$ 表示最后一个 $1$ 取在 $q_i$ 处，倒数第二个 $1$ 取在 $q_j$ 处的情况下，前缀 $i$ 的代价的最小值。
转移枚举下一个 $1$ 的位置即可，二维前缀和预处理转移系数后，时间复杂度 $\mathcal O(n^3)$。
代码
const int N = 507;
const ll inf = 1e18;
int n;
ll a[N][N], b[N][N], f[N][N], ans = inf;
inline ll calc(int k, int j, int i) {
return b[j+1][i] + a[n][j] - a[n][k] - a[i][j] + a[i][k];
}
int main() {
rd(n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j) rd(a[i][j]);
for (int j = 1; j <= n; j++)
for (int i = j; i; i--)
b[i][j] = b[i+1][j] + b[i][j-1] - b[i+1][j-1] + a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
for (int i = 1; i < n; i++) {
f[i][0] = calc(0, 0, i);
ans = min(ans, f[i][0] + calc(0, i, n));
for (int j = 1; j < i; j++) {
f[i][j] = inf;
for (int k = 0; k < j; k++)
f[i][j] = min(f[i][j], f[j][k] + calc(k, j, i));
ans = min(ans, f[i][j] + calc(j, i, n));
}
}
print(ans);
return 0;
}
ABC String
题意
- 给定一个仅包含
ABC的字符串 $s$。 - 要求 $s$ 的一个最长子序列，满足
ABC出现次数相同，且相邻字符不同。 - $|s| \le 10^6$。
题解
考虑将 $s$ 中相邻的相同字符缩成一个，这显然不影响答案。
记 $s$ 中 A,B,C 的出现次数分别为 $c_A,c_B,c_C$，不妨设 $c_A \le c_B \le c_C$。
将 A 看作分隔符，则将当前串分成了 $c_A + 1$ 段，每段只有 B,c。记 B,C 都有的段数为 $c_1$，单个 B 的段数为 $c_2$，单个 C 的段数为 $c_3$，若 $c_1 + c_2 \ge c_3$，可以构造取到答案的上界 $3c_A$：
- 每次找到一个
C，满足删去它之后串内相邻字符依然不相同，删去它，直到 $c_B = c_C$。 - 每次找到相邻的
B和C，满足删去它们之后串内相邻字符依然不相同，删去它们，直到 $c_A = c_B = c_C$。
若 $c_1 + c_2 < c_3$，每次找到单个 C 段，删去 C 以及 $0/1$ 个 A（优先考虑首尾，这样不用删 A），直到 $c_1+c_2 \ge c_3$，然后使用上面的构造方法即可。
使用链表维护，时间复杂度 $\mathcal O(n)$；使用 set 维护，时间复杂度 $\mathcal O(n \log n)$。
代码
const int N = 1e6 + 7;
int n, t[3];
char s[N], c[3];
set<int> p;
inline void del(int x, int c) {
p.erase(x), --t[c];
}
int main() {
rds(s, n);
for (int i = 0; i < 3; i++) c[i] = 'A' + i;
for (int i = 1; i <= n; i++)
if (s[i] != s[i+1]) p.insert(i), ++t[s[i]-'A'];
if (t[1] > t[2]) swap(t[1], t[2]), swap(c[1], c[2]);
if (t[0] > t[1]) swap(t[0], t[1]), swap(c[0], c[1]);
if (t[1] > t[2]) swap(t[1], t[2]), swap(c[1], c[2]);
int c1 = 0, c2 = 0, c3 = 0, o1 = 0, o2 = 0;
for (int x : p)
if (s[x] == c[0]) {
if (o1 && o2) ++c1;
else if (o1) ++c2;
else if (o2) ++c3;
o1 = o2 = 0;
} else if (s[x] == c[1]) o1 = 1;
else o2 = 1;
if (o1 && o2) ++c1;
else if (o1) ++c2;
else if (o2) ++c3;
o1 = o2 = 0;
if (c1 + c2 < c3) {
if (s[*p.begin()] == c[2] && s[*++p.begin()] == c[0])
del(*p.begin(), 2), --c3;
if (c1 + c2 < c3) {
if (s[*--p.end()] == c[2] && s[*--(--p.end())] == c[0])
del(*--p.end(), 2), --c3;
if (c1 + c2 < c3)
for (int x : p)
if (s[x] == c[0]) {
if (o1 && o2) {
del(o1, 0), del(o2, 2);
o1 = x, o2 = 0;
if (c1 + c2 == --c3) break;
} else o1 = x, o2 = 0;
} else if (s[x] == c[1]) o1 = 0, o2 = 0;
else if (s[x] == c[2]) {
if (o1 && !o2) o2 = x;
else o1 = 0, o2 = 0;
}
}
}
if (t[1] < t[2]) {
auto it = p.begin();
while (it != p.end()) {
auto itl = it, itr = it;
if (s[*it] != c[2] || !(it == p.begin() || ++itr == p.end() || s[*--itl] != s[*itr])) {
++it;
continue;
}
del(*it++, 2);
if (t[1] == t[2]) break;
}
}
if (t[0] < t[1]) {
auto it = p.begin();
while (it != p.end()) {
auto itl = it, itr = it, itrr = it;
if (s[*it] == c[0] || ++itr == p.end() || s[*itr] == c[0] || s[*it] == s[*itr] || !(it == p.begin() || (itrr = itr, ++itrr) == p.end() || s[*--itl] != s[*itrr])) {
++it;
continue;
}
int x = s[*it] == c[1] ? 1 : 2, y = x == 1 ? 2 : 1;
del(*it++, x), del(*it++, y);
if (t[0] == t[1]) break;
}
}
for (int x : p) printc(s[x]);
return 0;
}
Square Constraints
题意
- 给定 $n$，求满足以下条件的 $0 \sim 2n-1$ 的排列 $p_{0\dots2n-1}$ 的个数。
- 对于 $i \in [0,2n-1]$，满足 $n^2 \le i^2 + p_i^2 \le (2n)^2$。
- $n \le 250$，答案对 $P$ 取模。
题解
本质上，这依然是一个 $p_i \in [l_i,r_i]$ 的计数问题。
在没有下界限制的情况下，我们有个经典的做法是，将 $r_i$ 从小到大排序，这样当考虑第 $i$ 个数时，由于前面的 $r$ 都 $\le r_i$，因此无论前面怎么填，第 $i$ 个数的方案数都为 $r_i + 1 – i$（编号从 $0$ 开始），总方案数为 $\prod_{i=0}^{2n-1} r_i + 1 – i$。
在有下界时，我们可以考虑容斥，设 $f(k)$ 表示至少有 $k$ 个数小于下界时的方案数，则答案为 $\sum_{k=0}^{2n} (-1)^kf(k)$。
回到本题，题意的约束条件比较奇怪，考虑将它变得直观一点就是：
- 以原点为圆心在第一象限画两个半径分别为 $n,2n$ 的 $1/4$ 圆，对于 $i \in [0,2n-1]$，$(i,p_i)$ 必须在这两个 $1/4$ 圆之间（含圆上）。
于是我们有 $l_{n\dots2n-1} = 0$，因此只有对于 $i \in [0,n-1]$ 才有可能 $p_i < l_i$。
考虑枚举若干个 $i$ 要求 $p_i < l_i$，则此时相当于没有下界限制的计数，用上面的方法即可。
然而显然我们不能枚举每个 $i \in [0, n-1]$ 是否要求 $p_i < l_i$，有没有什么办法可以直接计算出 $f(k)$ 呢？
注意到对 $r$ 排序后求 $\prod_{i=0}^{2n-1} r_i + 1 – i$，本质上相当于对于每个 $i$，其贡献为，$\le r_i$ 的数的个数（$r_i+1$ 个），减去比 $r_i$ 小的限制的个数（$r_i$ 相同则钦定一个顺序）。
考虑：
- 对于 $i \in[0,n-1]$，以 $l_i – 1$ 为第一关键字，$r_i$ 为第二关键字。
- 对于 $i \in [n, 2n-1]$，以 $r_i$ 为第一关键字，$l_i-1$ 为第二关键字。
排序，设排序后的序列为 $q_{1\dots2n}$（注意，这里是从 $1$ 开始编号，也只有这里从 $1$ 开始编号）。
考虑 DP，设 $f_{i,j}$ 表示对于 $q_{1\dots i}$ 均满足 $\le r$，且其中有 $j$ 项满足 $< l$ 时对答案的贡献。
设 $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 的有 $t$ 个，考虑如何转移，观察上面那个直观的限制图：
- 若 $q_i \in [0,n-1]$，且只要求 $p_{q_i} \le r_{q_i}$，其贡献为：
$\le r_{q_i}$ 的数（$r_{q_i} + 1$ 个），减去比 $r_{q_i}$ 小的限制的个数：- 所有 $i \in [n,2n-1]$ 的 $r_i$（$n$ 个）
- $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 的 $q$（$t$ 个）
- $q_{i+1\dots 2n-1}$ 中 $\in [0,n-1]$ 且要求 $<l$ 的 $q$（$k-j$ 个）
转移：$f_{i,j}\leftarrow f_{i-1,j} \cdot (r_{q_i} + 1 – (n + t + k – j))$。
-
若 $q_i \in [0,n-1]$，且要求 $p_{q_i} < l_{q_i}$，其贡献为：
$< l_{q_i}$ 的数（$l_{q_i}$ 个），减去比 $l_{q_i}-1$ 小的限制的个数：- $q_{1\dots i-1}$ 中 $\in [n,2n-1]$ 的 $q$（$i-1-t$ 个）
- $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 且要求 $<l$ 的 $q$（$j-1$ 个）
转移：$f_{i,j} \leftarrow f_{i-1,j-1} \cdot (l_{q_i} – (i-1-t+(j-1)))$。
-
若 $q_{n,2n-1}$，其贡献为：
$\le r_{q_i}$ 的数（$r_{q_i} + 1$ 个），减去比 $r_{q_i}$ 小的限制的个数：- $q_{1\dots i-1}$ 中 $\in [n,2n-1]$ 的 $q$（$i-1-t$ 个）
- $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 且要求 $<l$ 的 $q$（$j$ 个）
转移：$f_{i,j} \leftarrow f_{i-1,j} \cdot (r_{q_i} + 1 – (i-1-t+j))$。
时间复杂度 $\mathcal O(n^3)$。
代码
const int N = 507;
int n, l[N], r[N], q[N];
modint f[N][N], ans;
inline modint calc(int k) {
f[0][0] = 1;
for (int i = 1, t = 0; i <= n << 1; t += q[i] < n, i++)
for (int j = 0; j <= min(min(i, k), t + (q[i] < n)); j++)
if (q[i] < n) f[i][j] = f[i-1][j] * (r[q[i]] + 1 - (n + t + k - j)) + (j ? f[i-1][j-1] * (l[q[i]] - (i - 1 - t + (j - 1))) : 0);
else f[i][j] = f[i-1][j] * (r[q[i]] + 1 - (i - 1 - t + j));
return f[n<<1][k];
}
int main() {
rd(n, P);
for (int i = 0; i < n << 1; i++)
l[i] = max(0, (int)ceil(sqrt(n * n - i * i))),
r[i] = min(2 * n - 1, (int)floor(sqrt(4 * n * n - i * i))),
q[i+1] = i;
sort(q + 1, q + (n << 1 | 1), [&](int i, int j) {
pi x = i < n ? mp(l[i] - 1, r[i]) : mp(r[i], l[i] - 1);
pi y = j < n ? mp(l[j] - 1, r[j]) : mp(r[j], l[j] - 1);
return x < y;
});
for (int i = 0; i <= n; i++)
if (i & 1) ans -= calc(i);
else ans += calc(i);
print(ans);
return 0;
}
