Atcoder Beginner Contest 144

Posted on | Views:

被 $D$ 卡了一会.

D Water Bottle

分两种情况做.

第一种情况,初始的水没有达到容器体积的一半.

第二种情况,初始的水达到了容器体积的一半.

利用反三角函数求出角度.

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const double pi=acos(-1.0);
int main()
{
	double a=(double)(read()),b=(double)(read()),x=(double)(read());
	if(x/a/a/b<0.5)
	{
		double s=x/a;
		printf("%.10lf\n",atan(b*b/2/s)/pi*180.0);
	}
	else
	{
		double s=a*b-x/a;
		printf("%.10lf\n",atan(2*s/a/a)/pi*180.0);
	}
	return 0;
}

E Gluttony

可以二分一个答案 $mx$ .

检验时,贪心去匹配,让 $a$ 最小的人去吃 $f$ 最大的食物.

限定 $a\cdot f\le mx$ ,可以算出每个人的权值至少要减少几次,判断这个总和是否超过 $k$ 即可.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
ll n,k,a[MAXN],f[MAXN];
bool check(ll mx)
{
	ll t=k;
	for(int i=1;i<=n;++i)
	{
		int j=n+1-i;
		ll x=mx/f[j];
		t-=max(0LL,a[i]-x);
		if(t<0)
			return false;
	}
	return true;
}
int main()
{
	n=read(),k=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
		f[i]=read();
	ll L=0,R=(ll)(1e12),res;
	sort(a+1,a+1+n);
	sort(f+1,f+1+n);
	while(L<=R)
	{
		ll mid=(L+R)>>1;
		if(check(mid))
			res=mid,R=mid-1;
		else
			L=mid+1;
	}
	cout<<res<<endl;
	return 0;
}

F Fork in the Road

设 $f(i)$ 表示点 $i$ 到 $n$ 的期望步数,设 $S_i={j|(i,j)\in E }$ ,则转移有
$$
f(n)=0,f(i)=\frac{1}{|S_i|} \sum_{j\in S_i} f(j)
$$
暴力做法是枚举每条边,计算出删掉它之后的答案,时间复杂度是 $O(m^2)$ 的.

其实对于所有以 $i$ 为起点的边 $(i,j)$ ,只需要贪心删去 $f(j)$ 最大的那条边去更新答案即可.

这样只用删 $O(n)$ 次边,时间复杂度 $O(nm)$ .

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const double inf=1e18;
const int MAXN=601;
vector<int> G[MAXN];
int n,m;
double f[MAXN];
double calc(int x)
{
	f[n]=0;
	for(int i=n-1;i>=1;--i)
	{
		f[i]=0;
		int siz=G[i].size();
		double mx=0;
		for(auto j:G[i])
		{
			f[i]+=f[j];
			mx=max(mx,f[j]);
		}
		if(i==x && siz>1)
			--siz,f[i]-=mx;
		f[i]/=(double)siz;
		f[i]+=1;
	}
	return f[1];
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		G[u].push_back(v);
	}
	double ans=calc(n);
	for(int i=1;i<n;++i)
		ans=min(ans,calc(i));	
	printf("%.10lf\n",ans);
	return 0;
}