ReMind

Recent Writing

See 247 more →

2023睿抗省赛C

6 min read

题意

在某个游戏中有一个骰子游戏。在游戏中，你需要投掷 5 个标准六面骰子（骰子为一个正方体，6 个面上分别有1、2、3、4、5、6中的一个数字，骰子的质量均匀），投出的点数根据组合会获得一个“获胜等级”。获胜等级从高到低如下：

  • 五个同点数 - 五个骰子显示相同的点数
  • 四个同点数 - 四个骰子显示相同的点数
  • 葫芦 - 一对和一个三个同点数（如1、1、3、3、3）
  • 六高顺子 - 投出的点数为 2、3、4、5、6
  • 五高顺子 - 投出的点数为 1、2、3、4、5
  • 三个同点数 - 三个骰子显示相同的点数（如1、1、1、2、3）
  • 两对 - 投出的点数中有两对是相同的（如 1、1、2、2、3）
  • 一对 - 投出的点数有一对是相同的（如 1、1、2、3、4）
  • 无 - 除去以上的其他情况

要选择任意骰子重投一次，要在重投后获得更好的等级的概率最大，要选择多少骰子？如果概率相同，选择更少的骰子

输入样例

3
1 1 2 2 3
1 1 2 3 4
1 1 1 2 3

输出样例

3 4 9
3 13 18
2 4 9

题解

不可能是每种等级有固定方案的

一共才5个骰子，n^2的级别也才25加5次询问

那关键就是，要怎么算概率

首先确定成功条件，写check函数来将当前情况分级，每次改动之后就查看是否到达更高的级别

每个位置的更改只有5种可能，一共5个位置，可以用DFS暴搜所有的可能更改，因为修改还有数量限制，所以DFS退出条件应该修改过的骰子数量，如果改完后级别更高，就记录

那么概率怎么算？ 每次多修改一个骰子的分母会乘上6

每次修改的分子会是修改该数量骰子后，DFS成功达到高级别的次数，也就是只要记录下成功的次数，就可以得到该方案的概率

此时要用到状态压缩，因为修改的数量相同，修改位置不同属于不同的方案，首先要遍历不同数量，再状态压缩该数量下遍历不同的方案，记录修改的位置（数组存储），用这些位置DFS对原数组进行修改（改到新数组里），每次修改后判别是否到达下一级别，是就 cnt++

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 7;
 
int a[N], b[N], n = 5;
 
struct ANS {
    int x, y, cnt;
};
 
ANS ans;
int cnt, p;
vector<int> v;
 
int check(int a[])
{
    map<int, int> mp;
    for(int i = 1; i <= n; i ++)
    {
        mp[a[i]] ++;
    }
 
    if((int)mp.size() == 1) return 1;
 
    if((int)mp.size() == 2)
    {
        for(auto y: mp)
        {
            if(y.second == 4) return 2;
            if(y.second == 3) return 3;
        }
    }
 
    if((int)mp.size() == 5)
    {
        if(!mp.count(1)) return 4;
        else if(!mp.count(6)) return 5;
    }
 
    if((int)mp.size() == 3)
    {
        for(auto y: mp)
        {
            if(y.second == 3) return 6;
            if(y.second == 2) return 7;
        }
    }
 
    if((int)mp.size() == 4)
        return 8;
    
    return 9;
}
 
void dfs(int now)
{
    //要修改的数达到要求了
    if(now == (int)v.size())
    {
        if(check(b) < p) ++ cnt;
        return;
    }
 
    for(int i = 1; i <= 6; ++ i)
    {
        b[v[now]] = i;
        //遍历所有的修改方法
        dfs(now + 1);
    }
}
 
void solve()
{
    for(int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
    }
 
    //重置答案
    ans = {0, 0, 0};
    p = check(a);
    if(p == 1)
    {
        cout << 0 << ' ' << 0 << ' ' << 1 << endl;
        return;
    }
 
    //分母
    int q = 1;
    for(int k = 1; k <= n; ++ k)
    {
        //分母先乘上6
        q *= 6;
        //ans通分
        ans.x *= 6, ans.y *= 6;
 
        for(int i = 0; i < 1 << n; ++ i)
        {
            if(__builtin_popcount(i) != k)
                continue;
            v.clear();
            //存放修改这些位置，达到更高级别的分子
            cnt = 0;
            for(int j = 1; j <= 5; ++ j)
            {
                //重置赋值b为a
                b[j] = a[j];
            }
 
            for(int j = 0; j < 5; ++ j)
            {
                //记录要修改的位置
                if(i >> j & 1)
                {
                    v.push_back(j + 1);
                }
            }
 
            dfs(0);
 
            //如果分母为0，直接赋值
            if(ans.y == 0) ans = {cnt, q, k};
            else 
            {
                if(cnt > ans.x)
                {
                    ans = {cnt, q, k};
                }
            }
            //而且从小到大遍历k，同样大小的分子不会更新为大的k的情况
        }
    }
 
    int g = __gcd(ans.x, ans.y);
 
    cout << ans.cnt << ' ' << ans.x / g << ' ' << ans.y / g << endl;
}
 
 
int main()
{
    int t;
    cin >> t;
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    while(t --)
    {
        solve();
    }
    return 0;
}

难度还可以，只要在于实现

Graph View