2 条题解

  • 0
    @ 2026-7-9 18:44:45
    #include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+10;
    struct node{int x,y;}a[N];
    bool cmp(node n1,node n2){return n1.x!=n2.x?n1.x<n2.x:n1.y<n2.y;}
    int c[N],id[N],dp[N],pre[N],n,m;
    void add(int x,int k,int tid)
    {
    	for(;x<=m;x+=x&-x)
    		if(k>=c[x])
    			id[x]=tid,c[x]=k;
    }
    void dfs(int x,int px,int py)
    {
    	if(pre[x])dfs(pre[x],a[x].x,a[x].y);
    	for(int i=a[x].x+1;i<=px;i++)cout<<"D";
    	for(int i=a[x].y+1;i<=py;i++)cout<<"R";
    }
    signed main()
    {
    	int k;cin>>n>>m>>k;
    	for(int i=1;i<=k;i++)cin>>a[i].x>>a[i].y;
    	a[++k]={n,m};a[++k]={1,1};
    	sort(a+1,a+k+1,cmp);
    	for(int i=1;i<=k;i++)
    	{
    		int t=a[i].y;
    		for(;t;t-=t&-t)
    			if(c[t]>=dp[i])
    				dp[i]=c[t],pre[i]=id[t];
    		dp[i]++;
    		add(a[i].y,dp[i],i);
    	}
    	cout<<dp[k]-2<<'\n';
    	dfs(pre[k],n,m);
    	return 0;
    }
    • 0
      @ 2026-3-8 9:28:25
      #include<bits/stdc++.h>
      #define int long long
      #define lowbit(x) (x&(-x))
      using namespace std;
      const int N=2e5+10;
      int n,m,q,c[N],ans;
      struct node{
      	int x,y;
      	void read(){scanf("%lld%lld",&x,&y);}
      }a[N];
      int dp[N],v[N],pos[N];
      bool cmp(node x,node y){
      	if(x.x==y.x)return x.y<y.y;
      	return x.x<y.x;
      }
      void add(int x,int e,int id){
      	for(int i=x;i<=m;i+=lowbit(i)){
      		if(e>=c[i])c[i]=e,pos[i]=id;
      	}
      }
      int ask(int x){
      	int sum=0,ps=0;
      	for(int i=x;i;i-=lowbit(i)){
      		if(c[i]>=sum){
      			sum=c[i];
      			ps=pos[i];
      		}
      	}
      	return ps;
      }
      signed main(){
      	scanf("%lld%lld%lld",&n,&m,&q);
      	for(int i=1;i<=q;i++)a[i].read();
      	sort(a+1,a+1+q,cmp);
      	a[0].x=1;a[0].y=1;
      	a[q+1].x=n;a[q+1].y=m;
      	for(int i=1;i<=q;i++){
      		int x=ask(a[i].y);
      		dp[i]=dp[x]+1;
      		v[i]=x;
      		add(a[i].y,dp[i],i);
      	}
      	int k=ask(m);printf("%lld\n",dp[k]);
      	int x=1,y=1;
      	stack<int>s;s.push(q+1);
      	int pos=k;
      	while(pos!=0){
      		s.push(pos);
      		pos=v[pos];
      	}
      	while(s.size()){
      		int i=s.top();
      		s.pop();
      		while(x<a[i].x){
      			printf("D");
      			x++;
      		}
      		while(y<a[i].y){
      			printf("R");
      			y++;
      		}
      	}
      	return 0;
      }
      
      • 1

      信息

      ID
      7969
      时间
      2000ms
      内存
      1024MiB
      难度
      8
      标签
      递交数
      15
      已通过
      6
      上传者