没想到官方题解的线性做法，所以这里提供一个比较困难的 ds 做法。直接做比较困难，考虑直接维护序列的平均攻击力。初始时平均攻击力为 ，这里将其写作非化简分数的形式即 。
然后考虑每个操作对答案的贡献：
- 卡牌选择：可以看作是分子和分母同时加 （后面简记为 操作）。
- 神秘石头：可以看做是分母减 （后面简记为 操作）。
但是你需要时刻保持分母不为 。
特判掉无解的情况。此时 exchange argument 一下，发现在保持任意时刻分母不为 的前提下，先进行 操作再进行 操作，和调换她们的顺序效果相同。于是容易想到反悔贪心，初始的时候全部设为进行 操作，然后对于每一个 分叉路，若当前时刻分母的前缀 的最小值 则根据上面 ea 出的结论，直接将其修改为进行 操作， 后缀内所有分母的前缀 均增加 ，否则前缀 不变。
直接模拟过程时间复杂度为 ，用线段树等 ds 优化可以做到 解决。
// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
const int N = 1000010;
const int inf = 1e18;
const int mod = 998244353;
int a[N], pre[N];
struct Node
{
int l, r, mi, tag;
inline void init(int p) { l = r = p, mi = pre[p], tag = 0; }
inline void push(int x) { mi += x, tag += x; }
} tree[N << 2]; inline Node operator+(const Node &l, const Node &r)
{
return {l.l, r.r, min(l.mi, r.mi), 0};
} inline void build(int l, int r, int rt)
{
if (l == r)
return tree[rt].init(l);
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
inline void pushdown(int rt)
{
if (tree[rt].tag)
{
tree[rt << 1].push(tree[rt].tag);
tree[rt << 1 | 1].push(tree[rt].tag);
tree[rt].tag = 0;
}
}
inline void modify(int rt, int ll, int rr, int v)
{
int &l = tree[rt].l, &r = tree[rt].r;
if (ll <= l && r <= rr)
return tree[rt].push(v);
int mid = l + r >> 1;
pushdown(rt);
if (ll <= mid)
modify(rt << 1, ll, rr, v);
if (mid < rr)
modify(rt << 1 | 1, ll, rr, v);
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
inline int qry(int rt, int ll, int rr)
{
int &l = tree[rt].l, &r = tree[rt].r;
if (ll <= l && r <= rr)
return tree[rt].mi;
int mid = l + r >> 1, res = inf;
pushdown(rt);
if (ll <= mid)
res = qry(rt << 1, ll, rr);
if (mid < rr)
res = min(res, qry(rt << 1 | 1, ll, rr));
return res;
}
signed main()
{
cin.tie(0)->sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
vector<int> v;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
if (!a[i])
a[i] = -1, v.emplace_back(i);
}
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + a[i];
build(1, n, 1);
for (int &i : v)
if (tree[1].mi < 0)
modify(1, i, n, 2), a[i] = 1;
int p = 1, q = 1;
if (tree[1].mi < 0)
{
cout << -1 << '\n';
continue;
}
for (int i = 1; i <= n; ++i)
if (a[i] == 1)
++p, ++q;
else
--q;
int g = gcd(p, q);
p /= g, q /= g;
cout << p << ' ' << q << '\n';
}
return 0;
}
喜欢的话，留下你的评论吧～