企业官网建设流程全解析

G 快速幂 算法

(1) 如果将 a 自乘一次，就会变成 a^2 。再把 a^2 自乘一次就会变成 a^4 。然后是 a^8…… 自乘 n 次的结果是 a^2n 。对吧……

(2) a^xa^y=a^x+y，这个容易。

(3) 将 b 转化为二进制观看一下：

比如 b=(11)10​ 就是 (1011)2​ 。从左到右，这些 1 分别代表十进制的 8,2,1。可以 说 a^11=a^8×a^2×a^1。

快速幂 =把指数看成二进制，只在 1 的位置乘，其他位置用平方跳过

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a,b,p; ll ans=1,o; ll fast(ll a,ll b,ll p) { ll ans=1; a%=p; // 避免a的数据太大 while(b) { if(b%2==1) // if(b&1) ans=(ans*a)%p; a=(a*a)%p; 将p拆分为二进制数 可以降低时间和空间 b/=2; // b>>=1; } return ans; } int main() { cin>>a>>b>>p; o=fast(a,b,p); printf("%lld^%lld mod %lld=%lld",a,b,p,o); }

F 第三边

主要是 题目的理解

244+353=597不能超过第三边

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,t; ll sum; int a[200005]; int main() { ios::sync_with_stdio(false); cin.tie(0); ios::sync_with_stdio(false); cout.tie(0); cin>>t; while(t--) { cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } if(n==1) cout<<a[0]<<endl; else { sum=0; for(int i=0;i<n;i++) { sum+=a[i]; } cout<<sum-(n-1)<<endl; } } return 0; }

J 跳石头 二分答案

• 求最小值→mid = (l + r) / 2
• 求最大值→mid = (l + r + 1) / 2

#include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,L; int a[50005]; bool check(int x) { int t=0,cnt=0; for(int i=0;i<n;i++) { if(a[i]-t<x) cnt++; else t=a[i]; } if(L-t<x) cnt++; return cnt<=m; } int er(int l,int r) { while(l<r) { int mid=(l+r+1)/2; // 必须加一 不加一会陷入死循环 if(check(mid)) l=mid; else { r=mid-1; } } return l; } int main() { ios::sync_with_stdio(false); cin.tie(0); ios::sync_with_stdio(false); cout.tie(0); cin>>L>>n>>m; for(int i=0;i<n;i++) { cin>>a[i]; } int ans=er(0,L); cout<<ans<<endl; return 0; }