ABC-273解题报告

发表于 分类于

D. LRUD Instructions

题意：一个左上角为 (1,1)(1,1)、右下角为 (H,W)(H,W) 的矩阵，矩阵中有 nn 个障碍。你初始在 (r,c)(r,c)，给你一个操作序列，每个操作为向上/下/左/右走若干格，如果遇到障碍/走到边界则停止。每次操作后输出当前位置。

用数据结构存下每行中的障碍和每列中的障碍，每次从中找到最近的障碍，如果被挡住则走到障碍的上一格，否则正常走。

best code:

By tourist

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w, r, c;
  cin >> h >> w >> r >> c;
  int n;
  cin >> n;
  map<int, set<int>> mr;
  map<int, set<int>> mc;
  for (int i = 0; i < n; i++) {
    int rr, cc;
    cin >> rr >> cc;
    mr[rr].insert(cc);
    mc[cc].insert(rr);
  }
  int q;
  cin >> q;
  while (q--) {
    string op;
    int cnt;
    cin >> op >> cnt;
    if (op[0] == 'R') {
      auto it = mr[r].lower_bound(c);
      if (it != mr[r].end()) {
        c = min(*it - 1, c + cnt);
      } else {
        c += cnt;
      }
    }
    if (op[0] == 'D') {
      auto it = mc[c].lower_bound(r);
      if (it != mc[c].end()) {
        r = min(*it - 1, r + cnt);
      } else {
        r += cnt;
      }
    }
    if (op[0] == 'L') {
      auto it = mr[r].lower_bound(c);
      if (it != mr[r].begin()) {
        c = max(*prev(it) + 1, c - cnt);
      } else {
        c -= cnt;
      }
    }
    if (op[0] == 'U') {
      auto it = mc[c].lower_bound(r);
      if (it != mc[c].begin()) {
        r = max(*prev(it) + 1, r - cnt);
      } else {
        r -= cnt;
      }
    }
    r = max(r, 1);
    r = min(r, h);
    c = max(c, 1);
    c = min(c, w);
    cout << r << " " << c << '\n';
  }
  return 0;
}

这份代码有两个好的地方：

  1. 使用 map 套 set 来维护障碍，避免了复杂的离散化处理。
  2. 将越界情况统一处理，每次操作最后使用四行 min⁡/max⁡\min/\max 来处理越界。

By WA_TLE

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include "bits/stdc++.h"
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define REP(i, n) for(int i = 0;i < (n);i++)
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}

int main(void){
    int H,W,rs,cs,i,j,n;cin>>H>>W>>rs>>cs>>n;

    vector<pair<int,int>>rc(n+2);
    vector<pair<int,int>>cr(n+2);
    for(i=0;i<n;i++){
        int r,c;cin>>r>>c;
        rc[i]=mp(r,c);
        cr[i]=mp(c,r);
    }
    rc[n]=mp(mod,mod);
    cr[n]=mp(mod,mod);
    rc[n+1]=mp(-mod,-mod);
    cr[n+1]=mp(-mod,-mod);
    SO(rc);
    SO(cr);
    int Q;cin>>Q;
    while(Q--){
        char d;int l;
        cin>>d>>l;
        if(d=='U'){//r--
            auto kabe=*prev(lower_bound(cr.begin(),cr.end(),mp(cs,rs)));
            rs-=l;
            chmax(rs,1);
            if(kabe.fir==cs){chmax(rs,kabe.sec+1);}
        }
        if(d=='D'){//r++
            auto kabe=*lower_bound(cr.begin(),cr.end(),mp(cs,rs));
            rs+=l;
            chmin(rs,H);
            if(kabe.fir==cs){chmin(rs,kabe.sec-1);}
        }
        if(d=='L'){//c--
            auto kabe=*prev(lower_bound(rc.begin(),rc.end(),mp(rs,cs)));
            cs-=l;
            chmax(cs,1);
            if(kabe.fir==rs){chmax(cs,kabe.sec+1);}
        }
        if(d=='R'){//c++
            auto kabe=*lower_bound(rc.begin(),rc.end(),mp(rs,cs));
            cs+=l;
            chmin(cs,W);
            if(kabe.fir==rs){chmin(cs,kabe.sec-1);}
        }
        cout<<rs<<" "<<cs<<endl;
    }
    return 0;
}

这份代码巧妙地利用了 pair 自带比较函数的特点，使用正反两个 pair 数组维护障碍，同样避免了离散化且实现巧妙。

By Factorio

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
#include <bits/stdc++.h>
using namespace std;
map<int, set<int> > r, c;
int n, m, sx, sy, o, x, y, q, l;
char d;
int main()
{
    cin >> n >> m >> sx >> sy >> o;
    for (int i = 0; i < o; i++)
    {
        cin >> x >> y;
        r[x].insert(y);
        c[y].insert(x);
    }
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        cin >> d >> l;
        if (d == 'L')
        {
            r[sx].insert(0);
            int p = *--r[sx].upper_bound(sy);
            sy = max(sy - l, p + 1);
        }
        else if (d == 'R')
        {
            r[sx].insert(m + 1);
            int p = *r[sx].upper_bound(sy);
            sy = min(sy + l, p - 1);
        }
        else if (d == 'U')
        {
            c[sy].insert(0);
            int p = *--c[sy].upper_bound(sx);
            sx = max(sx - l, p + 1);
        }
        else
        {
            c[sy].insert(n + 1);
            int p = *c[sy].upper_bound(sx);
            sx = min(sx + l, p - 1);
        }
        printf("%d %d\n", sx, sy);
    }
    return 0;
}

这份代码的巧妙之处在于，每次询问先把朝向的边界加入 set，使三种情况得到统一，更好地避免了分类讨论。

worse code:

By cxm1024

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
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
int xx[200010],yy[200010],tmpx[200010],tmpy[200010],cntx=0,cnty=0;
vector<int> xt[200010],yt[200010];
signed main() {
    int h,w,r,c,n,q;
    cin>>h>>w>>r>>c>>n;
    for(int i=1;i<=n;i++) {
        cin>>xx[i]>>yy[i];
        tmpx[++cntx]=xx[i],tmpy[++cnty]=yy[i];
    }
    sort(tmpx+1,tmpx+cntx+1);
    cntx=unique(tmpx+1,tmpx+cntx+1)-tmpx-1;
    sort(tmpy+1,tmpy+cnty+1);
    cnty=unique(tmpy+1,tmpy+cnty+1)-tmpy-1;
    for(int i=1;i<=n;i++) {
        xt[lower_bound(tmpx+1,tmpx+cntx+1,xx[i])-tmpx].push_back(yy[i]);
        yt[lower_bound(tmpy+1,tmpy+cnty+1,yy[i])-tmpy].push_back(xx[i]);
    }
    for(int i=1;i<=cntx;i++)
        sort(xt[i].begin(),xt[i].end());
    for(int i=1;i<=cnty;i++)
        sort(yt[i].begin(),yt[i].end());
    cin>>q;
    while(q--) {
        char op;
        int len;
        cin>>op>>len;
        int nowx=lower_bound(tmpx+1,tmpx+cntx+1,r)-tmpx;
        if(tmpx[nowx]!=r) nowx=0;
        int nowy=lower_bound(tmpy+1,tmpy+cnty+1,c)-tmpy;
        if(tmpy[nowy]!=c) nowy=0;
        if(op=='U') {
            auto tmp=lower_bound(yt[nowy].begin(),yt[nowy].end(),r);
            if(tmp==yt[nowy].begin()) r=max(1,r-len);
            else {
                tmp--;
                r=max(r-len,(*tmp)+1);
            }
        }
        else if(op=='D') {
            auto tmp=lower_bound(yt[nowy].begin(),yt[nowy].end(),r);
            if(tmp==yt[nowy].end()) r=min(r+len,h);
            else r=min(r+len,(*tmp)-1);
        }
        else if(op=='L') {
            auto tmp=lower_bound(xt[nowx].begin(),xt[nowx].end(),c);
            if(tmp==xt[nowx].begin()) c=max(1,c-len);
            else {
                tmp--;
                c=max(c-len,(*tmp)+1);
            }
        }
        else {
            auto tmp=lower_bound(xt[nowx].begin(),xt[nowx].end(),c);
            if(tmp==xt[nowx].end()) c=min(w,c+len);
            else c=min(c+len,(*tmp)-1);
        }
        cout<<r<<" "<<c<<endl;
    }
    return 0;
}

这份代码直接使用离散化后的 vector 数组来存储障碍，且用了过多分类讨论，实现繁琐。

改进版本：

By cxm1024

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
#include<bits/stdc++.h>
using namespace std;
int x[200010],y[200010],cntx=0,cnty=0;
map<int,set<int> > xt,yt;
signed main() {
    int h,w,r,c,n,q;
    cin>>h>>w>>r>>c>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++) {
        xt[x[i]].insert(y[i]);
        yt[y[i]].insert(x[i]);
    }
    cin>>q;
    while(q--) {
        char op;
        int len;
        cin>>op>>len;
        if(op=='U') {
            auto tmp=yt[c].lower_bound(r);
            if(tmp==yt[c].begin()) r=max(1,r-len);
            else {
                tmp--;
                r=max(r-len,(*tmp)+1);
            }
        }
        else if(op=='D') {
            auto tmp=yt[c].lower_bound(r);
            if(tmp==yt[c].end()) r=min(r+len,h);
            else r=min(r+len,(*tmp)-1);
        }
        else if(op=='L') {
            auto tmp=xt[r].lower_bound(c);
            if(tmp==xt[r].begin()) c=max(1,c-len);
            else {
                tmp--;
                c=max(c-len,(*tmp)+1);
            }
        }
        else {
            auto tmp=xt[r].lower_bound(c);
            if(tmp==xt[r].end()) c=min(w,c+len);
            else c=min(c+len,(*tmp)-1);
        }
        cout<<r<<" "<<c<<endl;
    }
    return 0;
}

wrong code:

By MMNMM（TLE）

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/extc++.h>

template<typename T, typename S>
std::ostream& operator<<(std::ostream& os, const std::pair<T, S>& p){
    os << p.first << " " << p.second;
    return os;
}

int main() {
    using namespace std;
    long H, W;
    cin >> H >> W;
    pair<long, long> now{};
    cin >> now.first >> now.second;

    unsigned long N;
    cin >> N;
    unordered_map<long, set<long>> vertical, horizontal;
    for(unsigned long i{}; i < N; ++i){
        long x, y;
        cin >> x >> y;
        vertical[x].insert(y);
        horizontal[y].insert(x);
    }

    unsigned long Q;
    cin >> Q;
    for(unsigned long i{}; i < Q; ++i){
        char d;
        long l;
        cin >> d >> l;
        switch(d){
            case 'L':
                if(vertical.count(now.first)){
                    const auto walls{vertical[now.first]};
                    const auto next_wall{walls.upper_bound(now.second)};
                    if(next_wall == begin(walls))now.second -= l;
                    else now.second = max(now.second - l, *prev(next_wall) + 1);
                }else now.second -= l;
                break;
            case 'R':
                if(vertical.count(now.first)){
                    const auto walls{vertical[now.first]};
                    const auto next_wall{walls.lower_bound(now.second)};
                    if(next_wall == end(walls))now.second += l;
                    else now.second = min(now.second + l, *next_wall - 1);
                }else now.second += l;
                break;
            case 'U':
                if(horizontal.count(now.second)){
                    const auto walls{horizontal[now.second]};
                    const auto next_wall{walls.upper_bound(now.first)};
                    if(next_wall == begin(walls))now.first -= l;
                    else now.first = max(now.first - l, *prev(next_wall) + 1);
                }else now.first -= l;
                break;
            case 'D':
                if(horizontal.count(now.second)){
                    const auto walls{horizontal[now.second]};
                    const auto next_wall{walls.lower_bound(now.first)};
                    if(next_wall == end(walls))now.first += l;
                    else now.first = min(now.first + l, *next_wall - 1);
                }else now.first += l;
                break;
        }
        now.first = clamp(now.first, 1L, H);
        now.second = clamp(now.second, 1L, W);
        cout << now << endl;
    }
    return 0;
}

这份代码 TLE 的原因在于第 35、43、51、59 行为了简化代码将 set 复制了一份，而 set 的直接复制是 O(n)O(n) 的，所以导致超时。如果要复制的话，可以选择按引用赋值，即将 const auto walls{vertical[now.first]}; 改为 const auto &walls=vertical[now.first]; 便不会超时。该语句相当于指向了原 set 而不会重新复制一份。

选自《Effective C++》：

The meaning of passing an object by value is defined by the copy constructor of that object’s class. This can make pass-by-value an extremely expensive operation.

E. Notebook

题意：你需要维护一个序列，支持：push_back、pop_back、记录一个新版本、回退版本。

首先看到这题，第一反应想到用可持久化的数据结构来维护，但对于这道题而言显然过于麻烦了。于是想到可以通过依赖树，将可持久化问题转为非可持久化来做，建图跑 DFS 即可。

By cxm1024

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
#include<bits/stdc++.h>
using namespace std;
map<int,int> m;
int a[500010];
pair<string,int> ask[500010];
vector<int> now;
vector<pair<int,pair<string,int> > > e[500010];
int ans[500010];
void dfs(int x) {
    if(now.empty()) ans[x]=-1;
    else ans[x]=now.back();
    for(auto v:e[x]) {
        int flag=-1;
        if(v.second.first=="ADD")
            now.push_back(v.second.second);
        else if(v.second.first=="DELETE")
            if(!now.empty())
                flag=now.back(),now.pop_back();
        dfs(v.first);
        if(v.second.first=="ADD")
            now.pop_back();
        else if(v.second.first=="DELETE")
            if(flag!=-1)
                now.push_back(flag);
    }
}
signed main() {
    ios::sync_with_stdio(false);
    int n,tot=0;
    cin>>n;
    for(int i=1;i<=n;i++) {
        a[i]=++tot;
        cin>>ask[i].first;
        if(ask[i].first!="DELETE")
            cin>>ask[i].second;
        if(ask[i].first=="LOAD")
            e[m[ask[i].second]].push_back({a[i],{"",0}});
        else e[a[i-1]].push_back({a[i],ask[i]});
        if(ask[i].first=="SAVE")
            m[ask[i].second]=a[i];
    }
    dfs(0);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    cout<<endl;
    return 0;
}

然而这个做法仍然不够简洁。注意到由于只需要支持 push_back 和 pop_back 这两个较为基础的操作，我们可以使用链表维护。这里使用反向链表，并维护当前的末尾指针，则每次生成新版本只需要记录当前的末尾即可拉出来一整条链。push_back 只需要增加一个元素作为新末尾并指向原末尾；pop_back 则不需要真的删除元素，单纯把当前末尾指针回退一格即可。显然时空复杂度是可以接受的。

By tourist

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
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  map<int, int> note;
  vector<pair<int, int>> all(1, make_pair(0, -1));
  int at = 0;
  for (int qq = 0; qq < tt; qq++) {
    string op;
    cin >> op;
    if (op == "ADD") {
      int num;
      cin >> num;
      all.emplace_back(at, num);
      at = (int) all.size() - 1;
    }
    if (op == "DELETE") {
      at = all[at].first;
    }
    if (op == "SAVE") {
      int num;
      cin >> num;
      note[num] = at;
    }
    if (op == "LOAD") {
      int num;
      cin >> num;
      at = note[num];
    }
    cout << all[at].second << " \n"[qq == tt - 1];
  }
  return 0;
}

维护 notebook 也可以不用 map 而使用哈希：

做法1参考（By ygussany）

做法2参考（By rainboy）

时间复杂度上可以优化掉一个 log⁡\log，思路，没有本质区别。

这道题本质上是维护一个可持久化栈，经典的做法就是用链表维护。我们也可以将其封装起来，作为一个专门的数据结构：

By sapphire15

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i = 0; i < int(n); i++)
#define per(i,n) for(int i = (n) - 1; 0 <= i; i--)
#define rep2(i,l,r) for(int i = (l); i < int(r); i++)
#define per2(i,l,r) for(int i = (r) - 1; int(l) <= i; i--)
#define MM << " " <<
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)x.size()

template <typename T>
void print(const vector<T> &v, T x = 0) {
    int n = v.size();
    for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');
    if (v.empty()) cout << '\n';
}

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template <typename T>
bool chmax(T &x, const T &y) {
    return (x < y) ? (x = y, true) : false;
}

template <typename T>
bool chmin(T &x, const T &y) {
    return (x > y) ? (x = y, true) : false;
}


template<class T>
class PersistentStack {
    private:

    class PSNode;
    using node_ptr = std::shared_ptr<PSNode>;

    struct PSNode {
        T _val;
        node_ptr _next;
        PSNode() : _next(nullptr) {}
        PSNode(T x, node_ptr p)
        : _val(x), _next(p) {}
    };

    node_ptr _target;
    std::size_t _size;

    PersistentStack(node_ptr p, std::size_t sz)
    : _target(p), _size(sz) {}

    PersistentStack reverse() {
        PersistentStack now = *this;
        PersistentStack ret;
        while(!now.empty()) {
            ret = ret.push(now.top());
            now = now.pop();
        }
        return ret;
    }

    // friend PersistentQueue<T>;

    public:

    PersistentStack() : _size(0) {
        _target = std::make_shared<PSNode>();
    }

    bool empty() const {
        return _target->_next == nullptr;
    }

    T& top() const {
        assert(!empty());
        return _target->_val;
    }

    size_t size() const noexcept {
        return _size;
    }

    PersistentStack pop() const {
        assert(!empty());
        return PersistentStack(_target->_next, _size - 1);
    }

    PersistentStack push(const T x) const {
        node_ptr ret_p = std::make_shared<PSNode>(x, _target);
        return PersistentStack(ret_p, _size + 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    unordered_map<int, PersistentStack<int>> mp;
    PersistentStack<int> a;
    int q; cin >> q;
    vector<int> ans(q);
    rep(i,q) {
        string s; cin >> s;
        if(s == "ADD") {
            int x; cin >> x;
            a = a.push(x);
        } else if(s == "DELETE") {
            if(!a.empty()) a = a.pop();
        } else if(s == "SAVE") {
            int x; cin >> x;
            mp[x] = a;
        } else if(s == "LOAD") {
            int x; cin >> x;
            a = mp[x];
        }
        if(a.empty()) ans[i] = -1;
        else ans[i] = a.top();
    }
    print(ans);
}