2023.09.18
T1 刘谋
题面描述
现在，反抗军首领大司马交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及骚猪帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。
赛时做法
直接暴力 BFS 求出每次连通块，时间复杂度 \(\mathcal{O}(k\times n)\)，预估得分 \(30\text{pts}\)，实际得分 \(30\text{pts}\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int n, m;
bool vis[N], p[N];
vector<int> e[N];
inline void bfs(int st) {
queue<int> q;
q.push(st);
vis[st] = 1;
while(!q.empty()) {
int tmp = q.front();
q.pop();
for(auto i : e[tmp]) {
if(!p[i] && !vis[i]) {
vis[i] = 1;
q.push(i);
}
}
}
return ;
}
int main() {
cin >> n >> m;
while(m--) {
int x, y;
scanf("%d%d", &x, &y);
e[x].push_back(y);
e[y].push_back(x);
}
int k, cnt = 0;
cin >> k;
for(int i = 0; i < n; i++) {
if(!vis[i]) {
bfs(i);
++cnt;
}
}
for(int i = 0; i < n; i++) {
vis[i] = 0;
}
printf("%d\n", cnt);
while(k--) {
int x, cnt = 0;
scanf("%d", &x);
p[x] = 1;
for(int i = 0; i < n; i++) {
if(!p[i] && !vis[i]) {
bfs(i);
++cnt;
}
}
for(int i = 0; i < n; i++) {
vis[i] = 0;
}
printf("%d\n", cnt);
}
return 0;
}
正解
删边求联通块个数，反过来就变成加边求联通块个数
天
题面描述
我们称一个矩阵是美丽的，当且仅当该这矩阵中不存在两个相同的数在同一列或在同一行。
给定 n 个数，刘谋要求你选出尽量多的数，使它们能够组成一个美丽的矩形。
注意，本题要求输出选出的数的个数与组成矩形大小和具体方案。
正解
考虑枚举短边的长度 \(r\) ， 那么枚举短边长度就是 \(\mathcal{O}(\sqrt{n})\)的，对于每一种短边长度我们 check 一次，那么总复杂度就是 \(\mathcal{O}(n\times\sqrt{n})\) 的，记 \(cnt_i\) 为数字 \(i\) 的个数，那么我们至多能填 \(sr=\sum\min\{cnt_i, r\})\) 个数，长边至多为 \(\left\lfloor sr\div r\right\rfloor\)，然后就是构造方案了， 方案的构造也很简单，首先把每个数按照出现次数从大到小排序排成一个数列，直接从一个点开始每次向右下角一格不停地放就行了。
抽烟
题面描述
给定一棵 \(n\) 个结点的有根树 \(T\)，结点从 \(1\) 开始编号，根结点为 \(1\) 号结点，每个结点有一个正整数权值 \(v_i\)。
设 \(x\) 号结点的子树内（包含 \(x\) 自身）的所有结点编号为 \(c_1,c_2,\cdots,c_k\)，定义 x 的价值为：\(val(x) = (v_{c_1} + d(c_1, x))\oplus(v_{c_2} + d(c_2, x))\oplus(v_{c_k} + d(c_k, x))\)。
其中 \(d(x,y)\) 表示树上 \(x\) 号结点与 \(y\) 号结点间唯一简单路径所包含的边数，\(d(x, x)=0\)。\(\oplus\) 表示异或运算。
请你求出 \(\sum\limits_{i=1}^nval(i)\) 的结果。
赛时做法
依旧用香香的暴力，时间复杂度 \(\mathcal{O}(n\times(n+m))\)。预估分数 \(10\text{pts}\)，实际得分 \(40\text{pts}\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 525015;
int n, v[N], dep[N], f[N];
vector<int> e[N];
inline void dfs(int x) {
dep[x] = dep[f[x]] + 1;
for(auto i : e[x]) {
if(i == f[x]) {
continue;
}
dfs(i);
}
}
int ans = 0, sum = 0;
inline void dfs2(int x, int ff) {
sum ^= (v[x] + dep[x] - dep[ff]);
for(auto i : e[x]) {
if(i == f[x]) {
continue;
}
dfs2(i, ff);
}
}
signed main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> v[i];
}
for(int i = 2; i <= n; i++) {
cin >> f[i];
e[i].push_back(f[i]);
e[f[i]].push_back(i);
}
f[1] = 0;
dep[0] = 0;
dfs(1);
for(int i = 1; i <= n; i++) {
sum = 0;
dfs2(i, i);
ans += sum;
}
cout << ans;
return 0;
}
正解
考虑用 trie 树维护子树内所有点的 \((v+dis)\)，然后合并这个 trie 树就行，那么这个 trie 树需要支持的操作就是求全局异或和，插入一个数，全局加一，第三个操作把 trie 树按数位从低到高建每次交换左右儿子，进入新的左儿子，再交换左右儿子，进入新的儿子，不断重复就可以了，复杂度 \(\mathcal{O}(n\times\log_2n)\)。
神仙
题面描述
有 \(n\) 种商品，第 \(i\) 种商品的价格是 \(c_i\)，购买后可以增加 \(h_i\) 的快乐指数，将于第 \(t_i\) 天上市。商品的保质期为 \(p\) 天，过期后不能再购买，即第 \(i\) 种商品只能在第 \(t_i\) 天到第 \(t_i + p − 1\) 天之间购买，每种商品只能购买一次。
有 \(q\) 个询问，每次给定两个整数 \(a,b\)，求在第 \(a\) 天去购物，最多使用 \(b\) 元的情况下可以得到的最大快乐指数。询问之间互不干扰。
赛时做法
仍然是暴力进行 01 背包，时间复杂度为 \(\mathcal{O}\left(t\times n\times \left(\max\limits_{i\in[1,n]}\{t_i\}+p-1\right)\right)\)。预估分数 \(40\text{pts}\)，实际分数 \(40\text{pts}\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
struct node {
int c, h, l, r;
} a[N];
int n, p, f[N];
int main() {
cin >> n >> p;
for(int i = 1; i <= n; i++) {
cin >> a[i].c >> a[i].h >> a[i].l;
a[i].r = a[i].l + p - 1;
}
int q;
cin >> q;
while(q--) {
int aa, bb;
cin >> aa >> bb;
for(int i = 1; i <= bb; i++) {
f[i] = 0;
}
for(int i = 1; i <= n; i++) {
if(aa < a[i].l || aa > a[i].r) {
continue;
}
for(int j = bb; j >= a[i].c; j--) {
f[j] = max(f[j], f[j - a[i].c] + a[i].h);
}
}
cout << f[bb] << '\n';
}
fclose(stdin);
fclose(stdout);
return 0;
}
正解
把商品打到线段树上去线段树分治，然后遍历线段树，每次遇见一个新物品更新一次背包，复杂度 \(O(n)\)，遍历之前记录一下当前的背包数列，遍历完回溯的时候赋值就行，因为所有物品是 \(O(n\times\log_2p)\) 的，所以复杂度 \(O(n^2\times\log_2p)\)。
总结
这次预估分数 \(30+20+10+40=100\)，实际分数 \(30+20+40+40=130\)，感觉有点难，后两题涉及了 trie 和线段树分治，不在能力范畴之内了。