根據(jù)之前刷過(guò)的題還是總結(jié)一下結(jié)論和模板吧。不然一會(huì)兒就又忘完了。
感覺(jué)知道一些結(jié)論做題是很有幫助的。

目錄

• 快速的判斷一個(gè)大數(shù)是不是3的倍數(shù)，或9的倍數(shù)
• 判斷一個(gè)字符串是不是回文
• 求n!的約數(shù)個(gè)數(shù)
• 判斷是不是潤(rùn)年
• 求n!轉(zhuǎn)化成2進(jìn)制的位數(shù)
• 以知三角形的邊求面積
• 約瑟夫環(huán)問(wèn)題
• 倆數(shù)互質(zhì)，最大不可以組合出的數(shù)字
• 等比數(shù)列，等差數(shù)列求和公式
• 求一個(gè)數(shù)轉(zhuǎn)換成2進(jìn)制中1的個(gè)數(shù)
• 大數(shù)與大數(shù)的乘法
• 一元三次方程求解
• 凸多邊形對(duì)角線交點(diǎn)的個(gè)數(shù)
• 平面上有N條直線，最多有幾個(gè)交點(diǎn)
• 用N個(gè)三角形最多可以把平面分成幾個(gè)區(qū)域
• 多重集的排列組合問(wèn)題
• 求一個(gè)數(shù)的約數(shù)之和。
• 階乘的末尾零的個(gè)數(shù)
• 求倆字符串的最長(zhǎng)不公共子序列
• 加速輸入輸出流
• map嵌套pair
• 求階乘某一個(gè)因子出現(xiàn)的次數(shù)。
• 棋盤遍歷問(wèn)題
• 求[1，n]所有數(shù)的約數(shù)個(gè)數(shù)之和的問(wèn)題
• 質(zhì)數(shù)的平方數(shù)只有三個(gè)因子

快速的判斷一個(gè)大數(shù)是不是3的倍數(shù)，或9的倍數(shù)

將這個(gè)數(shù)的所有位的數(shù)相加，如果mod3等于0就是3的倍數(shù)，如果mod9等于0就是9的倍數(shù)
詳細(xì)的推理過(guò)程
注意: 這里只適用于 3和9。

bool check9(string s) {int cnt=0;for(int i=0;i<s.size();i++) cnt+=s[i]-'0';if(cnt%9==0) return true;else return false; } bool check3(string s) {int cnt=0;for(int i=0;i<s.size();i++) cnt+=s[i]-'0';if(cnt%3==0) return true;else return false; }

判斷一個(gè)字符串是不是回文

bool check(string s) {string a=s; reverse(a.begin(),a.end());return s==a; }

求n!的約數(shù)個(gè)數(shù)

一個(gè)數(shù)約數(shù)的個(gè)數(shù)等于這個(gè)數(shù)分解質(zhì)因子后，(每個(gè)質(zhì)數(shù)的個(gè)數(shù)+1）的乘積

typedef long long int LL; map<LL,LL>mp; void f(LL x) {for(int i=2;i<=x/i;i++) while(x%i==0) mp[i]++,x/=i;if(x!=1) mp[x]++; } LL solve(int n) {LL ans=1;for(int i=2;i<=n;i++) f(i);for(auto i=mp.begin();i!=mp.end();i++) ans=ans*(i->second+1);return ans; }

判斷是不是潤(rùn)年

bool judge(int year) {if(year%400==0|| (year%4==0&&year%100!=0) ) return true;else return false; }

求n!轉(zhuǎn)化成2進(jìn)制的位數(shù)

LL solve(int n) {double sum=0;for(int i=1;i<=n;i++) sum+=log2(i);return sum+1; }

以知三角形的邊求面積

double solve(int a,int b,int c) {double p=(a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c)); }

約瑟夫環(huán)問(wèn)題

公式推理

int solve(int n,int k)//1到n個(gè)人,報(bào)到k的最后留下來(lái)的編號(hào) {int ans=0;for(int i=2;i<=n;i++) ans=(ans+k)%i;return ans+1; }

倆數(shù)互質(zhì)，最大不可以組合出的數(shù)字

ab-a-b==(a-1)*(b-1)-1

int solve(int a,int b){return (a-1)*(b-1)-1;}

等比數(shù)列，等差數(shù)列求和公式

求一個(gè)數(shù)轉(zhuǎn)換成2進(jìn)制中1的個(gè)數(shù)

int lowbit(int x){return x&-x;} int solve(int x)//輸入一個(gè)數(shù)x {int cnt=0;while(x) x-=lowbit(x),cnt++;return cnt; }

大數(shù)與大數(shù)的乘法

vector<int> mul(vector<int> &A,vector<int> &B) {int t=0; vector<int> C;C.push_back(0);//目的是容器里初始化for(int j=0;j<B.size();j++){for(int i=0;i<A.size();i++){C.push_back(0);C[i+j]+=A[i]*B[j];}}for(int i=0;i<C.size();i++)//處理進(jìn)位{if(C[i]>=10)C[i+1]+=C[i]/10,C[i]=C[i]%10;} while(C.size()>1&&C.back()==0) C.pop_back();//處理前導(dǎo)零return C; }

一元三次方程求解

void solve(double a,double b,double c,double d)//只適用于三個(gè)解互相不通的情況。 {double A,B,C,T,ac,x1,x2,x3;A=b*b-3*a*c; B=b*c-9*a*d; T=(2*A*b-3*a*B)/(2*sqrt(A*A*A)); ac=acos(T); x1=(-b-sqrt(A)*cos(ac/3)*2)/3/a; x2=(-b+sqrt(A)*(cos(ac/3)-sqrt(3)*sin(ac/3)))/(3*a); x3=(-b+sqrt(A)*(cos(ac/3)+sqrt(3)*sin(ac/3)))/(3*a); printf("%.2lf %.2lf %.2lf",x1,x2,x3); }

凸多邊形對(duì)角線交點(diǎn)的個(gè)數(shù)

首先一個(gè)交點(diǎn)對(duì)應(yīng)兩條對(duì)角線，二這兩條對(duì)角線是有四個(gè)點(diǎn)確定的。
所以只要求$C_n^4$就可以了 即 n(n-1)(n-2)(n-3)/24

typedef unsigned long long int LL; LL solve(LL x){return x*(x-1)/2*(x-2)/3*(x-3)/4;}

平面上有N條直線，最多有幾個(gè)交點(diǎn)

倆線一個(gè)點(diǎn)，共 $C_n^2$個(gè)點(diǎn)

int solve(int x){return x*(x-1)/2;}

用N個(gè)三角形最多可以把平面分成幾個(gè)區(qū)域

f[i]=f[i-1]+6*(i-1)
推導(dǎo)

LL f[100005]; LL solve(int n) {f[1]=2;for(int i=2;i<=n;i++) f[i]=f[i-1]+6*(i-1);return f[n]; }

多重集的排列組合問(wèn)題

實(shí)戰(zhàn)題目: 猴子排序的期望 ， 擅長(zhǎng)解密的小紅同學(xué)

求一個(gè)數(shù)的約數(shù)之和。

typedef long long int LL; const int mod=1e9+7; map<LL,LL>mp; void f(int x) {for(int i=2;i<=x/i;i++) while(x%i==0) mp[i]++,x/=i;if(x!=1) mp[x]++; } LL solve() {LL ans=1;for(auto i=mp.begin();i!=mp.end();i++){LL temp=1;int m=i->second;LL a=i->first;for(int j=1;j<=m;j++) temp=(temp*a+1)%mod;ans=(ans*temp)%mod;}return ans; }

階乘的末尾零的個(gè)數(shù)

int solve(int n) {int ans=0;while(n) ans+=n/5,n/=5;return ans; }

求倆字符串的最長(zhǎng)不公共子序列

int solve(string a,string b) {if(a==b) return -1;else return max(a.size(),b.size()); }

加速輸入輸出流

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

map嵌套pair

typedef pair<int,int> p; map<p,int> mp;mp[p(dx,dy)]++;

求階乘某一個(gè)因子出現(xiàn)的次數(shù)。

int solve(int n,int x) {int ans=0;while(n) ans+=n/x,n/=x;return ans; }

棋盤遍歷問(wèn)題

給定一個(gè) N×M 的方格棋盤，請(qǐng)問(wèn)一個(gè)棋子從棋盤左上角出發(fā)，能否在不重復(fù)經(jīng)過(guò)棋盤上的方格的情況下，遍歷整個(gè)棋盤一次再回到起點(diǎn)。 if(n==1&&m==1) puts("Y"); else if(n==1||m==1) puts("N"); else if(n%2==0||m%2==0) puts("Y"); else puts("N");

求[1，n]所有數(shù)的約數(shù)個(gè)數(shù)之和的問(wèn)題

LL n,ans=0; scanf("%lld",&n); for(LL i=1,j;i<=n;i=j+1)//節(jié)約時(shí)間 { j=n/(n/i);ans+=(n/i)*(j-i+1); } printf("%lld\n",ans);

質(zhì)數(shù)的平方數(shù)只有三個(gè)因子

總結(jié)

以上是生活随笔為你收集整理的刷算法题总结的一些结论公式的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。