因为很久没刷算法题了手有点生,所以刷些题记录下
快速幂和取余运算
//取模运算的性质
(a*b)%p=[(a%p)*(b%p)]%p
快速幂模板题
https://www.luogu.com.cn/problem/P1226
对于本题来说,用这种方法让O(b)的算法复杂度变成了O(log2b)
#include<iostream>
using namespace std;
typedef long long ll;
ll fast_power(ll a,ll b,ll c){
ll ans=1;
a%=c;//防止a初始值过大
while(b){//b不为0就循环
if(b&1){//为奇数就让ans*a,让底数开平方,让指数缩小一半
ans*=a;
ans%=c;//由取模运算的性质
}
//偶数的话就不需要ans*a,直接让底数开平方,让指数缩小一半就行
a*=a;
a%=c;//由取模运算的性质
b>>=1;
}
return ans;
}
int main(){
ll a,b,c;
cin>>a>>b>>c;
cout<<a<<"^"<<b<<" mod "<<c<<"=";
cout<<fast_power(a,b,c);
return 0;
}
https://www.luogu.com.cn/problem/P1010
这个题嘞,乍一看好像能写,实际一写我就寄了,去看看佬们的代码
思路呢,模拟递归。
1、找到2的幂次方最接近n且小于n
2、让n减去这个2的幂次方
3、这个2的幂次方如果幂大于2就再对这个幂搜索
4、n减去2次幂之后还大于2就对n再搜索
5、如果n为0或1或2就结束
#include<iostream>
using namespace std;
typedef long long ll;
ll n;
void search(ll x){
if(x!=0){
cout<<2;//先输出一个2,再对后面进行添加
int q=1,p=0;//q为底数,p为指数
while(q<=x){//先找到小于x且最接近的2次幂
q*=2;
++p;
}
--p;//实际上多加了一次,所以减去
q/=2;//之前那个2的幂次方多乘了一次2
if(p==0||p==2){
cout<<"("<<p<<")";//进行特判,且p=1的时候不需要加括号
}
if(p>=3){//只要比2大就继续搜索
cout<<"(";
search(p);
cout<<")";
}
x-=q;//减去少掉的部分
if(x){
cout<<"+";//如果x不为0的话,就后面添个+再搜索后续部分
search(x);
}
}
}
int main(){
cin>>n;
search(n);
return 0;
}
哎呀,这思路帅啊
其实还是我太菜了
剩下还有其他思路,暂时不看了刷下一道去了
https://www.luogu.com.cn/problem/P6039
开始的时候一看,哎挺简单的,直接对着B点丢球过去然后求个x/y就行,然后写完,还没交,去看看别人的代码,好家伙咋还有这么多分析。
原来是我直接没考虑2*r大于OA,然后看了下别人的证明,也不算很难,把图一画还是明了的
啊还有就是没有考虑到x=0,y=0的情况哇,这种情况下任意方向丢传送器都可以,取最小的tan也就是取0的情况,这道题就算完成了
结果还是有些细节出错啊,还把Error打成ERROR哈哈
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
double x,y,r;
int main(){
cin>>x>>y>>r;
double ma=0;
ma=sqrt(x*x+y*y);
double ans=0;
ans=abs(ma-2*r);//第一次忘了加绝对值了
printf("%.6lf\n",ans);
if(x==0&&y==0){
cout<<"0.00";
}
else if(y==0){
cout<<"Error";//爷笑了这个整成ERROR了
}
else{
printf("%.2lf",abs(x/y));//这个也忘了还有绝对值
}
return 0;
}
https://www.luogu.com.cn/problem/P6022
这道题竟然能靠我的脑子想出来,还真是不容易啊
虽然很简单
qwq
#include<iostream>
using namespace std;
int n,m,sum=0,summ=0;//sum代表每次喝的数字,summ代表兑换的数字
long long ans=0;//最终喝掉的可乐
int a[6],b[6];//a数组是附属品的兑换值,b是附属品的拥有值
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
cin>>a[i];
}
sum=n;
while(sum){
summ=0;
ans+=sum;//每轮都喝可乐
for(int i=1;i<=m;++i){
b[i]+=sum;//附属品的增加
summ+=b[i]/a[i];//附属品兑换的可乐
b[i]=b[i]%a[i];//附属品的剩余
}
if(summ>=n){//如果一轮获得的兑换可乐比最初都多就代表无限白嫖
cout<<"Inf";
return 0;
}
sum=summ;//新的一轮能喝的可乐
}
cout<<ans;
return 0;
}
后续的话会尽量保持刷到开学
标签:音速,cout,int,ll,long,ans,次方,include,刷些 From: https://www.cnblogs.com/whynot-ne/p/17048006.html