D - Sequence Query

题目大意

我们有一个空序列$A$。请依次处理$Q$个命令，每个命令有三种类型，每种类型的格式如下：

1 x：将$x$加入$A$（不去重）
2 x k：求在$A$的$\le x$的元素中，第$k$大的值。
3 x k：求在$A$的$\ge x$的元素中，第$k$小的值。

$1\le Q\le 2\times 10^5$
$1\le x\le 10^{18}$
==$1\le k\le 5$==

分析

注意题面中的$1\le k\le 5$，我们可以用multiset解决问题。
multiset顾名思义，就是不去重的set，支持二分查找操作。关于multiset的具体用法，请看这里
对于每个查询，我们作如下处理：

1 x：直接加入multiset
2 x k：先upper_bound，再将iterator向前移动$k$步
3 x k：先lower_bound，再将iterator向后移动$k$步

前面提到，因为$k$的值很小，所以移动iterator的时间复杂度可以忽略不计。
因此，总时间复杂度最优为$\mathcal O(Q)$，平均$\mathcal O(Q\log Q)$，最坏$\mathcal O(Q\log Q)$。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


#include <cstdio>
#include <set>
using namespace std;

int main()
{
    multiset<long long> s;
    int q;
    scanf("%d", &q);
    while(q--)
    {
        int op;
        long long x;
        scanf("%d%lld", &op, &x);
        if(op == 1) s.insert(x);
        else
        {
            int k;
            scanf("%d", &k);
            if(op == 2)
            {
                bool bad = false;
                auto it = s.upper_bound(x);
                for(; k--; --it)
                    if(it == s.begin())
                    {
                        bad = true;
                        break;
                    }
                if(bad) puts("-1");
                else printf("%lld\n", *it);
            }
            else
            {
                auto it = s.lower_bound(x);
                for(; --k; ++it)
                    if(it == s.end())
                        break;
                if(it == s.end()) puts("-1");
                else printf("%lld\n", *it);
            }
        }
    }
    return 0;
}

E - Putting Candies

题目大意

给定长度为$N$的序列$A=(A_0,A_1,\dots,A_{N-1})$。
有一个空盘子。Takahashi每次会在其中加入$A_{(X\bmod N)}$颗糖果（$X$是当前盘子中糖果的数量）。
求$K$次操作后的糖果总数。

$2\le N\le 2\times 10^5$
$1\le K\le 10^{12}$
$1\le A_i\le 10^6$

分析

根据鸽笼原理（又称抽屉原理），$A_{(X\bmod N)}$的结果在最多$N$次操作后一定会重复。
因此，这道题可以看作数学上的一道周期问题。（~~又是数学题?!~~）
我们只需分别记录结果对应的时间和时间对应的结果即可。
最终总时间复杂度$\mathcal O(n)$，空间复杂度$\mathcal O(n)$。

代码

代码参考：AtCoder官方题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


#include <cstdio>
#define maxn 200005
using namespace std;

using LL = long long;
LL A[maxn], S[maxn];
int pre[maxn];

int main()
{
    int n;
    LL k;
    scanf("%d%lld", &n, &k);
    for(int i=0; i<n; i++)
        scanf("%lld", A + i);
    for(int i=1; i<n; i++)
        pre[i] = -1;
    int time, s;
    for(int i=0; i<n; i++)
    {
        S[i + 1] = S[i] + A[S[i] % n];
        if(pre[S[i + 1] % n] != -1)
        {
            s = pre[S[i + 1] % n];
            time = i + 1;
            break;
        }
        pre[S[i + 1] % n] = i + 1;
    }
    if(k <= s) printf("%lld\n", S[k]);
    else
    {
        int p = time - s;
        LL X = S[time] - S[s], t = k - s - 1;
        printf("%lld\n", S[s + t % p + 1] + t / p * X);
    }
    return 0;
}

F - Skate

题目大意

有一个$H\times W$的网格。网格上有$N$个障碍物，第$i$个的位置是$(X_i,Y_i)$。
我们从$(s_x,s_y)$开始，每一步向上、下、左、右中的一个方向行走，直到撞上障碍物，停在它前面的方格中。求到达$(g_x,g_y)$所用的最少步数。若无法到达终点，输出-1。

$1\le H,W\le 10^9$
==$1\le N\le 10^5$==
$1\le s_x,g_x,X_i\le H$
$1\le s_y,g_y,Y_i\le W$
$(s_x,g_x)\ne(g_x,g_y)\ne(X_i,Y_i)$
$(X_i,Y_i)\ne(X_j,Y_j)$（$i\ne j$）

分析

这道题看似数据范围很大，实则不然。因为$N$只有$10^5$，所以我们很容易想到使用$\text{BFS}$，用map存储每行每列，对于每个坐标，二分查找当前行/列中的位置即可。

代码

写代码时注意事项主要有两点：

行和列的坐标一定要排序，也可以用set
注意二分边界情况

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


#include <cstdio>
#include <queue>
#include <set>
#include <unordered_map>
using namespace std;

using LL = long long;
unordered_map<int, set<int>> row, col;
unordered_map<LL, int> dis;

inline LL pack(LL x, int y) { return x << 31LL | y; }
inline void unpack(const LL& b, int& x, int& y) { x = b >> 31LL, y = b & 0x7fffffff; }

int main()
{
    int h, w, n, sx, sy, gx, gy;
    scanf("%d%d%d%d%d%d%d", &h, &w, &n, &sx, &sy, &gx, &gy);
    for(int i=0; i<n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        row[x].insert(y);
        col[y].insert(x);
    }
    LL target = pack(gx, gy);
    queue<pair<LL, int>> q;
    q.emplace(pack(sx, sy), 0);
    while(!q.empty())
    {
        auto [p, d] = q.front(); q.pop();
        if(!dis.emplace(p, d).second) continue;
        if(p == target) { printf("%d\n", d); return 0; }
        int x, y;
        unpack(p, x, y), ++d;
        if(row.count(x))
        {
            auto& s = row[x];
            auto it = s.lower_bound(y);
            if(it != s.end()) q.emplace(pack(x, *it - 1), d);
            if(it != s.begin()) q.emplace(pack(x, *--it + 1), d);
        }
        if(col.count(y))
        {
            auto& s = col[y];
            auto it = s.lower_bound(x);
            if(it != s.end()) q.emplace(pack(*it - 1, y), d);
            if(it != s.begin()) q.emplace(pack(*--it + 1, y), d);
        }
    }
    puts("-1");
    return 0;
}