【kickstart】 kickstart 2021 roundD

kickstart 2021 roundD

kick start的题目质量非常高，感觉前三题没有问题，自己可以确定前三题做出来。前两题做出来了，后来因为有事，三四题就没有做。第三题不用看解答就能干出来。

Arithmetic Square

题目

地址

https://codingcompetitions.withgoogle.com/kickstart/round/00000000004361e3/000000000082b813

题意

暴力

思路

  1. 第一题比较简单，大意就是给定一个3x3的矩阵，求问修改最中间的数，使得上下和对角线的三个数字组成的等差序列最多。暴力尝试所有可能的等差数列即可。

    代码

    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
    #include<iostream>
    #include<vector>
    #include<set>
    #include<unordered_set>
    #include<map>
    #include<unordered_map>
    #include<string>
    #include<stack>
    #include<algorithm>
    #include<limits.h>

    using namespace std;

    void slove(int t){
        int ans = 0;
        int curr = 0;
        map<int,int> cnt;
        vector<vector<long long>> matrix(3,vector<long long>(3));
        cin>>matrix[0][0]>>matrix[0][1]>>matrix[0][2];
        cin>>matrix[1][0]>>matrix[1][2];
        cin>>matrix[2][0]>>matrix[2][1]>>matrix[2][2];
        if((matrix[0][1] - matrix[0][0]) == (matrix[0][2] - matrix[0][1])) ans++;
        if((matrix[2][1] - matrix[2][0]) == (matrix[2][2] - matrix[2][1])) ans++;
        if((matrix[1][0] - matrix[0][0]) == (matrix[2][0] - matrix[1][0])) ans++;
        if((matrix[1][2] - matrix[0][2]) == (matrix[2][2] - matrix[1][2])) ans++;
        
        int a = matrix[1][2] - matrix[1][0];
        if(a%2 == 0){
            cnt[a/2 + matrix[1][0]]++;
        }
        int b = matrix[2][1] - matrix[0][1];
        if(b%2 == 0){
            cnt[b/2 + matrix[0][1]]++;
        }
        int c = matrix[2][2] - matrix[0][0];
        if(c%2 == 0){
            cnt[c/2 + matrix[0][0]]++;
        }
        int d = matrix[2][0] - matrix[0][2];
        if(d%2 == 0){
            cnt[d/2 + matrix[0][2]]++;
        }
        for(auto v : cnt){
            curr = max(curr,v.second);
        }
        ans += curr;
        cout<<"Case #"<<t<<": ";
        cout<<ans;
        cout<<endl;
    }

    int main(){
        int t;
        cin>>t;
        for(int i = 0; i < t; ++i){
            slove(i+1);
        }
        return 0;
    }

Cutting Intervals

题目

地址

https://codingcompetitions.withgoogle.com/kickstart/round/00000000004361e3/000000000082b933

题意

差分数组 + 贪心

思路

  1. 给定一系列的二维空间中的线段，在限定的切割操作中，求问最多可以把这些线段切成多少段？
  2. 我们可以参考线段的切割情况如下：

    我们可以看到可以利用查分数组，即可计算连续的区间内每切一次可以增加多少条线段，我们设区间$[x,y]$总共有d条线段重合，则我们首先可以知道在区间$[x+1,y-1]$我们每切割一次则可以增加d条线段，但在区间两个端点处需要特殊处理，我们此时需要判断在点$y$处需要特殊处理，因为端点处；我们首先讲可以进行切割的区间加入到待选队列中，并按照重合的次数进行排序。但是我们需要注意的是区间的右端点，需要将右端点为结束端点的线段去掉。
    1
    2
    3
    4
    5
    |__|__|________|  |        |     | 
    |  |  |________|__|________|     |
    |  |——|————————|——|        |     |
    |  |  |        |__|________|_____|
    1  2  3        6  7        10    12
  3. 如上图所示，我们可以看到在区间[1,2]之间只有1条线段重合，在区间[2,3]之间有两条线段重合，在区间[3,6]之间只有3条线段重合，[6,7]之间有3条线段重合，[7,10]之间有两条线段重合，[10,12]之间有两条线段重合。我们知道区间分布如下：
  • [1,2]无法分割。
  • [2,3]无法分割。
  • [3,6]在(4,5)处每分割一次即可增加3个线段但在6处进行分割只能增加两条线段。
  • [7，10]在(8,9)处分割每分割一次即可增加2个线段，但在10分割只能增加1个线段
  • [10,12]在(11)处分割每分割一次即可增加1个线段，但在12处无法分割。
  1. 我们利用查分数组很快即可以计算出每个区间内重叠的线段的次数，并按照次数的大小进行排序即可，我们使用贪心策略，每次选取分割区间最大的点即可。

    代码

    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
    #include<iostream>
    #include<vector>
    #include<set>
    #include<unordered_set>
    #include<map>
    #include<unordered_map>
    #include<string>
    #include<stack>
    #include<algorithm>
    #include<limits.h>

    using namespace std;
    typedef long long LL;

    void slove(int t){
        long long ans = 0;
        long long n,c;
        map<long long,int> prev;
        map<long long,int> arrl;
        map<long long,int> arrr;
        cin>>n>>c;
        // 查分数组
        for(int i = 0; i < n; ++i){
            long long l,r;
            cin>>l>>r;
            prev[l]++;
            prev[r]--;
            arrl[l]++;
            arrr[r]++;
        }
        
        ans = n;
        map<long long,long long> arr;
        long long left = -1;
        long long curr = 0;
        // 记录左端点与右端点
        for(auto v : prev){
            if(curr == 0){
                left = v.first;
                curr += v.second;
            }else{
                arr[curr] += v.first - left - 1;
                arr[curr-arrr[v.first]]++;
                left = v.first;
                curr += v.second;
            }
        }
        // 贪心策略每次取切割可以得到的最大线段的点
        for(auto it = arr.rbegin(); it != arr.rend(); it++){
            long long x = min(c,it->second);
            ans += x*it->first;
            c -= x;
            if(c <= 0) break;
        }
        cout<<"Case #"<<t<<": ";
        cout<<ans;
        cout<<endl;
    }

    int main(){
        int t;
        cin>>t;
        for(int i = 0; i < t; ++i){
            slove(i+1);
        }
        return 0;
    }

Final Exam

地址

https://codingcompetitions.withgoogle.com/kickstart/round/00000000004361e3/000000000082bffc

题意

二分查找

思路

  1. 感觉第三题要比第二题简单许多，就是一个典型的二分查找的应用即可。我们知道给定难度P,则我们知道绝对值最小值得点肯定在距离点p最近的两个区间，我们利用二分查找，查找距离点p最近的两个区间$[l{1},r{1}],[l{2},r{2}]$且满足$l{1}\le r{1}\le l{2}\le r{2}$，如果点p在区间$[l{1},r{1}]$范围内，则我们可以知道当前最小的绝对值为0，则我们将p从区间内取出，并将原有区间$[l{1},r{1}]$划分为两个新的区间$[l{1},p-1],[p+1,r{1}]$,并将这两个新的区间加入到待选序列中。
    1
    2
    ________  |    __________
    [l1,r1]  p       [l2,r2]
  2. 如果不在区间内，则肯定距离p最近的点要么为$r{1},l{2}$,则我们优先从这两个点中选择距离最近的点即可，假设$r{1}$距离点p最近，则我们将$r{1}$从区间内取出，然后再更新区间为$[l{1},r{1}-1]$.

    代码

    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
    #include<iostream>
    #include<vector>
    #include<set>
    #include<unordered_set>
    #include<map>
    #include<unordered_map>
    #include<string>
    #include<stack>
    #include<algorithm>
    #include<limits.h>

    using namespace std;
    typedef long long LL;

    void slove(int t){
        int n,m;
        map<LL,LL> pb;
        vector<LL> ans;
        cin>>n>>m;
        vector<LL> arr = vector<LL>(m);
        for(int i = 0; i < n; ++i){
            LL a,b;
            cin>>a>>b;
            pb[b] = a;
        }
        for(int i = 0; i < m; ++i){
            cin>>arr[i];
            auto it = pb.lower_bound(arr[i]);
            if(it == pb.end()){
                it--;
                ans.push_back(it->first);
                LL a = it->first;
                LL b = it->second;
                pb.erase(a);
                a--;
                if(a >= b) pb[a] = b;
            }else{
                LL a = it->first;
                LL b = it->second;
                if(it->second > arr[i]){
                    if(it == pb.begin()){
                        ans.push_back(b);
                        b++;
                        pb.erase(a);
                        if(b <= a) pb[a] = b;
                    }else{
                        it--;
                        LL c = it->first;
                        LL d = it->second;
                        if(abs(arr[i]-c) > abs(arr[i] - b)){
                            ans.push_back(b);
                            b++;
                            pb.erase(a);
                            if(b <= a) pb[a] = b;
                        }else{
                            ans.push_back(c);
                            pb.erase(c);
                            c--;
                            if(d <= c) pb[c] = d;
                        }
                    }                
                }else{
                    ans.push_back(arr[i]);
                    LL c = arr[i] - 1;
                    LL d = arr[i] + 1;
                    pb.erase(a);
                    if(c >= b) pb[c] = b;
                    if(d <= a) pb[a] = d;
                }
            }
        }
        
        cout<<"Case #"<<t<<": ";
        for(int i = 0; i < ans.size(); ++i){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }

    int main(){
        int t;
        cin>>t;
        for(int i = 0; i < t; ++i){
            slove(i+1);
        }
        return 0;
    }

#

欢迎关注和打赏，感谢支持！

算法
#kickstart
【kickstart】 kickstart 2021 roundD
http://example.com/2026/09/08/力扣周赛题解/64/
Author
Mike Meng
Posted on
September 8, 2026
Licensed under