我的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;
}
京公网安备 11010502036488号