松岗建设网站做网页和网站一样吗

当前位置： 首页 > news >正文

松岗建设网站,做网页和网站一样吗,福州seo公司技术,网站后台管理教程为了更好的阅读体检#xff0c;可以查看我的算法学习网站 在线评测链接:P1119 题目内容 塔子哥是一个热爱数学的年轻数学家#xff0c;他对数字和因子分解有着深入的研究。 有一天#xff0c;他在一次偶然的探索中发现了一款神奇的游戏#xff0c;名为“除数游戏”。 在…为了更好的阅读体检可以查看我的算法学习网站 在线评测链接:P1119 题目内容 塔子哥是一个热爱数学的年轻数学家他对数字和因子分解有着深入的研究。 有一天他在一次偶然的探索中发现了一款神奇的游戏名为“除数游戏”。 在这个游戏中玩家需要在一个整数数组 a a a 中选择一个大于 1 1 1的数字 a i a_i ai​ 并将其除以其中一个素因子 p p p 素因子是能被 a i a_i ai​ 整除的素数。接着玩家可以继续将新数字除以素因子直到进行了 k k k 次操作。 塔子哥很快就意识到这个游戏可以为他的研究提供很多有用的信息。他开始探究在最多进行 k k k 次操作的情况下玩家能够通过该游戏达到的最小数组总和是多少 输入描述 第一行输入两个正整数 n n n和 k k k代表数组大小以及操作次数。 第二行输入 n n n个正整数 a i a_i ai​代表数组的元素。 1 ≤ n , k ≤ 200000 1\leq n,k\leq 200000 1≤n,k≤200000 1 ≤ a i ≤ 1 0 6 1\leq a_i\leq 10^6 1≤ai​≤106 输出描述 一个整数代表操作后的所有元素最小的和。 样例 输入 5 2 1 2 3 4 5输出 9思路 贪心优先队列数论优化 1.贪心策略由于要最小化数组的总和那么对于某一个数 a i a_i ai​ , 要除一定是除它最大的质因子 m a x f a c t o r ( a i ) maxfactor(a_i) maxfactor(ai​)。 这样下降的最多下降量为: Δ i a i − m a x f a c t o r ( a i ) \Delta_i a_i - maxfactor(a_i) Δi​ai​−maxfactor(ai​) 。所以显然每一次操作我们肯定是选择 m a x ( Δ i ) max(\Delta_i) max(Δi​) 的位置 i i i 。然后还需要更新这个值。 2.引入高级数据结构数据量比较大为了能够快速实现我们这个贪心策略我们需要一个可以快速 1.寻找最大值 2.删除最大值 3.插入值 的数据结构。这个显然可以使用优先队列维护。 3.引入数论优化:在优先队列的排序过程中由于我们需要获取 m a x f a c t o r maxfactor maxfactor , 这个东西如果每次都暴力获得复杂度为 O ( V ) O(\sqrt{V}) O(V ​) ,那么导致总复杂度为 O ( k ∗ l o g n ∗ V ) O(k*log n * \sqrt{V}) O(k∗logn∗V ​) 。 这是不可接受的(虽然期望复杂度无法达到这么高但是我们总是希望有更优的解法)。所以我们需要先预处理出 [ 1 , V 1 e 6 ] [1,V1e6] [1,V1e6] 中的所有数的 m a x f a c t o r ( i ) maxfactor(i) maxfactor(i) 。 这个预处理方法我们可以直接使用埃式筛的方法转移伪代码如下: for i in 2 … V:if maxfactor[i] : continuefor j in i - V , step imaxfactor[j] max(maxfactor[j] , i)这样一来 m a x f a c t o r ( i ) { 0 i ∈ p r i m e m a x P r i m e F a c t o r o f i o t h e r \Large maxfactor(i)\left{\begin{matrix} 0 i\ \in\ prime\ maxPrimeFactor\ of\ i other \end{matrix}\right. maxfactor(i)⎩ ⎨ ⎧​0maxPrimeFactor of i​i ∈ primeother​ 最后如果用一句话解释这个题的本质就是TopK变种罢了 具体细节见代码 类似题目推荐 LeetCode 见 贪心 - 代码随想录 . 这个只是入门刷完也并不意味着能做出这题。 CodeFun2000 提供一些贪心题 P1014 2022.10.8-美团春招-塔子玩游戏 开胃菜1 P1211 塔子大厂真题模拟赛-第一题-魔法石(Ⅰ) 开胃菜2 P1279 2023.05.06-春招-第三题-塔子哥的游戏 同样是贪心 优先队列的经典题目推荐做一做 P1239 2023.04.20-华为od-第一题-总最快检测效率 同样是贪心 优先队列的经典题目推荐做一做 P1148 2023.4.3-阿里巴巴-研发岗-第三题-又一个数论题 虽然不是贪心题。但是也是常见算法套上了数论的优化 代码 CPP #includebits/stdc.h using namespace std; const int maxn 1e6 5; #define ll long long int f[maxn] , a[maxn]; // 优先队列的节点 struct Node {int x;// 定义顺序bool operator (const Node a) const {int g1 x - x / f[x];int g2 a.x - a.x / f[a.x];// 优先下降量大的放堆顶return g1 g2;} }; priority_queueNode q; int main (){int n , k;// f 就是 上文的maxfactor , 即最大质因数f[1] 1;for (int i 2 ; i maxn ; i){if (f[i] ! 0) continue;for (int j i ; j maxn ; j i){f[j] max(f[j] , i);}}cin n k;// 把a[i] 都放入堆同时获得最大值ll sum 0;for (int i 1 ; i n ; i){cin a[i];sum a[i];q.push({a[i]});}// 模拟操作while (k–){// 每次从堆顶拿出下降量最多的元素Node g q.top();q.pop();// 更新总和sum - g.x;sum g.x / f[g.x];// 重新放入堆q.push({g.x / f[g.x]});}// 输出总和cout sum endl;return 0; }python from random import * import sys from collections import * from math import * from functools import * from heapq import *def solve(n,k,arr):mx max(arr)tot sum(arr)#f 就是 上文的maxfactor , 即最大质因数f list(range(mx1))for i in range(2,mx1):if f[i] ! i: continuefor j in range(i2,mx1,i):f[j] i hq []# 先把所有元素的可能序列都先全部放到序列中for a in arr:while a 1:hq.append(a//f[a]-a)a // f[a]# 建堆heapify(hq)# 取前k大for _ in range(k):if not hq: break tot heappop(hq)return tot # 读入 n, k list(map(int,input().split())) arr list(map(int,input().split())) print(solve(n,k,arr))Java import java.util.; public class Main {static int MAXN 1000010;static int[] prime new int[MAXN];public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int k sc.nextInt();prime[1] 1;PriorityQueueNode pq new PriorityQueue();isPrime();// 先将n个数放入优先队列for (int i 0; i n; i) {int x sc.nextInt();Node node new Node(x, prime[x]);pq.offer(node);}// 模拟while (k– 0){Node node pq.poll();int data node.data;int x data / node.prime;pq.offer(new Node(x, prime[x]));}long ans 0;while (!pq.isEmpty()){ans pq.poll().data;}System.out.println(ans);}// 求最大素数private static void isPrime() {for (int i 2; i MAXN; i){if (prime[i] 0){for (int j i; j MAXN; j i){prime[j] i;}}}}// 自定义排序static class Node implements ComparableNode{int data;int prime;public Node(int data, int prime) {this.data data;this.prime prime;}Overridepublic int compareTo(Node o) {// 下降量最大优先return (o.data - o.data / o.prime) - (this.data - this.data / this.prime);}} }Go package mainimport (container/heapfmt )const maxn 1e6 5type Node struct {x int }type PriorityQueue []Nodefunc (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool {g1 : pq[i].x - pq[i].x/f[pq[i].x]g2 : pq[j].x - pq[j].x/f[pq[j].x]// 优先下降量大的放堆顶return g1 g2 } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] pq[j], pq[i] }func (pq *PriorityQueue) Push(x interface{}) {node : x.(Node)*pq append(*pq, node) }func (pq *PriorityQueue) Pop() interface{} {n : len(*pq)node : (*pq)[n-1]*pq (*pq)[:n-1]return node }var f [maxn]int var a [maxn]intfunc main() {var n, k int// f 就是 上文的 maxfactor即最大质因数f[1] 1for i : 2; i maxn; i {if f[i] ! 0 {continue}for j : i; j maxn; j i {f[j] max(f[j], i)}}fmt.Scan(n, k)// 把 a[i] 都放入堆同时获得最大值var sum int64 0pq : make(PriorityQueue, n)for i : 0; i n; i {fmt.Scan(a[i])sum int64(a[i])pq[i] Node{a[i]}}heap.Init(pq)// 模拟操作for i : 0; i k; i {// 每次从堆顶拿出下降量最多的元素g : heap.Pop(pq).(Node)// 更新总和sum - int64(g.x)sum int64(g.x / f[g.x])// 重新放入堆heap.Push(pq, Node{g.x / f[g.x]})}// 输出总和fmt.Println(sum) }func max(x, y int) int {if x y {return x}return y }Js 注意已知的OJ上的JavaScript都不提供优先队列,要手写优先队列这里塔子哥提供一种实现。 // 基于堆实现优先队列 , 函数名参考Java实现的priorityQueue class Pqueue {constructor(cpr) {this.queue [];this.size 0;this.cpr cpr;}swap(i, j) {let tmp this.queue[i];this.queue[i] this.queue[j];this.queue[j] tmp;}// 上浮swim() {let ch this.queue.length - 1;while (ch ! 0) {let fa Math.floor((ch - 1) / 2);const ch_node this.queue[ch];const fa_node this.queue[fa];if (this.cpr(ch_node, fa_node) 0) {this.swap(ch, fa);ch fa;} else {break;}}}// 下沉sink() {let fa 0;while (true) {let ch_left 2 * fa 1;let ch_right 2 * fa 2;let ch_max;let ch_max_node;const fa_node this.queue[fa];const ch_left_node this.queue[ch_left];const ch_right_node this.queue[ch_right];if (ch_left_node ch_right_node) {// 注意这里应该要0因为左边优先级高if (this.cpr(ch_left_node, ch_right_node) 0) {ch_max ch_left;ch_max_node ch_left_node;} else {ch_max ch_right;ch_max_node ch_right_node;}} else if (ch_left_node !ch_right_node) {ch_max ch_left;ch_max_node ch_left_node;} else if (!ch_left_node ch_right_node) {ch_max ch_right;ch_max_node ch_right_node;} else {break;}// 注意这里应该要0因为父优先级高if (this.cpr(ch_max_node, fa_node) 0) {this.swap(ch_max, fa);fa ch_max;} else {break;}}}// 向优先队列中加入元素offer(ele) {this.queue.push(ele);this.size;this.swim();}// 取出最高优先级元素poll() {this.swap(0, this.queue.length - 1);this.size–;const ans this.queue.pop();this.sink();return ans;}// 只使用最高优先级元素不取出peek() {return this.queue[0];} }// 正片const maxn 1e6 5; let f new Array(maxn).fill(0); let a new Array(maxn).fill(0);let q new Pqueue((a , b) {let g1 a - Math.floor(a / f[a]);let g2 b - Math.floor(b / f[b]);return g2 - g1; }); f[1] 1; for (let i 2; i maxn; i) {if (f[i] ! 0) continue;for (let j i; j maxn; j i) {f[j] Math.max(f[j], i);} }process.stdin.resume(); process.stdin.setEncoding(utf-8); let input ; process.stdin.on(data, (data) {input data;return; }); process.stdin.on(end, () {const lines input.trim().split(\n);var [n, k] lines[0].split( ).map(Number);var a lines[1].split( ).map(Number);let sum 0;for (let i 0 ; i n; i) {sum a[i];q.offer(a[i]);}while (k–) {let x q.poll();sum - x;sum Math.floor(x / f[x]);q.offer(Math.floor(x / f[x]));}console.log(sum); });题目内容均收集自互联网如如若此项内容侵犯了原著者的合法权益可联系我: (CSDN网站注册用户名: 塔子哥学算法) 进行删除