AT ABC193D
题目描述
1到9每种牌各有k张,T和A各得到5张,其中4张明确,1张不明确,求T获胜的概率。
解题思路
1.结果为T获胜的情况数除(9k-8)*(9k-9)。
2.数据范围很小,可以直接枚举T和A的第五个数,计算T和A的分数。
3.若T的分数大,设T选i,A选j,则对结果的贡献为i的个数乘j的个数,但若i=j,则则对结果的贡献为i的个数乘(j的个数-1)。
AC代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; ll calc(string a){ int tmp[10]; for(int i=1;i<=9;i++) tmp[i]=i; for(int i=0;i<a.size();i++){ tmp[a[i]-'0']*=10; } ll ans=0; for(int i=1;i<=9;i++) ans+=tmp[i]; return ans; } int main() { ll k; ll cnt[10]; string a,b; cin>>k>>a>>b; for(int i=1;i<=9;i++) cnt[i]=k; for(int i=0;i<a.size();i++) cnt[a[i]-'0']--; for(int i=0;i<b.size();i++) cnt[b[i]-'0']--; ll ans=0; for(int i=1;i<=9;i++){ for(int j=1;j<=9;j++){ a.back()='0'+i; b.back()='0'+j; if(calc(a)<=calc(b)) continue; ans+=cnt[i]*(cnt[j]-(i==j)); //这里会爆int,cnt可以开ll } } ll sheng=9*k-8; cout<<1.0*ans/sheng/(sheng-1)<<endl; return 0; }
无论是题目,思路还是标程都太精妙了,太精妙了吧!