Tsukkomi

A 忘开 long long WA 一发,数组开小了 TLE 一发 qwq
B 又忘开 long longWA 一发 他忘开 long long 一直可以的 qwq
C, D 直接不会,总得来说这场打得很僵硬 orz

Read More »

Description

f(n,k)=a1=2na2=2nak=2n[i=1kai=n]f\left(n,k\right)=\sum_{a_1=2}^n\sum_{a_2=2}^n\dots\sum_{a_k=2}^n\left[\prod_{i=1}^ka_i=n\right]

给定 n,kn,k (1n230, 1k30)\left(1\leq n\leq2^{30},\ 1\leq k\leq30\right) ,求

ans=(i=1nf(i,k))mod(109+7)ans=\left(\sum\limits_{i=1}^nf\left(i,k\right)\right)\bmod\left(10^9+7\right)

HDU 上为多组测试。

Read More »

Description

给定长度为 nn (1n7.1×103)\left(1\leq n\leq7.1\times10^3\right) 的序列 aa (1ai109)\left(1\leq a_i\leq10^9\right) .
有一未知整数 x[1,n]x\in\left[1,n\right] ,判断 xx 是否大于 ii 的代价为 aia_i .
现保证序列 aa 单调不降,求能确保求出 xx 所需的最小代价。
TT (1T5×102)\left(1\leq T\leq5\times10^2\right) 组测试,保证 n7.1×103\sum n\leq7.1\times10^3 .

Read More »

Description

给定长度为 2n2^n (1n16)\left(1\leq n\leq16\right) 的序列 aa (0ai2321)\left(0\leq a_i\leq2^{32}-1\right) ,下标从 00 开始。
给定 qq (1q2×105)\left(1\leq q\leq2\times10^5\right) 次操作,操作分两种:

  • (1,l,r,k)\left(1,l,r,k\right) (0l,r2n1, 0k2321)\left(0\leq l,r\leq2^n-1,\ 0\leq k\leq2^{32}-1\right) .
    表示对所有 i[0,2n), l&i=l, i&r=ii\in\left[0,2^n\right),\ l\&i=l,\ i\&r=i ,令 ai=ai+ka_i=a_i+k .

  • (2,l,r)\left(2,l,r\right) (0l,r2n1)\left(0\leq l,r\leq2^n-1\right) ,表示求

    ansl,r=(l&i=l, i&r=iai)mod232ans_{l,r}=\left(\sum_{l\&i=l,\ i\&r=i}a_i\right)\bmod2^{32}

Read More »

Tutorial

阅读本文前应熟悉容量网络求 最大流增广路算法
具体可参考 Maximum Flow Minimum Cut 的相关内容。

Minimum Cost Maximum Flow ,即 最小费用最大流 ,又称 费用流
它指的是 带费用的 容量网络上 总花费最小 的最大流。
下面将给出前置知识并介绍求费用流的算法,附板子题。

Read More »

Tutorial

阅读本文前应熟悉 网络流基础 ,具体可参考 Network Flow .

Maximum Flow Minimum Cut ,即 最大流最小割
容量网络的 最大流最小割 是网络流问题中常见的研究对象。
两者的关系由 Max-Flow Min-Cut Theorem ,即 最大流最小割定理 指出。
求最大流的算法包括 EK , Dinic , ISAPHLPP 等。
下面将给出前置知识并分别介绍上述的 Theorem 和算法,附板子题。

Read More »