勇攀山丘小队（翻越篇）2——题解

Merge-Change230 / 2024-09-27 / 原文

前言

胸有丘壑，气吞山河。

正片

A 题

思路其实很简单，当你以当前位置在 $i$，油量为 $p$ 的地方开到了位置为 $j$，且 $p_{j+1}-i>p$ 时，你肯定走不了了。因此你应当在 $i$ 到 $j$ 找到能加油最多的加油站来进行加油。

需要动态维护这个最大值的数据结构我们可以利用堆来实现。

那过程就非常简单了，只用走不了时就加一次油即可。

AC code

#include<iostream>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=2e6+100;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
inline void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void wt(int x,char ch){
	write(x);
	putchar(ch);
}
int n,l,p;
int ans;
struct Node{
	int d,w;
	bool operator<(const Node &w) const{
		return d<w.d;
	}
}a[N];
bool cmp(Node a,Node b){return a.w<b.w;}
priority_queue<Node> q;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].d;
	cin>>l>>p;
	for(int i=1;i<=n;i++) a[i].w=l-a[i].w;
	sort(a+1,a+n+1,cmp);
	int i=1;
	while(p<l){
		while(a[i].w<=p&&i<=n) q.push(a[i++]);
		if(q.size()) p+=q.top().d,ans++,q.pop();
		else{cout<<"-1";return 0;}
	}
	cout<<ans<<'\n';
	return 0;
}

B 题

看见 $n\le 5000$ 直接想到 $O(n^2)$ 好吧。

定义 $f_i$ 表示 $i$ 包括本身分解以及其余的合法分解数量总和。

初始化显然是：$f_0=1$。

想一下，$i$ 枚举每个取值，从 $1$ 到 $n$。那么在内层中枚举 $j$，从 $i+1$ 到 $n$。每次 $j$ 都可以在 $i$ 的基础上增加一个数来凑齐，所以就有了转移方程：

\[f_j=f_j+f_{j-i}(1\le i < j \le n) \]

注意 $f_n$ 记得要 -1（不懂看定义）。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+100,mod=19930125;
int n,f[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n;
	f[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++) f[j]=(f[j]+f[j-i])%mod;
	}
	cout<<f[n]-1<<"\n";
	return 0;
}