首页 > 其他分享 >Solution Set 2023.12.12

Solution Set 2023.12.12

时间:2023-12-12 20:34:01浏览次数:37  
标签:std Set limits min 2023.12 sum 12 right valueType

ABC332G Not Too Many Balls

可以转化为最大流模型,设节点 \(x_i\) 代表第 \(i\) 种球,\(y_j\) 代表第 \(j\) 个盒子。考虑如下建边方案:

  • \(S \rightarrow x_i\),容量为 \(A_i\)
  • \(x_i \rightarrow y_j\),容量为 \(i \times k\)
  • \(y_j \rightarrow T\),容量为 \(B_j\)

可以发现该网络的最大流即为答案,但是由于边数是 \(\mathcal{O}(NM)\) 级别的,直接求最大流会超时。根据最大流最小割定理,若我们可以求出该网络的最小割,那么我们也可以获得答案,下面考虑如何求出最小割。

首先考虑如何表示出最小割的值,设点集 \(X = \left\{x_1, x_2, \cdots, x_N\right\}, Y = \left\{x_1, x_2, \cdots, x_N\right\}\),\(P\) 表示最小割方案中 \(X\) 中与 \(S\) 在同一连通块内的点集,\(Q\) 表示最小割方案中 \(Y\) 中与 \(S\) 在同一连通块内的点集。那么考虑三条边中都有哪些边被割掉,可以得出最小割的表达式:

\[\begin{aligned} \mathbf{mincut} &= \min\limits_{P \subseteq X} \min\limits_{Q \subseteq Y} \left(\sum\limits_{x_i \in X \setminus P} A_i + \sum\limits_{x_i \in P}\sum\limits_{y_j \in Y \setminus Q} i \times j + \sum\limits_{y_j \in Q} B_j\right) \end{aligned}\]

设 \(k = \sum\limits_{x_i \in P} i, L = \dfrac{N\left(N + 1\right)}{2}\),通过枚举 \(x\) 的值,我们有:

\[\begin{aligned} \mathbf{mincut} &= \min\limits_{0 \le k \le L} \min\limits_{P \subseteq X \land \sum\limits_{x_i \in P} i = k}\min\limits_{Q \subseteq Y} \left(\sum\limits_{x_i \in X \setminus P} A_i + \sum\limits_{x_i \in P}\sum\limits_{y_j \in Y \setminus Q} i \times j + \sum\limits_{y_j \in Q} B_j\right)\\ &= \min\limits_{0 \le k \le L} \min\limits_{P \subseteq X \land \sum\limits_{x_i \in P} i = k}\min\limits_{Q \subseteq Y} \left(\sum\limits_{x_i \in X \setminus P} A_i + \sum\limits_{y_j \in Y \setminus Q} k \times j + \sum\limits_{y_j \in Q} B_j\right) \\ &= \min\limits_{0 \le k \le L} \min\limits_{P \subseteq X \land \sum\limits_{x_i \in P} i = k}\left(\sum\limits_{x_i \in X \setminus P} A_i + \sum\limits_{y_j \in Y} \min\left\{k \times j, B_j\right\}\right) \end{aligned}\]

其中最后一步转化是因为 \(Y\) 中的每个节点要么属于 \(Q\),要么属于 \(Y \setminus Q\),也就是其会产生 \(k \times j\) 或 \(B_j\) 的贡献,故可以直接取最小值。

对于上式的前半部分,即 \(f_k = \min\limits_{P \subseteq X \land \sum\limits_{x_i \in P} i = k}\sum\limits_{x_i \in X \setminus P} A_i\)。我们可以使用 \(\tt{01}\) 背包在 \(\mathcal{O}(NL)\) 的时间内求出对于 \(0 \le k \le L\) 的所有 \(f_k\) 的值。

对于上式的后半部分,即 \(g_k = \sum\limits_{y_j \in Y} \min\left\{k \times j, B_j\right\}\)。可以发现当 \(k = 0\) 时,所有的节点均会从 \(k \times j\) 来产生贡献,而由于 \(k \times j\) 随 \(k\) 的增长而单调递增,因此对于所有满足 \(y_j \in Y\) 的 \(j\),均存在一个 \(k_0\) 使得当 \(k \ge k_0\) 时,其会产生 \(B_j\) 而不是 \(k \times j\) 的贡献,所以有 \(\forall k \ge k_0, B_j \le k \times j\),解得 \(k_0 = \dfrac{B_j}{j}\)。因此我们对于每个 \(j\) 求出出其对应的 \(k_0\) 后遍历 \(0 \le k \le L\) 并求出 \(g_k\) 即可。

最终答案即为 \(\min\limits_{0 \le k \le L} f_k + g_{L - k}\)。复杂度为 \(\mathcal{O}(N^3 + M)\)。

Code
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;

constexpr valueType INF = std::numeric_limits<valueType>::max() >> 3;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    valueType const S = N * (N + 1) / 2;

    ValueVector A(N + 1), B(M + 1);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    for (valueType i = 1; i <= M; ++i)
        std::cin >> B[i];

    ValueVector F(S + 1, INF);

    F[0] = 0;

    for (valueType i = 1; i <= N; ++i) {
        for (valueType j = S; j >= i; --j)
            F[j] = std::min(F[j], F[j - i] + A[i]);
    }

    ValueVector G(S + 1, 0);

    ValueMatrix H(S + 1);

    for (valueType i = 1; i <= M; ++i) {
        valueType const pos = B[i] / i;

        if (pos <= S)
            H[pos].emplace_back(i);
    }

    {
        valueType indexSum = M * (M + 1) / 2, valueSum = 0;

        for (valueType i = 0; i <= S; ++i) {
            G[i] += i * indexSum + valueSum;

            for (auto const &iter : H[i]) {
                indexSum -= iter;

                valueSum += B[iter];
            }
        }
    }

    valueType ans = INF;

    for (valueType i = 0; i <= S; ++i)
        ans = std::min(ans, F[i] + G[S - i]);

    std::cout << ans << std::endl;

    return 0;
}

ARC125E Snack

ABC332G Not Too Many Balls,我们可以将其转化为最大流模型后求其最小割,化简后的最小割表达式为:

\[\min\limits_{P \subseteq X} \min\limits_{Q \subseteq Y} \left(\sum\limits_{x_i \in X \setminus P} A_i + \sum\limits_{y_j \in Y} \min\left\{\left\lvert P \right\rvert \times B_j, C_j\right\}\right) \]

求 \(f_k = \min\limits_{P \subseteq X \land \left\lvert P \right\rvert = k} \sum\limits_{x_i \in X \setminus P} A_i\) 是平凡的,将 \(A\) 序列排序后做前缀和即可。

对于 \(g_k = \sum\limits_{y_j \in Y} \min\left\{k \times B_j, C_j\right\}\) 同 ABC332G Not Too Many Balls,可以得出 \(k_0 = \dfrac{C_j}{B_j}\)。

复杂度为 \(\mathcal{O}(N \log N + M)\)。

Code
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;

constexpr valueType INF = std::numeric_limits<valueType>::max() >> 3;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    ValueVector A(N + 1, 0), B(M + 1, 0), C(M + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    for (valueType i = 1; i <= M; ++i)
        std::cin >> B[i];

    for (valueType i = 1; i <= M; ++i)
        std::cin >> C[i];

    ValueVector F = A;

    std::sort(F.begin(), F.end());
    std::partial_sum(F.begin(), F.end(), F.begin());

    ValueVector G(N + 1, 0);
    ValueMatrix bucket(N + 1);

    for (valueType i = 1; i <= M; ++i) {
        valueType const pos = C[i] / B[i];

        if (pos <= N)
            bucket[pos].push_back(i);
    }

    valueType SumB = std::accumulate(B.begin(), B.end(), (valueType) 0), SumC = 0;

    for (valueType i = 0; i <= N; ++i) {
        G[i] = i * SumB + SumC;

        for (auto const &iter : bucket[i]) {
            SumB -= B[iter];
            SumC += C[iter];
        }
    }

    valueType ans = INF;

    for (valueType i = 0; i <= N; ++i)
        ans = std::min(ans, F[i] + G[N - i]);

    std::cout << ans << std::endl;

    return 0;
}

标签:std,Set,limits,min,2023.12,sum,12,right,valueType
From: https://www.cnblogs.com/User-Unauthorized/p/2023-12-12.html

相关文章

  • CF1253F Cheap Robot
    题意给定一个图,走过一条边的花费为权值,其中有\(k\)个充电点。你需要确定一个电量的上限,使得满足从\(a\)走到\(b\)。Sol先对于每个点求出她走到充电点最近的距离,用\(dij\)随便跑跑。考虑从\(a\tob\)一条边的贡献。设当前的电量上限为\(c\)。可得:\[c-dis_a\ge......
  • 2023-12-12 双十二思考借钱给steve的事
    2023-12-12   2014年投资了3.8W合伙成立半山腰。这个事情也怪我当初,我看Sw总要创业,做的事情又是有经验的,投资一点,以后赚了就跟着赚一点,亏了我也认栽。从一开始,就没有想过投资2~3万,要他回报给我2~300万。能赚个10几万,我觉得就很不错了。后面就很多年里,应该有7~8年,每年都问我......
  • 12.12邻接表存储实现图的深度优先遍历(c++)
    今天学习了数据结构中的邻接表存储实现图的深度优先遍历,其中让我受益匪浅,以下是我的解题思路。编写程序,实现由邻接表存储实现无向图的深度优先搜索遍历的功能。顶点为字符型。输入格式:第一行输入顶点个数及边的个数,第二行依次输入各顶点,第三行开始依次输入边的两个顶点,用空格......
  • 12.11 迪杰斯特拉方法实现最短路径(c++)
     今天通过自主学习,,对数据结构中的迪杰斯特拉方法实现最短路径进行了深造,让我学会了很多新的东西。首先是问题描述:用迪杰斯特拉算法实现有向网的最短路径输入格式:第一行输入有向网的顶点和边数,第二行输入各顶点值,用空格间隔,第三行开始输入各条边的两个点的及边上的权值,用空......
  • 2023年12月陕西广州/深圳软考高级信息系统项目管理师招生简章
    信息系统项目管理师是全国计算机技术与软件专业技术资格(水平)考试(简称软考)项目之一,是由国家人力资源和社会保障部、工业和信息化部共同组织的国家级考试,既属于国家职业资格考试,又是职称资格考试。信息系统项目管理师,属于软考三个级别中的“高级”。 【报考要求】 不设学历与资历条......
  • 2023年12月DAMA-CDGP数据治理专家认证招生简章
    DAMA认证为数据管理专业人士提供职业目标晋升规划,彰显了职业发展里程碑及发展阶梯定义,帮助数据管理从业人士获得企业数字化转型战略下的必备职业能力,促进开展工作实践应用及实际问题解决,形成企业所需的新数字经济下的核心职业竞争能力。DAMA是数据管理方面的认证,帮助数据从业者提升......
  • 2023年12月成都/杭州/深圳NPDP产品经理认证招生简章
    产品经理国际资格认证NPDP是新产品开发方面的认证,集理论、方法与实践为一体的全方位的知识体系,为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。 【认证机构】 产品开发与管理协会(PDMA)成立于1979年,是全球范围内产品开发与管理专业人士最杰出的倡导者,协助个人、企业或......
  • 备受大家喜爱的网工公开课!12月14日又开始啦!
    带你一起走进网工的世界!【G-LAB】新一轮网工入门免费公开课......
  • 2023年12月北京/上海/广州/深圳DAMA-CDGA/CDGP数据治理认证招生
    DAMA认证为数据管理专业人士提供职业目标晋升规划,彰显了职业发展里程碑及发展阶梯定义,帮助数据管理从业人士获得企业数字化转型战略下的必备职业能力,促进开展工作实践应用及实际问题解决,形成企业所需的新数字经济下的核心职业竞争能力。DAMA是数据管理方面的认证,帮助数据从业者提升......
  • 云原生周刊:Kubernetes v1.29 新特性一览 | 2023.12.11
    开源项目推荐kubedogKubedog是一个用于在CI/CD部署管道中监视和跟踪Kubernetes资源的库。这个库被用于werfCI/CD工具中,在部署过程中跟踪资源。RunWhenLocalrunwhen-local是一个工具,用于在本地环境中运行runwhen脚本。runwhen是一个灵活的任务调度工具,可以根据条......