首页 > 其他分享 >P1668 题解

P1668 题解

时间：2024-02-28 15:25:17浏览次数：12  
标签：ch P1668 int 题解 void read while inline

两种做法。

一、最短路

题目要求区间数量最小。如果能建出图来，就可以转换为最短路问题。

具体地，我们从 \(l-1\to r\) 连一条长度为 \(1\) 的边，意味着要多经过 \((l-1,r]\) 这一个区间。这是左开右闭的形式。

现在还有一个问题：通过这种边我们只能到达区间的右端点，如果想向左到达区间内部的其他点或者到达另一个区间，该怎么办呢？

我们可以对于 \(i\in[1,T]\)，从 \(i\to i-1\) 连一条长度为 \(0\) 的边，这样既可以向左移动，又不会算错答案（显然点的移动不会增加新的区间）。

然后求 \(0\) 到 \(T\) 的最短路即可（因为左开右闭）。

注意到边权只有 \(0,1\) 两种取值，所以可以使用 01BFS。时间复杂度 \(O(T+n)\)。

代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define gt getchar
#define pt putchar
typedef long long ll;
const int N=1e6+5;
using namespace std;
using namespace __gnu_pbds;
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
	x=0;bool sgn=0;char ch=gt();
	while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
	while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
	if(sgn) x=-x;
}
template<class T,class ...T1> inline void read(T &x, T1 &...x1){
	read(x);
	read(x1...);
}
template<class T> inline void print(T x){
	static char st[70];short top=0;
	if(x<0) pt('-');
 	do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top) pt(st[top--]);
}
template<class T> inline void printsp(T x){
	print(x);
	putchar(' ');
}
template<class T> inline void println(T x){
	print(x);
	putchar('\n');
}
inline void put_str(string s){
	int siz=s.size();
	for(int i=0;i<siz;++i) pt(s[i]);
	printf("\n");
}
struct edge{
	int to,nxt,w;
}e[N<<1];
int head[N],cnt,n,T,dis[N];
deque<int>dq;
inline void add_edge(int f,int t,int w){
	e[++cnt].to=t;
	e[cnt].w=w;
	e[cnt].nxt=head[f];
	head[f]=cnt;
}
inline void BFS_01(int s){
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[s]=0;
	dq.push_back(s);
	while(dq.size()){
		int u=dq.front();
		dq.pop_front();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(w) dq.push_back(v);
				else dq.push_front(v);
			}
		}
	}
}
signed main(){
	read(n,T);
	for(int i=1;i<=T;++i) add_edge(i,i-1,0);
	for(int u,v,i=1;i<=n;++i){
		read(u,v);
		add_edge(u-1,v,1);
	}
	BFS_01(0);
	println(dis[T]==0x3f3f3f3f?-1:dis[T]);
	return 0;
}

现在加强一下，\(T\) 开到 \(10^9\)，怎么办？

注意到区间长度统一缩小后对答案没有影响，因此考虑离散化。

细节：注意我们是要从 \(l-1\to r\) 连边，所以应将 \(l-1\) 和 \(r\) 离散化（而不是 \(l\)）！并且，起点 \(S=0\) 和终点 \(T\) 也需要离散化，然后跑最短路时直接使用离散化后的结果。

时间复杂度 \(O(n\log n)\)，瓶颈在于离散化。

代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define gt getchar
#define pt putchar
typedef long long ll;
const int N=1e6+5;
using namespace std;
using namespace __gnu_pbds;
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
	x=0;bool sgn=0;char ch=gt();
	while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
	while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
	if(sgn) x=-x;
}
template<class T,class ...T1> inline void read(T &x, T1 &...x1){
	read(x);
	read(x1...);
}
template<class T> inline void print(T x){
	static char st[70];short top=0;
	if(x<0) pt('-');
 	do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top) pt(st[top--]);
}
template<class T> inline void printsp(T x){
	print(x);
	putchar(' ');
}
template<class T> inline void println(T x){
	print(x);
	putchar('\n');
}
inline void put_str(string s){
	int siz=s.size();
	for(int i=0;i<siz;++i) pt(s[i]);
	printf("\n");
}
struct edge{
	int to,nxt,w;
}e[N<<1];
int head[N],cnt,n,T,dis[N],lsh[N<<1],tot,u[N],v[N];
deque<int>dq;
inline void add_edge(int f,int t,int w){
	e[++cnt].to=t;
	e[cnt].w=w;
	e[cnt].nxt=head[f];
	head[f]=cnt;
}
inline void BFS_01(int s){
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[s]=0;
	dq.push_back(s);
	while(dq.size()){
		int u=dq.front();
		dq.pop_front();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(w) dq.push_back(v);
				else dq.push_front(v);
			}
		}
	}
}
signed main(){
	read(n,T);
	int S=0;
	lsh[++tot]=S;
	for(int i=1;i<=n;++i){
		read(u[i],v[i]);
		lsh[++tot]=u[i]-1,lsh[++tot]=v[i];
	}
	lsh[++tot]=T;
	sort(lsh+1,lsh+tot+1);
	tot=unique(lsh+1,lsh+tot+1)-(lsh+1);
	for(int i=1;i<=n;++i){
		u[i]=lower_bound(lsh+1,lsh+tot+1,u[i]-1)-lsh;// u[i]-1
		v[i]=lower_bound(lsh+1,lsh+tot+1,v[i])-lsh; 
		add_edge(u[i],v[i],1);
	}
	S=lower_bound(lsh+1,lsh+tot+1,S)-lsh;
	T=lower_bound(lsh+1,lsh+tot+1,T)-lsh;
	for(int i=S+1;i<=T;++i) add_edge(i,i-1,0);
	BFS_01(S);
	println(dis[T]==0x3f3f3f3f?-1:dis[T]);
	return 0;
}

二、dp

考虑 DP。

设 \(f_i\) 表示 \([1,i]\) 中所有数被覆盖所需要的最小区间数。初始有 \(f_0=0\)。

记 \(mn_i\) 表示以 \(i\) 为右端点的所有区间中左端点最小值（显然长度更长的区间更优），没有则为 \(-1\)，分类讨论：

  • \(mn_i=-1\)：直接跳过。

  • \(mn_i\not=-1\)：考虑在原有基础上添加 \(i\) 所在的区间，有 \(f_i=\min_{j=mn_i-1}^{i-1}f_j+1\)

分析复杂度：最坏情况下就是区间为 \([1,...T-n+1],[1...T-n+2],....,[1,T]\)。复杂度为 \(O(\sum_{i=0}^{n-1}T-i)=O(Tn)\)，过不了。

但是由于数据水，所以能过（但是 1.2s 巨慢）。

代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define gt getchar
#define pt putchar
typedef long long ll;
const int N=1e6+5;
using namespace std;
using namespace __gnu_pbds;
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
	x=0;bool sgn=0;char ch=gt();
	while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
	while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
	if(sgn) x=-x;
}
template<class T,class ...T1> inline void read(T &x, T1 &...x1){
	read(x);
	read(x1...);
}
template<class T> inline void print(T x){
	static char st[70];short top=0;
	if(x<0) pt('-');
 	do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top) pt(st[top--]);
}
template<class T> inline void printsp(T x){
	print(x);
	putchar(' ');
}
template<class T> inline void println(T x){
	print(x);
	putchar('\n');
}
inline void put_str(string s){
	int siz=s.size();
	for(int i=0;i<siz;++i) pt(s[i]);
	printf("\n");
}
int n,T,l[N],r[N],min_l[N],f[N];
signed main(){
	read(n,T);
	memset(min_l,0x3f,sizeof(min_l));
	for(int i=1;i<=n;++i) read(l[i],r[i]),min_l[r[i]]=min(min_l[r[i]],l[i]);
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=T;++i){
		if(min_l[i]==0x3f3f3f3f) continue;
		for(int j=min_l[i]-1;j<i;++j) f[i]=min(f[i],f[j]+1);
	}
	println(f[T]==0x3f3f3f3f?-1:f[T]);
	return 0;
}

考虑优化，注意 DP 的转移方程，实际上就是一个 RMQ。再加上 \(f_i\) 的更新，也就是说我们只需要支持区间求 \(\min\)，单点修改的操作即可。用一棵线段树维护即可。时间复杂度 \(O(T\log T)\)。

求出来区间 \(\min\) 之后有一点小细节，具体见代码。

代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define gt getchar
#define pt putchar
typedef long long ll;
const int N=1e6+5;
using namespace std;
using namespace __gnu_pbds;
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
	x=0;bool sgn=0;char ch=gt();
	while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
	while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
	if(sgn) x=-x;
}
template<class T,class ...T1> inline void read(T &x, T1 &...x1){
	read(x);
	read(x1...);
}
template<class T> inline void print(T x){
	static char st[70];short top=0;
	if(x<0) pt('-');
 	do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top) pt(st[top--]);
}
template<class T> inline void printsp(T x){
	print(x);
	putchar(' ');
}
template<class T> inline void println(T x){
	print(x);
	putchar('\n');
}
inline void put_str(string s){
	int siz=s.size();
	for(int i=0;i<siz;++i) pt(s[i]);
	printf("\n");
}
int n,T,l[N],r[N],min_l[N],f[N];
struct Node{
	int l,r;
	int mn;
}node[N<<2];
inline int lson(int x){return x<<1;}
inline int rson(int x){return x<<1|1;}
inline void push_up(int p){
	node[p].mn=min(node[lson(p)].mn,node[rson(p)].mn);
}
void build(int p,int l,int r){
	node[p].l=l,node[p].r=r;
	if(l==r) return node[p].mn=0x3f3f3f3f,void();
	int mid=l+((r-l)>>1);
	build(lson(p),l,mid);
	build(rson(p),mid+1,r);
	push_up(p);
}
int query(int p,int l,int r){
	if(l<=node[p].l&&node[p].r<=r) return node[p].mn;
	int mid=node[p].l+((node[p].r-node[p].l)>>1);
	if(r<=mid) return query(lson(p),l,r);
	if(l>mid) return query(rson(p),l,r);
	return min(query(lson(p),l,r),query(rson(p),l,r));
}
void update(int p,int x,int k){
	if(node[p].l==node[p].r) return node[p].mn=k,void();
	int mid=node[p].l+((node[p].r-node[p].l)>>1);
	if(x<=mid) update(lson(p),x,k);
	else update(rson(p),x,k);
	push_up(p);
}
signed main(){
	read(n,T);
	memset(min_l,0x3f,sizeof(min_l));
	for(int i=1;i<=n;++i) read(l[i],r[i]),min_l[r[i]]=min(min_l[r[i]],l[i]);
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	build(1,0,T);
	update(1,0,0);
	for(int i=1;i<=T;++i){
		if(min_l[i]==0x3f3f3f3f) continue;
		f[i]=query(1,min_l[i]-1,i-1);
		if(f[i]!=0x3f3f3f3f) f[i]++;
		update(1,i,f[i]);
	}
	println(f[T]==0x3f3f3f3f?-1:f[T]);
	return 0;
}

应该也可以离散化。

标签：ch,P1668,int,题解,void,read,while,inline
From： https://www.cnblogs.com/syzqwq/p/18040516

相关文章

  • P1266 速度限制 题解
    考虑分层图。把图按速度分成\(V\)层，\(f_{i,j}\)表示点\(i\)在第\(j\)层（速度为\(j\)）的编号。注意：这里的速度为\(j\)是指到达\(i\)那一条边的速度（\(i\)为终点）。考虑一种naive的建边方式：首先，记当前点为\(u\)，速度为\(i\)；\(u\)的出边速度为\(j\)，长度为\(l\)，终点......
  • ABC302 Ex 题解
    首先我们考虑\(v\)固定怎么做。实际上就是ARC111B。考虑建图，对每个\((a_i,b_i)\)建一条无向边，那么问题就变成了：对于每条边都要选择它以及其连接的一个点，最大化选出的点数。很明显可以对每个连通块分开考虑。记当前连通块的点数为\(V\)，边数为\(E\)。那么有结论：该连通块对......
  • ABC301 Ex 题解
    题意：你有一张无向连通图，定义\(d(s,t)\)表示从\(s\)到\(t\)所有路径中最大边权的最小值。现在给你三个数\(A_i,S_i,T_i\)，让你求出当\(A_i\)这条边的边权\(+1\)时，\(d(S_i,T_i)\)会增加多少。首先考虑一下\(A_j+1\)什么时候会对\(d(S_j,T_j)\)有影响。\(A_j>d(S_......
  • 第五届图灵杯中级组题解
    网址赛时得分\(25+50+5+1=81\)，rk67，逊死了。赛后发现T1爆搜+剪枝有\(50\)分，我【】【】。总结：还是菜。A.等差数列首先特判\(n\le4\)的情况。此时答案必然为Yes，只需要两两分组即可。由于第一个数必然在其中一个等差数列内，不妨强制令其在第一个等差数列内。考虑......
  • CF351D - Jeff and Removing Periods 题解
    首先做一点显然的转化：在进行第一次操作之后，可以将相同的数排在一起，这样一次就能删掉一种数。如果一开始就能删光一种数的话，那么次数就是区间颜色数，否则就是区间颜色数\(+1\)。所以现在原问题变成了两个问题：求区间内不同颜色数，判断区间内是否有某种颜色满足其出现位置构成等差数......
  • P9755 [CSP-S 2023] 种树 题解
    首先考虑如何求出第\(i\)棵树在\([l,r]\)时间段能长多高。这个东西可以差分一下然后等差数列求和。放一下代码：inlinelllcalc(inti,intx){ if(c[i]>=0){ return(lll)b[i]*x+(lll)c[i]*x*(x+1)/2; }else{ intd=(b[i]-1)/(-c[i]); if(x<=d)return(lll)b[i]*x+(l......
  • A-E题解
    A：对于任意一个满足条件的2*2矩阵，要么3个R和1个W，要么3个W和1个R。我们以3个R和1个W举例，只有以下4中情况满足：RR   RR   RW   WRRW  WR  RR   RR所以一种构造方法如下：奇数行全部放R；偶数行奇数列放R，偶数列放W即可。voidsolve(){intn;......
  • CF756D Bacterial Melee 题解
    给一个\(O(n^2)\)的做法。考虑从左到右扫描最终得到的字符串，如果当前的字符和前一个字符相同，就删掉这个字符。由题意可知，最终得到的字符串一定是\(s\)的一个子序列。我们定义状态\(dp[i][j]\)表示：当前子序列的最后一个字符是\(s[i]\)，已经填完了最终字符串的前\(j\)个字......
  • CF1034E Little C Loves 3 III 题解
    这道题与P6097【模板】子集卷积基本相同，但是每个元素的值属于\([0,3]\)，且\(n\le21\)，时限\(\rm1s\)。在做P6097这道题的时候，我们多开了一维用来记录二进制下\(1\)的个数。但是这道题每个元素的值只属于\([0,3]\)，我们可以用一种十分巧妙的方法：我们设\(f(x)\)表示\(......
  • P2065 [TJOI2011] 卡片 题解
    看大家建图时中间都连了质数点，发一个不用质数点的解法。我们可以先从源点向每一个蓝色卡片对应的点连一条边，再从每一个红色卡片对应的点向汇点连一条边。如果两张卡片可以一起拿走，那就在它们之间连一条边（蓝色连到红色），这些边的最大流量都是\(1\)。建好图以后我们就可以直接用Di......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99