P4068 [SDOI2016]数字配对

    • 162通过
    • 531提交
  • 题目提供者 ElevenDimensions
  • 评测方式 云端评测
  • 标签 二分图 最大流 素数判断,质数,筛法 网络流 贪心 各省省选 2016 山东
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有 n 种数字,第 i 种数字是 $a_i$、有 $b_i$ 个,权值是 $c_i$。

    若两个数字 $a_i$、$a_j$ 满足,$a_i$ 是 $a_j$ 的倍数,且 $a_i/a_j$ 是一个质数,

    那么这两个数字可以配对,并获得 $c_i \times c_j$ 的价值。

    一个数字只能参与一次配对,可以不参与配对。

    在获得的价值总和不小于 0 的前提下,求最多进行多少次配对。

    输入输出格式

    输入格式:

    第一行一个整数 n。

    第二行 n 个整数 $a_1,a_2,\cdots,a_n$。

    第三行 n 个整数 $b_1,b_2,\cdots,b_n$。

    第四行 n 个整数 $c_1,c_2,\cdots,c_n$。

    输出格式:

    一行一个数,最多进行多少次配对

    输入输出样例

    输入样例#1: 复制
    3
    2 4 8
    2 200 7
    -1 -2 1
    
    输出样例#1: 复制
    4

    说明

    测试点 1 ~ 3: $n \leq 10 $, $a_i \leq 10 ^ 9 $ , $b_i = 1 $,$ | c_i | \leq 10 ^ 5$ ​​;
    测试点 4 ~ 5: $n \leq 200 $, $a_i \leq 10 ^ 9 $ , $b_i \leq 10 ^ 5 $,$ c_i = 0 $;

    测试点 6 ~ 10: $n \leq 200 $, $a_i \leq 10 ^ 9 $ , $b_i \leq 10 ^ 5$ ,$ | c_i | \leq 10 ^ 5$ 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。