[ABC348] Atcoder ABC 248 A~G 题解
A
模拟
B
模拟，不卡精度。
C
模拟
D
注意，药不可以拿着，只可以在那个格子吃掉。
这就意味着，我们无论何时到达某个点，到达的点的集合都是固定的。
所以对于每个药店跑 BFS，然后看起点到终点是否连通即可。
int n, m, k, ad[N][N], f[N][N], in[N][N], tox[N], toy[N];
int tx, ty, sx, sy;
char g[N][N];
bool st[N][N];
bool check(int x, int y) {
return x > 0 && y > 0 && x <= n && y <= m && g[x][y] != '#';
}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
vector<int> G[N];
void add(int a, int b) {
if(a ^ b) G[a].push_back(b);
}
void dfs(int rt, int i, int j, int d) {
queue<pair<int, int> > q;
memset(st, 0, sizeof st);
memset(f, 0x3f, sizeof f);
f[i][j] = 0, q.push({i, j});
while(q.size()) {
auto [x, y] = q.front(); q.pop();
if(st[x][y]) continue;
st[x][y] = 1;
for(int k = 0; k < 4; k ++) {
int xx = x + dx[k], yy = y + dy[k];
if(!check(xx, yy)) continue;
if(f[xx][yy] > f[x][y] + 1) {
f[xx][yy] = f[x][y] + 1;
q.push({xx, yy});
}
}
}
for(int i = 1; i <= k; i ++)
if(f[tox[i]][toy[i]] <= d)
add(rt, i);
if(f[tx][ty] <= d) add(rt, k + 1);
}
bool find(int u) {
if(st[0][u]) return 0; st[0][u] = 1;
if(u == k + 1) return 1;
for(auto v : G[u])
if(find(v)) return 1;
return 0;
}
void work() {
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
cin >> g[i][j];
cin >> k;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++) {
if(g[i][j] == 'S') sx = i, sy = j;
else if(g[i][j] == 'T') tx = i, ty = j;
}
for(int i = 1; i <= k; i ++) {
int x, y, d;
cin >> x >> y >> d;
ad[x][y] = d, in[x][y] = i;
tox[i] = x, toy[i] = y;
}
if(!ad[sx][sy]) {
cout << "No\n";
return ;
}
for(int i = 1; i <= k; i ++)
dfs(i, tox[i], toy[i], ad[tox[i]][toy[i]]);
memset(st, 0, sizeof st);
if(find(in[sx][sy])) cout << "Yes\n";
else cout << "No\n";
}
E
【模板】换根 DP。
卡 ans = 1e18。
F
暴力题。
考虑 \(f_{i, j, k}\) 表示前 \(i\) 列，第 \(i\) 行与第 \(j\) 行是否合法。
转移即为：
\[f_{i, a, b}\to f_{i + 1, a, b}\oplus [g_{i, a} = g_{i, b}] \]这个很 bitset，所以用 bitset 维护每一列的颜色情况，然后滚掉一维即可通过。
bitset<N> f[N], c[1000][N];
int n, m, a[N][N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) cin >> a[i][j], c[a[i][j]][j][i] = 1;
for(int i = 1; i <= m; i ++)
for(int j = 1; j <= n; j ++)
f[j] = f[j] ^ c[a[j][i]][i];
int ans = 0;
for(int i = 1; i <= n; i ++)
ans += f[i].count() - f[i][i];
cout << ans / 2 << '\n';
return 0;
}
G
喵喵题，可惜也是重题。
如果只有一个 \(k\)，可以固定 \(\max\) 然后就是一个查询 \(b_i\le \max\) 的前 \(k\) 大数和，明显可以主席树+线段树二分搞（好像有更简单的解法，等其他大佬的题解）。
观察到决策单调性：
对于选 \(k\) 个元素，设 \(f(k, i)\) 表示选 \(k\) 个，\(\max = i\) 时的答案，\(g(k)\) 表示选 \(k\) 个的最佳决策点。
我们有 \(i < j\wedge f(k, i)\le f(k, j) \Longrightarrow f(k+ \Delta, i)\le f(k+ \Delta, j), \Delta\ge 0\)，这是因为 \(i < j\)，所以 \(j\) 选择的位置包含了 \(i\) 可选的位置，所以合法的增加选的个数之后，\(j\) 一定可以选 \(i\) 选的，甚至可以选比它更优的位置。
所以决策单调性分治即可解决问题。
需要注意离散化。
时间复杂度：\(O(n\log^2n)\)。
int n, f[N], disc[N], tot;
int find(int x) {
return lower_bound(disc + 1, disc + tot + 1, x) - disc;
}
struct qwq {
int a, b;
bool operator < (const qwq &W) const {
return b < W.b;
}
} p[N];
int dat[M], ls[M], rs[M], cnt[M], idx, root[N];
#define mid (l + r >> 1)
int update(int q, int l, int r, int x, int v) {
int p = ++ idx;
ls[p] = ls[q], rs[p] = rs[q], cnt[p] = cnt[q] + 1, dat[p] = dat[q] + v;
if(l == r) return p;
if(x <= mid) ls[p] = update(ls[q], l, mid, x, v);
else rs[p] = update(rs[q], mid + 1, r, x, v);
return p;
}
int query(int q, int l, int r, int k) {
if(l == r) return disc[l] * k;
if(cnt[rs[q]] < k) return query(ls[q], l, mid, k - cnt[rs[q]]) + dat[rs[q]];
return query(rs[q], mid + 1, r, k);
}
#undef mid
int g[N];
void solve(int l, int r, int ql, int qr) {
if(l > r || ql > qr) return ;
int mid = ql + qr >> 1, mid2 = -1, mx = -9e18;
// find best point for mid
for(int i = max(mid, l), t; i <= r; i ++) {
t = query(root[i], 1, tot, mid) - p[i].b;
if(t > mx) mx = t, mid2 = i;
}
f[mid] = mx;
solve(l, mid2, ql, mid - 1);
solve(mid2, r, mid + 1, qr);
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) cin >> p[i].a >> p[i].b, disc[++ tot] = p[i].a;
sort(p + 1, p + n + 1);
sort(disc + 1, disc + tot + 1);
tot = unique(disc + 1, disc + tot + 1) - disc;
for(int i = 1; i <= n; i ++)
root[i] = update(root[i - 1], 1, tot, find(p[i].a), p[i].a);
solve(1, n, 1, n);
for(int i = 1; i <= n; i ++) cout << f[i] << '\n';
return 0;
}
总结
爆了，卡 D 了，看错题了，非常尴尬。
F 想到做法了但是没敢写。
标签：ABC,return,int,题解,mid,tot,xx,disc,ABC348 From： https://www.cnblogs.com/MoyouSayuki/p/18125032