春训#1题解

A

难度： 900

合法的数字最高位一定不为 \(0\) ，这也就意味着低位只能全部为 \(0\) （如果有低位的话）。因此只需将最高位加一，其余位归零即可。

Code：

void solve() {n = read();int res = 1;while (n / res >= 10) res *= 10;int ans = ( n / res + 1 ) * res - n;cout << ans << '\n';
}

B

题目大意： 现有 \(n\) 个取值 \(1\)，\(2\) 或 \(3\) 的三元组。存在和不为 \(6\) 的三元组的方案被视为合法方案。求合法方案数。

难度： 1500

要求的方案数就是：全部的方案数 \(-\) 所有三元组和均为 \(6\) 的方案数。

由于对于每个三元组而言，总方案数是 \(27\) ，和为 \(6\) 的方案数是 \(7\) ，故最终答案为 \(27^n - 7^n\)。

Code：

void solve() {n = read();int ans1 = 1, ans2 = 1;FOR(i, 1, n) ans1 = ans1 * 7 % MOD;FOR(i, 1, n * 3) ans2 = ans2 * 3 % MOD;cout << (ans2 - ans1 + MOD) % MOD;
}

C

题目大意： 给定出入会记录的一部分。判断哪些人可能满足：会中有人时始终在会中。

难度： 1800

首先，显然全程未出现记录的人一定符合要求，且不影响其他人的判断。我们在分析过程中无视他们即可。

第一条记录是出会的人在片段开始前就在会中。因此只要有这样的球员存在，第一条记录是入会的人一定不符合要求。而如果这样的人不存在，可能符合要求的只剩第一个入会的人。

接着我们模拟出会入会的情况。以下两种情况会被取消资格：

1. 出会时还有其他人在会中。
2. 出会时会中没人，但紧接着有其他人入会。

模拟结束后仍然未被取消资格的人，或全程无记录的人是符合要求的人。

Code:

void solve() {cin >> n >> m;map<int, int> mp;FOR(i, 1, m) {cin >> c[i] >> a[i];mp[a[i]] = 1;}int cnt = 0;FOR(i, 1, m) {if (c[i] == '+') {b[a[i]] = 1;} else {if (!b[a[i]]) {d[a[i]] = 1;ans[a[i]] = 1;cnt++;b[a[i]] = 1;}}}if (cnt == 0) {ans[a[1]] = 1;d[a[1]] = 1;}FOR(i, 1, m) {if (c[i] == '+') {cnt++;}if (c[i] == '-') {cnt--;if (cnt > 0) ans[a[i]] = 0;if (i != m) {if (a[i + 1] != a[i]) {ans[a[i]] = 0;}}}}FOR(i, 1, n) if (mp[i] == 0) ans[i] = 1;int tot = 0;FOR(i, 1, n) if (ans[i]) tot++;cout << tot << '\n';FOR(i, 1, n) if (ans[i]) cout << i << " ";
}

D

题目大意： 定义一个排列的值是其字典序排名，排列求和的结果是，两排列值之和模排列总数的结果对应的排列。求指定两排列的和。

难度： 2000

这似乎是康托展开的板子题，不过在听讲评之前我并不知道。

注意到一个排列的排名可如下计算：

\[R_p = \sum _{i = 1} ^{n} (r_i - 1) (n - i)! \]

其中 \(r_i\) 代表 \(p_i\) 在 \(p_k(k \geq i)\) 中的排名。因此也可知 \(r_i\leq n - i.\)

我们使用权值线段树记录到当前位置为止 \(x\) 是否还能选，则 \(x\) 的前缀和（不含 \(x\) ）即为 \(x\) 在剩下的数中的排名。

题目所求为两排列的排名之和，我们考虑以"各位分别相加+进位"的方法处理排名相加的过程。若进位至第零位，则正好满足了模 \(n!\) 的要求，无需处理。

进位完成后，只需再根据每一位在剩下数中的排名复原其值即可。这一操作赛时我通过二分查找+线段树来实现，时间复杂度 \(O(n\log^2n)\) ，未能通过此题。使用线段树上二分可将复杂度降至 \(O(n\log n)\) ，可以通过此题。

Code:

#include <bits/stdc++.h>
using namespace std;#define FOR(i,j,k) for (int i = j; i <= k; i++)
#define ROF(i,j,k) for (int i = j; i >= k; i--)int n, m, k;inline int read() {char ch = getchar(); int x = 0, f = 1;while ((ch > '9' || ch < '0') && ch != '-') ch = getchar();if (ch == '-') { ch = getchar(); f = - 1; }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}template <class Info, class Tag> class SGT {private:#define l(p) (p << 1)#define r(p) (p << 1 | 1)#define mid (l + r) / 2int n;vector<Info> info;vector<Tag> tag;void pushup(int p) { info[p] = info[l(p)] + info[r(p)]; }void pushdown(int p, int l, int r) {addTag(l(p), l, mid, tag[p]);addTag(r(p), mid + 1, r, tag[p]);tag[p] = Tag();}void addTag(int p, int l, int r, const Tag &v) {info[p].apply(v); tag[p].apply(v);}void rmodify(int p, int l, int r, int x, int y, const Tag &v) {if (l > y || r < x) return;if (r <= y && l >= x) { addTag(p, l, r, v); return; }pushdown(p, l, r);rmodify(l(p), l, mid, x, y, v);rmodify(r(p), mid + 1, r, x, y, v);pushup(p);}void pmodify(int p, int l, int r, int x, const Info &v) {if (l == r) { info[p] = v; return; }pushdown(p, l, r);if (x <= mid) pmodify(l(p), l, mid, x, v);else pmodify(r(p), mid + 1, r, x, v);pushup(p);}Info query(int p, int l, int r, int x, int y) {if (l > y || r < x) return Info();if (r <= y && l >= x) return info[p];pushdown(p, l, r);return query(l(p), l, mid, x, y) + query(r(p), mid + 1, r, x, y);}int findkth(int p, int l, int r, int k) {if (l == r) return l;else {pushdown(p, l, r);if (info[l(p)].sum >= k) return findkth(l(p), l, mid, k);else return findkth(r(p), mid + 1, r, k - info[l(p)].sum);pushup(p);}}public:SGT(int _n) : n(_n), info(_n << 2), tag(_n << 2) {};SGT(vector<Info> vc) : SGT(vc.size()) {auto build = [&](auto self, int p, int l, int r) {if (l == r) {info[p] = vc[l];return;}self(self, l(p), l, mid);self(self, r(p), mid + 1, r);pushup(p);};build(build, 1, 1, n);}void rmodify(int x, int y, const Tag &v) { rmodify(1, 1, n, x, y, v); }void pmodify(int x, const Info &v) { pmodify(1, 1, n, x, v); }Info query(int x, int y) { return query(1, 1, n, x, y); }int findkth(int k) { return findkth(1, 1, n, k); }};struct Tag {long long add;Tag(): add(0) {}Tag(int val): add(val) {}void apply(Tag v) { add += v.add; }
};struct Info {int len;long long sum;Info(): len(1), sum(0) {}Info(int val): len(1), sum(val) {}void apply(Tag v) { sum += v.add * len; }
};Info operator+(Info a, Info b) {Info c;c.len = a.len + b.len;c.sum = a.sum + b.sum;return c;
}signed main() {n = read();vector<int> p(n + 1), q(n + 1);vector<int> rp(n + 1), rq(n + 1), rk(n + 1);vector<bool> vis(n + 1);FOR(i, 1, n) p[i] = read() + 1;FOR(i, 1, n) q[i] = read() + 1;SGT<Info, Tag> tp(n), tq(n), tt(n);FOR(i, 1, n) {tp.pmodify(p[i], Info(1));rp[i] = p[i] - tp.query(1, p[i]).sum;tq.pmodify(q[i], Info(1));rq[i] = q[i] - tq.query(1, q[i]).sum;rk[i] = rp[i] + rq[i];}ROF(i, n - 1, 1) {rk[i - 1] += rk[i] / (n - i + 1);rk[i] %= (n - i + 1);}FOR(i, 1, n) tt.pmodify(i, Info(1));FOR(i, 1, n) {int u = tt.findkth(rk[i] + 1);tt.pmodify(u, Info(0));cout << u - 1 << " ";}return 0;
}