讲题

P5323 光线

两个玻璃的透光率和反光率可以合并，如下列式解方程即可：

解得：

从 1 到 n 全合并起来即可。

const mod inv = (mod)1 / 100;

int main() {
    mod p1 = 1, q1;
    ll n;
    cin >> n;
    while (n--) {
        mod p2, q2, nxp, nxq;
        cin >> p2 >> q2;
        p2 *= inv, q2 *= inv;
        nxp = p1 * p2 / ((mod)1 - q1 * q2);
        nxq = p2 * p2 * q1 / ((mod)1 - q1 * q2) + q2;
        p1 = nxp, q1 = nxq;
    }
    cout << p1;
    return 0;
}

NOI 嘉年华

题意

$n\le 200$

做法

将时间离散化，$f(i,j),g(i,j)$ 分别表示第 i 个时间点前/第 i 个时间点后，第一个会场举办 j 个活动，第二个会场最多举办多少活动。预处理出一个数组 $in(l,r)$ 表示完全包含在这段时间里的活动数量，转移： \(f(i,j)\gets \max_{k<i}(f(k,j)+in(k,i),f(k,j-in(k,i)))\) g 类似。

询问的时候先枚举一个包含当前活动的时间区间，然后和左右拼接，$O(n^5)$。

预处理：

这样查询的时候就只需要枚举两维，瓶颈在预处理，$O(n^4)$

$f(l,i),g(r,j)$随着 i,j 增加单调减，因此上面的东西有决策单调性。双指针即可，复杂度 $O(n^3)$。

作业题

题意

给一个图，求出其所有生成树的边权和乘边权 gcd 之和 $n\le 30,w\le 152501$。

小贴士： 矩阵树定理可以在 $O(n^3)$ 时间内求出所有生成树树的边权乘积之和。这里的边权可以是任意数据类型，但要求这个数据类型支持加减乘除，并且符合整数的所有运算规律。

做法

显然是先枚举一个 gcd ，保留边权为 gcd 倍数的边，然后统计当前所有生成树的边权之和。随后做一个高维差分，就得到了 gcd 恰好为每个数的所有生成树边权之和。

现在问题变成了：给一个图，求出所有生成树边权之和。

暴力

枚举一条边，用矩阵树算出来有多少个生成树包含这个边（矩阵树中的边权赋为 1）。

复杂度爆炸，过不了。

智慧

矩阵树算的是边权乘积之和，我们要求的是和之和。考虑在矩阵树中，把每个边的边权用 $w_ix+1$ 替代，运算过程中对 $x^2$ 取模，最终答案的一次项系数就是边权和之和。

相乘即为权值和：

除法：在 $\mod {x^2}$ 意义下进行：

复杂度 $O(n^3w)$，依然过不了，但是每次枚举一个 gcd，判断一下当前可选边数是否大于 n-1，就可过。

最多有 $\frac{ m\max(d(w)) }{n-1}$ 个数满足条件，可以通过。

P5336 [THUSC2016]成绩单

题意

$n\le 50,w\le 1000$

主要想 dp 状态

做法

$f(l,r,vl,vr)$ 表示把区间 $[l,r]$ 删到只剩下值在 $[vl,vr]$ 的最小代价。$g(l,r)$ 表示把 $[l,r]$ 全删光的代价，枚举中点转移即可。

CF1637E Best Pair

题意

给一个长度为 n 的数组 a，定义 $cnt_x$ 为 x 这个值在 a 中的出现次数。定义函数 $f(x,y)=(cnt_x+cnt_y)(x+y)$（要求 $x < y$）。 还给出 m 个无序数对，称其为“坏数对”。

对于所有“不坏的”无序数对 $(x,y)$，求出 $f(x,y)$ 的最大值。

$n,m\le 3\times 10^5,a_i \le 10^9$

做法

我们先把 a 排个序，然后相同的一段缩成一个二元组 {值,出现个数}。

想想 m=0 咋做。想了半天，这个函数似乎没法硬维护，只能往性质方向想尤其是根号方面的。

考虑枚举一个 y，看看哪些 x 可能成为答案的：

• 如果出现 $x_1>x_2$，满足 $cnt_{x_1}\ge cnt_{x_2}$ 那 $x_2$ 必然没用

因此，所有可能成为答案的 x，都在 y-1 向左的 cnt 的单调栈上。

因此，我们只需要：

• 枚举右端点 y
  • 令 $x\gets y-1$
  • 不断进行直到 $x=0$：
    • 用 $f(x,y)$ 更新答案
    • $x\gets pre[x]$

内部每循环一次，$cnt_x$ 至少增加 1，而 $\sum cnt_i=n$，所以内部的循环最多不会跑超过 $\sqrt n$ 次，复杂度 $O(n\sqrt n)$。

而有 m 的时候，我们稍微改一下即可：

• 枚举右端点 y
  • 令 $x\gets y-1$
  • 不断进行直到 $x=0$：
    • 如果 $(x,y)$ 是好的
      • 用 $f(x,y)$ 更新答案
      • $x\gets pre[x]$
    • 否则
      • $x\gets x-1$

代码

考试的时候求前驱的部分写错了调半天没过，吐了

const char nl = '\n';
const ll MXN = 1e6 + 5;
const ll INF = 1e18;

ll n, m, arr[MXN];
char str[MXN];
vec<ll> bad[MXN];

ll v[MXN], cnt[MXN], pre[MXN];
set<pi> last;
bool ban[MXN];
int main() {
    /* freopen("test.in", "r", stdin); */
    /* freopen("test.out", "w", stdout); */
    ios::sync_with_stdio(0);
    cin.tie(0);
    setp(6);
    ll t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (ll i = 1; i <= n; i++) {
            cin >> arr[i];
            bad[i].clear();
        }
        sort(arr + 1, arr + 1 + n);
        ll ind = 0;
        for (ll i = 1; i <= n; i++) {
            if (arr[i] != arr[i - 1]) {
                ++ind;
                v[ind] = arr[i];
                cnt[ind] = 0;
            }
            ++cnt[ind];
        }
        cnt[0]=INF;
        stack<ll> stk;
        stk.push(0);
        for (ll i = 1; i <= ind; i++) {
            while(cnt[i]>=cnt[stk.top()])stk.pop();
            pre[i] = stk.top();
            stk.push(i);
            /* cout << pre[i]; */
        }
        while (m--) {
            ll x, y;
            cin >> x >> y;
            x = lower_bound(v + 1, v + 1 + ind, x) - v;
            y = lower_bound(v + 1, v + 1 + ind, y) - v;
            if (x > y) swap(x, y);
            bad[y].push_back(x);
        }
        ll ir = ind, il, ans = 0;
        while (ir) {
            if (ban[ir])
                --ir;
            else {
                for (ll nx : bad[ir]) ban[nx] = 1;
                ll il = ir - 1;
                while (il) {
                    if (ban[il])
                        --il;
                    else {
                        ans = max(ans, (cnt[il] + cnt[ir]) * (v[il] + v[ir]));
                        il = pre[il];
                    }
                }
                for (ll nx : bad[ir]) ban[nx] = 0;
                --ir;
            }
        }
        cout << ans << nl;
    }
    return 0;
}

作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接

• Previous
  国王饮水记
• Next
  博科摆