伊苏比的梦幻之旅(三)比赛题解

比赛地址:http://qscoj.cn/contest/25/

第9-1关 咒语转换(小数据)

分析:将八进制转换为二进制,八进制只有一位,所以数据范围只有0-7,直接手动转换就好了。注意0-1是一位,2-3是两位,4-7是三位。

标程:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if (n==0) cout<<0<<endl;
    if (n==1) cout<<1<<endl;
    if (n==2) cout<<10<<endl;
    if (n==3) cout<<11<<endl;
    if (n==4) cout<<100<<endl;
    if (n==5) cout<<101<<endl;
    if (n==6) cout<<110<<endl;
    if (n==7) cout<<111<<endl;
    return 0;
}

第9-2关 咒语转换(中数据)

分析:八进制长度最大为17,所以能表示的最大的数为8^17-1,在long long的范围内,我们可以先考虑把八进制转换成我们熟悉的十进制,再把十进制转换成二进制就很方便了。

标程:

#include<bits/stdc++.h>
using namespace std;
long long ans,b[65];
int main()
{
    int i,len;
    long long j;
    bool flag;
    string s;
    cin>>s;len=s.length();
    ans=0;j=1;flag=false;
    for(i=len-1;i>=0;i--)
    {
        ans+=j*(s[i]-48);
        j*=8;
    }
    for(i=62;i>=0;i--)
    {
        j=(1ll<<i);
        b[i]=ans/j;ans%=j;
    }
    for(i=62;i>=0;i--)
    {
        if (b[i] || i==0) flag=true;
        if (flag) printf("%d",b[i]);
    }
    printf("
");
    return 0;
}

第9-3关 咒语转换(大数据)

分析:八进制数字的长度最大为170000,不知道很多同学是不是就想到了高精度呢?其实呀,根本不需要高精度。八进制转二进制有个特点,就是8是2的3次方。所以,我们可以将八进制数以字符串的形式读入,将一个数字拆成二进制的三个数字顺序写下来就行了,注意一下最高位转换时要去掉前导0.

标程:

#include<bits/stdc++.h>
using namespace std;
string s1[8]={"0","1","10","11","100","101","110","111"};
string s2[8]={"000","001","010","011","100","101","110","111"};
int main()
{
    string s;
    int i,len;
    cin>>s;len=s.length();
    cout<<s1[s[0]-48];
    for(i=1;i<len;i++)
        cout<<s2[s[i]-48];
    cout<<endl;
    return 0;
}

第10-1关 报数游戏(小数据)

分析:小数据非常良心,都告诉了你x,y,z的值,所以直接手工计算都能得出答案(^o^)/~

标程:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n>>n>>n>>n;
    if (n==1) cout<<1<<endl;
    if (n==2) cout<<7<<endl;
    if (n==3) cout<<11<<endl;
    if (n==4) cout<<13<<endl;
    if (n==5) cout<<17<<endl;
    if (n==6) cout<<19<<endl;
    if (n==7) cout<<23<<endl;
    return 0;
}

第10-2关 报数游戏(中数据)

分析:数据范围为10^7,其实只用for循环加上判断直到找到第n个既不是x,又不是y,还不是z的倍数的数。事实证明,在x,y,z分别取2,3,5时所需要找的次数最多。根据容斥定理,1~q的数中大约有q/2+q/3+q/5-q/(2*3)-q/(3*5)-q/(2*5)+q/(2*3*5)=11q/15的数会是2、3、5的倍数,所以有约4q/11的数会被报到,而10^7除以4/11的答案也在O(n)算法复杂度接受的范围内,故直接for循环扫一遍就好。

标程:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,n,i,cnt;
    scanf("%d%d%d%d",&a,&b,&c,&n);cnt=0;
    for(i=1;;i++)
    {
        if (i%a!=0 && i%b!=0 && i%c!=0) cnt++;
        if (cnt==n)
        {
            cout<<i<<endl;
            return 0;
        }
    }
}

第10-3关 报数游戏(大数据)

分析:根据第10-2关的相关分析,我们可以通过容斥定理计算出1-q之间有多少个数会被报到(不是x,y,z任何一个数的倍数),直接计算不是其倍数的数不好计算。可以计算出是x,y,z中一个数的倍数的数的个数。计算公式为S=q/x+q/y+q/z-q/gcd(x,y)-q/gcd(y,z)-q/gcd(z,x)+q/gcd(x,y,z);q-S就是报到的数。然后我们可以通过二分的方式找出最早报出N个数的q值,就是本题的答案。注意x,y,z均为10^7,直接乘会爆long long,就得用相除的方式判断一下gcd(x,y,z)是否比10^18大,如果比他大的话就不用管它了。

标程:

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{
    return b==0?a:gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
    long long ans,k;
    ans=a/gcd(a,b);k=1e18/ans;
    if (k<b) ans=-1;
    else ans*=b;
    return ans;
}
int main()
{
    long long l,r,x,y,z,n,m,ans;
    long long xy,yz,zx,xyz;
    cin>>x>>y>>z>>n;
    l=0;r=1e18;
    while(l+1<r)
    {
        m=(l+r)/2;
        ans=m/x+m/y+m/z;
        xy=lcm(x,y);
        yz=lcm(y,z);
        zx=lcm(z,x);
        ans-=(m/xy+m/yz+m/zx);
        xyz=lcm(xy,z);
        if (xyz!=-1) ans+=m/xyz;
        if (m-ans>=n) r=m;
        else l=m;
    }
    cout<<r<<endl;
    return 0;
}

第11-1关 未来世界(小数据)

分析:数据范围只有1-17,N天后都不会超出这个月,直接输出2017,5,14+N就好了。

标程:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    cout<<"2017 5 "<<n+14<<endl;
    return 0;
}

第11-2关 未来世界(中数据)

分析:数据范围为10^7,所以可以直接往后枚举就好。我的方法是将闰年和平年每个月的日期储存起来,然后日期到32就变为1,并给月份加1;月份到13就变1,并给年份加1.然后再判断这个日期合不合法,合法的话就给计数器加1,计数器到N的时候就输出这个日期。

标程:

#include<bits/stdc++.h>
using namespace std;
int run[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int ping[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool leap(int y)
{
    if (y%400==0) return true;
    if (y%4==0 && y%100!=0) return true;
    return false;
}
int main()
{
    int y,m,d,n,cnt;
    scanf("%d",&n);
    y=2017;m=5;d=14;cnt=0;
    while(cnt<n)
    {
        d++;
        if (d==32) {d=1;m++;}
        if (m==13) {m=1;y++;}
        if (leap(y))
        {
            if (d<=run[m]) cnt++;
        }
        else
        {
            if (d<=ping[m]) cnt++;
        }
    }
    cout<<y<<" "<<m<<" "<<d<<endl;
    return 0;
}

第11-3关 未来世界(大数据)

分析:数据范围为10^17,直接for肯定超时。但是,每年的天数不完全一样,每4年的天数也不都完全一样。因此,很多同学可能觉得难以下手。但实际上,这肯定是有规律的。根据闰年的定义,我们知道每400年固定会有97个闰年,因此每400年的天数是固定不变的,为365*400+97=146097天,所以我们先对这个天数取模,看这个天数包含多少个400年,再把剩余的天数按照第11-2关的方法暴力跑一下就可以确定月和日,最后再在年份上加上前面的商乘上400的值就是正确答案了。

标程:

#include<bits/stdc++.h>
using namespace std;
int run[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int ping[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool leap(int y)
{
    if (y%400==0) return true;
    if (y%4==0 && y%100!=0) return true;
    return false;
}
int main()
{
    int m,d,cnt;
    long long n,y,x;
    scanf("%lld",&n);x=n/146097;n%=146097;
    y=2017;m=5;d=14;cnt=0;
    while(cnt<n)
    {
        d++;
        if (d==32) {d=1;m++;}
        if (m==13) {m=1;y++;}
        if (leap(y))
        {
            if (d<=run[m]) cnt++;
        }
        else
        {
            if (d<=ping[m]) cnt++;
        }
    }
    y+=400*x;
    cout<<y<<" "<<m<<" "<<d<<endl;
    return 0;
}

第12关 万物皆空

分析:本题纯属娱乐,根据题目的意思,没有任何输入输出,把头文件和主函数打一下就好了。

标程:

#include<stdio.h> 
int main(){}
原文地址:https://www.cnblogs.com/cs-lyj1997/p/6852661.html