赵一静的博客
十月集训10月18日DAY2题解
赵一静 LV11 玄仙 LV 2 @ 2024-10-18 20:04:31

模拟

The Bucket List（模拟）

思路

因为挤奶的时间范围很小，而又没有重复，所以只要用a[i]数组记录当前所需要的桶的数量。

对于每个开始时间，让a[s]+=b，表示需要用桶，对于每个结束时间，则让a[t]-=b，表示挤完奶桶在这个时间换回去了，桶的需求量减少了b。

最后再从可能的最早的时间枚举到可能的最晚的时间，寻找a数组的max值即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=1e3+10;

int a[tt];

int main(){
	freopen("blist.in","r",stdin);
	freopen("blist.out","w",stdout);
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		int s,t,b;
		cin >>s>>t>>b;
		a[s]+=b;
		a[t]-=b;
	}
	int max_n=0,cnt=0;
	for(int i=1;i<=tt;i++){
		cnt+=a[i];
		max_n=max(max_n,cnt);
	}
	cout <<max_n;
	return 0;
}

Measuring Traffic（模拟）

思路

分类讨论三种情况下所产生的影响，设当前范围为 $[x，y]$ 。

如果该路段的流量范围是 $[a，b]$ ，则 $[x，y]$ 变为 $[max(a，x)，min(b，y)]$ 。

如果该路段的增加流量范围是 $[a，b]$ ，则 $[x，y]$ 变为 $[x+a，y+b]$ 。

如果该路段的减少流量范围是 $[a，b]$ ，则 $[x，y]$ 变为 $[x-b，y-a]$ 。

我们假定初始范围为 $[-2e9,2e9]$ ，从前往后处理，即可得到最终流量范围。从后往前处理，即可得到初始流量范围，注意此时增加和相减是相反的。

代码

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int tt=110;
string s[tt];
int a[tt],b[tt];

signed main(){
	freopen("traffic.in","r",stdin);
	freopen("traffic.out","w",stdout);
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		cin >>s[i]>>a[i]>>b[i];
	}
	int l_1=-2e9,r_1=2e9;
	for(int i=n;i>=1;i--){
		if(s[i]=="on"){
			l_1-=b[i];
			r_1-=a[i];
			l_1=max(0ll,l_1);
		}else if(s[i]=="off"){
			l_1+=a[i];
			r_1+=b[i];
		}else{
			l_1=max(l_1,a[i]);
			r_1=min(r_1,b[i]);
		}
	}
	cout <<l_1<<" "<<r_1<<endl;
	int l_2=-2e9,r_2=2e9;
	for(int i=1;i<=n;i++){
		if(s[i]=="off"){
			l_2-=b[i];
			r_2-=a[i];
			l_2=max(0ll,l_2);
		}else if(s[i]=="on"){
			l_2+=a[i];
			r_2+=b[i];
		}else{
			l_2=max(l_2,a[i]);
			r_2=min(r_2,b[i]);
		}
	}
	cout <<l_2<<" "<<r_2;
	return 0;
}

贪心

Movie Festival II（贪心）

思路

这题需要用到贪心的策略，即先结束的电影先安排，这样才能看尽可能多的电影。

这题可以归类为区间问题，先按照结束时间对区间进行升序排序。用大小为 $k$ 的multiset维护电影的结束时间。

区间遍历的过程中，找multiset中最大小于当前结束时间的元素。

若找到，则可观看的电影数+1，同时更新multiset。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

bool cmp(pair<int,int> a,pair<int,int> b){
	if(a.second<b.second) return 1;
	else if(a.second>b.second) return 0;
	else{
		return a.first<=b.first;
	}
}

signed main(){
	freopen("movie.in","r",stdin);
	freopen("movie.out","w",stdout);
	int n,k;
	cin >>n>>k;
	vector<pair<int,int>> v(n);
	for(int i=0;i<n;i++){
		int a,b;
		cin >>a>>b;
		v[i]={a,b};
	}
	sort(v.begin(),v.end(),cmp);
	multiset<int> m;
	for(int i=0;i<k;i++){
		m.insert(0);
	}
	int cnt=0;
	for(auto x:v){
		auto it=m.upper_bound(x.first);
		if(it==begin(m)){
			continue;
		}
		m.erase(--it);
		m.insert(x.second);
		cnt++;
	}
	cout <<cnt;
	return 0;
}

动态规划

Dice Combinations（DP）

思路

状态表示： $cnt[i]$ 表示用 $1，2，3，4，5，6$ 可以组成和为 $i$ 的方案数。

状态计算： $cnt[i]+=cnt[i-a[j-1]]\%mod$

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e6+10;
const int mod=1e9+7;

int cnt[tt];

signed main(){
	freopen("dice.in","r",stdin);
	freopen("dice.out","w",stdout);
	int n=6,x;
	cin >>x;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		a[i]=i+1;
	}
	memset(cnt,0,sizeof cnt);
	cnt[0]=1;
	for(int i=0;i<=x;i++){
		for(int j=1;j<=n;j++){
			if(i-a[j-1]>=0){
				cnt[i]+=cnt[i-a[j-1]];
				cnt[i]%=mod;
			}
		}
	}
	cout <<cnt[x];
	return 0;
}

Minimizing Coins（DP）

思路

状态表示： $f[i]$ 表示用 $c_1，c_2，c_3，…，c_n$ 可以组成和为 $i$ 的最小方案所用的数字。

状态计算： $f[w]=min(f[w],f[w-a[i-1]]+1)$

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=1e6+10;
int f[tt];

int main(){
	freopen("coin.in","r",stdin);
	freopen("coin.out","w",stdout);
	int n,x;
	cin >>n>>x;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin >>a[i];
	}
	for(int i=0;i<=x;i++){
		f[i]=0x3f3f3f3f;
	}
	f[0]=0;
	for(int i=1;i<=n;i++){
		for(int w=a[i-1];w<=x;w++){
			f[w]=min(f[w],f[w-a[i-1]]+1);
		}
	}
	if(f[x]==0x3f3f3f3f) cout <<-1;
	else cout <<f[x];
	return 0;
}

Coin Combinations I（DP）

思路

状态表示： $cnt[i]$ 表示用 $c_1，c_2，c_3，…，c_n$ 可以组成和为 $i$ 的方案数。

状态计算： $cnt[i]+=cnt[i-a[j-1]]\%mod$

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e6+10;
const int mod=1e9+7;

int cnt[tt];

signed main(){
	freopen("coin1.in","r",stdin);
	freopen("coin1.out","w",stdout);
	int n,x;
	cin >>n>>x;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin >>a[i];
	}
	memset(cnt,0,sizeof cnt);
	cnt[0]=1;
	for(int i=0;i<=x;i++){
		for(int j=1;j<=n;j++){
			if(i-a[j-1]>=0){
				cnt[i]+=cnt[i-a[j-1]];
				cnt[i]%=mod;
			}
		}
	}
	cout <<cnt[x];
	return 0;
}

Coin Combinations II（DP）

思路

状态计算： $cnt[i]$ 表示用 $c_1，c_2，c_3，…，c_n$ 可以组成和为 $i$ 的不同有序方法方案数。

状态计算： $cnt[j]+=cnt[j-a[i]]\%mod$

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e6+10;
const int mod=1e9+7;

int a[tt];
int cnt[tt];

signed main(){
	freopen("coin2.in","r",stdin);
	freopen("coin2.out","w",stdout);
	int n,x;
	cin >>n>>x;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	cnt[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=a[i];j<=x;j++){
			cnt[j]+=cnt[j-a[i]];
			cnt[j]%=mod;
		}
	}
	cout <<cnt[x];
	return 0;
}

Removing Digits（DP）

思路

状态表示： $f[i]$ 表示从这个数字中减去一个数字的值，使得数字等于 $0$ 所需的步骤数最小。

状态计算： $f[i]=min(f[i],f[i-(res\%10))]+1)$

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	freopen("digits.in","r",stdin);
	freopen("digits.out","w",stdout);
	int n;
	cin >>n;
	vector<int> f(n+1,2e9);
	f[0]=0;
	for(int i=1;i<=n;i++){
		int res=i;
		while(res!=0){
			int op=res%10;
			f[i]=min(f[i],f[i-op]+1);
			res/=10;
		}
	}
	cout <<f[n];
	return 0;
}

十月集训10月18日DAY2题解

模拟

The Bucket List（模拟）

思路

代码

Measuring Traffic（模拟）

思路

代码

贪心

Movie Festival II（贪心）

思路

代码

动态规划

Dice Combinations（DP）

思路

代码

Minimizing Coins（DP）

思路

代码

Coin Combinations I（DP）

思路

代码

Coin Combinations II（DP）

思路

代码

Removing Digits（DP）

思路

代码

谢谢

状态

开发

支持

关于

十月集训10月18日DAY2题解

模拟

The Bucket List（模拟）

思路

代码

Measuring Traffic（模拟）

思路

代码

贪心

Movie Festival II（贪心）

思路

代码

动态规划

Dice Combinations（DP）

思路

代码

Minimizing Coins（DP）

思路

代码

Coin Combinations I（DP）

思路

代码

Coin Combinations II（DP）

思路

代码

Removing Digits（DP）

思路

代码

谢谢

状态

开发

支持

关于

登录