【bzoj1263】[SCOI2006]整數劃分 高精度

題目描述

從文件中讀入一個正整數n(10≤n≤31000)。要求將n寫成若干個正整數之和,并且使這些正整數的乘積最大。 例如,n=13,則當n表示為4+3+3+3(或2+2+3+3+3)時,乘積=108為最大。

輸入

只有一個正整數: n (10≤n≤31000)

輸出

第1行輸出一個整數,為最大乘積的位數。 第2行輸出最大乘積的前100位,如果不足100位,則按實際位數輸出最大乘積。 (提示:在給定的范圍內,最大乘積的位數不超過5000位)。

樣例輸入

13

樣例輸出

3
108


題解

高精度

首先根據某小學奧數理論,如果n%3==0,則全拆成3;如果n%3==1,則拆出來一個4,其余全拆成3;如果n%3==2,則拆出來一個2,其余全拆成3.

然后高精度乘低精度就好了。

由于有位數限制,所以比較懶沒有壓位,可能會慢點。

#include <cstdio>
#include <cstring>
struct data
{int len , num[5010];data(){len = 0 , memset(num , 0 , sizeof(num));}data operator=(const int a){len = 1 , num[0] = a;return *this;}data operator*(const int a)const{data t;int i;for(i = 0 ; i < len ; i ++ ) t.num[i] += num[i] * a , t.num[i + 1] += t.num[i] / 10 , t.num[i] %= 10;t.len = len + (bool)t.num[len];return t;}void output(){printf("%d\n" , len);int i;for(i = len - 1 ; i >= 0 && i >= len - 100 ; i -- ) printf("%d" , num[i]);printf("\n");}
}ans;
int main()
{int n , i;scanf("%d" , &n);ans = (n + 1) % 3 + 2;for(i = 1 ; i <= (n - 2) / 3 ; i ++ ) ans = ans * 3;ans.output();return 0;
}

轉載于:https://www.cnblogs.com/GXZlegend/p/6670378.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/393286.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/393286.shtml
英文地址,請注明出處:http://en.pswp.cn/news/393286.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

rails i18n模型_Rails國際化的完整指南(i18n)

rails i18n模型by Anastasia由Anastasia Rails國際化的完整指南(i18n) (The Complete Guide to Rails Internationalization (i18n)) In this article you are going to learn how to translate your Rails application into multiple languages, work with translations, loc…

分表后需要注意的二三事

前言 本篇是上一篇《一次分表踩坑實踐的探討》&#xff0c;所以還沒看過的朋友建議先看上文。 還是先來簡單回顧下上次提到了哪些內容&#xff1a; 分表策略&#xff1a;哈希、時間歸檔等。分表字段的選擇。數據遷移方案。而本篇文章的背景是在我們上線這段時間遇到的一些問題并…

DNS 原理

阮老師的作品&#xff0c;非常精彩&#xff0c;轉載&#xff01; DNS 是互聯網核心協議之一。不管是上網瀏覽&#xff0c;還是編程開發&#xff0c;都需要了解一點它的知識。 本文詳細介紹DNS的原理&#xff0c;以及如何運用工具軟件觀察它的運作。我的目標是&#xff0c;讀完此…

leetcode1169. 查詢無效交易

如果出現下述兩種情況&#xff0c;交易 可能無效&#xff1a; 交易金額超過 1000 或者&#xff0c;它和另一個城市中同名的另一筆交易相隔不超過 60 分鐘&#xff08;包含 60 分鐘整&#xff09; 每個交易字符串 transactions[i] 由一些用逗號分隔的值組成&#xff0c;這些值分…

銷售員/學員/講師系統

前言: 今晚寫一篇關于學員/講師/銷售員CRM系統。這個小項目是27號開始做的&#xff0c;大概搞了一星期不到。我把一些知識點總結下&#xff0c;還寫下當時克服的BUG。 Django練習小項目&#xff1a;學員管理系統設計開發 帶著項目需求學習是最有趣和效率最高的&#xff0c;今天…

Linux內核啟動

1 內核編譯 解壓縮&#xff1a;tar xjf linux-2.6.22.6.tar.bz2打補丁&#xff1a; path -p1 < ../linux-2.6.22.6_jz2440.patch(其中p1是忽略補丁文件中的一級目錄)配置&#xff1a; 方法一&#xff1a;使用make menuconfig逐項配置方法二&#xff1a;使用默認配置&#xf…

node.js使用手冊_權威的Node.js手冊

node.js使用手冊Developer and freeCodeCamp camper Flavio Copes has published his entire Node.js Handbook online for free - both on freeCodeCamps Medium publication and as a .pdf file. You can read it here.開發人員和freeCodeCamp營員Flavio Copes在freeCodeCamp…

自動化運維之saltstack(二)states深入理解

深入了解SLS的可以參考這篇博文&#xff1a;http://www.ituring.com.cn/article/42238 個人覺得這篇文章翻譯的不錯&#xff0c;所以轉載過來。 Salt Sates 眾多強大而有力的涉及都是建立在簡單的原則之上。Salt SLS系統也是努力想K.I.S.S看齊。&#xff08;Keep It Stupidly …

java里面的 |運算符_Java 中 | ^ 運算符的簡單使用

背景今天碰到了代碼中的按位與運算&#xff0c;復習一下&#xff0c;先列一個各個進制數據表。順便復習一下十進制轉二進制的計算方式&#xff1a;接下來解釋下這三個運算符&#xff1a;&  按位與&#xff0c;都轉為二進制的情況下&#xff0c;同為1則為1&#xff0c;否則…

leetcode915. 分割數組

給定一個數組 A&#xff0c;將其劃分為兩個不相交&#xff08;沒有公共元素&#xff09;的連續子數組 left 和 right&#xff0c; 使得&#xff1a; left 中的每個元素都小于或等于 right 中的每個元素。 left 和 right 都是非空的。 left 要盡可能小。 在完成這樣的分組后返回…

徹底理解正向代理、反向代理、透明代理

套用古龍武俠小說套路來說&#xff0c;代理服務技術是一門很古老的技術&#xff0c;是在互聯網早期出現就使用的技術。一般實現代理技術的方式就是在服務器上安裝代理服務軟件&#xff0c;讓其成為一個代理服務器&#xff0c;從而實現代理技術。常用的代理技術分為正向代理、反…

使用showMessageDialog顯示消息框

-----------------siwuxie095 工程名&#xff1a;TestJOptionPane 包名&#xff1a;com.siwuxie095.showdialog 類名&#xff1a;TestMessageDialog.java 工程結構目錄如下&#xff1a; 代碼&#xff1a; package com.siwuxie095.showdialog; import java.awt.BorderLayout;…

將Javascript帶到邊緣設備

Smart devices today are very similar to labour-saving gadgets a generation ago: Where previously everything got a power cord, now everything gets a chip. 如今的智能設備與上一代的省力小工具非常相似&#xff1a;以前所有設備都配有電源線&#xff0c;而現在所有設…

java 泛型 父子_使用通配符和泛型:完成父子類關系的List對象的類型匹配

泛型和通配符使用泛型和通配符都可以讓一個方法所表示的算法邏輯適應多種類型。Java中具備繼承關系的類A、B(A extends B)它們的集合List和List之間是沒有繼承關系的&#xff0c;可以使用泛型或通配符來讓一個方法支持同時接受List和List。代碼場景這里分別定義類Animal、Dog和…

重定向描述符

文件描符 縮寫 描述 0 STDIN 標準輸入 1 STDOUT 標準輸出 2 STDERR 標準錯誤 1、重定向錯誤和數據 1234[rootlogicserver tmp]# ls -al data1 haha 2> qingyun.txt 1&g…

NodeJS學習筆記(一)——搭建開發框架Express,實現Web網站登錄驗證

目錄 開發環境  1、建立工程  2、目錄結構  3、Express配置文件  4、Ejs模板  5、安裝常用庫及頁面分離  6、路由  7、session  8、頁面訪問控制及提示JS是腳本語言&#xff0c;腳本語言都需要一個解析器才能運行。對于寫在HTML頁面里 的JS&#xff0c;瀏覽器充…

LeetCode-208 Implement Trie (Prefix Tree)

題目描述 Implement a trie with insert, search, and startsWith methods. 題目大意 實現對一棵樹的插入、搜索以及前序查找操作。 &#xff08;樹的每個節點代表一個小寫字母&#xff0c;從根節點到葉節點代表一個完整的單詞&#xff09; 示例 E Trie trie new Trie();trie.…

react組件生命周期_React組件生命周期-掛鉤/方法介紹

react組件生命周期React components have several lifecycle methods that you can override to run your code at a particular time in the process.React組件具有幾種生命周期方法&#xff0c;您可以重寫它們以在流程中的特定時間運行代碼。 In this video, Nick Karnik de…

(馬世龍)Linux下CACTI完全搭建技術文檔二

續&#xff08;馬世龍&#xff09;Linux下CACTI完全搭建技術文檔一 6.完成cacti的安裝1. 首先檢查一下rra/下面&#xff0c;有沒有數據2. snmpwalk -v 2c -c public ServerIP if 用來測試被控對象(serverIP)是否開啟了SNMP服務3. snmpwalk -v 2c ServerIP -c public .1.3.6.1.4…

項目經理如何管理情緒?這三本書管理書籍你必須要看

本文主要是介紹三本管理的書籍&#xff0c;需要全部書籍的可以加Q群375508415去拿走。里面很多大神的PMP資料。 大家有沒有覺得項目經理有時像個政委&#xff0c;做員工思想工作&#xff1b; 有時像個HR&#xff0c;操心員工的穩定和發展&#xff1b; 有時像個咨詢顧問&#xf…