我的vj是 计科合1902王子豪 zihao521
这是我的题解,如果不对多多指正哈,原题链接:
HPU算法协会公开课第二期: 【基础算法2】https://vjudge.net/contest/375071#overview
这次根据做题先后顺序写题解,话不多说开始了
F - 人见人爱A^B
思路:明确快速幂的用法。快速幂值得是快速求得A^B次方的方法,加上mod表示大数取出来几位。
原理:某个数字取余之后相乘再取余保持余数不变 。
模板代码实现原链接:
//原理实现 typedef long long ll; ll poww(ll x,ll y,ll mod) //x底数,y指数,mod位数 { ll ans=1; x=x%c; //加上这个是因为积的取余数=取余的积的取余 //就是n个相同的数字相乘对某一个数x取余数,可以先让相同的数字对n取余数。然后每次都取余数。 while(y){ if(y&1) ans=(ans*x)%mod; x=(x*x)%mod; y>>=1; } return ans; }
如果看不懂,可以参考这个csdn的讲解https://blog.csdn.net/zwj1452267376/article/details/47134577?locationNum=8&fps=1
模板分析: 1.先让底数取模,大大的减少底数的大小
2.用&符号,来判断是不是1奇数 是1有必要乘出来
3.就是n个相同的数字相乘对某一个数x取余数,可以先让相同的数字对n取余数。然后每次都取余数。
我们返璞归真一下:为什么要这样算:.首先直接地来设计这个算法,直接设计算法。
版本一:
int ans = 1; for(int i = 1;i<=b;i++) { ans = ans * a; } ans = ans % c;
这个算法的时间复杂度体现在for循环中,为O(b).这个算法存在着明显的问题,如果a和b过大,很容易就会溢出。
那么,我们先来看看第一个改进原理:即积的取余等于取余的积的取余。
版本二
int ans = 1; a = a % c; //加上这一句 for(int i = 1;i<=b;i++) { ans = ans * a % c;; } ans = ans % c;
版本三 就是题中的快速幂模板了,无论奇数偶数都适用。
int PowerMod(int a, int b, int c) { int ans = 1; a = a % c; while(b>0) { if(b % 2 = = 1) ans = (ans * a) % c; b = b/2; a = (a * a) % c; } return ans; }
所以,F 人见人爱的题解就是:
#include<iostream> using namespace std; int main(){ int a,b; while(scanf("%d%d",&a,&b)&&a&&b){ long ans=1; a=a%1000; while(b){ if(b&1) ans=ans*a%1000; a=a*a%1000; b>>=1; } printf("%lld\n",ans); } return 0; }
E - Rightmost Digit
思路:快速幂。
题目要求:求出来最低位。也就是mod=10;
代码实现:
#include<iostream> using namespace std; int main(){ int t,a,b,ans; cin>>t; while(t--){ cin>>a; ans=1; b=a%10; while(a){ if(a&1) ans=(ans*b)%10; b=(b*b)%10; a=a>>1; } cout<<ans<<endl; } return 0; }
C - Key Set
思路:也是快速幂解法,不过要明确,题目中的mod和底数和指数各是多少。
原理:快速幂套模板,以及明确总集合个数。
当然也可以直接盲猜一下是2^n-1,个。
#include<iostream> //规律是 目标集合为2^n-1 typedef long long ll; const ll c = 1000000007; using namespace std; void find(ll a,ll b,ll c){ ll ans=1; a=a%c; while(b){ if(b&1) ans=ans*a%c; a=a*a%c; b>>=1; } printf("%lld\n",ans-1); } int main(){ ll t,n,ans=1,a,b; cin>>t; while(t--){ cin>>n; find(2,n-1,c);//2为底,n-1为次数,c为mod } return 0; }
A - Pseudoprime numbers伪素数
思路:输两个数p,a,p为素数,则直接输出no,否则进行ap = a (mod p),也就是a^p % p == a?等于就yes,不等于就是no。
注意,这里面需要把ans设置成1,a保留下来最终对比,p保留下来成为mod。
素数筛+快速幂
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; //素数筛 int prime(int n){ int count=0; for(int i=2;i*i<=n;i++){ if(n%i==0){ count=1; break; } } if(count) return 0;//不是素数 else return 1;//是素数 } int main(){ ll a,p; while(cin>>p>>a&&a&&p){ if(prime(p)){ printf("no\n"); continue; } //ap = a (mod p),也就是a^p % p == a?等于就yes, ll ans=1;//用来存取素数幂 ll sum=a;//存取初始a ll mod=p;//存取mod while(p) { if(p&1){ ans=ans*a%mod; } a=a*a%mod; p>>=1; } if(ans==sum) printf("yes\n"); else printf("no\n"); } return 0; }
D - Distribution money
思路:桶排序,找到目的人记录,找不到输出-1;
#include<iostream> #include<algorithm> #include<cstring> using namespace std; int vis[10000]; int a[10000]; int main(){ int n; while(scanf("%d",&n)!=EOF){ memset(vis,0,sizeof(vis)); int count=0; //如果查找到的话count变为对应的工号 //查找不到的话就是判断是0的状态下的 输出-1 for(int i=0;i<n;i++){ cin>>a[i]; //桶 vis[a[i]]++; //判断是不是某个痛大于总数的一半了 if(vis[a[i]]>n/2){ count=a[i];//这个人就是要寻找的那个人 } } if(!count){ printf("-1\n"); } else printf("%d\n",count); } return 0; }
B - Raising Modulo Numbers
问题:读题读不懂,唉。
思路:题意:给出一组数据,求(A1B1+A2B2+ ... +AHBH)mod M.其中第一个输入的数字,是总的需要输出的个数,第二个输入的是mod,第三个输入的是具体的这n组数据A1B1A2B2A3B3乃至最后一个各是多少。
#include<iostream> using namespace std; typedef long long ll; ll quick(ll a, ll b, ll mod) { ll ans = 1; while(b){ if(b & 1) ans = ans * a % mod; a = a * a % mod; b>>=1; } return ans; } int main() { int Z; scanf("%d",&Z); while(Z--) { ll sum = 0; ll M;//mod ll k;//数据数 scanf("%lld",&M); scanf("%lld",&k); while(k--) { ll a,b; scanf("%lld%lld",&a,&b); sum = sum + quick(a,b,M); } printf("%lld\n",sum%M); } return 0; }
I - Can you solve this equation?
思路:二分,首先判断输入的y是不是大于函数带入x=100的时候,判断是不是小于6,如果是都不用二分了,直接x肯定不符合,直接continue即可。
如果不是呢,那就需要二分,首先定义eps 1e-8,然后while内是模板 r-l>=eps,然后下面区间最值取值的时候就要想一想了,如果你输入了y,并且中间值取值的时候进去函数,小于你的y,说明你的mid取值太小了,需要将mid变成左区间,也就是l=mid;反之r=mid;最后输出mid。
#include<iostream> #include<cmath> #include<algorithm> #define eps 1e-8 using namespace std; double judge(double x){ return 8.0*pow(x,4.0)+ 7*pow(x,3.0)+ 2.0*pow(x,2.0)+ 3.0*x +6.0; } int main(){ int t; cin>>t; double max=judge(100); while(t--){ double y; cin>>y; if(y>max||y<6){ printf("No solution!\n"); continue; } double l=0.0,r=100.0,mid; while(r-l>=eps){ mid=(l+r)/2; if(y>judge(mid)) l=mid; else if(y<judge(mid)) r=mid; } printf("%.4lf\n",mid); } return 0; }
H - Pie
老蛋糕了,思路二分,不过细节得注意。
#include<iostream> #include<algorithm> #include<cmath> #define eps 1e-6 //最小为1e-4 所以设置为1e-6 #define pi acos(-1.0) //pi精度设定 acos(-1.0) using namespace std; int N,F; double r; double s[10000];//表示每个蛋糕的面积 bool check(double x){ int z=0; for(int i=1;i<=N;i++){ z+=(int)(s[i]/x); //让每一个蛋糕的面积 除以预计的个人每个人假设应该分的 面积 球的人数 //并且加起来,求得 } if(z>=F) return 1; else return 0; } int main(){ int t; cin>>t; while(t--){ cin>>N>>F; F++; double sum=0; for(int i=1;i<=N;i++){ cin>>r; s[i]=pi*r*r; sum+=s[i];//记录目前的所有蛋糕面积 } //开始二分构造 double l=0.0,r=sum/F,mid=0; while(fabs(l-r)>eps){ mid=(l+r)/2; if(check(mid)){ l=mid;//当你的中间取值都满足条件时, //说明比它小的都满足条件,那么此时下界就变为中间取值,当中间取值不满足条件时 //,说明比它大的都不满足条件,那么这时候上界就变为中间取值。 } else r=mid; } printf("%.4lf\n",l); } return 0; }
二分的模板问题
整数二分算法模板 —— 模板题 AcWing 789. 数的范围
bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用: int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用: int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }
浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根
bool check(double x) {/* ... */} // 检查x是否满足某种性质 double bsearch_3(double l, double r) { const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }