反正不管作弊 我直接赛时发题解
提个建议 下次这种比赛别办了 出题人和防作弊措施都很幽默
赛时题面出锅 几百个人$wa$了几百发 过了十多分钟才改 改完过了很久才发公告
然后东拼西凑原题和板子题 几个$noi$金牌出的题就这水平是吧
$B.CF1404E$原题
题意:给出一个$n*n$的网格图,某些格子是空格,某些格子是墙,用最少的横/竖条恰好覆盖所有空格,且横/竖条之间不可有公共格子。$(n <= 50)$
考虑每个目标格子初始时独立,每删除一条两个目标格子之间的分界线会将两个连通块合并,减少一个所需木条,一个块的纵向边和横向边不能同时被删除,于是以横纵边为两部建立二分图,连边表示不可同时删除,题目转化为求二分图的最大独立集,即点数减最大匹配数,再用总的格子数减去以上结果即为答案。
$Code$
#include <iostream>
#include <cstring>
using namespace std;
const int K = 210, N = 80010, M = 480010;
const int INF = 0x3f3f3f3f;
int e[M], ne[M], h[N], f[M], idx;
int q[N], cur[N], d[N];
int n, S, T;
char g[K][K];
bool vis[N];
void insert(int u, int v, int c) {
e[idx] = v, ne[idx] = h[u], f[idx] = c, h[u] = idx++;
e[idx] = u, ne[idx] = h[v], f[idx] = 0, h[v] = idx++;
}
bool bfs() {
int tt = -1, hh = 0;
memset(d, -1, sizeof d);
q[++tt] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] == -1 && f[i]) {
d[j] = d[t] + 1;
cur[j] = h[j];
if (j == T) return true;
q[++tt] = j;
}
}
}
return false;
}
int find(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
cur[u] = i;
int j = e[i];
if (d[j] == d[u] + 1 && f[i]) {
int t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic() {
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%s", g[i] + 1);
memset(h, -1, sizeof h);
S = N - 1, T = S - 1;
int v = 0, e = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][j] != 'P') continue;
++v;
int u = (i - 1) * n + j, d = i * n + j, r = u + n * n, l = r - 1;
if (g[i - 1][j] == 'P' && !vis[u]) ++e, vis[u] = true, insert(S, u, 1);
if (g[i][j - 1] == 'P' && !vis[l]) ++e, vis[l] = true, insert(l, T, 1);
if (g[i - 1][j] == 'P') {
if (g[i][j + 1] == 'P') insert(u, r, 1);
if (g[i][j - 1] == 'P') insert(u, l, 1);
}
if (g[i + 1][j] == 'P') {
if (g[i][j + 1] == 'P') insert(d, r, 1);
if (g[i][j - 1] == 'P') insert(d, l, 1);
}
}
}
printf("%d\n", v - e + dinic());
return 0;
}
$E.KD-tree$优化$dp$
题意:有$n$个学科,第$i$个学科有耗时$a_i$和性价比$b_i$,每个学科占用时间区间为$(i-a_i,i+a_i)$,收益为$a_i*b_i$,选出一些学科使得没有学科的占用区间包含别的学科的区间中点,使得收益总和最大。$(n<=10^5)$
考虑限制条件
记 $l_i=i-a_i \;\;\;\;\;\; r_i=i+a_i$
$f_i$为考虑前$i$个学科的最大收益
有如下状态转移
$f_j=max\begin{Bmatrix}f_i+a_j*b_j\end{Bmatrix} \;\;\;\;\;\; (i<=l_j \;\; and \;\; r_i<=j)$
问题转化为加入某个带权点,查询矩形中权值最大的点,于是使用$KD-tree$优化。
$Code$
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
const int K = 2;
const double threshold = 0.75;
struct Point {
int x[K];
long long v;
};
struct Node {
int l, r;
int mn[K], mx[K];
Point p;
long long v;
int sz;
#define ls tr[x].l
#define rs tr[x].r
}tr[N];
int n;
int root, idx;
Point p[N];
int pool[N], top;
int now_k;
int a[N], b[N];
template<typename T> void chmin(T& x, T v) { if (v < x) x = v; }
template<typename T> void chmax(T& x, T v) { if (v > x) x = v; }
int new_node() { return top ? pool[top--] : ++idx; }
bool cmp(Point a, Point b) { return a.x[now_k] < b.x[now_k]; }
void dfs(int x, int cnt) {
if (!x) return;
dfs(ls, cnt);
pool[++top] = x;
p[tr[ls].sz + cnt + 1] = tr[x].p;
dfs(rs, tr[ls].sz + cnt + 1);
}
void pushup(int x) {
auto &u = tr[x], &l = tr[ls], &r = tr[rs];
u.sz = l.sz + r.sz + 1;
u.v = max(u.p.v, max(l.v, r.v));
for (int i = 0; i < K; i++) {
u.mn[i] = u.mx[i] = u.p.x[i];
if (ls) chmin(u.mn[i], l.mn[i]), chmax(u.mx[i], l.mx[i]);
if (rs) chmin(u.mn[i], r.mn[i]), chmax(u.mx[i], r.mx[i]);
}
}
int build(int l, int r, int k) {
if (l > r) return 0;
int mid = l + r >> 1;
int x = new_node();
now_k = k, nth_element(p + l, p + mid, p + r + 1, cmp);
tr[x].p = p[mid];
ls = build(l, mid - 1, (k + 1) % K);
rs = build(mid + 1, r, (k + 1) % K);
pushup(x);
return x;
}
void rebuild(int& x, int k) {
if (threshold * tr[x].sz <= (double)max(tr[ls].sz, tr[rs].sz))
dfs(x, 0), x = build(1, top, k);
}
void insert(int& x, Point p, int k) {
if (!x) {
x = new_node();
ls = rs = 0;
tr[x].p = p;
pushup(x);
return;
}
if (p.x[k] <= tr[x].p.x[k]) insert(ls, p, (k + 1) % K);
else insert(rs, p, (k + 1) % K);
pushup(x), rebuild(x, k);
}
void query(int x, int a, int b, long long& f) {
Node& u = tr[x];
if (!x || f > u.v || a < u.mn[0] || b < u.mn[1]) return;
if (a >= u.mx[0] && b >= u.mx[1]) { chmax(f, u.v); return; }
if (a >= u.p.x[0] && b >= u.p.x[1]) chmax(f, u.p.v);
query(ls, a, b, f), query(rs, a, b, f);
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
insert(root, (Point) {0, 0, 0}, 0);
long long res = 0;
for (int i = 1; i <= n; i++) {
long long tmp = 0;
int li = max(0, i - a[i]);
int ri = min(n, i + a[i]);
query(root, li, i, tmp);
tmp += 1ll * b[i] * a[i];
res = max(res, tmp);
insert(root, (Point) {i, ri, tmp}, 0);
}
cout << res << '\n';
return 0;
}
$I.$广义$SAM$
题意:给一棵树,每个点的代表字符是他的度数,问对于所有往下走的路径,本质不同子串个数。$(n<=10^5)$
直接广义$SAM$板子。
$Code$
#include <iostream>
#include <cstring>
#include <unordered_map>
#define int long long
using namespace std;
const int N = 100010;
const int mod = 1e9 + 7;
int n;
struct SAM {
struct Node {
int fa, len;
unordered_map<int, int> ch;
}node[N << 1];
int q[N];
int last = 1, tot = 1;
int pos[N];
int ch[N], fa[N];
int d[N];
int e[N << 1], ne[N << 1], h[N], idx;
SAM() {
memset(h, -1, sizeof h);
pos[0] = 1;
}
void insert(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int extend(int c, int last) {
int p = last, np = ++tot;
node[np].len = node[p].len + 1;
for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
if (!p) node[np].fa = 1;
else {
int q = node[p].ch[c];
if (node[q].len == node[p].len + 1) node[np].fa = q;
else {
int nq = ++tot;
node[nq] = node[q], node[nq].len = node[p].len + 1;
node[q].fa = node[np].fa = nq;
for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
}
}
return np;
}
void dfs(int u, int father) {
pos[u] = extend(d[u], pos[father]);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == father) continue;
dfs(j, u);
}
}
int solve() {
int res = 0;
for (int i = 2; i <= tot; i++)
res += node[i].len - node[node[i].fa].len;
return res;
}
}sam;
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
sam.insert(u, v);
sam.insert(v, u);
sam.d[u]++, sam.d[v]++;
}
sam.dfs(1, 0);
cout << sam.solve() << '\n';
return 0;
}
佬,出结果了
巨佬啊
jls A题有思路嘛
乱搞题 讲题的人说是随机化(
谢谢jiaols!
可怜了我的综测,没有早点遇到你
可以问问最短路的吗
可以搜一下分层图最短路 是板题
这题也是原题,洛谷叫飞机路线什么的
下次建议@我
下次建议@我
垃圾比赛
OrzOrz
下次建议@我
真牛逼,为什么我提前没有看到,怪不得最后5分钟排名飞掉
我居然没早点看到
tql%%%%