2020 Multi-University Training Contest 4部分补题
1002 Blow up the Enemy
Blow up the Enemy
题意
张三和儿子选择武器与之对战，张三对每样武器的选择概率同等，求儿子胜出的概率
思路
儿子选择武器肯定选择价值最大的武器，张三如果不选择一样的武器那么在相同次数内就会输，那么有k个最快的武器，则儿子输的概略为k/(2n),儿子赢的概率为1-k/(2n);
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
int sum[100010];
int main()
{
int t,n,i,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
sum[i]=(100-a)/a*b;
if(100%a)
sum[i]+=b;
}
sort(sum+1,sum+1+n);
int ma=sum[1];
int k=1;
for(i=2;i<=n;i++)
{
if(sum[i]==ma)
k++;
}
double cnt=1-1.0*k/(2*n);
printf("%lf\n",cnt);
}
return 0;
}
|
1005 Equal Sentences
Equal Sentences
题意
对于句子s中的单词，向前移一位或向后移一位或没交换得到的两个句子几乎相等，求不同句子的几乎等于s的个数。
思路
将第i个元素进行交换或者不交换，如果交换的字符串相等，即还为原来的值，否则dp[i]=dp[i]+dp[i-2];
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| //使用杭电提交语言选择g++,c++显示编译错误
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int dp[100010];
string s[100010];
int main()
{
int t,i;
cin>>t;
while(t--)
{
int n;
cin>>n;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
cin>>s[i];
}
dp[0]=1;
dp[1]=1;
for(i=2;i<=n;i++)
{
dp[i]=dp[i-1];
if(s[i]!=s[i-1])
{
dp[i]=(dp[i]+dp[i-2])%1000000007;
}
}
cout<<dp[n]<<endl;
}
return 0;
}
|
1011 Kindergarten Physics
Kindergarten Physics
题意
有两个重a,b千克的物体，初始距离为d,在只受重力的影响下，求他们之间距离。
思路
可知距离不变，直接输出初始距离即可
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int a,b,d,t0;
scanf("%d%d%d%d",&a,&b,&d,&t0);
printf("%d\n",d);
}
return 0;
}
|