牛客寒假算法集训营（4）

72 阅读 0 评论 48 点赞

我是靠谱客的博主犹豫皮带，最近开发中收集的这篇文章主要介绍牛客寒假算法集训营（4），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接牛客寒假算法训练营（四）

A 取石子游戏

签到题先手必赢

B 走方格

C 走迷宫

E 涂颜色

显然题目要求相邻方格颜色不能一样又只有黑白两种颜色

那么一行就只有两种涂色方法所以n行就是2的n次方

然后需要注意的是这个题是大数我们需要用欧拉降幂关于欧拉降幂

c++代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
const int mod=1e9+7;
char a[maxn],b[maxn];
ll pow_mod(ll x,ll n){//快速幂
    ll ans=1;
    x=x%mod;
    while(n!=0){
        if(n&1)
            ans=ans*x%mod;
        n>>=1;
        x=x*x%mod;
    }
    return ans;
}
int main(){
    scanf("%s%s",a,b);
    int l=strlen(a);
    ll n=0;
    //欧拉降幂
    for(int i=0;i<l;i++){
        n=(n*10+a[i]-'0')%(mod-1);
    }
    printf("%lldn",pow_mod(2,n));
    return 0;
}

当然对于大数问题我们可以用python（没学过临时试了一下py）

py代码

def pow_mod(a,b,c):
    ans=1
    while b>0:
        if b&1:
            ans=ans*a%c
        b>>=1
        a=a*a%c
    return ans%c
n,m = map(int,input().split())
n=n%1000000006
ans = pow_mod(2,n,1000000007)
print(ans)

赛后知道了 py里面有一个算幂的函数 pow 这个函数可以进行a的b次方mod n 的运算而且不用降幂

果然 python就是可以为所欲为附上代码

n,m = list(map(int,input().split()))
print(pow(2,n,1000000007))

//读一个数的方法
n= int(input())

I 回文串

J 减肥计划

这个题也算是本场签到题

给了两个力和角度求合力

余弦定理就好了

注意一下使用三角函数传参应该是弧度制所以先把题目给的角度转换成弧度制

代码

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
int n,x,y;
int main(){
    double a,b,r;
    scanf("%lf%lf%lf",&a,&b,&r);
    r=r*PI/180;//转换弧度制
    r=PI-r;
    double ans=a*a+b*b-2*a*b*cos(r);//余弦定理
    printf("%.10fn",sqrt(ans));
    return 0;
}