CF educational round 28

发表于 | 分类于

Codeforces Educational Round 28

A. Curriculum Vitae

给定一个01序列，需要删除一些数，使得保留的数尽量多，而且满足每个0前面都不是1.

题解：贪心。首先要保证0前面都不是1，最后的序列肯定是前面一段连续的0，后面一段连续的1，那么只要枚举这个0,1的分界点然后算一下分界点前面0的个数+后面1的个数就好了。

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
 #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+1e2+7;
int n,s[N],ans,tot;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i];
	s[n+1]=1;
	for(int i=1;i<=n+1;i++)
		if(s[i]==1)	
		{
			tot=0;
			for(int j=1;j<i;j++)
				tot+=(s[j]==0);
			for(int j=i;j<=n;j++)
				tot+=(s[j]==1);
			ans=max(ans,tot);
		}	
	cout<<ans;
}

B. Math Show

给定n个任务，每个任务都包含k个子任务，每个任务的子任务都是相同的，子任务都有一个需要花费的时间，完成一个子任务会获得一分。并且对于每一个任务，如果完成了所有的k个子任务，可以获得额外的一分。给定一个总时间，问最高的得分。

题解：贪心。枚举完成了几个大任务，剩下的因为贡献都是1,贪心选取就好了。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=107;
ll n,k,m,t[N];
ll sum,ans;
int main()
{
	cin>>n>>k>>m;
	for(int i=1;i<=k;i++)
		cin>>t[i],sum+=t[i];
	sort(t+1,t+k+1);
	for(ll i=0;i<=n;i++)
	{
		ll tot=0;
		ll rem;
		if(m>=sum*i)
			rem=m-sum*i;
		else
			break;
		tot+=(k+1)*i;
		for(int j=1;j<=k;j++)
			for(int h=1;h<=n-i;h++)
				if(rem>=t[j])
					rem-=t[j],tot++;
		ans=max(ans,tot);
	}
	cout<<ans;
}

C. Four Segments

给定一个序列长度$n\leq 5000$，定义一个函数$S(i,j)$为$[i+1,j]$的和，现在要找出$0\leq a\leq b \leq c \leq n$使得$S(0,a)-S(a,b)+S(b,c)-S(c,n)$最大。

题解：考虑枚举一个分段点，剩下还有两个分段点，单调性肯定有，用双指针卡一卡就好了。但是这样写起来很麻烦。考虑可以枚举中间那个分段点，然后答案式子就变成了两段的一个前缀-后缀最大，然后只要$O(n)$枚举两边的分段点分别在哪里就可以$O(n^2)$解决了。

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
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4+1e3+7;
long long n,a[N],d0,d1,d2,sum1,sum2,s[N],ans=-1e18;
long long S(int l,int r)
{
	return s[r]-s[l];
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],s[i]=s[i-1]+a[i];
	for(int i=0;i<=n;i++)
	{
		sum1=-1e18,sum2=-1e18;
		int tmp0,tmp2;
		for(int j=0;j<=i;j++)
			if(S(0,j)-S(j,i)>sum1)
				sum1=S(0,j)-S(j,i),tmp0=j;
		for(int j=i;j<=n;j++)
			if(S(i,j)-S(j,n)>sum2)
				sum2=S(i,j)-S(j,n),tmp2=j;
		if(sum1+sum2>ans)
			ans=sum1+sum2,d0=tmp0,d2=tmp2,d1=i;
	}
	cout<<d0<<" "<<d1<<" "<<d2;
}

D. Monitor

给一个$n\times m(n,m\leq 500)$的矩阵，其中有一些方块会在$t$时间后坏掉，问最早什么时候有$k\times k$的一个正方形全部坏掉

题解：这个$t$显然符合二分的性质。考虑二分这个$t$，判断的时候我们可以把所有坏掉的变成$0$，然后只需要求全0最大子正方形。

这个满足DP的条件:
设$f[i][j]$为$(i,j)$为右下角的最大子正方形。那么有：
$$f[i][j]=min{f[i][j-1],f[i-1][j],f[i-1][j-1]}+1(a[i][j]!=0)$$
$$f[i][j]=0 (a[i][j]=0)$$

然后判断就好了

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
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=507;
int n,m,k,r[N][N],q,now[N][N],f[N][N];
bool check(int s)
{
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			now[i][j]=max(r[i][j]-s,0);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(now[i][j]>0)
				f[i][j]=0;
			else
				f[i][j]=min(f[i][j-1],min(f[i-1][j],f[i-1][j-1]))+1;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(f[i][j]>=k)
				return true;
	return false;
}
int main()
{
	cin>>n>>m>>k>>q;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			r[i][j]=1e9+7;
	for(int i=1;i<=q;i++)
	{
		int x,y,t;
		cin>>x>>y>>t;
		r[x][y]=t;
	}
	int l=-1,r=1e9+1;
	while(r-l>1)
	{
		int mid=(l+r)>>1;
		if(check(mid))
			r=mid;
		else
			l=mid;
	}
	if(!check(r))
		cout<<"-1";
	else
		cout<<r;
}

E. Chemistry in Berland

给定一些物品，有一个需求和一个当前有的量，第$2\leq i$物品都可以转化为$x<i$物品，$1:1$，或者$k:1$转化过来。询问有没有可能使所有物品都满足需求。

题解：考虑这个转化的条件，一定是一棵树的形状，所以我们可以考虑树形$dp$，考虑怎么转化，要先递归下去，如果满足不了条件可以把$dp$赋值成为$-INF$,然后根据转化比例和子节点的正负进行转化，最后只要判断$dp[1]$的正负即可。

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=100005;
const ll INF=(1LL<<60)-1;
vector<pair<int,int> > e[MAXN];
ll a[MAXN],b[MAXN],dp[MAXN];
void dfs(int u)
{
    dp[u]=b[u]-a[u];
    for(int i=0;i<(int)e[u].size();i++)
    {
        int v=e[u][i].first,r=e[u][i].second;
        dfs(v);
        if(dp[v]<0)
        {
            if(-dp[v]<INF/r)
                dp[u]+=dp[v]*r;
            else
                dp[u]=-INF;
            if(dp[u]<-INF)
                dp[u]=-INF;
        }
        else dp[u]+=dp[v];
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=2;i<=n;i++)
    {
        int x,k;
        scanf("%d%d",&x,&k);
        e[x].push_back(make_pair(i,k));
    }
    dfs(1);
    return 0*printf("%s\n",(dp[1]>=0 ? "YES" : "NO"));
}

F. Random Query

问对于序列，所有的$l,r\leq n$，区间$[min(l,r),max(l,r)]$的元素个数的期望。

题解：对于每个元素求出他上一次出现的位置，然后扫描一遍考虑所有后缀区间元素种类在这个位置和上个位置的变化，然后最后$ans\times 2-n$就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 1048576
int n, a[N],last[N];
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
  ll s=0,ans=0;
  for(int i=1;i<=n;i++)
  {
    s+=i-last[a[i]];
	last[a[i]]=i;
    ans+=s;
  }
  ans=ans+ans-n;
  double fans=(double)ans/((ll)n*n);
  printf("%.12f\n",fans);
}