牛客網小白月試合10 A B C

10180 ワード

小白月試合はますます悪くなってきた.私もますます料理が増えたのかもしれない.
a題
Actciは偶然1つの鉱洞を発見して、この鉱洞の構造は1本の二叉木に似ていて、Actciが発見した鉱洞はちょうど根のノードのところに位置して、できるだけ早く掘り起こすために、Actciは彼女の小さい仲間たちを探して助けに来て、地質の原因のため、毎日小さい仲間たちは1本の子ノードまでの道(時間を消費しません)に通じるしかありません.つまり、毎日1つのノードが1つのサブノードにしか道路を建設できないということです.1つの道路を歩くには1日かかります.1つの道路を発見すると、一部のパートナーが残って探査を続けることを選択します.
構想:時計を打ったり、絵を描いたりして法則を探したりするのはフィポラチ数列の和を求めることだ.
  
#include 
using namespace std;
const long long mod=10000000007;
long long f[5000005];
int main()
{
    long long n;
    cin>>n;
    f[1]=1;
    f[2]=2;
    for(int i=3;i<=n;i++){
        f[i]=f[i-1]+f[i-2];
        f[i]=(f[i]+mod)%mod;
    }
    long long ans=0;
    for(int i=1;i<=n;i++) ans=(ans+f[i])%mod;
    cout<endl;
    return 0;
}

b問題も法則を探しているだろう.
ある年のある月のある日の数学の授業で、Actciは宇宙を泳いでいて、彼の何度も教えても改めないで、彼女の数学の先生はActciのために、彼を起こすのが難しいことを決めました.
「咳咳、私は今1つの数aを与えます.
0≦a≦1010000)、aが3,5,8,11のいくつかの数の倍数であるかどうかを判断し、あなたは1秒の時間しかなく、答えられないと、ああ、%#W$%@#$...」.
彼の後ろのテーブルのあなたはどうしてActciの“被害”を見ることができて、そこであなたは彼を助けることにしました.
考え方:stringの判断に対して、3で割り切れると、1位あたりの和が3で割り切れるはずで、5で割り切れると末位が5で割り切れる、8で割り切れる、1位10位100位で構成される数を要求し、8で割り切れる、11で割り切れる、奇数位と偶数位の差が11で割り切れる
  
#include 
using namespace std;
int main()
{
    int n,m;
    string s;
    cin>>s;
    int sum=0;
    int sum1=0,sum2=0;
    int flag=0;
    for(int i=0;i){
        if(i%2==0) sum1+=s[i]-'0';
        else sum2+=s[i]-'0';
        sum+=s[i]-'0';
    }
    int t=0;
    int length=s.length();
    t+=s[length-3]-'0';
    t*=10;
    t+=s[length-2]-'0';
    t*=10;
    t+=s[length-1]-'0';
    int num[5];
    if(sum%3==0) num[flag++]=3;
    if((s[s.length()-1]-'0')%5==0) num[flag++]=5;
    if(t%8==0) num[flag++]=8;
    if(abs(sum1-sum2)%11==0) num[flag++]=11;
    if(flag){
        cout<<"Yes"<<endl;
        for(int i=0;i' ';
    }
    else cout<<"No"<<endl;
    return 0;
}

Cの問題をしたことがある人はとても多くて、しかしいつも時間の複雑さを感じて少し問題があって、データはintを爆発します
Actciは授業中に一眠りして、授業が終わると数学の先生に補習を探しに行って、先生に1つのテーマを聞きました:2つの数a,bを与えて、aとbのすべての公約数は何ですか?数学の先生はこの問題を見ると簡単すぎて、答えたくないので、あなたに渡しました.100%のデータに対して、1≦a,b≦10^13
構想:まずこの2つの数のgcdを求めてから質量因数分解を行う.直接暴力は無謀だ
  
#include 
using namespace std;
long long gcd(long long a,long long b){
    return b==0?a:gcd(b,a%b);
}
int main()
{
    long long n,m;
    cin>>n>>m;
    long long t=gcd(n,m);
    //long long s=(n/t)*m;
    set<long long> num;
    for(long long i=1;i*i<=t;i++){
        if(t%i==0){
            num.insert(i);
            num.insert(t/i);
        }
    }
     for(set<long long>::iterator it=num.begin() ;it!=num.end();it++)
    {
        cout<' ';
    }
    return 0;
}

 
転載先:https://www.cnblogs.com/maybe96/p/10178188.html