Codeforces Round#595解题报告

ACM 阅读量

超哥教我打CF，写一篇解题报告纪念一下。

A.Yet Another Dividing into Teams

题意

给定一个序列，问你需要把这个序列分成多少段，才能保证每一段中的所有数字他们的差值都严格大于1

题解

数据范围较小，直接 $set$ 暴力，记录有多少个 $set$ ，然后把 $set$ 里面的元素从大到小排序，把原序列排序，直接判定第一个每个 $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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3+7;
int a[MAXN];
set<int> S[MAXN];
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++)
            cin >> a[i];
        sort(a+1,a+1+n);
        int cnt = 1;
        S[cnt].insert(-a[1]);
        for(int i = 2;i <= n;i++){
            //set<int>::iterator it;
            bool flag = true;
            for(int j = 1;j <= cnt;j++){
                if(a[i] - -*S[j].begin() > 1){
                    S[j].insert(-a[i]);
                    flag = false;
                    break;
                }
            }
            if(flag){
                cnt++;
                S[cnt].insert(-a[i]);
            }
        }
        cout << cnt << endl;
        for(int i = 1;i <= cnt;i++)
        	S[i].clear();
    }
    return 0;
}

B.Books Exchange

题意

$B1,B2$ 题意相同，只是 $n$ 的数据范围不同。给定一个序列，代表，第 $i$ 个人每天都会把自己手中的书传递给第 $a_i$ 这号人，问每个人最少在第多少天会受到自己原来的那本书。

题解

很像洛谷的一道题，忘了是啥了。直接 $dfs$ 判环，对于 $B1$ ，直接暴力枚举 $i$ 每次都去 $dfs$ 就行，而对于 $B2$，需要记录一下这个环上所有的点的天数，因为同一个环，所有人收到书的时间是一样的

代码

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
// B1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3+7;
vector<int> V[MAXN];
bool flag;
void dfs(int s,int x,int sum){
    if(flag){
        cout << sum << " ";
        return ;
    }
 
    for(int i = 0;i < V[x].size();i++){
        if(s == V[x][i])
            flag = true;
        dfs(s,V[x][i],sum+1);
    }
}
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--){
        int n,v;
        cin >> n;
        for(int i = 1;i <= n;i++){
            cin >> v;
            V[i].push_back(v);
        }
        for(int i = 1;i <= n;i++){
            flag = false;
            dfs(i,i,0);
        }
        cout << endl;
        for(int i = 1;i <= n;i++)
            V[i].clear();
    }
    return 0;
}
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
//B2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+7;
const int INF = 0x3f3f3f3f;
vector<int> V[MAXN];
int a[MAXN],sum;
bool flag;
void dfs(int s,int x){
    if(flag){
        a[s] = sum;
        return ;
    }
 
    for(int i = 0;i < V[x].size();i++){
        if(s == V[x][i])
            flag = true;
        sum++;
        dfs(s,V[x][i]);
        a[V[x][i]] = sum;
    }
}
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--){
        int n,v;
        cin >> n;
        memset(a,INF,sizeof(a));
        for(int i = 1;i <= n;i++){
            cin >> v;
            V[i].push_back(v);
        }
        for(int i = 1;i <= n;i++){
            flag = false;
            sum = 0;
            if(a[i] == INF)
                dfs(i,i);
        }
        for(int i = 1;i <= n;i++){
            cout << a[i] << " ";
        }
        cout << endl;
        //memset(a,INF,sizeof(a));
        for(int i = 1;i <= n;i++)
            V[i].clear();
    }
    return 0;
}

C.Good Numbers

题意

给你一个 $n$ ，让你找到一个比 $n$ 大的最小的 $m$，使得 $m$ 是由3的不同次幂加和得来

题解

先打一个表，我尝试了几次，发现 $3^{38}$ 以内的数加和是大于 $10^{18}$ 次方的，其实就是 $3$ 进制表示形式不能有 $2$，我们比较容易求出最大小于 $n$ 的数，因为我们可以从 $3$ 的高位往低位试。然后从低位到高位，把第一个 $3$ 进制位为 $0$ 的位置变成 $1$ ，其后位置全部变成 $0$，就是刚好大于等于 $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
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3+7;
const int INF = 0x3f3f3f3f;
int vis[MAXN];
ll b[MAXN];
int main() {
    ios::sync_with_stdio(false);
    b[0] = 1;
    for(ll i = 1;i <= 38;i++){
        b[i] = 3*b[i-1];
    }
    int T;
    cin >> T;
    while(T--){
        ll n;
        cin >> n;
        ll sum = 0;
        for(int i = 38;i >= 0;i--){
            if(sum + b[i] < n){
                vis[i] = 1;
                sum += b[i];
            }
        }
 
        for(int i = 0;i <= 38;i++){
            if(vis[i] == 1){
                sum -= b[i];
            } else {
                sum += b[i];
                break;
            }
        }
        cout << sum << endl;
        memset(vis,0,sizeof(vis));
    }
    return 0;
}

D.Too Many Segments

题意

给你 $n$ 个线段，求至少删除几个线段能使每个点被覆盖的次数严格小于 $k$

题解

贪心 + 线段树区间染色，首先我们想要保留尽量多的区间, 那么就要剩下的区间尽量少的重叠, 那么根据这个性质我们可以对区间进行先按右端点从小到大, 若右相等则按左从小到大这样排序.

线段树做两个事情：1.查询区间最大值(当前区间被线段覆盖得最多的这个点，判断是否还能继续加，不能就说明这条边要删去，计入答案)。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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN = 3e5+7;
const int INF = 0x3f3f3f3f;
int n,k;
vector<int> ans;
struct Tree{
    int l,r;
    int cnt;
    int mid(){
        return (l + r) >> 1;
    }
    int tag;
}tree[MAXN << 2];

struct Node{
    int l,r,index;
}DATA[MAXN];

bool cmp(Node a,Node b){
    if(a.l == b.l)
        return a.r < b.r;
    return a.l < b.l;
}

void PushUp(int rt){
    tree[rt].cnt = max(tree[rt << 1].cnt,tree[rt << 1|1].cnt);
}

void PushDown(int rt){
    if(tree[rt].tag){
        tree[rt << 1].tag += tree[rt].tag;
        tree[rt << 1|1].tag += tree[rt].tag;
        tree[rt << 1].cnt += tree[rt].tag;
        tree[rt << 1|1].cnt += tree[rt].tag;
        tree[rt].tag = 0;
    }
}

void BuildTree(int l,int r,int rt){
    tree[rt].l = l,tree[rt].r = r,tree[rt].cnt = 0;
    if(l == r)
        return ;
    int mid = tree[rt].mid();
    BuildTree(l,mid,rt << 1);
    BuildTree(mid+1,r,rt << 1|1);
}

void Update(int l,int r,int rt){
    if(tree[rt].l == tree[rt].r){
        tree[rt].tag++;
        tree[rt].cnt++;
        return ;
    }
    PushDown(rt);
    int mid = tree[rt].mid();
    if(r <= mid)
        Update(l,r,rt << 1);
    else if(l > mid)
        Update(l,r,rt << 1|1);
    else{
        Update(l,mid,rt << 1);
        Update(mid+1,r,rt << 1|1);
    }
    PushUp(rt);
}

int Query(int l,int r,int rt){
    if(tree[rt].l == tree[rt].r){
        return tree[rt].cnt;
    }
    int mid = tree[rt].mid();
    PushDown(rt);
    int ret = -1;
    if(r <= mid)
        ret = max(ret,Query(l,r,rt << 1));
    else if(l > mid)
        ret = (ret,Query(l,r,rt << 1|1));
    else{
        ret = max(ret,max(Query(l,mid,rt << 1) , Query(mid+1,r,rt << 1|1)));
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    scanf("%d %d",&n,&k);
    BuildTree(1,MAXN,1);
    for(int i = 1;i <= n;i++){
        scanf("%d %d",&DATA[i].l,&DATA[i].r);
        DATA[i].index = i;
    }
    sort(DATA+1,DATA+1+n,cmp);
    for(int i = 1;i <= n;i++){
        if(Query(DATA[i].l,DATA[i].r,1) < k){
            Update(DATA[i].l,DATA[i].r,1);
        } else {
            ans.push_back(DATA[i].index);
        }
    }
    printf("%d\n",ans.size());
    int sz = ans.size();
    for(int i = 0;i < ans.size();i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

E.By Elevator or Stairs?

题意

人在 $1$ 楼想去 $n$ 楼，可以选择上楼梯，或者等电梯，上楼梯需要花费 $a_i$ 的时间，坐电梯需要花费 $b_i$ 的时间，但是包括一个等待的时间 $c$，问到顶楼最小的时间花费。

题解

傻逼 $dp$ 题，$dp[i][0]$ 代表在第 $i$ 层走楼梯所用的最少花费， $dp[i][1]$ 代表在第 $i$ 层坐电梯所用的最少花费，然后直接 $dp$ 就完事。

初始化 dp[0][0] = 0;注意人在电梯里面的不用再计算等待电梯的时间

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN = 2e5+7;
const int INF = 0x3f3f3f3f;
int n,c;
int a[MAXN],b[MAXN];
int dp[MAXN][2];
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> c;
    for(int i = 1;i < n;i++)
        cin >> a[i];
    for(int i = 1;i < n;i++)
        cin >> b[i];
    memset(dp,INF,sizeof(dp));
    dp[0][0] = 0;
    dp[0][1] = INF;
    for(int i = 1;i < n;i++){
        dp[i][0] = min(dp[i-1][0] + a[i],dp[i][0]);
        dp[i][0] = min(dp[i-1][1] + a[i],dp[i][0]);
        dp[i][1] = min(dp[i-1][1] + b[i],dp[i][1]);
        dp[i][1] = min(dp[i-1][0] + b[i] + c,dp[i][1]);
    }
    cout << "0 ";
    for(int i = 1;i < n;i++)
        cout << min(dp[i][0],dp[i][1]) << " ";
    return 0;
}

F.Maximum Weight Subset

树形DP？ 挖坑待补

Powered by Hexo and Hexo-theme-hiker

Copyright © 2018 - 2020 Never Give Up! All Rights Reserved.

访客数 : | 访问量 :