2015内蒙古程序设计竞赛题解一

发布于 2019-04-22  46 次阅读


最近抽空做了2015省赛题,先发前五题的题解

A 我只要红色气球!

直接将输入进行52次乘1.1

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        double a;
        cin>>a;
        for(int i=0;i<52;i++)
        {
        a*=1.1;
        }
        cout<<(int)a<<endl;
    }
}

B 搬砖

很容易想到要均分,不能均分的话就两份相差一.可用递归实现

#include<iostream>
#include<cstdio>
using namespace std;
int dp[10000000+5];
int solve(int n)
{
    if(n==1) return 0;
    if(dp[n]!=0)return dp[n];
    if(n&1) return dp[n]=solve(n/2)+solve(n/2+1)+1;
    return dp[n]=2*solve(n/2);
}
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<solve(n)<<endl;
    }
}

C 投币洗衣机

简单模拟

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n,a,b,c,v;
    while(scanf("%d %d %d %d",&n,&a,&b,&c)==4)
    {
        int t=0,ans=0;
        while(n--)
        {
            scanf("%d",&v);
            t+=v;
            if(t>=c)
            {
                ans+=4;
                t=0;
            }
            else if(t>=b)
            {
                ans+=3;
                t=0;
            }
            else if(t>=a)
            {
                ans+=2;
                t=0;
            }
        }
        cout<<ans<<endl;
    }
}

D 玩骰子

为了实现方便,我就将每种骰子组合对应一个分数

(这题写的有点复杂)

#include<iostream>
#include<cstdio>
using namespace std;
int score(int a,int b,int c)
{
    if(a==b&&a==c&&b==c) return a*10000;
    if(a==b) return a*1000+c;
    if(a==c) return a*1000+b;
    if(b==c) return b*1000+a;
    if(b<c)swap(b,c);
    if(a<b)swap(a,b);
    if(b<c)swap(b,c);
    return a*100+b*10+c;
}
int main()
{
    int a,b,c,d,e,f,t;
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>c>>d>>e>>f;
        if(score(a,b,c)>score(d,e,f))
        {
            printf("%.3f\n",1.0);
            continue;
        }

        float m=0;

        int cnt=0;
        for(int i=1;i<=6;i++)
        {
            if(score(i,b,c)>score(d,e,f))cnt++;
        }
        if(cnt*1.0/6>m)m=cnt*1.0/6;

        cnt=0;
        for(int i=1;i<=6;i++)
        {
            if(score(a,i,c)>score(d,e,f))cnt++;
        }
        if(cnt*1.0/6>m)m=cnt*1.0/6;

        cnt=0;
        for(int i=1;i<=6;i++)
        {
            if(score(a,b,i)>score(d,e,f))cnt++;
        }
        if(cnt*1.0/6>m)m=cnt*1.0/6;
        printf("%.3f\n",m);
    }

}

E 质方数

先算出范围内的所有质方数,用到了线性筛法

由于数据范围不大,查找时直接遍历了

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int zfs[10000],index;
int p[10000];
int main()
{
    for(int i=2;i<10000;i++)
    {
        if(p[i]==0)zfs[index++]=i*i;
        for(int j=2;j*i<10000;j++)
        {
            p[i*j]=1;
            if(i%j==0)break;
        }
    }
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int ans,m=99999999;
        for(int i=0;i<index;i++)
        {
            int d=abs(zfs[i]-n);
            if(d<m)
            {
                m=d;ans=zfs[i];
            }
        }
        cout<<ans<<endl;
    }
}