1005, 1010, 1003, 1009, 1007, 1004
(写到T7了不会T3的组合数学,我无敌了.)
1005 修复公路
签到题, 首先把传送门转化为两条双向边, 然后用并查集维护加上所有传送门的双向边之后有多少联通块.
观察到每个点旁边的点要不就全是同一联通块中的点,要不是别的联通块的点, 这时候只要连一条长度为\(1\)的公路就能把这两个联通块合并.
所以答案就是联通块数量\(-1\).
code:
class DSU {
public:
std::vector<int> d;
DSU(std::size_t size) : d(size + 1) {
std::iota(d.begin(), d.end(), 0);
}
int root(int u) {
return d[u] == u ? u : d[u] = root(d[u]);
}
void bind(int u, int v) {
d[root(u)] = root(v);
}
};
void solve() {
int n;
cin >> n;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
DSU dsu(n);
for (int i = 1; i <= n; i++) {
if (i - arr[i] >= 1) {
dsu.bind(i, i - arr[i]);
}
if (i + arr[i] <= n) {
dsu.bind(i, i + arr[i]);
}
}
int ans = -1;
for (int i = 1; i <= n; i++) {
ans += dsu.root(i) == i;
}
cout << ans << endl;
}1010 选择配送
这里要求的是曼哈顿距离的最大值.
观察\((a, b)\)到一个点\((x, y)\)的曼哈顿距离是\(max(abs((x + y) – (a + b)), abs((x – y) – (a – b)))\).
那么\((x, y)\)到一个点集中的点的距离的最大值其实就是:
\(max(abs((x + y) -max (a_i + b_i)), abs((x + y) -min (a_i + b_i)), abs((x – y) -max (a_i – b_i)), abs((x – y) -min (a_i – b_i)))\).
我们计算下这个点集的\(max (a_i + b_i)\), \(min (a_i + b_i)\), \(max (a_i – b_i)\), \(min (a_i – b_i)\) 即可.
code:
void solve() {
int n, m;
cin >> n >> m;
int min_plus = 2 * INF, max_plus = -2 * INF, min_min = 2 * INF, max_min = -2 * INF;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
min_plus = min(min_plus, x + y);
max_plus = max(max_plus, x + y);
min_min = min(min_min, x - y);
max_min = max(max_min, x - y);
}
int ans = 2 * INF;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
ans = min(ans, max({abs(min_plus - (x + y)), abs(max_plus - (x + y)), abs(min_min - (x - y)), abs(max_min - (x - y))}));
}
cout << ans << '\n';
}1001 数列计数
铸币\(xkm\)不会😭.
1003 拼尽全力
首先很容易得到: 如何进行面试的顺序不会影响是否能通过每一次面试(当然这个顺序得满足面试时能力满足要求).
那我们就可以用一个队列存放我们现在能通过的面试, 然后一个个遍历.
当我们通过一个面试之后, 能力值会增加, 就可能能通过更多的面试, 那如何找到更多的能通过的面试呢?
当某个能力值满足某个面试的时候, 我们无法知道这个面试的其他能力是否也是满足的. 这时候就可以用一个\(cnt\)来记录这个面试还有几个能力是不够的, 当\(cnt\)为\(0\)时就加入到队列. 同时对每个能力维护一个数组, 根据需要的能力值递增的存放面试\(id\). 这样我们就可以在\(O(n \times m + m \times n \log{n})\)的复杂度下去维护这个问题了.
最后\(check\)是否有非零的\(cnt\)即可.
code:
void solve() {
int n, m;
cin >> n >> m;
vector<LL> now(m);
for (auto &i : now) cin >> i;
vector<vector<int>> cs(n, vector<int>(m)), ws(n, vector<int>(m));
vector<vector<pair<int, int>>> todo(m);
vector<int> cnt(n);
queue<int> que;
for (int i = 0; i < n; i++) {
auto &c = cs[i], &w = ws[i];
for (auto &x : c) cin >> x;
for (auto &x : w) cin >> x;
for (int j = 0; j < m; j++) {
if (c[j] > now[j])
cnt[i]++, todo[j].push_back({c[j], i});
}
if (cnt[i] == 0) {
que.push(i);
}
}
for (int i = 0; i < m; i++)
sort(todo[i].begin(), todo[i].end());
vector<int> p(m), len(m);
for (int i = 0; i < m; i++)
len[i] = todo[i].size();
while (que.size()) {
auto x = que.front();
que.pop();
for (int i = 0; i < m; i++) {
now[i] += ws[x][i];
while (p[i] < len[i] && now[i] >= todo[i][p[i]].first) {
cnt[todo[i][p[i]].second]--;
if (cnt[todo[i][p[i]].second] == 0) {
que.push(todo[i][p[i]].second);
}
p[i]++;
}
}
}
if (accumulate(cnt.begin(), cnt.end(), 0LL) == 0) {
cout << "YES" << '\n';
} else {
cout << "NO" << '\n';
}
}1009 部落冲突
只考虑操作\(1\)很容易想到启发式合并. 操作\(2\), \(4\)也很好维护.
主要就是操作\(3\)会带来一些问题.
这时候我们可以建一个双向的映射, 把实际的编号映射到我们虚拟的编号, 同时也能把虚拟的编号反向映射到实际的编号. 这样就能\(O(1)\)实现操作\(3\).
同时要注意我们操作\(1\)启发式合并可能是\(a \to b\), 这时候再来个操作\(3\)即可.
code:
void solve() {
int n, q;
cin >> n >> q;
vector<int> view(n + 1), review(n + 1), d(n + 1);
vector<set<int>> haves(n + 1);
for (int i = 1; i <= n; i++) haves[i].insert(i);
iota(view.begin(), view.end(), 0);
iota(review.begin(), review.end(), 0);
iota(d.begin(), d.end(), 0);
while (q--) {
int op;
cin >> op;
if (op == 1) {
int a, b;
cin >> a >> b;
int aa = view[a], bb = view[b];
if (haves[aa].size() >= haves[bb].size()) {
for (auto i : haves[bb]) {
haves[aa].insert(i);
d[i] = aa;
}
} else {
for (auto i : haves[aa]) {
haves[bb].insert(i);
d[i] = bb;
}
swap(view[a], view[b]);
swap(review[aa], review[bb]);
}
} else if (op == 2) {
int a, b;
cin >> a >> b;
int dd = d[a], bb = view[b];
d[a] = bb;
haves[dd].erase(a);
haves[bb].insert(a);
} else if (op == 3) {
int a, b;
cin >> a >> b;
int aa = view[a], bb = view[b];
swap(view[a], view[b]);
swap(review[aa], review[bb]);
} else {
int a;
cin >> a;
cout << review[d[a]] << '\n';
}
}
}1007 宝石商店
首先计算\(val\)的式子可以看出:
- \(0, 0 \to 0\)
- \(0, 1 \to 1\)
- \(1, 0 \to 1\)
- \(1, 1 \to 0\)
在01-Trie树上从高位到低位贪心即可, 然后区间查询就是很显然的可持久化01-Trie树.
code:
class trie_01 {
static const int size = 2e5 * 32 + 10; // 位数 * 数量
static const int e = 2; // 01
static const int n = 31; // max = 2 ^ n - 1;
int idx;
std::array<std::array<int, e>, size> tr;
std::array<int, size> cnt;
array<int, size> root;
int newnode() {
tr[idx].fill(0);
cnt[idx] = 0;
idx++;
return idx - 1;
}
static int to_int(int a, int d) {
return (a >> d) & 1;
}
public:
trie_01() : idx(0) { newnode(); }
void insert(int s, int ro) {
int p = newnode(), pre = root[ro - 1];
root[ro] = p;
tr[p] = tr[root[ro - 1]];
for (int i = n - 1; i >= 0; i--) {
int x = to_int(s, i); // 要映射到0开始的喵
tr[p][x] = newnode();
cnt[tr[p][x]] = cnt[tr[pre][x]] + 1;
tr[tr[p][x]] = tr[tr[pre][x]];
p = tr[p][x];
pre = tr[pre][x];
}
}
void clean() {
idx = 0;
newnode();
}
int query(int mask, int l, int r) {
int p = root[r], pre = root[l - 1];
int res = 0;
for (int i = n - 1; i >= 0; i--) {
int x = to_int(mask, i) ^ 1;
if (cnt[tr[p][x]] - cnt[tr[pre][x]]) {
res ^= 1 << i;
} else {
x ^= 1;
}
p = tr[p][x];
pre = tr[pre][x];
}
return res;
}
};
trie_01 trie;
void solve() {
trie.clean();
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
trie.insert(a, i);
}
while (q--) {
int l, r, x;
cin >> l >> r >> x;
cout << trie.query(x, l, r) << '\n';
}
}1004 弯曲筷子
不舒适度计算的式子可以看出最好选择的是相邻的筷子, 故先把所有筷子排序.
我们记必须选的筷子为"a".
那我们就可以写一个\(dp[m + 1][4]\), \(dp[i]\)表示考虑到第\(i\)个必须选择的筷子, 四个值分别代表:
- 匹配前面一个非a
- 匹配后面一个非a
- 匹配前面一个a
- 匹配后面一个a
\(O(1)\)进行一个\(dp\)的转移即可.
code:
void solve() {
int n, m;
cin >> n >> m;
vector<pair<LL, int>> c(n);
for (auto &i : c) cin >> i.first;
for (int i = 0; i < m; i++) {
int x;
cin >> x;
c[x - 1].second = 1;
}
sort(c.begin(), c.end());
vector<int> pp;
pp.push_back(0);
for (int i = 0, p = 0; i < m; i++) {
while (c[p].second == 0) {
p++;
}
c[p].second = i + 1;
pp.push_back(p);
p++;
}
// 匹配前面一个非a, 匹配后面一个非a, 匹配前面一个a, 匹配后面一个a
vector<array<LL, 4>> dp(m + 1, array<LL, 4>{INF, INF, INF, INF});
dp[0].fill(0);
dp[0][3] = INF;
for (int i = 0; i < n; i++) {
auto x = c[i].first;
auto id = c[i].second;
if (id == 0)
continue;
if (i != 0) {
if (!c[i - 1].second) {
dp[id][0] = (x - c[i - 1].first) * (x - c[i - 1].first) + min(dp[id - 1][0], dp[id - 1][2]);
if (i - 1 != 0 && !c[i - 2].second) {
dp[id][0] = min(dp[id][0], (x - c[i - 1].first) * (x - c[i - 1].first) + dp[id - 1][1]);
}
}
}
dp[id][2] = dp[id - 1][3];
if (i + 1 < n) {
if (!c[i + 1].second) {
dp[id][1] = (x - c[i + 1].first) * (x - c[i + 1].first) + min({dp[id - 1][0], dp[id - 1][1], dp[id - 1][2]});
}
}
if (id != m) {
dp[id][3] = (x - c[pp[id + 1]].first) * (x - c[pp[id + 1]].first) + *min_element(dp[id - 1].begin(), dp[id - 1].begin() + 3);
}
}
cout << *min_element(dp[m].begin(), dp[m].end()) << endl;
}