首页 > 其他分享 >[luoguAT_abc369_f]Gather Coins

[luoguAT_abc369_f]Gather Coins

时间:2024-09-07 18:13:45浏览次数:8  
标签:Coins int Gather abc369 给定 LIS 元素 include

题意

给定 \(N\times M\) 的网格,给定 \(K\) 个二元组 \((x_1, y_1), (x_2, y_2), \cdots , (x_K, y_K)\),求从 \((1, 1)\) 到 \((N, M)\) 只向右或向下走最多可以经过多少个给定的方格,并给出一种方案。

赛时 不会

赛后

由于只能向右或向下走,因此当前所处位置 \((nowx, nowy)\) 中,\(nowx\) 和 \(nowy\) 一定都是不降的。因此,我们可以将所有给定的点按照 \(x\) 为第一关键字,\(y\) 为第二关键字升序排序(事实上,这就是 pair 的排序方法),这样,问题就转化为了 \(O(n \log n)\) 的时间复杂度求所有点的 \(y\) 的最长不降子序列(LIS)及其中一种方案。

LIS

我们记录一个单调栈,当遍历到 \(y_i\) 时,在栈中查找第一个 \(>y_i\) 的元素并用 \(y_i\) 将其替换,特别的,如果没有这样的元素,则将 \(y_i\) 压入栈中,结合二分可以做到 \(O(n \log n)\),但是这样,单调栈中记录的元素并不是可行的方案。因此,需要记录 \(y_i\) 被放入栈中时的位置 \(pos_i\),这样,只需要倒序枚举,且使得最终答案满足 \(LIS_i\) 上的元素的 \(pos\) 为 \(i\) 即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define x first 
#define y second 

using namespace std;
typedef pair<int, int> PII;

const int N = 200005;

PII points[N], p[N];
int n, m, k;
int stk[N], top = 0, po[N], len;

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i ++ ) scanf("%d%d", &points[i].x, &points[i].y);

    sort(points + 1, points + k + 1);
	
    for (int i = 1; i <= k; i ++ ){
        int pos = upper_bound(stk + 1, stk + top + 1, points[i].y) - stk;
        top = max(top, pos);
        stk[pos] = points[i].y;
        po[i] = pos;
    }
    printf("%d\n", top);

    len = top;
    for (int i = k; i; i -- ){
        if (!len) break;
        if (po[i] == len) stk[len -- ] = points[i].y;
    }

    for (int i = 1, j = 1; i <= top; j ++ )
        if (points[j].y == stk[i]) i ++ , p[i] = points[j];

    p[1] = {1, 1}, p[top + 2] = {n, m};

    for (int i = 2; i <= top + 2; i ++ ){
        for (int j = 1; j <= p[i].x - p[i - 1].x; j ++ ) printf("D");
        for (int j = 1; j <= p[i].y - p[i - 1].y; j ++ ) printf("R");
    }

    return 0;
}

标签:Coins,int,Gather,abc369,给定,LIS,元素,include
From: https://www.cnblogs.com/XiaoJuRuoUP/p/-/luoguAT_abc369_f

相关文章

  • [luoguAT_abc369_e] Sight[luoguAT_abc369_e]Sightseeing Tour
    题意给定一个包含\(N\)个点和\(M\)条无向边的带权图,保证图中没有自环,但可能包含重边。给出\(Q\)次查询,每次查询给出\(K\)条边\(B_1,B_2,\cdots,B_K\),要求求出从节点\(1\)到节点\(N\)且这\(K\)条边都至少经过一次的最短路(经过边的方向和顺序任意)。赛时Dijkstra......
  • 题解:AT_abc369_e [ABC369E] Sightseeing Tour 详细版
    题目大意给定一个NNN个点,MMM条边的无向图。其中边有边权。有......
  • ABC369
     C对于一个等差数列,它里面包含的等差数列(取这个数列的第i位~第j位),必定也是等差数列。寻找等差数列的时候,如果一个等差数列,向最左/最右加1个数后,仍是等差数列,则把它们加上。从而寻找所有场上的等差数列,必定是不重叠的,等差数列彼此独立。从而可以从1遍历到n,O(n)复杂度。对于每......
  • [ABC369G] As far as possible
    考虑删除树上一条边\((u,v,l)\),此时剩余部分构成两个连通块,如果不包含节点\(1\)的连通块中有Aoki选择的点,那个这条边的贡献至少为\(2l\)。简单构造发现,当Takahashi构造的路径恰好为Aoki选择的点和\(1\)构成的虚树时,能够取到路径长度的最小值。此时我们将题目转......
  • 8.31 晚上 ABC369 总结 & 题解
    打了一天的比赛。ABCD太水了,直接放代码链接得了,点字母就能看对应代码。E-SightseeingTour看范围$N$只有$400$,所以我们可以先用floyd搞出任意两点间的距离。对于每次询问,发现$K_i$只有$5$,所以可以直接深搜应该走哪座桥,和应该走到哪一端。时间复杂度$O(N3+QK_i......
  • ABC369F F - Gather Coins 题解
    题目链接:https://atcoder.jp/contests/abc369/tasks/abc369_f题目大意:在一个\(H\timesW\)的二维迷宫中有\(N\)枚硬币,其中第\(i\)枚硬币在\((R_i,C_i)\)(本题中,我们用\((r,c)\)表示二维迷宫中从上到下第\(r\)行从左到右第\(c\)列的那个格子)。你一开始在迷宫的左......
  • abc369 题解
    切了A~F,还挺开心(但是如果上一次把G切了的话,我就上青了QAQ比赛链接:https://atcoder.jp/contests/abc369A-369题意:给定正整数\(a,b\)(\(1\lea,b\le100\)),请问有多少个整数\(x\)满足\(a,b,x\)排序后构成等差数列。思路:观察到\(a,b\)范围很小,直接枚举\(x\)即可。......
  • ABC369
    Alink判断\(A\),\(B\)之间可不可以放一个数,如果可以就是\(3\)个,不行就是\(2\)个(左右),但是如果\(A\),\(B\)相等就只有一个。点击查看代码#include<bits/stdc++.h>usingnamespacestd;signedmain(){ inta,b; cin>>a>>b; intx=b-a; if(x!=0){ if(x%2==0......
  • LeetCode 2952. Minimum Number of Coins to be Added
    原题链接在这里:https://leetcode.com/problems/minimum-number-of-coins-to-be-added/description/题目:Youaregivena 0-indexed integerarray coins,representingthevaluesofthecoinsavailable,andaninteger target.Aninteger x is obtainable ifthere......
  • Fancy Coins
    感觉这个凑的题目都是分类讨论1.\(n\leqk\timesa_k\),显然先将\(a_k\)一直取到不能取为止(如果最终方案不是这样,我们可以将方案中的\(k\)个面值为\(1\)的硬币或者\(1\)个面值为\(k\)的fancycoin替换为一个面值为\(k\)的regularcoin,答案肯定不会更差),于是\(n\)%\(=k\)1).\(n\leq......