电梯之王#

题目描述#

在惠州学院因为电梯数量很少，所以同学们坐电梯需要花钱，并且为了限制你坐电梯浪费盈利时间，学校专门给每一层设置了能坐的最高高度。，所以对每一层有两种元素: 1.花费一元坐电梯 2.能坐到的最高高度(例如给出的高度是X,那么第 $i$ 层能坐到的层数是 $[i + 1,i + X]$ 。但是请注意，因为惠州学院也想要锻炼学生的体魄，电梯不能往楼下坐。现在想要知道，如何最经济实惠坐到每一层。倘若坐不到则输出 $-1$ 。

思路#

Level 1 动态规划#

考虑 $dp[i]$ 表示走到第 $i$ 层所需的最小花费。~~这样竟然能拿九十分~~

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int maxn=1e7+10;
4
int dp[maxn];
5
int a[maxn];
6
int n;
7

8
inline int read()
9
{
10
    int x=0,f=1;
11
    char ch=getchar();
12
    while(ch<'0'||ch>'9')
13
    {
14
        if(ch=='-')
15
            f=-1;
16
        ch=getchar();
17
    }
18
    while(ch>='0' && ch<='9')
19
        x=x*10+ch-'0',ch=getchar();
20
    return x*f;
21
}
22

23
void write(int x)
24
{
25
    if(x<0)
26
        putchar('-'),x=-x;
27
    if(x>9)
28
        write(x/10);
29
    putchar(x%10+'0');
30
    return;
31
}
32

33
void init(){
34
    for(int i=0;i<maxn;i++){
35
        dp[i]=INT_MAX;
36
    }
37
}
38
int main(){
39
    n=read();
40
    init();
41
    for(int i=1;i<=n;i++){
42
        a[i]=read();
43
    }
44
    int last=1,cnt=1;
45
    int times=1;
46
    int lasti=-1;
47
    int runtime=0;
48
    cout<<"0\n";
49
    for(int i=1;i<n;){
50
        runtime++;
51
        if(runtime>n*3){
52
            break;
53
        }
54
        int maxpos=-1,pos;
55
        for(int j=i+1;j<=i+a[i];j++){
56
            if(j+a[j]>maxpos){
57
                maxpos=j+a[j];
58
                pos=j;
59
            }
60
        }
61
        for(int j=last+1;j<=i+a[i];j++){
62
            cout<<cnt<<endl;
63
            times++;
64
        }
65
        cnt++;
66
        last=i+a[i];
67
        i=pos;
68
        lasti=i;
69
    }
70
    return 0;
71
}

Level 2 贪心#

第一层电梯肯定是要坐的。那么现在第一层电梯就能到达一定范围的层数。利用贪心的思想，我们要尽可能利用现有的这些能到达的楼层，跳到更高的楼层。所以我们在这些范围内寻找所能到达楼层的最高值。那么我们又得到了一个新的范围。在这个范围内再次进行如上操作。

值得注意的是，两个范围很可能有重叠部分。为了保证严格的 $O(n)$ ，可以跳过重叠的部分。因为重叠部分里能到达的最高楼层一定小于当前选择的楼层。

~~好狼狈的代码：~~

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int maxn=1e7+10;
4
int dp[maxn];
5
int a[maxn];
6
int n;
7

8
inline int read()
9
{
10
    int x=0,f=1;
11
    char ch=getchar();
12
    while(ch<'0'||ch>'9')
13
    {
14
        if(ch=='-')
15
            f=-1;
16
        ch=getchar();
17
    }
18
    while(ch>='0' && ch<='9')
19
        x=x*10+ch-'0',ch=getchar();
20
    return x*f;
21
}
22

23
void write(int x)
24
{
25
    if(x<0)
26
        putchar('-'),x=-x;
27
    if(x>9)
28
        write(x/10);
29
    putchar(x%10+'0');
30
    return;
31
}
32

33
void init(){
34
    for(int i=0;i<maxn;i++){
35
        dp[i]=INT_MAX;
36
    }
37
}
38
int main(){
39
    n=read();
40
    init();
41
    for(int i=1;i<=n;i++){
42
        a[i]=read();
43
    }
44
    int last=1,cnt=1;
45
    int times=1;
46
    int lasti=-1;
47
    int runtime=0;
48
    cout<<"0\n";
49
    for(int i=1;i<n;){
50
        runtime++;
51
        if(runtime>n*3){
52
            break;
53
        }
54
        int maxpos=-1,pos;
55
        for(int j=i+1;j<=i+a[i];j++){
56
            if(j+a[j]>maxpos){
57
                maxpos=j+a[j];
58
                pos=j;
59
            }
60
        }
61
        for(int j=last+1;j<=i+a[i];j++){
62
            write(cnt);
63
            putchar('\n');
64
            times++;
65
        }
66
        cnt++;
67
        last=i+a[i];
68
        i=pos;
69
        lasti=i;
70
    }
71
    return 0;
72
}

元素#

题目描述#

给你 nn 个元素,每个元素有一个坐标 $(x, y)$ ,现在想让你求出有多少三元组 $(i,j,k)$ ,满足 $2x_j = x_i + x_k$ 并且 $2y_j = y_i + y_k$ 。

思路#

均摊 $O(n^2)$ 的算法。枚举前两个坐标，然后寻找第三个坐标。注意，当我们把原坐标排序后，寻找的第三个坐标也是有序的，不必要全部从头到尾地查找。

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3
int n;
4
const int maxn=1e9;
5
inline int read()
6
{
7
    int x=0,f=1;
8
    char ch=getchar();
9
    while(ch<'0'||ch>'9')
10
    {
11
        if(ch=='-')
12
            f=-1;
13
        ch=getchar();
14
    }
15
    while(ch>='0' && ch<='9')
16
        x=x*10+ch-'0',ch=getchar();
17
    return x*f;
18
}
19

20
void write(int x)
21
{
22
    if(x<0)
23
        putchar('-'),x=-x;
24
    if(x>9)
25
        write(x/10);
26
    putchar(x%10+'0');
27
    return;
28
}
29

30
map<pair<int,int>,int>bk,id;
31
map<int,int>getpos;
32
struct node{
33
    int x,y;
34
}a[10010];
35
bool cmp(node x,node y){
36
    if(x.x==y.x){
37
        return x.y<y.y;
38
    }else{
39
        return x.x<y.x;
40
    }
41
}
42
int ans=0;
43
int main(){
44
    n=read();
45
    for(int i=1;i<=n;i++){
46
        a[i].x=read(),a[i].y=read();
47
    }
48
    sort(a+1,a+1+n,cmp);
49
    for(int i=1;i<=n;i++){
50
        bk[{a[i].x,a[i].y}]++;
51
        id[{a[i].x,a[i].y}]=i;
52
        if(getpos[a[i].x]==0){
53
            getpos[a[i].x]=i;
54
        }
55
    }
56
    for(int i=1;i<=n;i++){
57
        int nowpos=i+2;
58
        for(int j=i+1;j<=n;j++){
59
            int newx=a[j].x*2-a[i].x;
60
            int newy=a[j].y*2-a[i].y;
61
            for(;nowpos<=n;nowpos++){
62
                if(a[nowpos].x<newx){
63
                    continue;
64
                }else if(a[nowpos].x>newx){
65
                    break;
66
                }else{
67
                    if(a[nowpos].y<newy){
68
                        continue;
69
                    }else if(a[nowpos].y>newy){
70
                        break;
71
                    }
72
                    if(a[nowpos].y==newy){
73
                        ans++;
74
                    }
75
                }
76
            }
77
        }
78
    }
79
    write(ans);
80
    return 0;
81
}

搜索#

题目描述#

$xyx$ 神仙来到了一个神奇的国度,这个国度由 $n$ 个相邻的城市组成.对于某个特定的城市 $i$ ,他有一个特殊的高度 $h_i$ .但是 $xyx$ 神仙喜欢一些特殊排列的城市高度.而且由于 $xyx$ 是神仙,所以他可以选择若干段不相交的区间 $[l,r]$ 并且将这个区间内的城市按照高度从小到大排序.现在 $xyx$ 神仙想知道,他能不能把面前的城市排列成他想要的高度排列.

思路#

如果有一段序列，想要它最终降序：如果原本就是降序的，可以实现；如果原来是升序的，就不行了。

所以我们考虑使用双指针，先看目标序列，对于每一段上升的区间，查看原来的区间是否恰好包含所有的这些数。如果否，就是 no 。

代码#

1
#include <bits/stdc++.h>
2
#define int long long
3
using namespace std;
4
const int maxn=1e6+10;
5
int t,n,a[maxn]={},b[maxn]={};
6
signed main(){
7
    cin>>t;
8
    while(t--){
9
        cin>>n;
10
        for(int i=1;i<=n;i++){
11
            cin>>a[i];
12
        }
13
        for(int i=1;i<=n;i++){
14
            cin>>b[i];
15
        }
16
        int i=1;
17
        bool flag=1;
18
        while(i<=n){
19
            map <int,int> sto;
20
            for(;b[i]>=b[i-1]&&i<=n;i++){
21
                sto[b[i]]++;
22
                sto[a[i]]--;
23
            }
24
            for(auto f:sto){
25
                if(f.second!=0){
26
                    flag=0;
27
                    break;
28
                }
29
            }
30
            b[i-1]=-1;
31
        }
32
        cout<<(flag?"yes\n":"no\n");
33
    }
34
    return 0;
35
}

电梯之王#

题目描述#

思路#

Level 1 动态规划#

Level 2 贪心#

元素#

题目描述#

思路#

代码#

搜索#

题目描述#

思路#

代码#

支持与分享

评论区

目录

CSP 2022 RP++

电梯之王#

题目描述#

思路#

Level 1 动态规划#

Level 2 贪心#

元素#

题目描述#

思路#

代码#

搜索#

题目描述#

思路#

代码#

支持与分享

评论区

目录