第 197 场周赛

Posted on | In , | |
Words count in article: 501 | Reading time ≈ 3

好数对的数目

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                ans += nums[i] == nums[j];
        return ans;
    }
};

仅含 1 的子串数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
    int numSub(string s) {
        int n = s.size();
        ll curr = 0, ans = 0;
        for (char c : s) {
            if (c == '1')
                curr++;
            else {
                ans += curr * (curr + 1) / 2;
                ans %= MOD;
                curr = 0;
            }
        }
        ans += curr * (curr + 1) / 2;
        ans %= MOD;
        return ans;
    }
};

概率最大的路径

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
const double eps = 1e-8;

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<double> prob(n);
        prob[start] = 1;
        vector<vector<pair<int, double>>> adj(n);
        for (int i = 0; i < edges.size(); ++i) {
            int u = edges[i][0], v = edges[i][1];
            double p = succProb[i];
            adj[u].emplace_back(v, p);
            adj[v].emplace_back(u, p);
        }
        priority_queue<pair<double, int>> pq;
        vector<bool> vis(n);
        pq.push({1, start});
        while (!pq.empty()) {
            auto top = pq.top();
            double p = top.first;
            int u = top.second;
            pq.pop();
            if (vis[u])
                continue;
            vis[u] = true;
            if (p < eps)
                continue;
            for (auto edge : adj[u]) {
                int v = edge.first;
                double now = p * edge.second;
                if (prob[v] < now) {
                    prob[v] = now;
                    pq.push({prob[v], v});
                }
            }
        }
        
        return prob[end]; 
    }
};

服务中心的最佳位置

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
const double eps = 1e-8;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

double calc(double ax, double ay, double bx, double by) {
    double dx = bx - ax, dy = by - ay;
    return sqrt(dx * dx + dy * dy);
}

class Solution {
public:
    double getMinDistSum(vector<vector<int>>& positions) {
        int n = positions.size();
        double x = 0, y = 0;
        for (auto v : positions) {
            x += v[0];
            y += v[1];
        }
        x /= n, y /= n;
        auto dist = [&](double cx, double cy) {
            double ans = 0;
            for (auto v : positions) 
                ans += calc(cx, cy, v[0], v[1]);
            return ans;
        };
        double d = dist(x, y);
        double step = 100.0;
        int done = 0;
        while (step > eps) {
            done = 0;
            for (int i = 0; i < 4; ++i) {
                double nx = (double)x + step * dx[i];
                double ny = (double)y + step * dy[i];
                double t = dist(nx, ny);
                if (t < d) {
                    d = t;
                    x = nx;
                    y = ny;
                    done = 1;
                    break;
                }
            }
            if (!done)
                step /= 2;
        }
        
        return d;
    }
};
Donate? comment?