1.使二进制字符串变美丽的最少修改次数

贪心

int minChanges(string s) {
    int ans = 0;
    for (int i = 0; i < s.length(); i += 2) {
        ans += s[i] != s[i + 1];
    }
    return ans;
}

2.和为目标值的最长子序列的长度

恰好装满型01背包

int lengthOfLongestSubsequence(vector<int> &nums, int target) {
    vector<int> f(target+1,INT_MIN);
    f[0]=0;
    int s=0;
    for (int x : nums) {
        s=min(s+x,target);
        for (int j=s;j>=x;j--) {
            f[j]=max(f[j],f[j-x]+ 1);
        }
    }
    return f[target]>0?f[target]:-1;
}

3.子数组不同元素数目的平方和 II

线段树

本题类似于2262. 字符串的总引力

子区间dp

dp[i]表示以i为结尾的所有子区间的不同计数的平方和

当放入nums[i]时，若前nums{0~i-1}不存在和nums[i]相等的数，则相当于在每个子区间后面添加nums[i]，一个子区间的增加原先大小为x，增加后大小为x+1，一个子区间的增量为​(x+1)^2-x^2=2*x-1，此时找不到设j为0

若前nums{0~i-1}存在和nums[i]相等的数，那等价于在上一次出现nums[j]的位置的后面都增加一个增量（2*x-1）

则表达式如下 ​ j=\left\{\begin{matrix} 0, &last[i]=0\\ last[i], &last[i]!=0\end{matrix}\right.
​dp[i]=dp[i-1]+fun(j+1,i)*2+i-j

其中fun(j+1,i)表示区间(j,i)的在填入nums[i]后的“不同计数”

class Solution {
    vector<long long> sum;
    vector<int> todo;
    const int mod=1e9+7;

    void do_(int o, int l, int r, int add) {
        sum[o] += (long long) add * (r - l + 1);
        todo[o] += add;
    }

    // o=1  [l,r] 1<=l<=r<=n
    // 把 [L,R] 加一，同时返回加一之前的区间和
    long long query_and_add1(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            long long res = sum[o];
            do_(o, l, r, 1);
            return res;
        }

        int m = (l + r) / 2;
        int add = todo[o];
        if (add != 0) {
            do_(o * 2, l, m, add);
            do_(o * 2 + 1, m + 1, r, add);
            todo[o] = 0;
        }

        long long res = 0;
        if (L <= m) res += query_and_add1(o * 2, l, m, L, R);
        if (m < R)  res += query_and_add1(o * 2 + 1, m + 1, r, L, R);
        sum[o] = sum[o * 2] + sum[o * 2 + 1];
        return res;
    }

public:
    int sumCounts(vector<int> &nums) {
        int n = nums.size();
        sum.resize(n * 4);
        todo.resize(n * 4);

        long long ans = 0, s = 0;
        unordered_map<int, int> last;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int j = last.count(x) ? last[x] : 0;
            s += query_and_add1(1, 1, n, j + 1, i) * 2 + i - j;
            ans = (ans + s) % mod;
            last[x] = i;
        }
        return ans;
    }
};