2020年百度之星·程序设计大赛 - 初赛一

发表于 分类于

比赛链接

A. Drink

枚举。

B. GPA

枚举。

C. Dec

多重背包DP。

D. Civilization

难度在于读懂题目。

读懂之后就是对于每个点求，排序贪心求出答案即可。

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=505;
inline int Abs(int x) {return x>0?x:-x;}

int a[N][N],dis[N][N],x,y,n,ans;
vector<int> adj;
inline int calc(int x,int y)
{
	adj.clear();
	int nx,ny;
	fo(i,-3,+3) fo(j,-3,+3)
	if(Abs(i)+Abs(j)<=3&&!((i==0)&&(j==0)))
	{
		nx=i+x; ny=j+y;
		if(nx>0&&nx<=n&&ny>0&&ny<=n) adj.pb(a[nx][ny]);
	}
	sort(all(adj));
	adj.pb(a[x][y]);
	reverse(all(adj));
	int sum=0,now=0,cnt=0,t;
	for(t=0;cnt!=9;t++)
	{
		sum+=now;
		if(sum>=8*cnt*cnt)
		{
			if(adj.size()>cnt) now+=adj[cnt];
			cnt++;
		}
	}
	return t;
}

int main()
{
	CASET
	{
		n=read(); x=read(); y=read(); ans=1000000000;
		fo(i,1,n) fo(j,1,n) a[i][j]=read();
		fo(i,1,n) fo(j,1,n) dis[i][j]=calc(i,j);
		fo(i,1,n) fo(j,1,n)
		{
			int k=Abs(i-x)+Abs(j-y);
			k=(k+1)/2;
			ans=min(ans,k+dis[i][j]);
		}
		printf("%d\n",ans-1);
	}
	return 0;
}

E. Rotate

由于 $a_i$ 的单调性，这些黑块连成的是一个森林。

由期望的线性性，我们只需统计每一层的贡献。也就是看单独出来了多少个 $a_i$。

假设考虑到第 $i$ 层，要算和 $i+1$ 层的贡献。显然这个贡献为这一层黑色块的个数减去与上一层黑色块有交的期望个数。

与上一层黑色块有交的情况可以分为完全包含和在黑白边界上。

这一层黑色块有 $\frac{a_i}{2}$ 个。

由于是随机旋转，这一层的黑色块与上一层黑色块完全包含的期望个数=这一层的黑色块与上一层白色块完全包含的期望个数。

这一层的黑色块与上一层在黑白边界上的期望个数为 $\frac{a_{i+1}}{2}$，因为一共有 $a_{i+1}$ 个边界，每个边界上的颜色概率都是 $\frac{1}{2}$。

而这一层的黑色块与上一层黑色块完全包含的期望个数+这一层的黑色块与上一层在黑白边界上的期望个数/2= $\frac{a_{i}}{4}$

解得这个贡献就是：$\frac{a_i-a_{i+1}}{4}$。

第 $n$ 层特殊考虑，贡献是 $\frac{a_n}{2}$。

因此答案就是：$\frac{1}{4}\sum_{i=1}^n(a_i-a_{i+1})+\frac{a_n}{2}=\frac{a_1+a_n}{4}$。

1
2
3
4

n=read();
fo(i,1,n) a[i]=read();
printf("%d\n",1ll*(a[1]+a[n])/2*((mod+1)/2)%mod);

G. Mosquito

可以先二分答案，然后建二分图，将矩阵上每个点看成右边的点，左边的是 $k$ 个点。然后用网络流判定。

但这样时间复杂度是 $O(T(nm)^{1.5}\log (n+m))$ 的，过不了。

因为 $k$ 很小，考虑用Hall定理加速判定。

我们需要对右边的点看是否存在完美匹配。

也就是枚举右边的点的一个子集，然后看左边 $k$ 个点中与之相连的所有的 $a_i$ 和是否大于等于子集的大小即可。

那么枚举左边与之相连的点的集合，然后看右边的集合最大能是多少就好了，一共有 $2^6$ 中情况，集合大小可以用Bitset加速判定，时间复杂度上就是 $2^6\times \frac{nm}{64}=nm$ 的。

时间复杂度 $O(Tknm)$，精细点该做法可以实现 $O(Tnm)$。

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
int n,m,k,x[6],y[6],z[1<<6],cnt;
bitset<1000*1001> b[1<<6],ba;
inline int Abs(int x) {return x>0?x:-x;}
inline bool check(int dis)
{
	ff(t,0,1<<k) b[t].reset();
	ff(t,0,k)
	{
		fo(i,1,n) fo(j,1,m)
			if(Abs(i-x[t])+Abs(j-y[t])<=dis)
				b[1<<t][(i-1)*m+j-1]=1;
	}
	ff(t,0,1<<k)
		if(lowbit(t)!=t)
			b[t]=b[t^lowbit(t)]|b[lowbit(t)];
	ff(t,0,1<<k)
		if((b[t^cnt]^ba).count()>z[t])
			return 0;
	return 1;
}
int s;
int main()
{
	CASET
	{
		n=read(); m=read(); k=read(); s=0;
		ba.reset();
		ff(i,0,n*m) ba.set(i);
		cnt=(1<<k)-1;
		ff(i,0,k) x[i]=read(),y[i]=read(),z[1<<i]=read(),s+=z[1<<i];
		if(s<n*m)
		{
			puts("-1"); continue;
		}
		ff(i,1,1<<k) if(lowbit(i)!=i) z[i]=z[i^lowbit(i)]+z[lowbit(i)];
		int l=0,r=n+m,mid;
		for(;l<=r;)
		{
			mid=l+r>>1;
			if(check(mid)) r=mid-1;
			else l=mid+1;
		}
		printf("%d\n",l);
	}
	return 0;
}