AtCoder Beginner Contest 266 E(期望) F(基环树)
E - Throwing the Die(期望)
题意
掷骰子游戏,游戏有 N N N轮。每次掷骰子得到的数字就是分数,游戏可以随时终止,但不能超过 N N N轮,最后一次掷骰子得到的数字就是最终分数。给定 N N N的值,求期望分数的最大值。
分析
掷骰子得到分数的期望值与 N N N有关,用 f [ N ] f[N] f[N]表示游戏进行 N N N轮分数期望的最大值。由于题目所求的是期望的最大值,因此在第 N N N轮对于投出的每一种情况,期望值不能小于 f [ N − 1 ] f[N-1] f[N−1],可得如下状态转移方程。
f [ N ] = 1 6 ∑ i = 1 6 m a x ( i , f [ N − 1 ] ) f\lbrack N\rbrack=\frac16\sum_{i=1}^6max(i,f\lbrack N-1\rbrack) f[N]=61i=1∑6max(i,f[N−1])
AC代码
double f[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i )
{
for(int j=1;j<=6;j )
{
f[i] =max(j*1.0,f[i-1])/6;
}
}
cout<<fixed<<setprecision(6)<<f[n]<<endl;
return 0;
}
F - Well-defined Path Queries on a Namori(基环树 并查集 DFS)
题意
给定一个含有 N N N个点 N N N条边的无向连通图,问图上两个不同的点之间简单路径是否唯一。简单路径是图上不重复经过某个点的路径。
分析
根据题目中的定义可知给定的图是基环树,基环树上有且仅有一个环。如果将环上的边删去,就可以得到若干棵以环上的点为根的树。如果两个点之间的简单路径不唯一,那么这两个点之间的路径一定经过环上的边。将环断开后得到的每棵树可以看做是一个连通块,如果两个点在同一个连通块则简单路径唯一,否则不唯一。在实现时可以用并查集或者DFS,两种方法都是从度数为1的点入手,可以参考下面的代码。
AC代码
并查集
const int N=2e5 10;
vector<int> v[N];
queue<int> q;
int pa[N],in[N];
int n,m;
int find(int x)
{
return pa[x]==x?pa[x]:pa[x]=find(pa[x]);
}
void merge(int x,int y)
{
pa[find(x)]=pa[find(y)];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i ) pa[i]=i;
for(int i=1;i<=n;i )
{
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
in[x] ,in[y] ;
}
for(int i=1;i<=n;i ) if(in[i]==1) q.push(i);
while(q.size()>0)
{
int x=q.front();
q.pop();
for(auto y:v[x])
{
merge(x,y);
in[y]--;
if(in[y]==1) q.push(y);
}
}
cin>>m;
while(m--)
{
int x,y;
cin>>x>>y;
if(find(x)==find(y)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
DFS
vector<vector<int>> g;
vector<bool> is_cycle;
vector<int> root_id;
void dfs(int v, int p) {
root_id[v] = root_id[p];
for(auto to : g[v]) {
if(to != p) dfs(to, v);
}
}
int main()
{
int n;
cin >> n;
g.resize(n);
is_cycle.resize(n, true);
root_id.resize(n, -1);
vector<int> deg(n);
for(int i = 0; i < n; i ) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
deg[u] , deg[v] ;
}
queue<int> que;
for(int i = 0; i < n; i ) {
if(deg[i] == 1) {
que.push(i);
}
}
while(!que.empty()) {
int v = que.front();
que.pop();
is_cycle[v] = false;
for(auto to : g[v]) {
if(deg[to] >= 2) {
deg[to]--;
if(deg[to] == 1) {
que.push(to);
}
}
}
}
for(int i = 0; i < n; i ) {
if(is_cycle[i]) {
root_id[i] = i;
for(auto to : g[i]) {
if(!is_cycle[to]) {
dfs(to, i);
}
}
}
}
int q;
cin >> q;
while(q--) {
int u, v;
cin >> u >> v;
--u, --v;
cout << (root_id[u] == root_id[v] ? "Yes" : "No") << endl;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfecgg
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01