2022 ICPC Hangzhou G and 2022 ICPC Jinan
ICPC Hangzhou
G
手玩可以发现合法的图中最多只有一个环。所以对于 \(m = n - 1\) 的情况直接判合法；对于 \(m > n\) 的情况直接判非法，此时图中肯定不知有一个环；需要考虑 \(m = n\) 即图是基环树的情况。
当图是基环树时，得到该图的一个生成树也就是断开一条环上的边，也就是说断开的每条边都要是等价的，这就要求这个图有对称性。假设以环上的第 \(i\) 个点为根的子树是 \(t_i\)，\(t_i = t_j\) 表示两颗子树同构，则任意 \(t_i = t_j\) 时，基环树上的任意一颗子树都同构，是可以的。还有一种情况是两种形态的树在基环树上交替出现，此时一定是偶环。
判断同构用树哈希：
using i64 = long long;
using u64 = unsigned long long;
// using i128 = __int128_t;
// using point = std::array<i128, 2>;constexpr i64 Mod = 998244353;
constexpr int N = 1e5, P = 10;
const u64 Mask = std::mt19937_64(time(nullptr))();;std::vector<int> adj[N + 5];
int deg[N + 5];
bool cir[N + 5];
u64 val[N + 5];void init(int n) {for (int i = 1; i <= n; ++i) {adj[i].clear();deg[i] = 0;cir[i] = false;}
}// 树哈希
u64 shift(u64 x) {x ^= Mask;x ^= x << 13;x ^= x >> 7;x ^= x << 17;x ^= Mask;return x;
}
u64 dfs(int cur, int lst) {val[cur] = 1ull;for (auto &to : adj[cur]) {if (to != lst && !cir[to]) {val[cur] += shift(dfs(to, cur));}}return val[cur];
}bool solve() {int n = 0, m = 0;std::cin >> n >> m;init(n);for (int i = 0; i < m; ++i) {int u = 0, v = 0;std::cin >> u >> v;adj[u].push_back(v);adj[v].push_back(u);deg[u] += 1;deg[v] += 1;}if (m == n - 1) {return true;}if (m > n) {return false;}// 找环std::queue<int> q;for (int i = 1; i <= n; ++i) {if (deg[i] == 1) {q.push(i);}}while (not q.empty()) {auto cur = q.front();q.pop();for (auto &to : adj[cur]) {if (deg[to] == 0) {continue;}deg[cur] -= 1;deg[to] -= 1;if (deg[to] == 1) {q.push(to);}}}for (int i = 1; i <= n; ++i) {if (deg[i] >= 2) {cir[i] = true;}}std::vector<int> node;for (int i = 1; i <= n; ++i) {if (!cir[i]) {continue;}int cur = i, lst = 0;do{node.push_back(cur);for (auto &to : adj[cur]) {if (cir[to] && to != lst) {lst = cur;cur = to;break;}}} while (cur != i);break;}// 奇环if (node.size() % 2) {auto p = dfs(node[0], 0);for (int i = 1; i < node.size(); ++i) {if (dfs(node[i], 0) != p) {return false;}}}// 偶环else {std::array<u64, 2> p = { dfs(node[0], 0), dfs(node[1], 0) };for (int i = 2; i < node.size(); ++i) {if (dfs(node[i], 0) != p[i & 1]) {return false;}}}return true;
}ICPC Jinan
A
先用操作 3 一定是不劣的，用完操作 3 后，问题就变成了将一个序列里的数通过加减调整成全部一样，同时你可以删掉 \(m\) 个数，当知道要变成什么数时，也就知道了该删掉那 \(m\) 个数，即操作次数最多的那些数。
可能的目标值是不多的，大约只有 \(N\times log_2(10^9)\)（即每个数一直除 2 直到 1 为止），于是我们就可以先预处理出序列里的数到所有可能值得操作数，再枚举最后可能的值，优先队列选出操作数少的 \(n - m\) 个就好了
constexpr int N = 500, L = 40;int n, m;
int a[N + 5];
std::vector<int> s;i64 d[N + 5][N * L];i64 cnt(int j) {i64 ret = 0;std::priority_queue<i64> q;for (int i = 1; i <= n; ++i) {if (q.size() < m) {q.push(d[i][j]);ret += d[i][j];}else if (q.top() > d[i][j]) {ret -= q.top();q.pop();q.push(d[i][j]);ret += d[i][j];} }return ret;
}bool solve() {std::cin >> n >> m;s.clear();m = n - m;for (int i = 1; i <= n; ++i) {std::cin >> a[i];int cur = a[i];while (cur != 0) {s.push_back(cur);cur /= 2;}}// 预处理操作数std::sort(s.begin(), s.end(), std::greater<int>());s.erase(std::unique(s.begin(), s.end()), s.end());for (int i = 1; i <= n; ++i) {int cnt = 0;for (int j = 0; j < s.size(); ++j) {while (a[i] / 2 > s[j]) {a[i] /= 2;cnt += 1;}d[i][j] = cnt + std::abs(a[i] - s[j]);if (a[i] > 1) {d[i][j] = std::min(d[i][j], 1ll * (cnt + 1 + s[j] - a[i] / 2));}}}i64 ans = Inf;for (int i = 0; i < s.size(); ++i) {ans = std::min(ans, cnt(i));}std::cout << ans << '\n';return true;
}