412

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;
}
};


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;
}
};


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;
}
};


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;
}



#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;
}



#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;
}