absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [-32] 100324 E(高斯消元)
[破碎的状态] [-31] 100324 J

[破碎的状态] [-31] 100324 C

absi2011 posted @ Jun 21, 2016 12:28:23 PM in 刷题记录 with tags 字符串 小高考 CF Gym , 268 阅读

感谢@JCarlson && @似水流年 的翻译

题意(贴JCarlson的翻译记录)

JCarlson很喜欢玩老虎机,我们现在来形容一下老虎机的构造。
老虎机有N个转轮。对于每个转轮,它有M个标志(本题用字母代替),然后显示在屏幕上的只有K个标志,和一条直线穿过一行字母。
JCarlson投入一个代币进去,然后拉杆,转轮就开始xtmd转,转到停下来为止。此时机器就会判断,如果那条直线上的字母如果符合一个特定的组合,机器就会吐出一定的代币。
这是普通的玩法,JCarlson通过玩老虎机每次都能赢空一个赌场。然而JCarlson觉得,仅仅一行直着的线实在是太没有新意了。于是JCarlson自己开了一家赌场并造了一台新·老虎机。
新老虎机有更多种的选择,同时判断的那个线也多了好几条,而且还有弯的。对于一条线的描述用<i1,i2,..,in>表达,每个值表示这条线穿过屏幕上的第几个标志。玩家可以选择若干条线进行判断,但与此同时花的代币也会增多。确切的讲每多使用一条线就要多一个代币。
现在提供给你这种新老虎机的相关信息:N个转轮,M个字母,屏幕上能最多同时显示K个字母,C种获奖组合,L条线。
接着N行每行M个字母表示第i个转轮上的字母信息。
接着C行每行N个字符和一个数字表示第i种获奖组合,*表示任意字母皆可。后面的数字表示它的奖金。
接下来L行每行N个数表示一条线。
你需要选择特定的一些线使得赢钱的比例最大:期望收益/使用的线数,这个值要最大。请你回答这个值以及使用的线。 (absi2011的PS:如果赢不了钱输出0/1,第二行输出0,包括不亏本的情况)

Warning:本题主要难度在于高精度计算,使用Java或Python的同学可以轻松愉快的秒杀这一题

我们无视掉k这种奇怪的东西..它和题目没有关系..

我们观察整个老虎机,我们显然可以算出每条线分别的收益..

然后我们就可以发现..所有线的收益是一样的..只跟每一种获奖组合有关..

这样的话选哪些也无关了,只分选和不选两种..

所以l也可以无视了

然后..暴力算赔不赔本吧..没了

这题主要难度在于高精度除高精度和高精度对高精度取模

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int cnt[45][225];
struct bigint
{
    int a[25];
    bigint (int x=0)
    {
        memset(a,0,sizeof(a));
        a[0]=x;
    }
    int & operator [](int x)
    {
        return a[x];
    }
    friend bool operator <= (bigint &a,bigint &b)
    {
        int i;
        for (i=19;i>=0;i--)
        {
            if (a[i]!=b[i]) return a[i]<b[i];
        }
        return true;
    }
    friend bool operator == (bigint &a,int b)
    {
        int i;
        for (i=1;i<20;i++)
        {
            if (a[i]!=0) return false;
        }
        return (a[0]==b);
    }
    void operator = (int b)
    {
        memset(a,0,sizeof(a));
        a[0]=b;
    }
    friend bigint operator + (const bigint &a,bigint &b)
    {
        int i;
        bigint c=a;
        for (i=0;i<20;i++)
        {
            c[i]+=b[i];
            if (c[i]>=10000)
            {
                c[i+1]++;
                c[i]-=10000;
            }
        }
        return c;
    }
    friend bigint operator - (const bigint &a,bigint &b)
    {
        int i;
        bigint c=a;
        for (i=0;i<20;i++)
        {
            c[i]-=b[i];
            if (c[i]<0)
            {
                c[i+1]--;
                c[i]+=10000;
            }
        }
        return c;
    }
    friend bigint operator * (bigint &a,bigint &b)
    {
        bigint c;
        int i,j;
        for (i=0;i<20;i++)
        {
            for (j=0;i+j<20;j++)
            {
                c[i+j]+=a[i]*b[j];
                c[i+j+1]+=c[i+j]/10000;
                c[i+j]%=10000;
            }
        }
        return c;
    }
    friend bigint operator * (const bigint &a,int b)
    {
        int i;
        bigint c=a;
        int g=0;
        for (i=0;i<20;i++)
        {
            long long t=(long long)c[i]*b+g;
            c[i]=t%10000;
            g=t/10000;
        }
        return c;
    }
    friend bigint operator << (bigint &a,int b)
    {
        int i;
        bigint c;
        for (i=b;i<20;i++)
        {
            c[i]=a[i-b];
        }
        for (;i-b<=20;i++)
        {
            if (a[i-b]>0) c[20]=-1;
        }
        return c;
    }
    friend bigint operator / (bigint a,bigint &b)
    {
        int i;
        bigint c;
        bigint b10=b*10;
        bigint b100=b*100;
        bigint b1000=b*1000;
        for (i=20;i>=0;i--)
        {
            bigint temp=b1000<<i;
            if (temp[20]!=-1)
            {
                for (;temp<=a;a=a-temp) c[i]+=1000;
            }
            temp=b100<<i;
            if (temp[20]!=-1)
            {
                for (;temp<=a;a=a-temp) c[i]+=100;
            }
            temp=b10<<i;
            if (temp[20]!=-1)
            {
                for (;temp<=a;a=a-temp) c[i]+=10;
            }
            temp=b<<i;
            if (temp[20]!=-1)
            {
                for (;temp<=a;a=a-temp) c[i]+=1;
            }
        }
        return c;
    }
    friend bigint operator % (bigint a,bigint &b)
    {
        int i;
        bigint c;
        bigint b10=b*10;
        bigint b100=b*100;
        bigint b1000=b*1000;
        for (i=20;i>=0;i--)
        {
            bigint temp=b1000<<i;
            if (temp[20]!=-1)
            {
                for (;temp<=a;) a=a-temp;
            }
            temp=b100<<i;
            if (temp[20]!=-1)
            {
                for (;temp<=a;) a=a-temp;
            }
            temp=b10<<i;
            if (temp[20]!=-1)
            {
                for (;temp<=a;) a=a-temp;
            }
            temp=b<<i;
            if (temp[20]!=-1)
            {
                for (;temp<=a;) a=a-temp;
            }
        }
        return a;
    }
    void output()
    {
        int i;
        for (i=19;i>0;i--)
        {
            if (a[i]!=0) break;
        }
        printf("%d",a[i]);
        for (i--;i>=0;i--)
        {
            printf("%04d",a[i]);
        }
    }
};
bigint gcd(bigint x,bigint y)
{
    if (y==0) return x;
    return gcd(y,x%y);
}
struct fenshu
{
    bigint zi;
    bigint mu;
    fenshu ()
    {
        zi=0;
        mu=1;
    }
    fenshu (int x,int y)
    {
        zi=x;
        mu=y;
    }
    fenshu (bigint x,bigint y)
    {
        zi=x;
        mu=y;
    }
    friend fenshu operator + (fenshu &a,fenshu &b)
    {
        fenshu c(a.zi+b.zi,b.mu);
        return c;
    }
    friend fenshu operator * (fenshu &a,fenshu &b)
    {
        return fenshu(a.zi*b.zi,a.mu*b.mu);
    }
};
char a[45];
int main()
{
    freopen("casino.in","r",stdin);
    freopen("casino.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    int k,c,l;
    scanf("%d%d%d",&k,&c,&l);
    int i;
    for (i=0;i<n;i++)
    {
        int j;
        scanf("%s",a);
        for (j=0;j<m;j++)
        {
            cnt[i][a[j]]++;
            cnt[i]['*']++;
        }
    }
    fenshu sum;
    for (i=0;i<c;i++)
    {
        scanf("%s",a);
        fenshu t;
        t.zi=1;
        t.mu=1;
        int j;
        for (j=0;j<n;j++)
        {
            fenshu x=fenshu(cnt[j][a[j]],m);
            t=t*x;
        }
        int ward;
        scanf("%d",&ward);
        t.zi=t.zi*ward;
        sum=sum+t;
    }
    if (sum.mu<=sum.zi)
    {
        sum.zi=sum.zi-sum.mu;
        bigint t=gcd(sum.zi,sum.mu);
        sum.zi=sum.zi/t;
        sum.mu=sum.mu/t;
        sum.zi.output();
        printf("/");
        sum.mu.output();
        if (sum.zi==0)
        {
            printf("\n0\n");
        }
        else
        {
            printf("\n1\n1\n");
        }
    }
    else
    {
        printf("0/1\n0\n");
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter