2024 年 7 月做题笔记
写在之前
算是开始归队了吧。感觉过去一年里文化课水平突飞猛进(飞升b(x)),算是找到了一点新的方向。
附上一张今天现拍的照片(x
访问这里
(图片背景经过处理)
因为 0727 才放假所以没做几个题(
(2024/7/28)「SNOI2017」炸弹
这道题第一眼看过去会想到一个暴力做法。建图,然后跑一堆 dfs 什么的。但是很明显时间复杂度是不行的(O(n^2) + O(n^2) \Rightarrow O(n^2)),于是想怎么优化。
根据我之前写过的 线段树优化建图,因为本题目涉及到 从点连向区间 的情况,那么可以使用这个优化技巧。之后你会发现,一个炸弹炸出来的所有点不正好是一个区间嘛(到这里其实跟「CEOI 2011」Traffic 的后面有点像,但是这里区间性质要更好想一点)!因此思路便明了了:线段树建图,然后跑 Tarjan 算 SCC 然后缩点,跑一遍拓扑,维护区间的左端点和右端点。
写过线段树优化建图的可能思维难度会低很多。
// 线段树最大节点编号
int ND_MX = 0;
// 节点 [p, p] 对应图上的点编号
int nd[4 * MAXN];
// 图和反图
vector<int> gr[4 * MAXN], reg[4 * MAXN];
inline void add_edge(int u, int v) { gr[u].push_back(v); }
struct Segt { int l, r; } tr[4 * MAXN];
struct Bomb { ll pos, rad; } bmb[MAXN];
struct Range { int l, r; /* 这里实现了一个 extend 方法 */ void extend(const Range& rhs) { l = min(l, rhs.l); r = max(r, rhs.r); } } vs[4 * MAXN];
struct Cmp { ll a, id; bool operator<(const Cmp& o) const { return a < o.a; } };
namespace SGraph {
void build(int l, int r, int p = 1)
{
tr[p].l = l; tr[p].r = r;
ND_MX = max(ND_MX, p);
if (l == r) return nd[l] = p, void();
int m = (l + r) / 2;
build(l, m, p << 1), build(m + 1, r, p << 1 | 1);
add_edge(p, p << 1), add_edge(p, p << 1 | 1);
}
void connect_from_range(int from, int l, int r, int p = 1)
{
if (tr[p].l > r || tr[p].r < l) return;
if (l <= tr[p].l && tr[p].r <= r) return add_edge(nd[from], p);
connect_from_range(from, l, r, p << 1);
connect_from_range(from, l, r, p << 1 | 1);
}
} // namespace Graph
namespace Tarjan {
int dfn[MAXN * 4], low[MAXN * 4], cnt, ins[MAXN * 4], scc[MAXN * 4], scccnt;
stack<int> st;
void dfs(int u)
{
low[u] = dfn[u] = ++cnt; ins[u] = 1; st.push(u);
for (auto v : gr[u]) {
if (!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
else if (ins[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++scccnt; int v;
do {
v = st.top(); st.pop(); ins[v] = 0; scc[v] = scccnt;
if (vs[scccnt].l == 0) {
// v: 线段树区间对应的点
vs[scccnt] = { tr[v].l, tr[v].r };
} else {
vs[scccnt].extend({ tr[v].l, tr[v].r });
}
} while (v != u);
}
}
} // namespace Tarjan
int n;
using Tarjan::scc;
namespace Topo {
queue<int> q;
int deg[4 * MAXN];
using Tarjan::scccnt;
inline void exec()
{
for (int i = 1; i <= scccnt; i++) {
if (!deg[i]) q.push(i);
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto v : reg[u]) {
vs[v].extend(vs[u]);
if (!--deg[v]) q.push(v);
}
}
}
} // namespace Topo
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n; SGraph::build(1, n);
// 按理说这个地方应该开一个数组然后排序 但是我没有
set<Cmp> st;
for (int i = 1; i <= n; i++) {
ll pos, rad; cin >> pos >> rad;
st.insert({ pos, i });
bmb[i] = { pos, rad };
}
for (int i = 1; i <= n; i++) {
ll pos = bmb[i].pos, rad = bmb[i].rad;
// 分成左半和右半区间 这样可以少考虑一点边界
auto lower = st.lower_bound({ pos - rad });
auto upper = --st.upper_bound({ pos + rad });
if (lower != st.end() && lower->id < i) SGraph::connect_from_range(i, lower->id, i - 1);
if (upper != st.end() && upper->id > i) SGraph::connect_from_range(i, i + 1, upper->id);
}
for (int i = 1; i <= ND_MX; i++) if (!Tarjan::dfn[i]) Tarjan::dfs(i);
// 缩点(直接建反向边)
for (int u = 1; u <= ND_MX; u++) {
for (auto v : gr[u]) {
if (scc[u] != scc[v]) {
reg[scc[v]].push_back(scc[u]);
Topo::deg[scc[u]]++;
}
}
}
// 拓扑!
Topo::exec();
// 答案!
ll ans = 0;
const ll MODN = 1e9 + 7;
for (int i = 1; i <= n; i++) {
Range& res = vs[scc[nd[i]]];
(ans += 1ll * i * (res.r - res.l + 1)) %= MODN;
}
cout << ans << '\n';
}
(2024/7/28)「CF1991B」AND Reconstruction
题意:给你 n-1 个数字 b_i,让你构造一个有 n 个元素的序列 a 使得每个 a_i \& a_{i+1}=b_i(& = 按位与),构造不了输出 -1
。
那么我们可以把这个问题拆分一下,看一看每个数字的每一位是一个什么情况。不难发现,b_i 的第 j 位为 1 的充要条件是 a_i 和 a_{i+1} 的第 j 位都为 1。所以,把 a_i、a_{i+1} 的对应位数设置成 1,最后判断是否可以满足条件即可。
inline void solve()
{
int n; cin >> n;
vector<int> b(n - 1), a; for (auto& x : b) cin >> x;
const int FULL = (1 << 30) - 1;
vector<bitset<30>> bs(n);
for (int j = 0; j < 30; j++) {
for (int i = 0; i < n - 1; i++) {
if (b[i] & (1 << j)) {
bs[i][j] = 1;
bs[i + 1][j] = 1;
}
}
}
// check
for (int i = 1; i < n; i++) {
if ((bs[i].to_ulong() & bs[i - 1].to_ulong()) != b[i - 1]) {
cout << "-1\n";
return;
}
}
for (int i = 0; i < n; i++) cout << bs[i].to_ulong() << ' ';
cout << '\n';
}