2021年度训练联盟热身训练赛第五场
Binary Seating
题意：
有两个房间0和1，你监考1号房间，学生任选一个房间去做题，每个人做题的时间都是确定的，结束监考的时间是你所在房间最后一个人写完了题，因为你急着回家玩，所以就问你回去的时间的期望是多少
思路1:
就当作高中二项分布来做
就需要计算每种 t 对应的概率
假设给定的每个人的时间是 1 2 2 2 3 6 7
我们计算时间为 2 时的概率：
比 2 少的随意他选哪个都行，而比他大的必须选0号房间，这样才能保证答完题的时间是 2 ，同时 三个2 至少有一个2得选，也就是有
其他的概率同上
最后只想要求 概率和时间乘积的和即可
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 200 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n;
double tr[100];
double ans;
double quick_pow(ll a, ll x){//快速幂，我也不知道我当时为什么要用快速幂（手动狗头
double ans = 1;
while (x > 0) {
if(x & 1){
ans *= a;
}
a *= a;
x >>= 1;
}
return ans;
}
int main(){
io;
cin>>n;
double cnt = 0, k;
for(int i = 1; i <= n; ++i){
cin>>tr[i];
}
sort(tr + 1, tr + 1 + n);//排序
ll l, r;
for(ll i = 1; i <= n; ++i){//找到找到有相同数的左右区间
l = lower_bound(tr + 1, tr + 1 + n, tr[i]) - tr;
r = upper_bound(tr + 1, tr + 1 + n, tr[i]) - tr - 1;
k = (quick_pow(2, r - l + 1) - 1) / quick_pow(2, n - l + 1);
cnt += (k * tr[i]);
i = r;
}
cout<<cnt<<endl;
return 0;
}
思路2:
我的思路太蠢了，其实还可以直接扫一遍区间，去计算每个时间贡献的期望值，同样的，对于时间 tr[i] ，他自己得选，他前面的随意，后面的不选，每个数贡献的期望就是：
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int dat[105];
int main()
{
int n;
double mi;
double ans=0;
cin>>n;
mi=pow(0.5,n);
for(int i=1;i<=n;++i)
{
cin>>dat[i];
}
sort(dat+1,dat+1+n);
for(int i=1;i<=n;++i)
{
ans+=mi*pow(2,i-1)*dat[i];
}
cout<<ans<<endl;
return 0;
}
B Cutting Corners
题意：
开始没读懂题，后来才发现是个水题，直接输出
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int main(){
int n, m;
cin>>n>>m;
int cnt = sqrt(n * n + m * m);
double ans = sqrt(n * n + m * m);
if(ans == cnt)cout<<n + m - ans<<endl;
else
printf("%.9lf\n",n + m - ans);
return 0;
}
C Ducky Debugging
题意：
乱七八糟的说了一堆，其实只需要判断输入的字符串的最后一个字符是什么即可
如果是 . 就输出*Nod*
如果是 ? 就输出Quack!
其他的就不输出
#include <bits/stdc++.h>
using namespace std;
string s;
int len;
int main()
{
while(getline(cin, s))
{
len = s.size();
if(s[len - 1] == '?') printf("Quack!\n");
else if(s[len - 1] == '.') printf("*Nod*\n");
else break;
}
return 0;
}
E Figure Skating
题意：
给出两个榜，第一个是预测的，第二个是真正的，问你谁的真实成绩高于预测成绩的值最大，如果没有答案，就输出suspicious，如果最大差值出现相等的情况，就输出真正排名靠前的那个人的名字
思路：
用map来映射名字与排名，然后按题意模拟即可
#include <bits/stdc++.h>
using namespace std;
map<string, int> mp;
string ar[1050];
struct node
{
int a, b;
string c;
int cx;
}br[1050];
int n, no;
string s;
bool flag;
bool cmp(node c, node d)
{
if(c.cx != d.cx) return c.cx < d.cx;
else return c.b < d.b;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
cin >> ar[i];
mp[ar[i]] = i;
br[i].a = i;
br[i].c = ar[i];
}
for(int i = 1; i <= n; ++i)
{
cin >> s;
no = mp[s];
br[no].b = i;
br[no].cx = br[no].b - br[no].a;
if(br[no].cx != 0) flag = 1;
}
if(!flag) printf("suspicious\n");
else
{
sort(br + 1,br + n + 1, cmp);
cout << br[1].c << '\n';
}
return 0;
}
I Jam-packed
题意：
n个罐子，无限个能装k个罐子的箱子，问n个罐子都装进去的前提下，k个箱子中装的最少的罐子数最多是多少？
思路：
比赛的时候脑子坏掉了，被这个签到题卡死了(╥﹏╥)
先算出最少需要多少个罐子，也就是
则装的最少的罐子数最多为
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 200 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int main(){
ll n, m;
cin>>n>>m;
if(n <= m)cout<<n<<endl;
else {
ll k = (n + m - 1) / m;
cout<<n / k<<endl;
}
return 0;
}
还有一个H题，6换9，9换6 的题，和上个周Code Jam差不多，我写了个大模拟，debug一晚上，到死都还有百分之十五的数据能hack我，艹
