[破碎的状态] [-31] 100324 C
感谢@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;
}
评论 (0)