A、最大公倍数

是一个结论题吧。
当 b b b 是奇数的时候，那么答案肯定是 b ∗ ( b − 1 ) ∗ ( b − 2 ) b*(b-1)*(b-2) b∗(b−1)∗(b−2)，因为他们两两互质。
然后当 b − a = = 2 b-a==2 b−a==2时，直接求一个lcm。
否则就是偶数：偶数的话如果是3的倍数,答案就是 ( b − 1 ) ∗ ( b − 2 ) ∗ ( b − 3 ) (b-1)*(b-2)*(b-3) (b−1)∗(b−2)∗(b−3)，否则b-1，就变成奇数的情况了。

class Solution {
public:
    
    #define ll long long
    template<typename T>T gcd(T a, T b) {return b==0?a:gcd(b, a%b);}
    template<typename T>T exgcd(T a,T b,T &g,T &x,T &y){if(!b){g = a,x = 1,y = 0;}
    else {exgcd(b,a%b,g,y,x);y -= x*(a/b);}}
    ll greatestcommonmultiple(int a, int b) {
        // write your code here
        ll res = 0;
        if(b&1)res = 1ll*b*(b-1)*(b-2);
        else if(b-a==2){
            res = lcm(b,lcm(b-1,b-2));
        }else{
            if(b%3!=0)res = 1ll*b*(b-1)*(b-3);
            else res =  1ll*(b-1)*(b-2)*(b-3);
        }
        return res;
    }
    ll lcm(int a,int b){
        return 1ll*a*b/gcd(a,b);
    }
};

B、房屋染色

定义 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] 表示以 i i i结尾颜色为 j j j且是否已有步行街的最小代价 ( 0 ≤ k ≤ 1 ) (0≤k≤1) (0≤k≤1)。
然后维护一个前缀和，那么转移就是
只移动一步。
d p [ i + 1 ] [ k ] [ 0 ] = m i n ( d p [ i + 1 ] [ k ] [ 0 ] , d p [ i ] [ j ] [ 0 ] + c o s t s [ i + 1 ] [ k ] ) ; dp[i+1][k][0] = min(dp[i+1][k][0],dp[i][j][0]+costs[i+1][k]); dp[i+1][k][0]=min(dp[i+1][k][0],dp[i][j][0]+costs[i+1][k]);
d p [ i + 1 ] [ k ] [ 1 ] = m i n ( d p [ i + 1 ] [ k ] [ 1 ] , d p [ i ] [ j ] [ 1 ] + c o s t s [ i + 1 ] [ k ] ) ; dp[i+1][k][1] = min(dp[i+1][k][1],dp[i][j][1]+costs[i+1][k]); dp[i+1][k][1]=min(dp[i+1][k][1],dp[i][j][1]+costs[i+1][k]);
有步行街。
d p [ i + p ] [ k ] [ 1 ] = m i n ( d p [ i + p ] [ k ] [ 1 ] , d p [ i ] [ k ] [ 0 ] + v a [ i + p ] [ k ] − v a [ i ] [ k ] ) ; dp[i+p][k][1] = min(dp[i+p][k][1],dp[i][k][0]+va[i+p][k]-va[i][k]); dp[i+p][k][1]=min(dp[i+p][k][1],dp[i][k][0]+va[i+p][k]−va[i][k]);

class Solution {
public:
    
    long long va[105][105];
    long long dp[105][105][2];
    int paintHouseIII(vector<vector<int>> &costs, int t) {
        // Write your code here.
        int n = costs.size(),m = costs[0].size();
        for(int i = 0;i < m;++i){
            for(int j = 0;j < n;++j){
                if(j==0)va[j][i] = costs[j][i];
                else va[j][i] = va[j-1][i] + costs[j][i];
               // cout<<j<<" "<<i<<" " << va[j][i]<<endl;
                dp[j][i][0] = dp[j][i][1] = INT_MAX;
            }
        }
        for(int i = 0;i < m;++i)dp[0][i][0] = dp[0][i][1] = costs[0][i];
        for(int i = 0;i < n;++i){
            for(int j = 0;j < m;++j){
                for(int k = 0;k < m;++k){
                    if(j==k){
                        for(int p = 0;p < t;++p){
                            if(i+p>=n)break;
                            dp[i+p][k][1] = min(dp[i+p][k][1],dp[i][k][0]+va[i+p][k]-va[i][k]);
                        }
                        continue;
                    }
                    if(i+1<n){
                        dp[i+1][k][0] = min(dp[i+1][k][0],dp[i][j][0]+costs[i+1][k]);
                        dp[i+1][k][1] = min(dp[i+1][k][1],dp[i][j][1]+costs[i+1][k]);
                    }
                }
            }
        }
        long long res = INT_MAX;
        for(int i = 0;i < m;++i)res = min(res,min(dp[n-1][i][1],dp[n-1][i][0]));
        return res;
    }
};

字符串游戏

抽象为 逆Nim 博弈
Nim 博弈：两个人玩游戏，有 n 堆石子，每次操作可以选一堆石子xjb拿，最少拿一颗，无子可取者为负。

class Solution {
public:
    
    bool stringGame(string &s) {
        // Write your code here.
        int num[30] = {0};
        for(int i = 0;i < s.size();++i){
            num[s[i]-'a']++;
        }
        int res = 0;
        bool f= 1,f1 = 0;
        for(int i = 0;i < 26;++i){
            if(!num[i])continue;
            res ^= num[i];
            if(num[i]!=1)f = 0;
            if(num[i]>1)f1 = 1;
        }
        if(f&&!res||f1&&res)return true;
        else return false;
    }
};

完美字符串

直接选取连续的0，然后最大限度的翻转它就ok了，即当有连续5个0，k=3，那么需要翻转2次。

class Solution {
public:
    
    int perfectString(string &s, int k) {
        long long res = 0;
        int i = 0,len,j;
        while(i < s.size()){
            if('1'==s[i]){i++;continue;}
            j = i;
            while(j<s.size()&&s[j]=='0')++j;
            len = j-i;
            res += len/k;
            if(len%k)res++;
            i = j;
        }
        return res;
    }
}a;