2017 计蒜之道初赛第三场 A+B

71 阅读 0 评论 47 点赞

我是靠谱客的博主体贴鸡翅，最近开发中收集的这篇文章主要介绍2017 计蒜之道初赛第三场 A+B，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在腾讯课堂的物理课上，进行了一个有趣的物理实验。

在一个长度为 LL 米的光滑轨道上，小车 A 在 00 时刻以 1mathrm{m/s}1m/s 的速度从左端出发向右运动，小车 B 在 tt 时刻以 1mathrm{m/s}1m/s 的速度从右端出发向左运动，两个小车的质量相等。假设所有碰撞都是弹性碰撞，也就是当两个小车相向碰撞时，他们各自会以原来的速度向相反的方向运动；小车和轨道两端发生碰撞时，小车会以原速度向反方向运动。

试求出 TT 时刻的时候，两个小车相距多远。

输入格式

输入三个整数 L(1 le L le 1000),L(1≤L≤1000), t(0 le t le 1000),t(0≤t≤1000), T(t le T le 1000)T(t≤T≤1000)。

输出格式

输出 TT 时刻两车之间的距离。

样例输入1

10 4 7
样例输出1

0
样例输入2

8 3 9
样例输出2

5
题解：由于T比较小，所以模拟这个过程。两个点相遇当做相遇而过，遇到边界速度反向即可。
代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int L,t,k;
int main()
{
cin>>L>>t>>k;
int l=0;
int r=L;
int lv,rv;
lv=1;
rv=-1;
for(int i=0;i<k;i++)
{
l+=lv;
if(l>=L)
{
lv=-lv;
l=L;
}
if(l<=0)
{
lv=-lv;
l=0;
}
if(i>=t)
{
r+=rv;
if(r<=0)
{
rv=-rv;
r=0;
}
if(r>=L)
{
rv=-rv;
r=L;
}
}
}
cout<<abs(r-l)<<endl;
}

不久前，腾讯推出了一款改进后的狼人杀游戏。如下是这款游戏的背景和详细规则：

很久很久以前，在莱茵河畔一座岸壁陡峭的山顶上，有一个名叫“杜斯特瓦德”的小村庄。不久前，这个小村庄每晚都会受到狼人的侵袭。每个夜晚，狼人都会在村中进行抢劫，并且会有一个村民成为这群狼人的牺牲品。然而村民们不会坐以待毙，他们试图在白天找到这些狼人并处决他们。

作为杜斯特瓦德村的长老，你需要组织村民来对抗狼人，村民包括许多有超能力的人，比如预言家可以检验一个人是否是隐藏在神民阵营的狼人、猎人可以开枪打死一名狼人。因为狼人白天隐藏的非常深，仅仅单人的行动往往不能限制狼人的行动，多人行动将会起到更好的效果。比如预言家和猎人一起行动将被检验出是狼人的“村民”直接打死，村庄将回归和平。

我们将这样的一对人所产生的战斗力记作 ww，值得注意的是，一个人可以被多次计算，比如预言家可以先后和猎人、女巫（或其他人）组合，即如果预言家和猎人的战斗力为 ww，预言家和女巫的战斗力为 w’w
′
，这三个人的战斗力之和为 w+w’w+w
′
。

不过因为经过“新月”事件，村庄贫苦破败，你需要支付一定的金额给各个被你聘用的村民，假设你邀请了k个村民，则需要 k(2n-k)k(2n−k) 块钱（nn 为村民总数），你的资金也不太足够，所以你希望资金的利用率最大，资金的利用率定义为：((被选择的人战斗力之和 // 你支付的资金))。除此之外有些人基于他们的重要性，是必须被选择的。你必须邀请他们来参加战斗（保证至少一人）。

输入格式

第一行包括两个整数 n,mn,m 分别表示 nn 个村民和有 mm 对人之间有战斗力。

接下来 mm 行，每行有三个整数 u_i,v_i,w_iu
i
,v
i
,w
i
(1 le u_i,v_i le n,(1≤u
i
,v
i
≤n, 1 le w_i le 100,1≤w
i
≤100, u_i neq v_i)u
i
≠v
i
) 表示这对人可以产生的战斗力 w_iw
i
。

接下来 nn 个数，对于第 ii 个数，00 表示第 ii 个人可参加战斗，11 表示第 ii 个人必须参加战斗（保证至少一个 11）。

对于简单版本，1 leq n leq 20,1≤n≤20, 0 le m le n(n-1)/20≤m≤n(n−1)/2；

对于中等版本，1 leq n leq 300,1≤n≤300, 0 le m le min(1000, n(n-1)/2)0≤m≤min(1000,n(n−1)/2)；

对于困难版本，1 leq n leq 400,1≤n≤400, 0 le m le min(10000, n(n-1)/2)0≤m≤min(10000,n(n−1)/2)。

输出格式

对于简单版本和中等版本，输出一个 44 位小数，表示资金利用率的最大值，结果四舍五入；

对于困难版本，输出一个 66 位小数，表示资金利用率的最大值，结果四舍五入。

样例输入1

3 1
1 2 3
1 0 0
样例输出1

0.3750
样例输入2

3 1
1 2 3
0 0 1
样例输出2

0.3333
题解：小数据因为n比较小，所以可以用二进制来表示所有可能，对于每种可能，先判断合不合法，然后计算贡献，维护最大值即可。
代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,u,v,w;
int mp[100][100];
int mus[100];
double
ans=0;
int solo(int y)
{
for(int j=0;j<n;j++)
{
if(mus[j]==1)
{
if(y&(1<<j)) continue;
return 0;
}
}
return 1;
}
void solve()
{
for(int i=0;i<(1<<n);i++)
{
double sum=0;
//
cout<<i<<" "<<solo(i)<<endl;
if(solo(i)==0) continue;
int k=0;
for(int j=0;j<n;j++)
{
if(i&(1<<j))
{
k++;
for(int p=1;p<=n;p++)
{
if(i&(1<<(p-1)))
sum+=mp[j+1][p];
}
}
}
double mx=sum/(k*(2*n-k)*1.0);
ans=max(ans,mx);
}
}
int main()
{
memset(mus,0,sizeof(mus));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
mp[u][v]=w;
}
for(int i=0;i<n;i++)
{
cin>>u;
if(u==1)
{
mus[i]=1;
}
}
solve();
printf("%.4fn",ans);
}