theory.md

习题

多边形构造

[!NOTE] LeetCode 2971. 找到最大周长的多边形

题意: TODO

[!TIP] 思路

如果有 k (k >= 3) 个 正 数 a1,a2,a3, ... ak 满足 a1 <= a2 <= a3 <= ... <= ak 且 a1 + a2 + a3 + ... + ak-1 > ak ，那么 一定 存在一个 k 条边的多边形，每条边的长度分别为 a1, a2, a3, ... ak

排序贪心即可

详细代码

C++

class Solution {
public:
    using LL = long long;
    const static int N = 1e5 + 10;
    
    LL s[N];
    
    long long largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        {
            s[0] = 0;
            for (int i = 1; i <= n; ++ i )
                s[i] = s[i - 1] + nums[i - 1];
        }
        
        // ATTENTION: 贪心即可 【不需要双指针】
        for (int i = n; i >= 1; -- i )
            if (s[i - 1] > nums[i - 1])
                return s[i];
        return -1;
    }
};

Python

---

拉格朗日四平方和

[!NOTE] LeetCode 279. 完全平方数

题意: TODO

[!TIP] 思路

拉格朗日四平方和定理

• 定理内容：每个正整数均可表示成不超过四个整数的平方之和，即答案只有1、2、3、4
• 重要的推论：
  1. 数n如果只能表示成四个整数的平方和，不能表示成更少的数的平方之和，必定满足n=(4^a)*(8b+7)
  2. 如果 n%4==0，k=n/4，n 和 k 可由相同个数的整数表示
• 如何利用推论求一个正整数最少需要多少个数的平方和表示：
  1. 先判断这个数是否满足 n=(4^a)*(8b+7)，如果满足，那么这个数就至少需要 4 个数的平方和表示，即答案为4。
  2. 如果不满足，再在上面除以 4 之后的结果上暴力尝试只需要 1 个数就能表示和只需要 2 个数就能表示的情况。
  3. 如果这个数本来就是某个数的平方，那么答案就是1
  4. 如果答案是2的话，那么n=a^2+b^2，枚举a即可
  5. 如果还不满足，那么就只需要 3 个数就能表示

详细代码

C++

class Solution {
public:
    bool check(int x) {
        int r = sqrt(x);
        return r * r == x;
    }

    int numSquares(int n) {
        if (check(n)) return 1;

        for (int a = 1; a <= n / a; a ++ )
            if (check(n - a * a))
                return 2;

        while (n % 4 == 0) n /= 4;
        if (n % 8 != 7) return 3;
        return 4;
    }
};

C++ dp

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1);
        for (int i = 1; i <= n; ++ i ) {
            dp[i] = i;
            for (int j = 1; j <= i / j; ++ j ) {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
};

Python

"""
完全背包问题

(动态规划) O(nn‾√)
设 f(i) 表示通过平方数组成 i 所需要完全平方数的最少数量。
初始时，f(0)=0其余待定。
转移时，对于一个 i，枚举 j，f(i)=min(f(i−j∗j)+1) ，其中 1≤j≤√i。
最终答案为 f(n)。
"""

import math
class Solution:
    def numSquares(self, n: int) -> int:

        goods = [i * i for i in range(1, int(math.sqrt(n))+1)]

        f = [float('inf')] * (n+1)
        f[0] = 0

        for good in goods:
            for j in range(good, n+1):
                f[j] = min(f[j], f[j-good]+1)

        return f[-1]

---

约数与完全平方数

[!NOTE] LeetCode 319. 灯泡开关

题意: TODO

[!TIP] 思路

每个灯泡开关被按的次数等于它的编号的约数个数。

最终灯泡是亮的，说明编号有奇数个约数。

下面我们证明：一个数有奇数个约数，等价于它是平方数。

略

详细代码

C++

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

Python

---

[!NOTE] LeetCode 672. 灯泡开关 Ⅱ

题意: TODO

[!TIP] 思路

经典状态机 重复

详细代码

C++ 推导

class Solution {
public:
    int flipLights(int n, int m) {
        n = min(n, 3);
        if (m == 0) return 1;
        if (m == 1) return n == 1 ? 2 : n == 2 ? 3 : 4;
        if (m == 2) return n == 1 ? 2 : n == 2 ? 4 : 7;
        return n == 1 ? 2 : n == 2 ? 4 : 8;
    }
};

C++ 状态机

class Solution {
public:
    int state[8][6] = {
        {1, 1, 1, 1, 1, 1},  // 不按
        {0, 0, 0, 0, 0, 0},  // 1
        {1, 0, 1, 0, 1, 0},  // 2
        {0, 1, 0, 1, 0, 1},  // 3
        {0, 1, 1, 0, 1, 1},  // 4
        {1, 0, 0, 1, 0, 0},  // 14
        {0, 0, 1, 1, 1, 0},  // 24
        {1, 1, 0, 0, 0, 1},  // 34
    };

    int work(int n, vector<int> ops) {
        set<int> S;
        for (auto op: ops) {
            int t = 0;
            for (int i = 0; i < n; i ++ )
                t = t * 2 + state[op][i];
            S.insert(t);
        }
        return S.size();
    }

    int flipLights(int n, int m) {
        n = min(n, 6);
        if (m == 0) return work(n, {0});
        else if (m == 1) return work(n, {1, 2, 3, 4});
        else if (m == 2) return work(n, {0, 1, 2, 3, 5, 6, 7});
        else return work(n, {0, 1, 2, 3, 4, 5, 6, 7});
    }
};

Python

---

[!NOTE] LeetCode 1375. 灯泡开关 III

题意: TODO

[!TIP] 思路

左边连续亮 则左边的都变成蓝色 求所有灯变成蓝色的时刻的数目

其实就是求 亮的个数 == 最靠右的灯的序号 的数目

详细代码

C++

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int res = 0;
        int maxv = 0, cnt = 0;
        for (auto k : light) {
            maxv = max(maxv, k);
            ++cnt;
            if (maxv == cnt) ++res;
        }
        return res;
    }
};

Python

---

[!NOTE] LeetCode 1529. 灯泡开关 IV

题意: TODO

[!TIP] 思路

• 显然需要从最左侧考虑 边处理边记录整个右侧的状态 扫一遍即可

• 赛榜有别的做法 都是从最右侧考虑得到：从左向右扫相邻数值不等则加1

详细代码

C++ 1

class Solution {
public:
    int minFlips(string target) {
        int n = target.size();
        int now = 0, res = 0;  // now表示整个处理点右侧的状态 res为改动次数
        for (int i = 0; i < n; ++i) {
            if (target[i] == '1' && now & 1)
                continue;
            else if (target[i] == '0' && !(now & 1))
                continue;
            now ^= 1, ++res;
        }
        return res;
    }
};

C++ 2

class Solution {
public:
    int minFlips(string s) {
        s = "0" + s;
        int res = 0;
        for (int i = 1; i < s.size(); ++i)
            if (s[i] != s[i - 1]) ++res;
        return res;
    }
};

Python

---

[!NOTE] LeetCode 365. 水壶问题

题意: TODO

[!TIP] 思路

详细代码

C++

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if (x + y < z) return false;
        return !z || z % __gcd(x, y) == 0;
    }
};



class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if (x + y < z) return false;
        if (x == 0 || y == 0) return z == 0 || x + y == z;
        return z % __gcd(x, y) == 0;
    }
};

Python

---

[!NOTE] Codeforces A. LCM Challenge

题意: TODO

[!TIP] 思路

思维题

数学推导 结论

详细代码

C++

// Problem: A. LCM Challenge
// Contest: Codeforces - Codeforces Round #146 (Div. 1)
// URL: https://codeforces.com/problemset/problem/235/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
using namespace std;

// 猜想错误
// https://codeforces.com/contest/235/submission/109974211
//
// When n is odd, the answer is obviously n(n-1)(n-2).
// When n is even, we can still get at least (n-1)(n-2)(n-3),
// so these three numbers in the optimal answer would not be
// very small compared to n. So we can just iterate
// every 3 number triple in [n-50,n] and update the answer.
//
// 1. 相邻的两个数一定互质
// 2. 相邻的两个奇数一定互质
//
// n 为奇数 ans = n * (n - 1) * (n - 2)
// n 为偶数 【此时 n与n-2显然会有公约数】
//        n % 3 != 0 意味着 n 和 n-3 没有约数 ans = n * (n - 1) * (n - 3)
//        n % 3 == 0 有公约数               ans = (n - 1) * (n - 2) * (n - 3)
using LL = long long;

int main() {
    LL n;
    cin >> n;

    if (n <= 2)
        cout << n << endl;
    else {
        if (n % 2 == 0) {
            // https://codeforces.com/contest/235/submission/109975226
            if (n % 3)
                cout << n * (n - 1) * (n - 3) << endl;
            else
                cout << (n - 1) * (n - 2) * (n - 3) << endl;
        } else
            cout << n * (n - 1) * (n - 2) << endl;
    }

    return 0;
}

Python

---

[!NOTE] Codeforces C. Divisibility by Eight

题意: TODO

[!TIP] 思路

重复做...小学奥数

一个数要被 8 整除 末尾三个数一定是 8 的倍数

详细代码

C++

// Problem: C. Divisibility by Eight
// Contest: Codeforces - Codeforces Round #306 (Div. 2)
// URL: http://codeforces.com/problemset/problem/550/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    s = "00" + s;
    int n = s.size();

    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            for (int k = j + 1; k < n; ++k) {
                int x = 100 * (s[i] - '0') + 10 * (s[j] - '0') + s[k] - '0';
                if (x % 8 == 0) {
                    cout << "YES" << endl << x << endl;
                    return 0;
                }
            }
    cout << "NO" << endl;

    return 0;
}

Python

---

概率

[!NOTE] Codeforces Archer

题意:

已知每局第一个人射中的概率是 $p$ ，第二个人射中的概率是 $q$ 。

谁先射中谁赢，求第一个人赢的概率。

[!TIP] 思路

$p = a / b, q = c / d$

$ans=p+(1−p)(1−q)p+[(1−p)(1−q)]^2p+[(1−p)(1−q)]^3p+...$

设 $x=(1-p)*(1-q)$ 则上式等于 $ans=p(1+x+x^2+x^3+...)$

后者等比数列求和，转化为 $ans=p((1-x^n)/(1-x))$

因为 $x$ 趋近于 $0$，$ans=p/(1-x)$

详细代码

C++

// Problem: B. Archer
// Contest: Codeforces - Codeforces Round #185 (Div. 2)
// URL: https://codeforces.com/problemset/problem/312/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
using namespace std;

int main() {
    double a, b, c, d;
    cin >> a >> b >> c >> d;

    double p = a / b, q = c / d;
    double x = (1.0 - p) * (1.0 - q);

    printf("%.12lf\n", p / (1 - x));

    return 0;
}

Python

---

有理数

[!NOTE] LeetCode 972. 相等的有理数

题意: TODO

[!TIP] 思路

详细代码

C++

class Solution {
public:
    // 任何一个有理数都可以和一个分数一一对应
    // 3.5(25) ==> 3/1 + 5/10 + 25/990
    // 0.(32) ==> 32/99

    using LL = long long;

    class Frac {
    public:
        LL x, y;
        Frac(LL _x, LL _y) {
            LL t = gcd(_x, _y);
            x = _x / t, y = _y / t;
        }

        LL gcd(LL x, LL y) { return y ? gcd(y, x % y) : x; }
        bool operator == (const Frac & p) const { return x == p.x && y == p.y; }
        Frac operator + (const Frac & p) const { return Frac(x * p.y + y * p.x, y * p.y); }
    };

    Frac get(string s) {
        int n = s.size(), i = 0;

        LL a = 0, b = 0, lb = 1, c = 0, lc = 1;

        while (i < n && s[i] != '.')
            a = a * 10 + s[i] - '0', i ++ ;
        i ++ ;  // skip '.'

        while (i < n && s[i] != '(')
            b = b * 10 + s[i] - '0', lb *= 10, i ++ ;
        i ++ ;  // skip '('

        while (i < n && s[i] != ')')
            c = c * 10 + s[i] - '0', lc *= 10, i ++ ;
        
        auto ret = Frac(a, 1) + Frac(b, lb);
        if (lc != 1)    // non-empty
            ret = ret + Frac(c, (lc - 1) * lb); // ATTENTION: *lb
        return ret;
    }

    bool isRationalEqual(string s, string t) {
        return get(s) == get(t);
    }
};

Python

---

方差

[!NOTE] LeetCode AutoX 2023 蚂蚁王国的蜂蜜

题意: TODO

[!TIP] 思路

方差又等于 $平方的均值 - 均值的平方$

故可以进一步简化计算过程

详细代码

C++ 数学定理

class Solution {
public:
    vector<double> honeyQuotes(vector<vector<int>>& handle) {
        double s = 0, t = 0, c = 0;
        vector<double> res;
        for (auto & h : handle) {
            int type = h[0];
            if (type == 1) {
                int x = h[1];
                s += x, t += x * x, c ++ ;
            } else if (type == 2) {
                int x = h[1];
                s -= x, t -= x * x, c -- ;
            } else if (type == 3) {
                res.push_back(c ? s / c : -1);
            } else {
                res.push_back(c ? t / c - s / c * s / c : -1);
            }
        }
        return res;
    }
};

C++ 暴力

class Solution {
public:
    const static int N = 110;
    
    int c[N], s, t;
    vector<double> honeyQuotes(vector<vector<int>>& handle) {
        memset(c, 0, sizeof c);
        s = 0, t = 0;
        
        vector<double> res;
        for (auto & h : handle) {
            int type = h[0];
            if (type == 1) {
                int p = h[1];
                c[p] ++ ;
                s += p, t ++ ;
            } else if (type == 2) {
                int p = h[1];
                c[p] -- ;
                s -= p, t -- ;
            } else if (type == 3) {
                if (t == 0)
                    res.push_back(-1);
                else
                    res.push_back((double)s / t);
            } else {
                if (t == 0)
                    res.push_back(-1);
                else {
                    double x = (double)s / t;
                    double y = 0;
                    for (int i = 0; i < N; ++ i )
                        if (c[i]) {
                            double v = (double)(i - x);
                            y += v * v * c[i];
                        }
                    res.push_back(y / t);
                }
            }
        }
        return res;
    }
};

Python

---