头像

雨小伍




离线:4小时前


活动打卡代码 AcWing 135. 最大子序和

雨小伍
4小时前
#include <iostream>
using namespace std;

const int N = 300000 + 7;

int a[N],s[N],q[N],n,m;
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        s[i] = s[i-1]+a[i];
    }
    // for(int i=1;i<=n;i++){
    //     cout << s[i] << " ";
    // }
    // cout << endl;
    int hh=0,tt=0;
    int res = -2e9;
    for(int i=1;i<=n;i++){
        if(hh<=tt && i-m > q[hh])hh++;

        res = max(res,s[i]-s[q[hh]]);
        while(hh<=tt && s[q[tt]]>=s[i]) tt--;
        q[++tt] = i;

        // cout << s[q[hh]] << ' ';
    }
    // cout << endl;
    cout << res << endl;

    return 0;
}



雨小伍
15小时前
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int res = 2e9;
        for(int i=0;i<nums.size();i++){
            cout << i << endl;
            int l =i+1,r=nums.size()-1;
            while(l<r){
                int s = nums[i]+nums[l]+nums[r];
                if (abs(s-target)<abs(res-target)) res= s;
                if(s>target){
                    r--;continue;
                }else if(s<target){
                    l++;continue;
                }
                return target;
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 15. 三数之和

雨小伍
16小时前
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;

        for(int i=0;i<nums.size();i++){
            if(i&&nums[i]==nums[i-1]) continue;

            for(int j=i+1,k=nums.size()-1;j<k;j++){
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                while( k>j+1 && nums[i]+nums[j]+nums[k] > 0)k-- ;
                if(nums[i]+nums[j]+nums[k] == 0) res.push_back({nums[i],nums[j],nums[k]});
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 14. 最长公共前缀

雨小伍
16小时前
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        if(strs.empty()) return res;
        for(int i=0;;i++){
            char c = strs[0][i];
            for(auto &st:strs){
                if(i>=st.size()|| st[i]!=c) return res;
            }
            res+=c;
        }

        return res;

    }
};



雨小伍
16小时前

class Solution { public: int romanToInt(string s) { unordered_map<char,int> hash; hash['I'] = 1, hash['V'] = 5; hash['X'] = 10, hash['L'] = 50; hash['C'] = 100, hash['D'] = 500; hash['M'] = 1000; int res = 0; for(int i=0;i<s.size();i++){ if(i+1<s.size()&& hash[ s[i] ] < hash[s[i+1]]) res-=hash[s[i]]; else res+=hash[s[i]]; } return res; } };




雨小伍
16小时前
class Solution {

public:

    string intToRoman(int num) {
        string cs[] = {
            "I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"
        };
        int vs[] = {
            1,4,5,9,10,40,50,90,100,400,500,900,1000
        };
        string res;
        for(int i=12;i>=0;i--){
            while(num>=vs[i]){
                res+=cs[i];
                num-=vs[i];
            }
        }
        return res;
    }
};



雨小伍
16小时前
class Solution {
public:
    int maxArea(vector<int>& h) {
        int res = 0;
        for(int l=0,r=h.size()-1;l<r;){
            res =  max(res,min(h[l],h[r])*(r-l));
            if(h[l]>h[r]) r--; 
            else l++;
        }
        return res;
    }
};


活动打卡代码 AcWing 1084. 数字游戏 II

雨小伍
17小时前
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std;

const int N = 11,M=100+7;;
int f[N][10][M],m;

int mod(int a,int b){
    return (a%b+b)%b;
}

void init(){
    memset(f,0,sizeof f);

    for(int i=0;i<=9;i++) f[1][i][mod(i,m)]=1;
    for(int i=2;i<N;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=9;k++)
                for(int l=0;l<m;l++)
                    f[i][j][l] += f[i-1][k][mod(l-j,m)];

}
int dp(int n){
    if(!n) return 1; 
    vector<int> nums;
    while(n) nums.push_back(n%10),n/=10;

    // cout << nums.size() << endl;
    int res = 0;
    int last = 0;
    n = nums.size();
    for(int i=n-1;i>=0;i--){
        int x= nums[i];

        for(int j=0;j<x;j++)
            res+=f[i+1][j][mod(-last,m)];
        last += x;
        // cout << mod(-last,m) << endl;
        if(!i && mod(last,m)==0) res++;
    }

    return res;
}

int main(){
    int l,r;
    while(cin >> l >> r >> m){
        init();
        cout << dp(r) - dp(l-1) << endl;
        // cout << dp(l) << endl;
    }
    return 0;
}



活动打卡代码 AcWing 1083. Windy数

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int N = 11;
int  f[N][10];

void init(){
    for(int i=0;i<=9;i++) f[1][i] = 1;
    for(int i=2;i<N;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=9;k++)
                if(abs(k-j)>=2)
                    f[i][j] += f[i-1][k];
}
int dp(int n){
    if(!n) return 0;
    vector<int> nums;
    while(n) nums.push_back(n%10),n/=10;
    int res = 0;
    int last = -2;
    for(int i=nums.size()-1;i>=0;i--){
        int x = nums[i];
        for(int j=(i==(nums.size()-1));j<x;j++)
            if(abs(j-last)>=2)
                res+=f[i+1][j];

        if (abs(x - last) >= 2) last = x;
        else break;

        if (!i) res ++ ;
    }
        // 特殊处理有前导零的数
    for (int i = 1; i < nums.size(); i ++ )
        for (int j = 1; j <= 9; j ++ )
            res += f[i][j];
    return res;

}

int main(){
    init();
    int l,r;
    cin >> l >> r;
    cout << dp(r) - dp(l-1) << endl;
    return 0;
}




活动打卡代码 AcWing 1082. 数字游戏

#include <iostream>
#include <vector>
using namespace std;

const int N = 11;
int f[N][10];
void init(){
    for(int i=0;i<=9;i++) f[1][i] = 1;
    for(int i=2;i<N;i++)
        for(int j=0;j<=9;j++)
            for(int k=j;k<=9;k++)
                f[i][j]+=f[i-1][k];
}

int dp(int n){
    if(!n) return 1;
    vector<int> num;
    while(n) num.push_back(n%10),n/=10;

    int res =0;
    int last=0;
    for(int i=num.size()-1;i >=0;i--){
        int x = num[i];

        for(int j=last;j<x;j++){
            res += f[i+1][j];
        }

        if (x < last) break;
        last = x;
        if(!i && x>=last) res++;
    }
    return res;
}

int main(){
    init();
    int a,b;
    while(cin >> a >> b)
        cout << dp(b) - dp(a-1) << endl;
    return 0;
}