JOISC 2018 题解
Visits: 1074
Day 1
道路建设
发现操作本质上是一个 $\text{access}$，LCT 维护即可，逆序对就把路径上的颜色块爬下来树状数组求就行了，时间复杂度 $\mathcal O(n \log^2 n)$。
const int N = 1e5 + 7;
struct LCT {
int f[N], ch[N][2], s[N], z[N], a[N];
#define lc ch[p][0]
#define rc ch[p][1]
#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
#define get(p) (p == ch[f[p]][1])
#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
#define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
inline void spd(int p) {
if (z[p]) {
if (lc) a[lc] = z[lc] = z[p];
if (rc) a[rc] = z[rc] = z[p];
z[p] = 0;
}
}
inline void rot(int p) {
int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
if ((f[p] = y) && !o) ch[y][v] = p;
}
void pre(int p) {
if (!isrt(p)) pre(f[p]);
spd(p);
}
inline void splay(int p) {
pre(p);
for (int x = f[p]; !isrt(p); rot(p), x = f[p])
if (!isrt(x)) rot(get(p) == get(x) ? x : p);
}
inline vector<pi> access(int p) {
vector<pi> ret;
int w = 0;
for (int x = 0; p; p = f[x=p])
splay(p), rc = x, upd(p),
ret.pb(mp(a[p], s[p] - w)), w = s[p];
return ret;
}
inline void link(int p, int x) {
int w = a[x];
splay(p), rc = x, f[x] = p, splay(x), upd(x), a[x] = z[x] = w;
}
} lct;
struct BIT {
vector<ll> c;
inline BIT() {}
inline BIT(int n) { c.resize(n); }
inline void add(ui x, ll k) {
while (x < c.size()) c[x] += k, x += x & -x;
}
inline ll ask(ui x) {
ll k = 0;
while (x) k += c[x], x -= x & -x;
return k;
}
};
int n, a[N];
int main() {
rd(n);
for (int i = 1; i <= n; i++) rd(a[i]), lct.a[i] = a[i];
sort(a + 1, a + n + 1);
int t = unique(a + 1, a + n + 1) - (a + 1);
BIT c(t + 1);
for (int i = 1; i <= n; i++)
lct.a[i] = lower_bound(a + 1, a + t + 1, lct.a[i]) - a;
lct.s[1] = 1;
for (int i = 1, x, y; i < n; i++) {
rd(x, y);
auto ret = lct.access(x);
ll ans = 0;
for (pi o : ret)
ans += o.se * c.ask(o.fi - 1), c.add(o.fi, o.se);
print(ans);
for (pi o : ret) c.add(o.fi, -o.se);
lct.link(x, y);
}
return 0;
}
栅栏
咕。
帐篷
设 $f_{i,j}$ 表示 $i,j$ 的答案，转移枚举第一行怎么填即可，采用记搜写法，时间复杂度 $\mathcal O(n^2)$。
const int N = 3e3 + 7;
const modint inv2 = (modint)1 / 2;
modint f[N][N];
bool v[N][N];
inline modint F(int n, int m) {
if (!n || !m) return 1;
if (v[n][m]) return f[n][m];
v[n][m] = 1;
modint &k = f[n][m];
k += F(n - 1, m);
k += m * F(n - 1, m - 1) * 4;
if (m >= 2) k += m * (m - 1) * inv2 * F(n - 1, m - 2);
if (n >= 2) k += m * (n - 1) * F(n - 2, m - 1);
return k;
}
int main() {
int n, m;
rd(n, m), print(F(n, m) - 1);
return 0;
}
Day 2
修行
题意相当于求有多少 $1\sim n$ 的排列满足 $p_i > p_{i+1}$ 的 $i$ 恰好 $k-1$ 个。
转化为求概率，等价于 $n$ 个 $[0,1)$ 的随机变量 $a_{1\dots n}$ 满足 $a_i > a_{i+1}$ 的 $i$ 恰好 $k-1$ 个的概率。
考虑构造 $b_{i} = [a_{i-1} > a_i] + a_i – a_{i-1}$，其中 $b_1 = a_1$，即 $a$ 为 $b$ 的前缀和的小数部分。
于是问题转化为求 $k-1 \le \sum_{i=1}^n b_i < k$ 的概率，可以差分一下。
考虑容斥掉 $b_i \in [0,1)$ 的限制，于是问题变成 $n$ 个 $[0,+\infty)$ 的数之和 $< k$ 的概率，这个概率实际上等于 $\frac{k^n}{n!}$。
总时间复杂度 $\mathcal O(n \log n)$。
int n, k;
inline modint calc(int k) {
modint ans = 0, o = 1;
for (int i = 0; i < k; i++, o = -o)
ans += o * binom(n, i) * ((modint)(k - i) ^ n);
return ans;
}
int main() {
rd(n, k), init(n);
print(calc(k) - calc(k - 1));
return 0;
}
路网服务
提答题，扔了。
最差记者 3
首先可以直接求出每个人的周期，即当 $i-1$ 走的长度不小于 $d_i$ 时，$i$ 将走 $i-1$ 所走的那么长。
于是 $d_i$ 为 $d_{i-1}$ 的倍数，则不同的 $d$ 只有 $\mathcal O(\log w)$ 个，则每次暴力求区间交即可，时间复杂度 $\mathcal O(q\log w)$。
const int N = 5e5 + 7;
int n, m, a[N];
int main() {
rd(n, m), rda(a, n), a[0] = 1;
vector<pi> p;
p.pb(mp(1, 0));
for (int i = 1; i <= n; i++) {
if (a[i] % a[i-1]) a[i] = (a[i] / a[i-1] + 1) * a[i-1];
if (a[i] == a[i-1]) ++p.back().se;
else p.pb(mp(a[i], i));
}
for (int i = 1, t, l, r, ans, lst; i <= m; i++) {
rd(t, l, r), ans = lst = 0;
for (pi o : p) {
int L = t / o.fi * o.fi - o.se, R = t / o.fi * o.fi - lst;
ans += max(0, min(r, R) - max(l, L) + 1), lst = o.se + 1;
}
print(ans);
}
return 0;
}
Day 3
比太郎的聚会
对于这种询问中的某个量之和与 $n$ 同阶的题目，通常有三个做法：
- 如果是在树上，可以考虑虚树。
- 这个量只有 $\mathcal O(\sqrt n)$ 种，算过的保存下来就可以直接用。
- 这个量 $> \sqrt n$ 的只有 $\mathcal O(\sqrt n)$ 个，可以暴力；$\le \sqrt n$ 的通常可以预处理。
本题考虑第三个性质即可。
安全门
咕。
Day 4
糖
其实是 经典题。
其实同样是个带悔贪心。
带悔贪心的解题方法：
- 算上反悔的代价之后用堆贪心。
- 模拟费用流。
首先贪心的选，当选择在 $i$ 之后，$i-1$ 和 $i+1$ 的位置要么同时选，要么同时不选，当同时选的时候就要撤销选择 $i$，因此我们可以将 $a_{i-1}+a_{i+1}-a_i$ 作为一个新的物品放入原本 $i$ 的位置，同时删掉 $i-1$ 和 $i+1$。
用链表和堆维护即可。
#define P pair<ll, int>
const int N = 2e5 + 7;
int n, m, l[N], r[N];
ll a[N], ans;
bool v[N];
priority_queue<P> q;
int main() {
rd(n), m = (n + 1) >> 1, rda(a, n), a[0] = a[n+1] = -1e18, r[n+1] = n + 1;
for (int i = 1; i <= n; i++)
q.push(mp(a[i], i)), l[i] = i - 1, r[i] = i + 1;
for (int i = 1; i <= m; i++) {
while (v[q.top().se]) q.pop();
int x = q.top().se;
q.pop(), ans += a[x], print(ans);
int L = l[x], R = r[x];
v[L] = v[R] = 1, a[x] = a[L] + a[R] - a[x];
l[x] = l[L], r[x] = r[R], r[l[x]] = x, l[r[x]] = x;
if (L >= 1 && R <= n) q.push(mp(a[x], x));
}
return 0;
}
图书馆
考虑先通过最多 $n$ 次询问找到某一端，方法为询问 $[1,n] – i$，若答案为 $1$ 说明是某一端。
然后从这一端不断地找到与其相邻的下一个位置。考虑二分，假设我们现在要找到与位置 $p$ 相邻的某个位置，设可能的位置集合为 $S$，将其均匀的分为 $A,B$ 两个集合，然后询问 $A$ 和 $A + p$ 的答案，如果后者等于前者，说明 $A$ 中存在与 $p$ 相邻的位置，否则说明 $B$ 中存在与 $p$ 相邻的位置，然后二分下去即可。
询问复杂度为 $\mathcal O(n \log n)$。
int n;
inline int ask(vi p, int w = 0) {
vi m(n);
for (int x : p) m[x-1] = 1;
if (w) m[w-1] = 1;
return Query(m);
}
void Solve(int n) {
srand(time(0) ^ n);
::n = n;
vi p(n);
for (int i = 0; i < n; i++) p[i] = i + 1;
random_shuffle(p.begin(), p.end());
for (int i = 0; i < n; i++) {
swap(p[0], p[i]);
if (i == n - 1 || ask(vi(p.begin() + 1, p.end())) == 1) break;
}
for (int i = 0; i < n - 1; i++) {
auto l = p.begin() + i + 1, r = p.end();
while (l + 1 != r) {
auto mid = l + ((r - l) >> 1);
if (ask(vi(l, mid)) == ask(vi(l, mid), p[i])) r = mid;
else l = mid;
}
swap(p[i+1], *l);
}
Answer(p);
}
野猪
咕。
