Reku
0%

Codeforces Round #412 (rated, Div. 1, based on VK Cup 2017 Round 3)

Posted on Edited on In Views: Valine:

A. Success Rate 因为最后结果一定是这个最简分数的整数倍，然后这个整数倍有个下界。发现这个整数倍可以二分，验证一下就好了。比较简单。 

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
#include<bits/stdc++.h>
using namespace std;
long long a,b,p,q;
bool pan(long long x)
{
	long long fm=q*x;
	long long fz=p*x;
	if(fm-b>=fz-a&&fz>=a) return 1;
	return 0;
}
void work()
{
	cin>>a>>b>>p>>q;
	long long l=b/q+!!(b%q);
	long long r=2147483600;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(pan(mid)==0) l=mid+1;
		else r=mid;
	}
	if(pan(l)==0) cout<<-1<<endl;
	else cout<<q*l-b<<endl;
}
int main()
{
	int T;
	cin>>T;
	while(T--) work();
	return 0;
}

B. Dynamic Problem Scoring 只对于A、B都做出来的题目，并且A的分数没有B多的情况下，才有交正确程序的必要。剩下都交错误程序就可以了（或者不交）

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
#include<bits/stdc++.h>
using namespace std;
int n;
int a[130][6]={};
bool pan(int x)
{
	int cnt[6];
	int ans[6];
	for(int i=1;i<=5;i++) cnt[i]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=5;j++) if(a[i][j]!=-1) cnt[j]++;
	}
	for(int i=1;i<=5;i++)
	{
		if(a[1][i]!=-1&&a[2][i]!=-1&&a[1][i]>a[2][i]) cnt[i]+=x;
	}
	long long a1=0,a2=0;
	for(int i=1;i<=5;i++)
	{
		if(2*cnt[i]>x+n) ans[i]=500;
		else if(4*cnt[i]>x+n) ans[i]=1000;
		else if(8*cnt[i]>x+n) ans[i]=1500;
		else if(16*cnt[i]>x+n) ans[i]=2000;
		else if(32*cnt[i]>x+n) ans[i]=2500;
		else ans[i]=3000;
		if(a[1][i]!=-1) a1+=(long long)ans[i]*(250-a[1][i])/250;
		if(a[2][i]!=-1) a2+=(long long)ans[i]*(250-a[2][i])/250;
	}
	if(a1>a2) return 1;
	else return 0;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=5;j++) cin>>a[i][j];
	}
	for(int i=0;i<=120*32;i++)
	{
		if(pan(i))
		{
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
	return 0;
}

C. Prairie Partition 思考了半天，终于猜出了答案一定是连续的结论。 知道这个结论之后，就不难了。 这个最多的表示，可以贪心贪出来，然后最少的合法表示，可以二分，然后贪心验证。

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[100010];
long long t[60];
int num[60];
int num1[60];
int pp=0;
bool pan(int x)
{
	memset(num,0,sizeof(num));
	memset(num1,0,sizeof(num1));
	int u=0;
	bool bj=0;
	for(int i=1;i<=n;i++)
	{
		while(a[i]>t[u]) u++;
		if(a[i]==t[u]&&num[u]<x&&(u==0||num[u]<num[u-1]))
		{
			num1[u]++;
			num[u]++;
			if(u!=0&&num1[u]>num1[u-1]) num1[u]=num1[u-1];
			if(u!=0&&num[u]==num[u-1]) u++;
			else if(num[u]==x) u++;
		}
		else
		{
			if(num1[u-1]>0) num1[u-1]--;
			else break;
		}
		if(i==n) bj=1;
	}
	return bj;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	t[0]=1;
	for(int i=1;i<=59;i++) t[i]=t[i-1]*2ll;
	int u=0;
	bool bj=0;
	int ma=0;
	int tt=0;
	for(int i=1;i<=n;i++)
	{
		while(a[i]>t[u]) u++;
		if(a[i]==t[u]&&(u==0||num[u]<num[u-1]))
		{
			num[u]++;
			num1[u]++;
			if(u==0) ma++,tt++;
			if(u!=0&&num1[u]>num1[u-1]) num1[u]=num1[u-1];
			if(u!=0&&num[u]==num[u-1]) u++;
		}
		else
		{
			if(num1[u-1]>0) num1[u-1]--;
			else break;
		}
		if(i==n) bj=1;
	}
	if(bj==0)
	{
		cout<<-1<<endl;
		return 0;
	}
	int l=1;
	int r=tt;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(pan(mid)) r=mid;
		else l=mid+1;
	}
	for(int i=l;i<=tt;i++)
	{
		printf("%d ",i);
	}
	printf("\n");
	return 0;
}

D. Perishable Roads 思考了半天，思考到了每个博物馆一定只有一个出度，然而没卵用，之后就卡住了。 看了看别人的代码，然后自己脑补了一下，乱写了一个差不多的。 先把所有的边权减去最小的边权，方便处理，这样所有的最小边权一定为0。 然后我们可以把所有点的最差结果初始化为2最小的连向这个点的边，因为对于所有的点，最差情况下就是走两条边，然后找到了最小边，剩下的所有点的贡献就都一样了。 然后需要计算这两条边的关系，如果第二条边小于第一条边，那这两个点的贡献就是路径的长度，如果不是的话，就是2边权。 用spfa乱算一下路径长度就可以了，反正最多只走两条路，时间复杂度应该不是问题（其实一直不太清楚spfa的时间复杂度）

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
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[2010][2010];
long long d[2010];
struct pp
{
	long long s;
	int num;
} w[2010];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) a[i][i]=0;
	long long tt=2147483600;
	for(int i=1;i<=n-1;i++)
	{
		for(int j=1;j<=n-i;j++)
		{
			scanf("%lld",&a[i][i+j]);
			a[i+j][i]=a[i][i+j];
			tt=min(tt,a[i][i+j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j) a[i][j]-=tt;
		}
	}
	for(int i=1;i<=n;i++)
	{
		d[i]=2147483600;
		for(int j=1;j<=n;j++)
		{
			if(i!=j) d[i]=min(d[i],2ll*a[i][j]);
		}
	}
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		q.push(i);
	}
	while(!q.empty())
	{
		int to=q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			if(to!=i)
			{
				if(d[to]+a[to][i]<d[i])
				{
					d[i]=d[to]+a[to][i];
					q.push(i);
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		long long ans=d[i]+tt*(n-1);
		printf("%lld\n",ans);
	}
	return 0;
}