C. 卡片放置
题目描述
有一些卡片，写着两个数字 \(A_i,B_i\)。你要将这些这些卡片排列，其对于你的分数为 \(\max(A_i,B_i)\cdot i\)，对于对手的分数为 \(\min(A_i,B_i)\cdot (N-i+1)\)。求令你的分数减对方分数的最大的方案数。
思路
我们来拆式子，这里令 \(A_i\ge B_i\)：
\[\begin{array}{l} &A_i\cdot i-B_i\cdot (N-i+1)\\ =&A_i\cdot i-B_i\cdot N+B_i\cdot i-B_i\\ =&(A_i+B_i)\cdot i-(N+1)\cdot B_i \end{array} \]后一项为定值，不看。很明显只有在 \(A_i+B_i\) 升序排列才最优，只有相同元素之间可以排列。预处理阶乘即可。
空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100001, MOD = int(1e9) + 7;
int n, a[MAXN], f[MAXN], ans = 1;
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
f[0] = 1;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
f[i] = 1ll * f[i - 1] * i % MOD;
}
for(int i = 1, x; i <= n; ++i) {
cin >> x;
a[i] += x;
}
sort(a + 1, a + n + 1);
for(int i = 1, j = 1; i <= n; i = j) {
for(; j <= n && a[i] == a[j]; ++j) {
}
ans = 1ll * ans * f[j - i] % MOD;
}
cout << ans;
return 0;
}
D. 合理架构
题目描述
有一个 \(N\) 个结点，以 \(1\) 为根的树，每个结点都有两个值 \(A_i,B_i\)。你要判断是否符合以下条件：
- 对于所有 \(u,v\) 使得 \(u\) 是 \(v\) 的祖先，要满足 \(A_u\ge A_v\and B_u\ge B_v\)。
- 对于所有 \(u\) 不是 \(v\) 的祖先，要满足 \(A_u<A_v\or B_u<B_v\)。
思路
条件 1 显然判断一下父子之间的 \(A,B\) 即可。
对于条件 2，我们求每个点 \(u\) 有多少个点 \(v\) 不满足条件 2。这个就是离线二维数点。
可以发现，只有 \(u\) 的祖先会不满足条件 2。所以只需判断不满足数量是否等于 \(dep_u\) 即可。
空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200001, INF = int(1e9) + 1;
struct Tree_Array {
int n, tr[MAXN];
void Clear(int m) {
n = m;
fill(tr + 1, tr + n + 1, 0);
}
void update(int p, int x) {
for(; p <= n; tr[p] += x, p += (p & -p)) {
}
}
int Getsum(int p) {
int sum = 0;
for(; p; sum += tr[p], p -= (p & -p)) {
}
return sum;
}
}tr;
int t, n, a[MAXN], b[MAXN], dep[MAXN], ans[MAXN];
vector<tuple<int, int, int, int>> ve[MAXN];
vector<int> e[MAXN], A, B, vec[MAXN];
bool dfs(int u, int fa) {
if(fa && (a[u] > a[fa] || b[u] > b[fa])) {
return 0;
}
dep[u] = dep[fa] + 1;
for(int v : e[u]) {
if(v != fa && !dfs(v, u)) {
return 0;
}
}
return 1;
}
void Solve() {
cin >> n;
A.clear(), B.clear();
for(int i = 0; i <= n; ++i) {
ve[i].clear(), vec[i].clear();
}
for(int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i];
e[i].clear();
A.emplace_back(a[i]);
B.emplace_back(b[i]);
ans[i] = 0;
}
sort(A.begin(), A.end()), A.erase(unique(A.begin(), A.end()), A.end());
sort(B.begin(), B.end()), B.erase(unique(B.begin(), B.end()), B.end());
for(int i = 1; i <= n; ++i) {
a[i] = lower_bound(A.begin(), A.end(), a[i]) - A.begin() + 1;
b[i] = lower_bound(B.begin(), B.end(), b[i]) - B.begin() + 1;
ve[a[i] - 1].emplace_back(b[i], n, -1, i);
ve[n].emplace_back(b[i], n, 1, i);
vec[a[i]].emplace_back(b[i]);
}
for(int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
if(!dfs(1, 0)) {
cout << "NO\n";
return;
}
tr.Clear(n);
for(int i = 1; i <= n; ++i) {
for(int x : vec[i]) {
tr.update(x, 1);
}
for(auto [l, r, x, id] : ve[i]) {
ans[id] += (tr.Getsum(r) - tr.Getsum(l - 1)) * x;
}
}
for(int i = 1; i <= n; ++i) {
if(ans[i] != dep[i]) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for(cin >> t; t--; Solve()) {
}
return 0;
}