暑假集训D10 2023.8.3 补题

D.DnD Dice

给出分别有不同个数的 \(4,6,8,12,20\) 面骰子, \(k\) 面骰子的每个面的点数分别是 \(1~k\) .

问用上所有骰子能组合出来的情况的概率从大到小排序,如果有相同的可能性的情况,按任意顺序即可.

\(\operatorname{Solution}\)

可以将骰子两两合并,合并后的骰子大小为 \([min_a+min_b,max_a+max_b]\) , 对合成后的新骰子点数一定 \(\in [min_a+min_b,max_a+max_b]\) ,并且有 $f[i+j] = f[i] \times f[j] $. 其中 \(f[i]\) 表示某个骰子掷到 \(i\) 的概率(特别地,对于一个没有合成过的骰子,概率是 \(1\div n\),其中 \(n\) 为该骰子的面数).由于最后合成一个大骰子,某一点数 \(i\) 概率一定是所有可能的情况总数之和除以所有合并前的小骰子面数之积,所以计算概率时可以不除骰子的面数.

最后合并到只剩余一个骰子就可以了.

这道题会爆 \(long\ long\) ,需要开 \(double\).

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<double,double> PII;
PII r [1000000];
struct dice
{
	double v[10000] = {0};
	int minv;
	int maxv;
};
dice create(int x)
{
	dice t;
	for (int i = 1; i <= x; i++)
	{
		t.v[i] = 1;
	}
	t.maxv = x;
	t.minv = 1;
	return t;
}
dice add(dice a, dice b)
{
	dice t;
	t.minv = a.minv + b.minv;
	t.maxv = a.maxv + b.maxv;
	for (int i = a.minv; i <= a.maxv; i++)
	{
		for (int j = b.minv; j <= b.maxv; j++)
		{
			t.v[i + j] += a.v[i] * b.v[j];
		}
	}
	return t;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	queue<dice> q;
	int x;
	
	dice a, b, c, d, e;
	a = create(4);
	b = create(6);
	c = create(8);
	d = create(12);
	e = create(20);
	cin >> x;
	for (int i = 1; i <= x; i++)
	{
		q.push(a);
	}
	cin >> x;
	for (int i = 1; i <= x; i++)
	{
		q.push(b);
	}
	cin >> x;
	for (int i = 1; i <= x; i++)
	{
		q.push(c);
	}
	cin >> x;
	for (int i = 1; i <= x; i++)
	{
		q.push(d);
	}
	cin >> x;
	for (int i = 1; i <= x; i++)
	{
		q.push(e);
	}
	
	while (q.size() > 1)
	{
		dice a = q.front();
		q.pop();
		dice b = q.front();
		q.pop();
		dice t = add(a, b);
		q.push(t);
		// sort(res.v+res.minv,res.v+res.maxv+1,greater<int>());
		// for (int i = res.minv; i <= res.maxv; i++)
		// {
		//     cout << res.v[i] << ' ';
		// }
		// cout<<endl;
	}
	dice res = q.front();
	

	int idx =0;
	for (int i = res.minv; i <= res.maxv; i++)
	{
		r[idx++] = {res.v[i],i};
		//cout <<i<<": " <<res.v[i] << ' ';
	}
	sort(r,r+idx,greater<PII>());
	for(int i= 0;i<idx;i++)
	{
		cout<<r[i].second<<" ";
	}
	
	return 0;
}

B.Balloon Darts

如果给出三个点的坐标,如何方便地判断三点共线?

三个点构造两个向量 \(A,B\) ,向量叉积 \(|A \times B|\) = \(x_1y_2 - x_2y_1\) ,结果为 \(0\) 则说明 \(A\) 与 \(B\) 平行

最开始给出 \(k=3\) 条直线,最开始所有的点都为未匹配到直线的点.

每次递归地处理.

首先随机地选出两个点构成一条直线,然后对剩下所有未匹配的点挨个检查是否在这条线上.如果不在这条线上,则标记.

然后进入下一层循环 \(k-1\) .