更新記錄
【1】2020.05.09-13:28
1.完善內容
【2】2020.07.18-09:11
1.更改了一個小小的錯誤
正文
觀前提示
- 此文章為重溫系列，并不會講的很細致
- 需要有一定高精度與排序基礎
高精度
前言
高精度說實話是好久沒打了，不是因為我沒時間刷題，而是因為我懶
高精度這個東西考察的就是細心，一點錯，滿盤皆輸
（對沒錯這就是我一般不刷高精度的原因）
所有代碼均經過壓行與評測處理，請放心食用
減法為加法的逆運算，除法為乘法的逆運算，所以不貼這兩個高精度的代碼
高精度加法
- 倒序存盤
- 按位加，考慮進位
- \(ans[i]=a[i]+b[i]\)
- \(ans[i+1]=(a[i]+b[i])/10\)
- \(ans[i]=(a[i]+b[i])\%10\)
- 輸出
本代碼用了玄學的進位處理，不要效仿
#include<iostream>
using namespace std;
string a,b;
int c[10001],d[10001],e[10001];
bool ba;
int main()
{
int js=0,we=0;
cin>>a>>b;
for(int i=0;i<a.length();i++)
c[i]=a[a.length()-i-1]-'0';
for(int i=0;i<b.length();i++)
d[i]=b[b.length()-i-1]-'0';
for(int i=0;i<max(a.length(),b.length());i++){
if(i>=min(a.length(),b.length())){
if(a.length()>b.length()) e[we]=e[we]+c[i];
else e[we]=e[we]+d[i];
}
else
e[we]=c[i]+d[i];
if(e[we-1]>=10)
e[we-1]%=10;e[we]+=1;
we+=1;
}
for(int i=we-1;i>=0;i--){
if(!e[i]&&!ba) continue;
else ba=1;
cout<<e[i];
}
}
高精度減法
- 倒序存盤
- 按位減，考慮退位
- 輸出
和加法一樣就不寫太多了
高精度乘法
計算的時候把大數放在前面會得到無限的便利
至于是什么便利就交給你們去發現了
那么我們首先來看一個例子
沒錯我們先倒序存盤
然后我們自己在草稿紙上演算，別忘記中間程序也要倒序處理
然后就是這么個效果
1234*567=699678
這么一觀察我們就能發現突破口
定義兩層回圈，按位乘
最后加起來，，，？
要不要補零啊
不需要
我們發現這都是一一對應的，回圈的時候控制一下就可以了
看錯范圍差點去寫FFT
有些人會發現我碼風變了，原因是被Java帶的QAQ
#include<iostream>
using namespace std;
string a,b;
bool ba;
int c[1001],d[1001],e[100001],la,lb;
void cmp1(){
if(a.length()==b.length()){
for(int i=0;i<a.length();i++){
if(a[i]<b[i]) {swap(a,b);return;}
}
}
else{
if(a.length()<b.length())
swap(a,b);
}
}
int main(){
cin>>a>>b;cmp1();
la=a.length()-1,lb=b.length()-1;
for(int i=la;i>=0;i--) c[la-i+1]=a[i]-'0';
for(int i=lb;i>=0;i--) d[lb-i+1]=b[i]-'0';
for(int i=1;i<=b.length();i++){
for(int o=1;o<=a.length();o++){
e[i+o-1]+=(d[i]*c[o]+e[i+o-2]/10);
e[i+o-2]%=10;
}
if(e[i+la]>9){
e[i+la+1]+=(e[i+la]/10);
e[i+la]%=10;
}
}
for(int i=la+lb+2;i>0;i--){
if(!ba&&!e[i]) continue;
else ba=1;
cout<<e[i];
}
}
高精度除法
每一位進行加法逼近，然后來次高精減
一直算到最后一位即可
排序
快速排序
這里主要寫sort函式
函式用法（已簡化）：\(sort(begin,end,cmp);\)
begin默認從零開始，所以要想排1~N begin應該+1
cmp就是自定義排序函式
cmp的實參的型別與要排序的陣列的型別一樣
注意：結構體排序必須寫cmp，否則報錯
二路歸并排序
- 代碼我用回車分為三部分
void msort(int s,int e){
if(s==e) return;
long long int mid=(s+e)/2;
msort(s,mid);msort(mid+1,e);
int i=s,j=mid+1,k=s;
while(i<=mid&&j<=e){
if(a[i]<=a[j]) {r[k]=a[i];k+=1;i+=1;}
else {r[k]=a[j];k+=1;j+=1;}
}
while(i<=mid) {r[k]=a[i];k+=1;i+=1;}
while(j<=e) {r[k]=a[j];k+=1;j+=1;}
for(int i=s;i<=e;i++)
a[i]=r[i];
}
第一部分
判斷與定義變數部分
if(s==e) return;：開頭和結尾一樣 = 只有一個數 = 直接跳出，不需要任何操作long long int mid=(s+e)/2;int i=s,j=mid+1,k=s;：定義mid，值為s與e的平均數（分治的標志），順便我們備份一下開頭和結尾，現在定義j將s至e分為兩個區間：s - mid , mid+1 - e，也就是：i - mid , j - e- 先讓左右區間分解，合并：
msort(s,mid);msort(mid+1,e);
第二部分
左右區間的合并
- 由于左右區間經過第一部分的操作，已經為有序區間，所以這兩個區間開頭的數必為區間最大（小）值，我們只要判斷開頭就可以了（這里以從小到大排列為例）
- 哪邊小，就將其加到另一個陣列中（為了不破壞原陣列），然后相應的區間端點+1（這個數判斷完了就要從下一個開始，由于是從端點開始判斷（端點開始是因為有序性，上文已經提及），就相當于縮小區間）
- 以此類推，直到一邊判斷完畢
- 此時原陣列依然可能有殘留的數，例如\({1，2，3，4}\)與\({5，6，7，8}\)這兩個區間
- 這時我們通過兩個回圈來清除
- 那么為什么要寫在一起而不判斷情況呢，我們可以進行一個小小的證明（真的很小QAQ）
-
- 由于一個區間已經復制完畢，所以必有一個區間長度為0
while(i<=mid&&j<=e){
//起始點等于結束點的時候，回圈依然成立，此時長度為1
if(a[i]<=a[j]) {r[k]=a[i];k+=1;i+=1;}
//這兩個
else {r[k]=a[j];k+=1;j+=1;}
//必會執行一個，導致起始點+1，此時起始點=結束點+1
}
所以這兩個while回圈只會執行一個
第三部分
陣列的復制
你都歸并好了你不復制回去嘛
堆排序
建個小根（大根）堆就排好了
void put(int a){
int now,next;hs+=1;
h[hs]=a;now=hs;
while(now>1){
next=now>>1;
if(h[now]>=h[next])
break;
swap(h[now],h[next]);
now=next;
}
}
一次插入時間復雜度為\(O(logn)\)
總復雜度為\(O(nlogn)\)
并且時間復雜度比較穩定
實戰
以下是我通過TLE換來的教訓
- 不一定什么都要用高精去和另一個高精去加，去乘
- 同樣的，不一定什么都要按位，有時候我們可以直接壓位計算，即將一個多位數看成一位數
例如這道題：
任意給定一個正整數N(N≤100)，計算2的n次方的值，
原題目鏈接
#include<iostream>
using namespace std;
int a[1001],cnt,times;
int jie(int num){
for(int i=0;i<num;i++){
for(int o=0;o<cnt;o++){
if(a[o]>9)
if(o==cnt-1)
cnt+=1;
a[o]*=2;
if(a[o-1]>9&&o)
a[o-1]-=10;a[o]+=1;
if(o==cnt-1)
if(a[o]>9){
cnt+=1;a[o]-=10;a[o+1]+=1;
break;
}
}
}
}
int main(){
a[0]=1;cnt=1;
cin>>times;jie(times);
for(int i=cnt-1;i>=0;i--)
cout<<a[i];
}
這個其實就是一個初級應用
再看一個例子
求10000以內n的階乘，
原題目鏈接
這個題就需要一定技巧了，暴力的結果只能是TLE
（還有Wonderful Answer呢awa）
例如最后一步：*10000
- 這個時候我們就要把10000看成一個數，一起乘進去
- 最后處理進位
單單*10000這一步，時間復雜度就變為了原來的1/5
那么整道題基本可以達到暴力的1/3 - 1/4倍的時間復雜度
不貼代碼了你自己做去awa
總結
- 高精度與排序都是比較基礎的內容，比賽一般不會單獨拿出來考
- 這更需要我們牢牢掌握它
不要以為簡單就不去練習，基礎的內容更需要我們經常復習
那么怎么“高效”復習呢，這里推薦一個視頻教程，每天看看就行了awa
打開鏈接：高精度與排序詳解
每天復習一遍不是很輕松，很棒的事嗎？（手動滑稽）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/51489.html
標籤：其他
上一篇：CF1286A Garland