第 182 场周赛

Posted on | In , | |
Words count in article: 702 | Reading time ≈ 4

5368. 找出数组中的幸运数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findLucky(vector<int>& arr) {
        map<int, int> mp;
        for(auto& i: arr) {
            mp[i]++;
        }
        int curmax = -1;
        for(auto i: mp) {
            if(i.first == i.second) {
                curmax = max(curmax, i.first);
            }
        }
        return curmax;
    }
};

5369. 统计作战单位数

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
class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = rating.size();
        vector<int> smallL(n);
        vector<int> bigR(n);
        vector<int> smallR(n);
        vector<int> bigL(n);
        int countmin = 0;
        int countbig = 0;
        for(int i=1; i<n; i++) {
            for(int j=0; j<i; j++) {
                if(rating[j] < rating[i]) countmin++;
                if(rating[j] > rating[i]) countbig++;
            }
            smallL[i] = countmin;
            bigL[i] = countbig;
            countmin = 0;
            countbig = 0;
        } // smallL bigL
        for(int i=0; i<n-1; i++) {
            for(int j=n-1; j>i; j--) {
                if(rating[j] < rating[i]) countmin++;
                if(rating[j] > rating[i]) countbig++;
            }
            smallR[i] = countmin;
            bigR[i] = countbig;
            countmin = 0;
            countbig = 0;
        } // smallR bigR
        int ret = 0;
        for(int i=1; i<n-1; i++) {
            ret += smallL[i]*bigR[i];
            ret += smallR[i]*bigL[i];
        }
        return ret;    
    }
};

5370. 设计地铁系统

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
class UndergroundSystem {
public:
    unordered_map<int , string> start;
    unordered_map<int , int> starttime;
    unordered_map<string , int> mp1;
    unordered_map<string , int> mp2;
    unordered_map<string , double> mp3;
    
    UndergroundSystem() {
        
    }
    
    void checkIn(int id, string stationName, int t) {
        starttime[id] = t;
        start[id] = stationName;
    }
    
    void checkOut(int id, string stationName, int t) {
        string tmp = start[id]+" "+stationName;
        mp1[tmp] += (t-starttime[id]);
        mp2[tmp] += 1;
        mp3[tmp] = (mp1[tmp]*1.0)/(mp2[tmp]*1.0);
    }
    
    double getAverageTime(string startStation, string endStation) {
        string tmp = startStation+" "+endStation;
        return mp3[tmp];
    }
};

5371. 找到所有好字符串

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
class Solution {
    int n = 0, m = 0;
    string evil;
    using ll = long long;
    const ll mod = 1e9 + 7;
public:
    ll dp[505][30][56];

    void kmp_init(int n, vector<int>&pi, const string&a)
    {
        pi = vector<int>(a.size(), 0);
        for (int i = 1; i < n; ++i)
        {
            int j = pi[i - 1];
            while (j > 0 && a[i] != a[j])
            {
                j = pi[j - 1];
            }
            if (a[i] == a[j]) j++;
            pi[i] = j;
        }
    }
    vector<int> p;
    ll dfs(int cur, int st, int front, bool op, const string&s)
    {
        if (front == m)return 0;
        if (cur >= n) return 1;
        if (!op && ~dp[cur][st][front]) return dp[cur][st][front];
        int mx = op ? s[cur] - 'a' : 25;
        ll res = 0;
        for (int i = 0; i <= mx; ++i)
        {
            if (i == evil[front] - 'a')
            {
                res += dfs(cur + 1, i, front + 1, op&& i == mx, s);
            }
            else
            {
                int tf = 0;
                if (front > 0)
                {
                    int j = p[front - 1];
                    while (j > 0 && evil[j] - 'a' != i)
                    {
                        j = p[j - 1];
                    }
                    if (evil[j] - 'a' == i) j++;
                    tf = j;
                }
                else
                {
                    tf = i == evil[0] - 'a';
                }
                res += dfs(cur + 1, i, tf, op&& i == mx, s);
            }
            res %= mod;
        }
        res %= mod;
        if (!op) dp[cur][st][front] = res;
        return res;
    }
    int findGoodStrings(int n, string s1, string s2, string evil) {
        if (s1 > s2) return 0;
        this->evil = evil;
        this->n = n;
        m = evil.size();
        kmp_init(m, p, evil);
        memset(dp, -1, sizeof(dp));
        ll res = dfs(0, 26, 0, 1, s1);
        memset(dp, -1, sizeof(dp));
        res = dfs(0, 26, 0, 1, s2) - res;
        int flag = 1;
        for (int i = 0; i + m <= n; ++i)
        {
            if (s1[i] == evil[0] && s1.substr(i, m) == evil)
            {
                flag = 0; break;
            }
        }
        return (res + mod + flag) % mod;
    }
};
Donate? comment?