test20190725 夏令营测试11

2019/07/25 12:36
阅读数 40

50+80+90=220。(每题满分90)

砍树

小A在一条水平的马路上种了n棵树,过了几年树都长得很高大了,每棵树都可以看作是一条长度为a[i]的竖线段。由于有的树过于高大,挡住了其他的树,使得另一些树得不到阳光。如果有两棵树i、j,i顶端与j底端连线的倾角大于45度,我们就定义为i挡住了j。现在小A希望将一些树砍低,使得不存在挡住的情况。他想知道总共最少需要砍掉多少长度,请你来帮他计算一下。 注意,如果同一位置有两棵树的话,根据题意,我们只能将这两棵树都砍成高度为0才能保证它们不相互挡住,但是高度为0并不代表这棵树不存在。

输入格式:

第一行一个正整数n,表示有n棵树。 接下来n行,每行两个正整数p[i], a[i],表示一棵树的位置和高度。

输出格式:

输一个数,表示最少砍断多少长度

样例输入:

3 0 2 1 2 3 3

样例输出:

3

数据范围:

对于50%的数据,n≤100 对于100%的数据,n≤100000, 0<p[i], a[i]≤10000

时间限制: 1 sec 空间限制: 128MB

<hr>

开始看错题了……原来树即使砍到高度为0它还是在那。

所以排序做一下就好了。

然后因为没有特判不需要砍就WA小数据……

统计方案

小B写了一个程序,随机生成了n个正整数,分别是a[1]..a[n],他取出了其中一些数,并把它们乘起来之后模p,得到了余数c。但是没过多久,小B就忘记他选了哪些数,他想把所有可能的取数方案都找出来。你能帮他计算一下一共有多少种取数方案吗?请把最后的方案数模1000000007后输出。 小B记得他至少取了一个数。

输入格式:

第一行三个正整数n,p,c,含义如题目所述。 接下来一行有n个正整数,表示生成的n个随机数。

输出格式:

一个数,方案数模1000000007。

样例输入:

2 7 2 1 2

样例输出:

2

数据范围:

对于30%的数据,n≤16 另有30%的数据,p≤10000 对于100%的数据,n≤32, p≤10^9, c≤10^9, a[i]<p, p是质数

时间限制: 1 sec 空间限制: 128MB

<hr>

meet in the middle,折半搜索模板题.

数据中有一个点c≥p,但是根据题面这是不合法的……

游戏

Alice和Bob两个人正在玩一个游戏,游戏有很多种任务,难度为p的任务(p是正整数),有1/(2^p)的概率完成并得到2^(p-1)分,如果完成不了,得0分。一开始每人都是0分,从Alice开始轮流做任务,她可以选择任意一个任务来做;而Bob只会做难度为1的任务。只要其中有一个人达到n分,即算作那个人胜利。求Alice采取最优策略的情况下获胜的概率。

输入格式:

一个正整数n,含义如题目所述。

输出格式:

一个数,表示Alice获胜的概率,保留6位小数。

样例输入:

1

样例输出:

0.666667

数据范围:

对于30%的数据,n≤10 对于100%的数据,n≤500

时间限制: 1sec 空间限制: 128MB

题解

数据范围这么小,随便定义状态都行。

$f[i,j]$表示Alice得了$i$分,Bob得了$j$分时的概率.

题目中的最优策略是什么呢?这里指的是各种Alice的各种方案中概率的最大值.

然后就是简单的概率DP了,时间复杂度$O(n^2\log n)$.

#include<bits/stdc++.h>
#define co const
#define il inline
template<class T>T read(){
	T x=0,w=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*w;
}
template<class T>T read(T&x){
	return x=read<T>();
}
using namespace std;

co int N=501;
int n;
bool vis[N][N];
double f[N][N];

double dp(int i,int j){
	if(i>=n) return 1;
	if(j>=n) return 0;
	if(vis[i][j]) return f[i][j];
	vis[i][j]=1;
	int up=ceil(log2(n-i));
	double ans=0;
	for(int p=0;p<=up;++p){
		double sum=pow(0.5,p+2)*(dp(i+(1<<p),j)+dp(i+(1<<p),j+1))+(1-pow(0.5,p+1))*0.5*dp(i,j+1);
		ans=max(ans,sum/(1-(1-pow(0.5,p+1))*0.5));
	}
	return f[i][j]=ans;
}
int main(){
	read(n);
	printf("%lf\n",dp(0,0));
	return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部