Znzryb's Blog
0%

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();
}

Posted on Edited on

题目大意

给定序列 h1,dots,hnh_1,dots,h_n。统计所有长度至少为 1 的等差子序列的个数（对 998244353998244353 取模）。

AC代码

具体思路与该题解一致

https://www.luogu.com.cn/article/hrn3rj07

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
#include <iostream>
#include <vector>
using namespace std;
const int mod=998244353,N=1010,MAXR=4e4+10,R=4e4;  // random
int n,h[N],dp[N][MAXR*2],ans;     // dp里存到这第i个塔时有每种公差有多少种方案  这个dp数组大约77MB 题目限制是500MB
// 还需要介绍的是 如 1 2 3 4 这个等差数列 在这题中有4+3+2+1种（单个+2个+3个+4个）
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>h[i];
    }
    for(int i=1;i<=n;i++) {
        ans++;                  // 这里ans统计单个
        for(int j=i-1;j>=1;j--) {
            dp[i][h[i]-h[j]+R]+=dp[j][h[i]-h[j]+R]+1;    // 这里dp统计多个（>=2）所以个数为1
            dp[i][h[i]-h[j]+R]%=mod;
            ans+=dp[j][h[i]-h[j]+R]+1;
            ans%=mod;
        }
    }
    ans%=mod;
    cout<<ans<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/183896339

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

Posted on Edited on

题目大意

在一条直线（或编号轴）上从起点出发，每次可以从位置 jj 跳到 ii，要求跳跃长度在区间 [l,r][l, r] 内。每到达一个位置会获得或损失对应的分值。问到达“终点对岸”（位置编号超过 nn）时，能得到的最大总分。

AC代码

比较裸的子序列提取dp（子序列为 [ i-r , i-l ] ），唯一需要注意的是

只要她下一步的位置编号大于N就算到达对岸。

所以你的dp范围要扩大一点

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
#include <iostream>
using namespace std;
typedef long long ll;
const ll N=4e5+10,inf=1e18+7;
ll n,l,r,A[N],dp[N],ans=-inf;    // dp存的是走到该点最多能够获得多少冰冻指数
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    // 移动到i+L,i+R 向前递增，无后效性
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++) {
        cin>>A[i];
    }
    dp[0]=A[0];
    for(int i=1;i<=n+r;i++) {
        dp[i]=-inf;
    }
    for(int i=1;i<=n+r;i++) {
        for(int j=i-l;j>=i-r && j>=0;j--) {
            dp[i]=max(dp[j]+A[i],dp[i]);
        }
    }
    for(int i=n;i<=n+r;i++)
        ans=max(ans,dp[i]);
    cout<<ans<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/183798861

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

Posted on Edited on

题目大意

给定若干次“鼹鼠出现”的信息：每次出现的时间 TiT_i 与坐标 (Xi,Yi)(X_i, Y_i)。初始在某个位置，每次可以在单位时间内移动一定距离（等价于曼哈顿距离不超过时间差）。问最多能打到多少只鼹鼠。

AC代码

思路见洛谷进阶篇P227

注释也算写的比较详细

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll M=1e4+10;
ll n,m,T[M],X[M],Y[M],dp[M],ans;
// dp存打了第i只鼹鼠的情况下，之前能打多少只鼹鼠(包括这第i只鼹鼠)
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        cin>>T[i]>>X[i]>>Y[i];

    }
    for(int i=1;i<=m;i++) {
        ll t=T[i],x=X[i],y=Y[i];
        dp[i]=1;
        for(int j=i-1;j>=1;j--) {
            if(t-T[j]==0) // 时间相同自然不可能状态转移
                continue;
            if(abs(x-X[j])+abs(y-Y[j])<=t-T[j]) //状态转移条件是曼哈顿距离小于时间差
                dp[i]=max(dp[i],dp[j]+1);
        }
    }
    for(int i=1;i<=m;i++) {
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/183675211

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

Posted on Edited on

题目大意

给定长度为 nn 的序列 AA，求其最长严格上升子序列（LIS）的长度。

AC代码

该题目实际上是要求最长上升子序列严格递增

AC https://www.luogu.com.cn/record/183531657

实际上我这题做法是O（n^2）的，不能通过下面这题。

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
#include <iostream>
using namespace std;
typedef long long ll;
const ll N=5010;
// dp 里存的是以i个数为头所能组成的最长上升子序列
ll n,dp[N],A[N],ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>A[i];
    }
    for(int i=1;i<=n;++i) {
        dp[i]=1;
    }
    for(ll i=n-1;i>=1;--i) {
        for(ll j=n;j>=i+1;--j) {
            if(A[i]<A[j]) {
                dp[i]=max(dp[i],1+dp[j]);
            }
        }
    }
    for(int i=1;i<=n;i++) {
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}
// https://www.luogu.com.cn/record/183531657

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