Znzryb's Blog
0%

ABC-376-F-Hands on Ring (Hard) 

Posted on Edited on

题目大意

有一个环形的 nn 个点（编号 1simn1sim n），两只手初始在固定位置。给出 mm 次操作，每次要求移动某一只手到指定点，移动代价为沿环走的最短步数，同时两只手不能占用同一个点（或有重叠限制）。求完成所有操作的最小总代价。

AC代码

其实与B题的唯一不同点就是你可以动另一只手。

这题让我想起来天津省选的线段

https://www.luogu.com.cn/problem/P3842

AC记录

这个线段就是你要忽略一些其实没有意义的情况，这道题应该也是一样，你不必把两只手在哪个点都存下来，因为后走和前走是一样的

注意防重叠条件的书写

就是我之前写if(pos≠j) 但实际上j有可能代表副手，也有可能代表主手，如果代表副手就有问题了，pos就是移动副手，副手不应该和副手重叠？搞笑

其实可以在cal函数中写这个逻辑，但因为这个cal函数是从B题拉过来的，我就懒得改了

分享一组hack数据

1
2
3
4
5
6
7
8
8 7
L 2
L 3
L 4
L 5
L 6
L 7
L 8

应输出

1
14

AC https://atcoder.jp/contests/abc376/submissions/59140626

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,m,dp[N][N],object;
char oper;
void debug() {
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;
    }
}
ll cal(char op,ll L,ll R,ll obj) {  // 计算并返回需要走几步
    ll res=0;
    if(op=='L') {
        ll zhenMove=abs(L-obj);
        ll fanMove=n-zhenMove;
        if(obj<L) {
            if(R<L && R>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(R>L && R<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }else {
        ll zhenMove=abs(R-obj);
        ll fanMove=n-zhenMove;
        if(obj<R) {
            if(L<R && L>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(L>R && L<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int opup=0;
    memset(dp,0x3f,sizeof(dp));
    ll inf = dp[0][0];
    dp[0][2]=0;                // 此时r在2
    ll opupObj=1;             // 假装有一个0号命令 让L走到 1
    for(int i=1;i<=m;i++) {
        cin>>oper>>object;
        int op= oper=='L'? 0:1;
        for(int j=1;j<=n;j++) {
            if(dp[i-1][j]==inf)
                continue;

            if(op==opup && op==0) {     // 此时 j 即为right手 opuploc 即为 left   dp里应该存的仍然是r手
                // r手可自由移动
                ll l=opupObj,r=j;
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                if(pos!=l)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=l)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }else if(op==opup && op==1) {
                // l手可自由移动
                ll l=j,r=opupObj;
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                if(pos!=r)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=r)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==1 && opup==0) {
                ll l=opupObj,r=j;           // 可以随便动的手是left 要动的手是right
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                if(pos!=r)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=r)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==0 && opup==1) {
                ll l=j,r=opupObj;           // 可以随便动的手是right 要动的手是left
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                if(pos!=l)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=l)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }
        }
        opup=op;opupObj=object;
    }
    ll ans=inf;
    for(int i=1;i<=n;i++) {
        ans=min(ans,dp[m][i]);
    }

    cout<<ans<<endl;
    // debug();
}
// AC https://atcoder.jp/contests/abc376/submissions/59140626

心路历程（WA，TLE，MLE……）

WA了13个点

https://atcoder.jp/contests/abc376/submissions/59134285

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,m,dp[N][N],object;
char oper;
void debug() {
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;
    }
}
ll cal(char op,ll L,ll R,ll obj) {  // 计算并返回需要走几步
    ll res=0;
    if(op=='L') {
        ll zhenMove=abs(L-obj);
        ll fanMove=n-zhenMove;
        if(obj<L) {
            if(R<L && R>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(R>L && R<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }else {
        ll zhenMove=abs(R-obj);
        ll fanMove=n-zhenMove;
        if(obj<R) {
            if(L<R && L>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(L>R && L<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int opup=0;
    memset(dp,0x3f,sizeof(dp));
    ll inf = dp[0][0];
    dp[0][2]=0;                // 此时r在2
    ll opupObj=1;             // 假装有一个0号命令 让L走到 1
    for(int i=1;i<=m;i++) {
        cin>>oper>>object;
        int op= oper=='L'? 0:1;
        for(int j=1;j<=n;j++) {
            if(dp[i-1][j]==inf)
                continue;

            if(op==opup && op==0) {     // 此时 j 即为right手 opuploc 即为 left   dp里应该存的仍然是r手
                // r手可自由移动
                ll l=opupObj,r=j;
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }else if(op==opup && op==1) {
                // l手可自由移动
                ll l=j,r=opupObj;
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==1 && opup==0) {
                ll l=opupObj,r=j;           // 可以随便动的手是left 要动的手是right
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==0 && opup==1) {
                ll l=j,r=opupObj;           // 可以随便动的手是right 要动的手是left
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }
        }
        opup=op;opupObj=object;
    }
    ll ans=inf;
    for(int i=1;i<=n;i++) {
        ans=min(ans,dp[m][i]);
    }

    cout<<ans<<endl;
    //debug();
}

WA了9个点，解决了一些特殊情况

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,m,dp[N][N],object;
char oper;
void debug() {
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;
    }
}
ll cal(char op,ll L,ll R,ll obj) {  // 计算并返回需要走几步
    ll res=0;
    if(op=='L') {
        ll zhenMove=abs(L-obj);
        ll fanMove=n-zhenMove;
        if(obj<L) {
            if(R<L && R>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(R>L && R<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }else {
        ll zhenMove=abs(R-obj);
        ll fanMove=n-zhenMove;
        if(obj<R) {
            if(L<R && L>obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }else {
            if(L>R && L<obj)
                res+=fanMove;
            else
                res+=zhenMove;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int opup=0;
    memset(dp,0x3f,sizeof(dp));
    ll inf = dp[0][0];
    dp[0][2]=0;                // 此时r在2
    ll opupObj=1;             // 假装有一个0号命令 让L走到 1
    for(int i=1;i<=m;i++) {
        cin>>oper>>object;
        int op= oper=='L'? 0:1;
        for(int j=1;j<=n;j++) {
            if(dp[i-1][j]==inf)
                continue;

            if(op==opup && op==0) {     // 此时 j 即为right手 opuploc 即为 left   dp里应该存的仍然是r手
                // r手可自由移动
                ll l=opupObj,r=j;
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }else if(op==opup && op==1) {
                // l手可自由移动
                ll l=j,r=opupObj;
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==1 && opup==0) {
                ll l=opupObj,r=j;           // 可以随便动的手是left 要动的手是right
                ll pos= object%n+1;
                if(l!=object)
                    dp[i][l]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][l]);
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,pos,r,object)+cal('L',l,r,pos),dp[i][pos]);
            }else if(op==0 && opup==1) {
                ll l=j,r=opupObj;           // 可以随便动的手是right 要动的手是left
                ll pos= object%n+1;
                if(r!=object)
                    dp[i][r]=min(dp[i-1][j]+cal(oper,l,r,object),dp[i][r]);
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
                pos= object==1 ? n:object-1;
                if(pos!=j)
                    dp[i][pos]=min(dp[i-1][j]+cal(oper,l,pos,object)+cal('R',l,r,pos),dp[i][pos]);
            }
        }
        opup=op;opupObj=object;
    }
    ll ans=inf;
    for(int i=1;i<=n;i++) {
        ans=min(ans,dp[m][i]);
    }

    cout<<ans<<endl;
    //debug();
}