|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
总结与反思
D - 遇到必须经过小于 w 的边之类问题想到 kruskal 重构树, dsu 预处理每个点的答案
A - 括号翻转
给定给一个字符串,其中含有很多括号,括号里的内容会被翻转,输出这个字符串去掉括号的结果。
没啥好说的...#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
string s;
int L[N], R[N], n;
stack<int> stk;
void dfs(int l, int r, int rev) {
if (l > r)
return;
if (rev) {
for (int i = r; i >= l; i--) {
if (s[i] != '(' && s[i] != ')')
cout << s[i];
else
dfs(L[i] + 1, i - 1, rev ^ 1), i = L[i];
}
} else {
for (int i = l; i <= r; i++) {
if (s[i] != '(' && s[i] != ')')
cout << s[i];
else
dfs(i + 1, R[i] - 1, rev ^ 1), i = R[i];
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("bracket.in", "r", stdin);
freopen("bracket.out", "w", stdout);
cin >> s;
n = s.size();
s = '-' + s;
for (int i = 1; i <= n; i++) {
if (s[i] == '(')
stk.push(i);
if (s[i] == ')') {
int x = stk.top();
stk.pop();
R[x] = i, L[i] = x;
}
}
dfs(1, n, 0);
return 0;
}
B - 香蕉
在一个树上给出 a, b, c, d, 问 a, b 和 c, d 之间的路径是否有相交
考试时候无脑线段树, 其实有很简单的做法, 画画图找出性质for (int i = 1; i <= m; i++) {
int u, v, x, y;
cin >> u >> v >> x >> y;
int S = getlca(u, v), T = getlca(x, y);
if (dep[S] < dep[T]) {
swap(S, T), swap(u, x), swap(v, y);
}
if (getlca(S, x) == S || getlca(S, y) == S)
cout << "YES\n";
else
cout << "NO\n";
}
C - 排列盒子
原题可以转化,构造一个排列,设定一个大小关系,使得逆序对的数量最小。
发现总颜色数很小, 考虑状压安排顺序
考试的时候没有搞出来预处理逆序对, tle 了, 可惜啊#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 20;
// cnt[i][j] 表示 i 优先于 j 产生的逆序对个数
ll cnt[M][M], sum[M];
int n, k;
ll f[(1 << M)];
ll Cost(int x, int st) {
ll res = 0;
for (int i = 0; i < k; i++) {
if ((st >> i) & 1)
continue;
// x 优先于 i
res += cnt[x][i];
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("box.in", "r", stdin);
freopen("box.out", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
x--;
for (int j = 0; j < k; j++) {
if (j == x)
continue;
// 假设 x 优先于 j, 那 x 前面的 j 的个数就是贡献
cnt[x][j] += sum[j];
}
sum[x]++;
}
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for (int st = 0; st < (1 << k); st++) {
for (int i = 0; i < k; i++) {
if ((st >> i) & 1)
continue;
f[st | (1 << i)] = min(f[st | (1 << i)], f[st] + Cost(i, st | (1 << i)));
}
}
cout << f[(1 << k) - 1];
return 0;
}
乱搞做法, 直接取最小值安排顺序, 但是有可能成环
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
for (int j = 1; j <= k; j++) {
if (x != j) {
p[x][j] += sum[j];
}
}
sum[x]++;
}
for (int i = 1; i <= k; i++) {
for (int j = i + 1; j <= k; j++) {
ans += min(p[i][j], p[j][i]);
}
}
}
D - 花园
Mr. Panda 有 N 个花园,编号从 1 到 N 。对于编号为 i 的花园,花园里只有一朵花,颜色为 。花园与花园之间有道路连接(道路是双向的)。每条道路都有一个花费,表示经过该道路花费的时间。
Mr. Panda 喜欢在他的N个花园中转悠,然后采尽可能多的同种颜色的花
然而,有时候他并不想花太多时间走同一段路
现在问题来了,每一次 Mr. Panda 会告诉你:他从哪个花园开始出发和他能忍受的走同一段路的花费的最大值w(也就是说,只有费用不超过w的道路可以通行)
请你判断Mr. Panda最多能采到的花是哪种颜色的花。如果有多种颜色符合条件,选择颜色编号最小的输出
这种的关于路径最大值最小要想最小生成树, 进而想到 kruskal 重构树
那么 lca 就是边权最大值, 每次询问在 lca 的子树内就是活动范围
那么怎么知道答案? 时间太大, 只能看看能不能提前全出来, 那就用 dsu 吧#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int K = 3e5 + 5;
// 和最大边权最小有关, 考虑 kruskal 重构树
// 建出来之后对于 u, 她的活动范围就是最大的权值不超过 w 的点的子树
// 然后就是询问区间众数, 这里用树上启发式合并来做, 求出每个点所在子树的答案, 也可以用线段树合并
// Global
int n, m, type, c[N];
// Kruskal tree
vector<int> e[M];
int val[M];
struct Kru {
int u, v, w;
} edges[K];
struct DSU {
int f[M], tot;
void Init() {
iota(f, f + M, 0);
tot = n;
}
int Find(int x) {
if (x == f[x])
return x;
return (f[x] = Find(f[x]));
}
int Merge(int x, int y) {
x = Find(x), y = Find(y);
if (x == y)
return 0;
tot++;
f[x] = tot, f[y] = tot;
e[tot].emplace_back(x);
e[tot].emplace_back(y);
return tot;
}
} dsu;
void Kruskal() {
dsu.Init();
val[0] = 1e9;
sort(edges + 1, edges + m + 1, [](Kru& a, Kru& b) { return a.w < b.w; });
for (int i = 1; i <= m; i++) {
int cur = dsu.Merge(edges[i].u, edges[i].v);
if (cur)
val[cur] = edges[i].w;
}
}
// DSU on tree
int cnt[M], tot, ans[M], mxid, mxap;
int f[M][18], hc[M], dfn[M], rdfn[M], siz[M];
void dfs0(int u, int pa) {
f[u][0] = pa;
siz[u] = 1;
dfn[u] = ++tot;
rdfn[tot] = u;
for (int i = 1; i < 18; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (auto ed : e[u]) {
if (ed == pa)
continue;
dfs0(ed, u);
siz[u] += siz[ed];
if (siz[hc[u]] < siz[ed])
hc[u] = ed;
}
}
void Modify(int col) {
cnt[col]++;
if (cnt[col] == mxap) {
mxid = min(mxid, col);
} else if (cnt[col] > mxap) {
mxap = cnt[col];
mxid = col;
}
}
void Add(int u) {
for (int i = dfn[u]; i < dfn[u] + siz[u]; i++) {
if (rdfn[i] > n)
continue;
Modify(c[rdfn[i]]);
}
}
void Del(int u) {
mxap = 0, mxid = 1e9;
for (int i = dfn[u]; i < dfn[u] + siz[u]; i++) {
if (rdfn[i] <= n)
cnt[c[rdfn[i]]] = 0;
}
}
void Solve(int u, int pa, bool keep) {
for (auto ed : e[u]) {
if (ed == pa || ed == hc[u])
continue;
Solve(ed, u, 0);
}
if (hc[u])
Solve(hc[u], u, 1);
for (auto ed : e[u]) {
if (ed == pa || ed == hc[u])
continue;
Add(ed);
}
if (u <= n)
Modify(c[u]);
ans[u] = mxid;
if (keep)
return;
Del(u);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("garden.in", "r", stdin);
freopen("garden.out", "w", stdout);
cin >> n >> m >> type;
for (int i = 1; i <= n; i++) {
cin >> c[i];
}
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges[i] = { u, v, w };
}
Kruskal();
for (int i = dsu.tot; i; i--) {
if (!dfn[i]) {
dfs0(i, 0);
Solve(i, 0, 0);
}
}
int last = 0, q;
cin >> q;
while (q--) {
int x, w;
cin >> x >> w;
if (type) {
x ^= last;
w ^= last;
}
for (int i = 17; i >= 0; i--) {
if (val[f[x][i]] <= w)
x = f[x][i];
}
last = ans[x];
cout << ans[x] << '\n';
}
return 0;
}
|
|