周赛好题难题总结

517周赛26期 div1晚间场第一场C题 吃饼干

题目描述

小海狸共有 $m$ 块饼干，编号从 $1$ 到 $m$。第 $i$ 块饼干需要 $a_i$ 分钟时间烘培，不需要一定连续 $a_i$ 分钟烘培一块饼干。

小海狸还有一份 $n$ 分钟的计划表，$d_i$ 表示第 $i$ 分钟小海狸能吃掉的饼干，$0$ 表示不能吃，吃饼干要花掉一分钟。

问吃掉饼干的最小分钟数，不能吃完输出 $-1$。

思路

可以二分最小分钟数，然后从二分的分钟数从后往前枚举，可以定义一个变量表示当前的剩余时间，每次看还有没有时间能做完饼干并且当前能吃，就吃掉。最后看能不能吃 $m$ 块饼干。

代码

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 <bits/stdc++.h>
using namespace std;

int n,m;
int a[100010],b[100010];
bool flag[100010];

bool check(int mi)
{
	int x=mi-1;
	for(int i=mi;i>=1;i--)
	{
		x=min(x,i-1);//更新时间，一个比较妙的细节处理。
		if(!flag[a[i]] && x>=b[a[i]] && a[i]>0) flag[a[i]]=1,x-=b[a[i]],x--;//注意x这里要多-1，吃饼干还需要时间。
	}
	int ans=0;
	for(int i=1;i<=m;i++) ans+=flag[i];
	return ans>=m;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	int l=0,r=n,best=-1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid)) best=mid,r=mid-1;
		else l=mid+1;
		for(int i=1;i<=m;i++) flag[i]=0;
	}
	printf("%d",best);
}

517周赛26期 div1晚间场第一场E题 电梯

题目描述

计算鸭在一栋有 $n$ 层的建筑物中，它可以在楼层间移动。建筑物从 $1$ 到 $n$ 从下到上编号。

计算鸭从 $a$ 楼开始出发，不能去 $b$ 楼，并且他从 $x$ 楼去 $y$ 楼需要满足 $|x - b| > |x - y|$。

问计算鸭有多少种方案可以成功乘坐 $k$ 次电梯，方案数对 $10^9 + 7$ 取模。

思路

观察题目，其实我们会发现，如果 $a > b$，计算鸭只能在 $b + 1 ~ n$ 之间移动,如果 $a < b$，则计算鸭只能在 $1 ~ b - 1$ 之间移动。

因为每一层楼与其他楼本质相同，所以我们如果发现 $a > b$，则可把整栋楼倒过来考虑，这样就只需要考虑一种情况了。

由于计算鸭可以到小于 $b$ 的任意一层楼，我们则可以设 $dp_{i k}$ 表示当前在 $i$ 位置走了 $k$ 步，所以我们就可以得出转移方程为:

1
dp[i][k]=dp[1~(i+b-1)/2][k-1];

$(i + b - 1) \div 2$ 表示能走的右端点，由于要满足 $|x - b| > |x - y|$,所以为中点。

那么直接用前缀和优化一下，答案就出来了。

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>
#pragma GCC optimize(2)
using namespace std;

const int N = 5001;
const int inf = 1e9 + 7;
void mo(int &x){while(x>inf)x-=inf;}
int dp[N][N],sum[N][N];
int n,a,b,kkk;

int main()
{
	scanf("%d%d%d%d",&n,&a,&b,&kkk);
	if(a>b) a=n-a+1,b=n-b+1;
	dp[a][0]=1;
	for(int k=1;k<=kkk;k++)
	{
		for(int i=1;i<b;i++) mo(sum[i][k-1]=(sum[i-1][k-1]+dp[i][k-1]));
		for(int i=1;i<b;i++)
		{
			mo(dp[i][k]+=sum[i-1][k-1]);
			mo(dp[i][k]+=(sum[(i+b-1)/2][k-1]-sum[i][k-1]+inf)%inf);
			
		} 
	}
	for(int i=1;i<=b;i++) mo(sum[i][kkk]=sum[i-1][kkk]+dp[i][kkk]);
	printf("%d",sum[b][kkk]);
}

517周赛26期 div1晚间场第五场E题

题目描述

给你一个 $01$ 序列，两个人轮流取数，每个人能取 $1$ ~ $2$ 个数。问你先手最少能取多少个 $1$。

注意，后手也是尽力让先手的 $1$ 个数尽量少。

思路

设 $dp_{i,0/1}$ 表示当前取到 $i$，上一个取数的人为 $0/1$。

则我们可以得到转移方程：

1
2
f[i][1]=min(f[i-1][0]+w[i],f[i-2][0]+w[i-1]+w[i]);
f[i][0]=min(f[i-1][1],f[i-2][1]);

而初始化为 

1
2
f[0][0]=0;
f[1][1]=w[1];

代码

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;

const int N=200010;
int f[N][2],w[N];

int main(){
    memset(f,0x3f,sizeof f); 
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    f[0][0]=0; 
    f[1][1]=w[1];
    for(int i=2;i<=n;i++)
    {
        f[i][1]=min(f[i-1][0]+w[i],f[i-2][0]+w[i-1]+w[i]);
        f[i][0]=min(f[i-1][1],f[i-2][1]);
    }

    cout<<min(f[n][1],f[n][0])<<endl;
	return 0;
}