2013年ICPC中国大陆区域赛真题

Golden Radio Base 黄金分割进制

题目读了好长时间，大体是要把十进制数字转化成黄金分割进制，当然肯定每个十进制数字的黄金分割进制数字都是唯一的

当时一直没懂  和 是什么意思后来终于才明白

可以推出   还有 

以此为根据，暴力把>1的位数上的数字拆开再把相邻的1进位直到没有相邻的且每一位上的数字至多为1

其实数组开100就可以，整数部分对1是斐波那契式的增长，所以最多50位就会超过10^9

#include<bits/stdc++.h>
using namespace std;

int ans[210],n;
bool f;

int main()
{
    while(~scanf("%d",&n))
    {
        memset(ans,0,sizeof(ans));
        ans[100] = n;
        f = 1;
        while(f)
        {
            f = 0;
            for(int i = 2;i <= 200; ++i)
                if(ans[i] > 1)
                {
                    ans[i + 1] += ans[i] / 2;
                    ans[i - 2] += ans[i] / 2;
                    ans[i] %= 2;
                    f = 1;
                }
            for(int i = 1;i <= 200; ++i)
                if(ans[i] && ans[i + 1])
                {
                    int x = min(ans[i],ans[i + 1]);
                    ans[i] -= x;
                    ans[i + 1] -= x;
                    ans[i + 2] += x;
                }
        }
        int l,r;
        for(int i = 200;i >= 1; --i)
            if(ans[i])
            {
                l = i;
                break;
            }
        for(int i = 1;i <= 200; ++i)
            if(ans[i])
            {
                r = i;
                break;
            }
        for(int i = l;i >= r; --i)
        {
            if(i == 99) printf(".");
            printf("%d",ans[i]);
        }
        printf("n");
    }
    return 0;
}

Little Tiger vs. Deep Monkey 背包+思维

题目：老虎和猴子比赛，有n道题目，猴子做对每道题的概率都是随机的，作对得分不然不得分，给出n个题目各自的得分，问狮子最少要多少分才能有p的概率不输给猴子

解：因为猴子是否做题目是随机的，可以计算出猴子得到某个得分的概率，求一个最小的x使得猴子得分小于x的概率是>=p

#include<bits/stdc++.h>
using namespace std;

int a[50],b[50],n,m,t;
double dp[50][40050],p;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%lf",&n,&p);
        b[0] = 0;
        for(int i = 1;i <= n;i++)
        {
            scanf("%d",&a[i]);
            b[i] = b[i - 1] + a[i];
        }
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for(int i = 1;i <= n;i++)
            for(int j = 0;j <= b[i];j++)
            {
                dp[i][j] += dp[i - 1][j] * 0.5;
                dp[i][j + a[i]] += dp[i - 1][j] * 0.5;
            }
        double g = 0;
        for(int i = 0;i <= b[n];i++)
        {
            g += dp[n][i];
            if(g >= p)
            {
                cout<<i<<'n';
                break;
            }
        }
    }
    return 0;
}

最后

以上就是乐观饼干为你收集整理的2013年ICPC中国大陆区域赛真题的全部内容，希望文章能够帮你解决2013年ICPC中国大陆区域赛真题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。