题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution:
    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        mod=10**9+7
        def calc(s:str)->int:
            @cache
            def dfs(i:int,cnt:int,limit:int,num:int)->int:
                if len(s)==i:
                    return min_sum<=cnt<=max_sum
                res=0
                if not num:
                    res=dfs(i+1,0,0,0)
                low=0 if num else 1
                up=int(s[i]) if limit else 9
                for d in range(low,up+1):
                    res+=dfs(i+1,cnt+d,limit and d==up,1)
                return res
            return dfs(0,0,1,0)
        num1=int(num1)-1
        return (calc(num2)-calc(str(num1)))%mod

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

https://blog.csdn.net/qq_61657632/article/details/131027730?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22131027730%22%2C%22source%22%3A%22qq_61657632%22%7D

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int N = 2e5+10;
using node=tuple<int,int,int>;
int n,m;
string s;
int a[N];
set<node> st;
bool v[N];
set<int> q;
//写个思路吧
//题目：需要有一个查询和修改最小值的数据结构 
//有一个快速找到x的前驱和后驱并且能删除x的数据结构
//然后我都用的平衡树set
//第一个set需要重构，我这里用的是元组
//第二个找前驱和后驱直接二分即可

int main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    cin>>n>>s;
    s="?"+s;
    for(int i=1;i<=n;i++) cin>>a[i],q.insert(i);
    for(int i=2;i<=n;i++)
        if(s[i-1]!=s[i])
            st.insert({abs(a[i]-a[i-1]),i-1,i});
    vector<pair<int,int>> res;
    q.insert(0);q.insert(n+1);
    while(st.size())
    {
        auto [w,x,y]=*st.begin();
        st.erase(st.begin());
        if(v[x]||v[y]) continue;
        v[x]=1,v[y]=1;
        q.erase(q.lower_bound(x));
        q.erase(q.lower_bound(y));
        res.push_back({x,y});
        int l=x-1,r=y+1;
        if(l<1||r>n) continue;
        auto it=q.lower_bound(x);
        it--;
        l=*it;
        r=*q.lower_bound(y);
        if(l==0||r==n+1||v[l]||v[r]) continue;
        if(s[l]!=s[r]) st.insert({abs(a[l]-a[r]),l,r});
    }
    cout<<res.size()<<"\n";
    for(auto&e:res){
        int x=e.first,y=e.second;
        if(x>y) swap(x,y);
        cout<<x<<" "<<y<<"\n";
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

https://blog.csdn.net/qq_61657632/article/details/130920120?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22130920120%22%2C%22source%22%3A%22qq_61657632%22%7D

A.

class Solution {
public:
    string removeTrailingZeros(string num) {
        while(num.size()&&num.back()=='0') num.pop_back();
        return num;
    }
};

B.

class Solution {
public:
    vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& g) {
        vector<vector<int>> res=g;
        int n=g.size(),m=g[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
            {
                int x=i-1,y=j-1;
                unordered_set<int> st;
                while(x>=0&&y>=0){
                    st.insert(g[x][y]);
                    x--,y--;
                }
                int a=st.size();st.clear();
                x=i+1,y=j+1;
                while(x<n&&y<m){
                    st.insert(g[x][y]);
                    x++,y++;
                }
                int b=st.size();
                res[i][j]=abs(b-a);
            }
        }
        return res;
    }
};

C.
考虑全变成1或者全变成0的情况
枚举中间为分割点肯定是最优的
如果当前字符不是目标字符串，只能翻转，如果和前一个字母相同且都不是目标字符直接，同时扩展
否则，只能老实翻转当前0-i的区间，且为了不改变0-i-1的区间，所以要同时翻转0-i-1的区间

class Solution {
public:
    long long minimumCost(string s) {
        int n=s.size();
        function<long long(char)> calc=[&](char c)->long long{
            long long res=0;
            int l=n/2-1;
            for(int i=0;i<=l;i++){
                if(s[i]!=c)
                {
                    if(i>0&&s[i]==s[i-1]||i==0) res++;
                    else res+=i+i+1;
                }
            }
            for(int i=n-1;i>l;i--){
                if(s[i]!=c){
                    if(i<n-1&&s[i]==s[i+1]||i==n-1) res++;
                    else res+=n-1-i+n-i;
                }
            }

            return res;
        };

        return min(calc('0'),calc('1'));
    }
};

D.首先这是个拓扑图
只能从值小的转移到值大的
所以可DP
然后排个序直接转移，暴力会tle
然后观察可得对于i，j的状态只会直接从第i行的最大值和j列的最大值转移过来
所以维护即可类似于单调栈思想，只不过这个单调栈是一直递增的

typedef pair<int,int> pii;
class Solution {
public:
    struct node{
        int w,x,y;
    };
    int maxIncreasingCells(vector<vector<int>>& mat) {
        int n=mat.size(),m=mat[0].size();
        vector<node> a;
        map<int,vector<pii>> mp;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                mp[mat[i][j]].push_back({i,j});
        }

        int res=0;

        vector<vector<int>> row(n+1);vector<vector<int>> col(m+1);
        for(auto&[k,a]:mp)
        {
            vector<int> mx;
            for(auto&[i,j]:a)
            {
                int now=1;
                if(row[i].size())
                now=max(now,row[i][0]+1);
                if(col[j].size())
                now=max(now,col[j][0]+1);
                mx.push_back(now);
                res=max(res,now);
            }
            for(int k=0;k<a.size();k++)
            {
                auto&[x,y]=a[k];
                while(row[x].size()&&row[x].back()<=mx[k])
                    row[x].pop_back();
                row[x].push_back(mx[k]);
                while(col[y].size()&&col[y].back()<=mx[k])
                    col[y].pop_back();
                col[y].push_back(mx[k]);
            }
        }
        return res;
    }
};

A.

class Solution {
public:
    int buyChoco(vector<int>& p, int money) {
        sort(p.begin(),p.end());
        int x=p[0]+p[1];
        if(x>money) return money;
        else return money-x;
    }
};

B.
爆搜加一点点优化

typedef pair<int,int> PII;
class Solution {
public:
    int minExtraChar(string s, vector<string>& d) {
        int n=s.size();
        int res=INT_MAX;
        unordered_map<int,vector<int>> mp;
        for(int i=0;i<n;i++)
        {
            for(auto&ss:d)
            {
                int m=ss.size();
                if(i+m-1<n){
                    string t=s.substr(i,m);
                    if(t==ss){
                        mp[i].push_back(i+m);
                    }
                }
            }    
        }
        function<void(int,int)> dfs=[&](int id,int cnt)
        {
            if(cnt>=res) return ;
            if(id>=n)
            {
                res=min(res,cnt);
                return ;
            }
            for(int i=0;i<mp[id].size();i++){
                dfs(mp[id][i],cnt);
            }
            dfs(id+1,cnt+1);
        };
        dfs(0,0);
        return res;
    }
};

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        ans=51
        n=len(s)
        g=defaultdict(list)
        for i in range(n):
            for t in dictionary:
                m=len(t)
                if i+m-1<n and s[i:i+m]==t:
                    g[i].append(i+m)
        def dfs(u:int,cnt:int):
            nonlocal ans
            if cnt>=ans:return
            if u>=n:
                ans=min(ans,cnt)
                return 
            for i in g[u]:
                dfs(i,cnt)
            dfs(u+1,cnt+1) 
        dfs(0,0)
        return ans

C.
贪心这题，但是范围很小比赛直接二进制枚举了

class Solution {
public:
    long long maxStrength(vector<int>& nums) {
        int n=nums.size();
        long long res=0;
        if(n==1) return nums[0];
        for(int i=0;i<1<<n;i++)
        {
            long long mx=0;
            for(int j=0;j<n;j++)
            {
                if(i>>j&1)
                {
                    if(mx==0&&nums[j]!=0)
                    {
                        mx=nums[j];
                    }
                    else
                    mx=mx*nums[j];
                }
            }
            res=max(res,mx);
        }
        return res;

    }
};

D.并查集+分解质因数
为啥看出并查集，其实题目意思就是问能否通过gcd形成一个集合
so并查集

const int N=1e5+10;
class Solution {
public:

    bool canTraverseAllPairs(vector<int>& nums) {
       unordered_map<int,int> mp;
       int n=nums.size();
        if(n==1) return true;
        vector<int> p(n+1,0),siz(n+1,0);
        int res=0;
        function<int(int)> find=[&](int x){
            if(p[x]!=x){
            p[x]=find(p[x]);
        }
        return p[x];
        };
        for(int i=0;i<n;i++) p[i]=i,siz[i]=1;
        for(int i=0;i<n;i++)
        {
            for(int j=2;j<=nums[i]/j;j++)
            {
                if(nums[i]%j==0)
                {
                    if(mp.count(j))
                    {
                        int a=find(i),b=find(mp[j]);
                        if(a!=b)
                        {
                            siz[b]+=siz[a];
                            p[a]=b;
                            res=max(res,siz[b]);
                        }
                    }    
                    else mp[j]=find(i);
                    while(nums[i]%j==0) nums[i]/=j;
                }
            }
            if(nums[i]>1)
            {
                if(mp.count(nums[i]))
                {
                        int a=find(i),b=find(mp[nums[i]]);
                        if(a!=b)
                        {
                            siz[b]+=siz[a];
                            p[a]=b;
                            res=max(res,siz[b]);
                        }
                    }    
                else mp[nums[i]]=find(i);
            }
        }

        return res==n;
    }
};

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5010;
char s[N][N],g[N][N];
char a[N][N];
int n,m,k;
int main()
{
    cin>>n>>k;
    int kk=k;
    int m=n;
    k--;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            cin>>a[i][j],s[i][j]=a[i][j];
    }
    while(k--){
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(s[i][j]=='.')
                {
                    for(int x=0;x<m;x++){
                        for(int y=0;y<m;y++)
                        {
                            g[i*m+x][j*m+y]=a[x][y];    
                        }
                    }
                }
                else
                {
                    for(int x=0;x<m;x++){
                        for(int y=0;y<m;y++)
                        {
                            g[i*m+x][j*m+y]='*';    
                        }
                    }
                }
            }
        }
        memcpy(s,g,sizeof(s));
        if(k==0) break;
        n=n*m;
    }
    int nn=pow(m,kk);

    for(int i=0;i<nn;i++){
        for(int j=0;j<nn;j++)
            cout<<s[i][j];
        cout<<"\n";
    }

};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

https://blog.csdn.net/qq_61657632/article/details/130894219?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22130894219%22%2C%22source%22%3A%22qq_61657632%22%7D