讲题 - Blog E

P5323 光线

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

{B=Ap1+Dq1D=Bq2C=Bp2E=Dp1+aq1\left\{ \begin{aligned} B&=Ap_1+Dq_1\cr D&=Bq_2\cr C&=Bp_2\cr E&=Dp_1+aq_1 \end{aligned} \right.⎩⎨⎧​BDCE​=Ap1​+Dq1​=Bq2​=Bp2​=Dp1​+aq1​​

{p12=CA=p1p21−q1q2q12=EA=p22q11−q1q2+q2\left\{ \begin{aligned} p_{12}&=\frac CA=\frac{p_1p_2}{1-q_1q_2}\cr q_{12}&=\frac EA=\frac{p_2^2q_1}{1-q_1q_2}+q_2 \end{aligned} \right.⎩⎨⎧​p12​q12​​=AC​=1−q1​q2​p1​p2​​=AE​=1−q1​q2​p22​q1​​+q2​​

从 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≤200n\le 200n≤200

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

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

ans=max⁡l,r,i,jmin⁡(i+j+in(l,r),f(l,i)+g(r,j))ans=\max_{l,r,i,j}\min(i+j+in(l,r),f(l,i)+g(r,j))ans=l,r,i,jmax​min(i+j+in(l,r),f(l,i)+g(r,j))

ans(x,y)=max⁡[x,y]⊂[l,r],i,jmin⁡(i+j+in(l,r),f(l,i)+g(r,j))ans(x,y)=\max_{[x,y]\subset[l,r],i,j}\min(i+j+in(l,r),f(l,i)+g(r,j))ans(x,y)=[x,y]⊂[l,r],i,jmax​min(i+j+in(l,r),f(l,i)+g(r,j))

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

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

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

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

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

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

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

复杂度爆炸，过不了。

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

相乘即为权值和：

∏(wix+1)≡(∑wi)x+1(modx2)\prod (w_ix+1)\equiv (\sum w_i)x+1 \pmod {x^2}∏(wi​x+1)≡(∑wi​)x+1(modx2)

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

(ax+b)−1=(b−a)b−2x+b−1(modx2)(ax+b)^{-1}=(b-a)b^{-2}x+b^{-1} \pmod {x^2}(ax+b)−1=(b−a)b−2x+b−1(modx2)

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

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

P5336 [THUSC2016]成绩单

n≤50,w≤1000n\le 50,w\le 1000n≤50,w≤1000

主要想 dp 状态

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

CF1637E Best Pair

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

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

n,m≤3×105,ai≤109n,m\le 3\times 10^5,a_i \le 10^9n,m≤3×105,ai​≤109

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

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

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

• 如果出现 x1>x2x_1>x_2x1​>x2​，满足 cntx1≥cntx2cnt_{x_1}\ge cnt_{x_2}cntx1​​≥cntx2​​ 那 x2x_2x2​ 必然没用

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

因此，我们只需要：

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

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

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

• 枚举右端点 y
  • 令 x←y−1x\gets y-1x←y−1
  • 不断进行直到 x=0x=0x=0：
    • 如果 (x,y)(x,y)(x,y) 是好的
      • 用 f(x,y)f(x,y)f(x,y) 更新答案
      • x←pre[x]x\gets pre[x]x←pre[x]
    • 否则
      • x←x−1x\gets x-1x←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
本文为作者原创，转载请注明出处：本文链接

阅读量 13

• Previous
  国王饮水记