Codeforces Round 895 (Div. 3) F~G
F. Selling a Menageri
考虑如何让卖出的价格翻倍，那么自然是从 \(i \to a_i\) 。通过这样连边，我们可以发现，边集构成了基环树森林。显而易见的是，如果不考虑环，那么图就是拓扑图，按照拓扑关系跑一遍，就可以使得所有点价值最多。
现在考虑环上的问题。如果出现一个环，那么会出现循环的问题：我们从哪里开始？因为这里形成了一个简单环，那么说明这个环上需要有一个不能被满足翻倍价格，也就是让其中一个点的前驱优先实现，则此时该边在图上不存在，该基环树变成有向无环图，此时可以通过拓扑排序得到序列。
问题是我们要如何确定让哪个点不被翻倍呢？贪心的想，让环中点权值最小的点不被翻倍即可，即断开在这个环中连向这个权值最小的边断开，即可。
最后，我们只需要对处理后的图跑一遍拓扑，即可得到答案序列。
这里处理环使用了强连通分量找环，写得比较麻烦。
void Main() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (auto &item : a) {
std::cin >> item;
item --;
}
std::vector<int> vw(n);
for (auto &item : vw) {
std::cin >> item;
}
std::vector adj(n, std::vector<int>{});
for (int i = 0; i < n; i ++) {
adj[i].emplace_back(a[i]);
}
std::vector<int> dfn(n, -1), low(n, -1), scc_id(n, -1);
std::vector<std::vector<int>> scc;
int scc_cnt = 0;
std::vector<int> stk;
std::vector<bool> inst(n);
auto tarjan = [&, stamp{0}](auto &self, int from) mutable -> void {
dfn[from] = low[from] = stamp ++;
stk.emplace_back(from);
inst[from] = true;
for (auto to : adj[from]) {
if (dfn[to] == -1) {
self(self, to);
low[from] = std::min(low[from], low[to]);
} else if (inst[from]) {
low[from] = std::min(low[from], dfn[to]);
}
}
if (dfn[from] == low[from]) {
int v;
scc.emplace_back(std::vector<int>{});
do {
v = stk.back();
stk.pop_back();
inst[v] = false;
scc_id[v] = scc_cnt;
scc.back().emplace_back(v);
} while (v != from);
scc_cnt ++;
}
};
for (int i = 0; i < n; i ++) {
if (dfn[i] == -1) {
tarjan(tarjan, i);
}
}
std::vector<bool> fuk(n);
for (auto &list : scc) {
std::ranges::sort(list, std::less{}, [&](auto x) { return vw[x]; });
if (list.size() >= 2) {
fuk[list.front()] = true;
}
}
std::vector radj(n, std::vector<int>{});
std::vector<int> ind(n);
for (int i = 0; i < n; i ++) {
if (!fuk[i]) {
radj[i].emplace_back(a[i]);
ind[a[i]] ++;
}
}
std::vector<int> ans;
ans.reserve(n);
for (int i = 0; i < n; i ++) {
if (ind[i] == 0) {
ans.emplace_back(i);
}
}
for (int i = 0; i < std::min<int>(n, ans.size()); i ++) {
int from = ans[i];
for (auto to : radj[from]) {
if (-- ind[to] == 0) {
ans.emplace_back(to);
}
}
}
assert((int)ans.size() == n);
for (auto item : ans) {
std::cout << item + 1 << ' ';
}
std::cout << '\n';
}
G. Replace With Product
因为 \(1\) 与其他数相乘后的结果会使得总和减少 \(1\) ，所以我们要避免过多的 \(1\) 被处理。因此，首先我们可以将两边多余的 \(1\) 先排除掉。
排除掉之后，我们仍然无法确定中间存在的 \(1\) 是否会对答案存在影响。考虑到相乘大小膨胀非常大，因此我们可以预处理这个范围内的相乘结果，如果比和的最大结果还大，那么可以直接选择这段区域。
如果还是不能确定是不是，还是由于相乘大小增长非常大，假设剩下的大于 \(1\) 的数字都是 \(2\) ，那么其一定不会太多，否则相乘结果非常大，满足之前的结论。
因为这些零散的数字比较少，我们直接两重循环遍历求解即可。
void Main() {
int n;
std::cin >> n;
std::vector<i64> a(n);
for (auto &item : a) {
std::cin >> item;
}
if (std::ranges::count(a, 1) == n) {
std::cout << 1 << ' ' << 1 << '\n';
return;
}
int l = 0, r = n - 1;
while (a[l] == 1) {
l ++;
}
while (a[r] == 1) {
r --;
}
i64 tot = 1;
for (int i = l; i <= r; i ++) {
tot *= a[i];
if (tot > 1e9) {
std::cout << l + 1 << ' ' << r + 1 << '\n';
return;
}
}
std::vector<int> pos;
for (int i = l; i <= r; i ++) {
if (a[i] > 1)
pos.emplace_back(i);
}
tot = reduce(a.begin(), a.end());
auto pre_ret = tot;
int L = 0, R = 0;
for (int i = 0; i < pos.size(); i ++) {
i64 m = 1, s = 0;
for (int j = i; j < pos.size(); j ++) {
int l = pos[i], r = pos[j];
m *= a[r];
s += a[r] - 1;
auto ret = tot - (r - l + 1) - s + m;
if (pre_ret < ret) {
pre_ret = ret;
L = l;
R = r;
}
}
}
std::cout << L + 1 << ' ' << R + 1 << '\n';
}