8月11日
[USACO12MAR] Haybale Restacking G
Link
思路
贪心加数学。
设 \(i\) 这块土地向左运 \(L_i\)。然后可以列出表达式。
\[A_i - L_i + L_{i + 1}=B_i \hspace{0.2cm}(for \hspace{0.2cm} 1\leq i \leq n-1)
\]
\[A_n-L_n+L_1=B_n
\]
然后按照[HAOI2008] 糖果传递推一下式子，就可以了。
代码
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5 + 5;
#define int ll
int a[N], b[N], c[N], n;
signed main() {FASTIO;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i] >> b[i];a[i] += a[i - 1], b[i] += b[i - 1];c[i] = b[i] - a[i];}sort(c + 1, c + n + 1);int k = c[(n + 1) / 2];int ans = 0;for (int i = 1; i <= n; ++i) {ans += abs(k - c[i]);}cout << ans << '\n';return 0;
}
[CSP-S2019] 树上的数
Link
挺好的贪心加性质题。并且可以由部分分推向正解。
首先考虑部分分。
Subtask 4 & 5
这里的图是菊花图。
手玩一下，发现菊花图其实就是原序列的一个轮换。
每次考虑一个值最小的点，找到最小的位置。细节比较多。
Subtask 2 & 3
这里的图是链。
发现，如果将 \(s\) 这个点移到 \(t\) 这个点，那么从 \(s\) 到 \(t\) 中间所有途径节点全部被确定，因为中间的边被断开。
对于每一次，找到 \(s\) 这个点是先断左边还是先断右边，维护即可。
正解
考虑对于每一个节点 \(s\) 找到它的边。那么它的边一定有先后断开的顺序。考虑将这些边编号。然后发现每次经过或出发或停止，都会产生一些断掉的链（不完整），所以判断能否成立，只需要判断能否形成一条完整的链。用并查集维护。
code
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 4005;
int F[N], siz[N];
int get(int x) {if (x == F[x]) return x;return F[x] = get(F[x]);
}
void merge(int x, int y) {x = get(x), y = get(y);if (siz[x] < siz[y]) swap(x, y);F[y] = x, siz[x] += siz[y];
}
int n, deg[N], ans[N], come[N], fa[N], ncnt = 1;
int num[N];
vector<pii> g[N];
int in[N], out[N], p[N];
bool flag[N], used[N];
int st[N], ed[N];
void clear(void) {ncnt = 1;for (int i = 0; i < N; ++i)g[i].clear();memset(deg, 0, sizeof deg);memset(used, 0, sizeof used);memset(st, 0, sizeof st);memset(ed, 0, sizeof ed);memset(in, 0, sizeof in);memset(out, 0, sizeof out);memset(ans, 0, sizeof ans);
}
int now;
void dfs(int u, int ff, int com) {come[u] = com;fa[u] = ff;if (!ff) {for (auto [son, id] : g[u])if (!st[u] && !in[id] && (!ed[u] || get(ed[u]) != get(id) || siz[get(ed[u])] == deg[u]))dfs(son, u, id ^ 1);return;}if (!ed[u] && !out[com] && (!st[u] || get(st[u]) != get(com) || siz[get(st[u])] == deg[u])) {flag[u] = 1;}for (auto [son, id] : g[u]) {if (son == ff) continue;if (get(id) != get(com) && !in[id] && !out[com] && id != st[u] && com != ed[u]) {if ((get(com) == get(st[u]) && get(id) == get(ed[u])) || (get(com) == get(ed[u]) && get(id) == get(st[u]))) {if (siz[get(st[u])] + siz[get(ed[u])] != deg[u]) continue;}dfs(son, u, id ^ 1);}}
}
void solve(void) {clear();cin >> n;for (int i = 1; i <= n; ++i)cin >> p[i];for (int i = 1; i < n; ++i) {int u, v; cin >> u >> v;g[u].emplace_back(v, ++ncnt);F[ncnt] = ncnt, siz[ncnt] = 1;g[v].emplace_back(u, ++ncnt);F[ncnt] = ncnt, siz[ncnt] = 1;deg[u]++, deg[v]++;}// st[3] = 5;for (int i = 1; i <= n; ++i)reverse(g[i].begin(), g[i].end());for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j)flag[j] = 0;now = p[i];dfs(p[i], 0, 0);for (int j = 1; j <= n; ++j) {if (j != p[i] && !used[j] && flag[j]) {ans[i] = j, ed[j] = come[j], used[j] = 1;int las = come[j] ^ 1;int u = fa[j];while (u != p[i]) {merge(come[u], las);++out[come[u]], ++in[las];las = come[u] ^ 1, u = fa[u];}// if (i == 1) cout << st[p[i]] << "----------------" << las << '\n';st[p[i]] = las;// if (i == 1) cout << st[p[i]] << "----------------" << las << '\n';// if (i == 1) cout << st[p[i]] << "-------------" << las << '\n';break;}}}for (int i = 1; i <= n; ++i) {cout << ans[i] << ' ';}cout << '\n';
}
int main() {// FASTIO;int t;cin >> t;while (t--)solve();return 0;
}