leetcode周赛_leetcode周赛可以百度吗

---

70周双周赛（2/4）

第三题 5973. K Highest Ranked Items Within a Price Range

https://leetcode-cn.com/problems/k-highest-ranked-items-within-a-price-range/

//learn
//tuple
//auto [steps, i, j]
//默认sort从前到后 从小到大 nb！
//emplace & emplace_back

const int d[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
class Solution {
public:
    vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {
        int n = grid.size(), m = grid[0].size();
        int lo = pricing[0], hi = pricing[1];
        int r = start[0], c = start[1];
        vector<tuple<int, int, int, int>> ans;//steps, price, i, j
        queue<tuple<int, int, int>> q; //step, startx, starty
        vector<vector<bool>> vis(n, vector<bool>(m));
        
        //first
        q.emplace(0, r, c); 
        vis[r][c] = true;

        //bfs：用bfs是因为每次只扩大一个距离，所以可以用vis标记 之后不查 因为之后查的step肯定更大
        while (!q.empty()) {
            auto [steps, i, j] = q.front(); 
            if (grid[i][j] >= lo && grid[i][j] <= hi)
                ans.emplace_back(steps, grid[i][j], i, j);
            q.pop();
            for (int t = 0; t < 4; ++t) {
                int ni = i + d[t][0], nj = j + d[t][1];
                if (ni < 0 || ni >= n || nj < 0 || nj >= m || vis[ni][nj] || grid[ni][nj] == 0)
                    continue;
                q.emplace(steps + 1, ni, nj);
                vis[ni][nj] = true;
            }
        }
        sort(ans.begin(), ans.end()); //默认sort从前到后 从小到大 nb！
        vector<vector<int>> ret;
        for (int i = 0; i < min(k, (int)ans.size()); ++i)
            ret.push_back(vector<int>{get<2>(ans[i]), get<3>(ans[i])});
        return ret;
    }
};    
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

71周双周赛

5986
https://leetcode-cn.com/problems/minimum-cost-to-set-cooking-time/
不需要上来就想细节怎么做
先想模拟的大块

/*
耐心读题 耐心模拟
*/
class Solution {
public:
    string normal0(int targetSeconds){
        string str;
        int second = targetSeconds % 60;
        int fen = targetSeconds / 60;
        if(fen>99) return "0000";
        if(fen<10){
            str = "0" + to_string(fen); 
        }else{
            str = to_string(fen);
        }
        if(second<10){
            str += "0" + to_string(second); 
        }else{
            str += to_string(second);
        }
        return str;
    }
    //+60
    string normal1(int targetSeconds){
        string str;
        int second = targetSeconds % 60 + 60;
        if(second>99) return "0000";
        
        int fen = targetSeconds / 60 - 1;
        if(fen<10){
            str = "0" + to_string(fen); 
        }else{
            str = to_string(fen);
        }
        if(second<10){
            str += "0" + to_string(second); 
        }else{
            str += to_string(second);
        }
        return str;
    }
    
    int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        string normal = normal0(targetSeconds);
        string n1 = normal;
        // if(n1[0]!='0'||n1[1]!='0'){
        //     n1 = normal1(targetSeconds);
        // }
        n1 = normal1(targetSeconds);
        cout<<normal<<" "<<n1<<endl;
        
        int move = 0;
        int push = 0;
        int cur = startAt;
        int begin = 0;
        int res = INT_MAX;
        //cal normal
        if(normal!="0000"){
            while(begin!=4){
                if(normal[begin]=='0'&&push==0){
                    begin++;
                    continue;
                }
                if((normal[begin]-'0')!=cur){
                    move++;
                }
                cur = normal[begin]-'0';
                push++;
                begin++;
            }
            if(moveCost * move + pushCost * push != 0){
                res = moveCost * move + pushCost * push;    
            }
            cout<<move<<" "<<push<<" "<<res<<endl;
        }
        move = 0;
        push = 0;
        begin = 0;
        cur = startAt;
        //cal n1
        if(n1!="0000"){
            while(begin!=4){
                if(n1[begin]=='0'&&push==0){
                    begin++;
                    continue;
                }
                if((n1[begin]-'0')!=cur){
                    move++;
                }    
                cur = n1[begin]-'0';
                push++;
                begin++;
            }  
            if(moveCost * move + pushCost * push != 0){
                res = min(res,moveCost * move + pushCost * push);
            }
            cout<<move<<" "<<push<<" "<<res<<endl;
        }
        
        return res;
    }
};
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

补题
https://leetcode-cn.com/problems/minimum-difference-in-sums-after-removal-of-elements/

282场周赛 2/4

T3 6010

超时想想二分
https://leetcode-cn.com/problems/minimum-time-to-complete-trips/solution/6010-chao-shi-shi-xiang-xiang-er-fen-by-3q7is/

二分模版
while l < r:
m = (l + r) >> 1
if check(m):
l = m + 1
else:
r = m

对于二分查找，一般可用以下模板，注意区别。另外可用类似 m = l + (r - l) / 2的方式解决溢出的问题。

有几场发布在了leetcode题解中

285 1/4

T3 6029

二进制枚举

x >> y //x右移y位
x << y //x左移y位

//贪心失败
//状压二进制枚举 / 01背包
//https://leetcode-cn.com/problems/maximum-points-in-an-archery-competition/solution/by-ctysss-6r70/ 
/*
转自-wannabeaguard
以前听到状态压缩，听到二进制就后退三步，做了几道类似的题貌似有一点点上道了。其实就是一种暴力美学，尤其在n<=20这种数量级，枚举所有的可能性也就是10^6这个数量级。

对于这道题来说，要枚举的就是bob可以在哪些区域赢，每个区域都有输赢两种可能，所以所有的可能方案有2^12=4096种，这个数量级就直接暴力憋犹豫了声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】