2023/2/13 蓝桥备战acwing刷题(set的使用、简单推个不等式+差分、快速幂、01背包模板回顾、类似01背包的题)

4454未初始化警告

set计数

#include<iostream>
#include<set>
using namespace std;int main(){int n,m;cin>>n>>m;set<int> s;int res = 0;s.insert(0);while(m--){int l,r;cin>>l>>r;if(s.count(r)==0){res++;}s.insert(l);}cout<<res<<endl;return 0;
}

4455出行计划

有题目可得不等式
$q>=t-c+1-k$
$q<=t-k$
但是如果正常的遍历会出现$O(n^2)$的复杂度
所以要优化的话，可以这么搞：

因为公式已知，我们可以得到能正常参加各个计划的q的区间
对这个区间都加一
最后询问时直接O(1)的访问就行
所以区间加法，用差分
细节是注意负值的处理，防止越界

#include<iostream>
using namespace std;
const int maxx = 2e5+10;struct Node{int t;int c;
};Node node[maxx];
int d[maxx];int main(){int m,k,n;cin>>n>>m>>k;//q+k>=t-c+1,q+k<=tfor(int i=0;i<n;i++){int t,c;cin>>t>>c;int l = t+1-c-k;int r = t-k;//注意处理一下负值l = max(l,1);if(r>0){d[l]++,d[r+1]--;}}for(int i=1;i<maxx;i++){d[i]=d[i-1]+d[i];}while(m--){int q;cin>>q;cout<<d[q]<<endl;}return 0;
}

4728乘方

用快速幂做的，注意用ull，ll会有问题

#include<iostream>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
const ll INF = 1e9;ll fastpow(ll a,ll b){ll res = 1;while(b>=1){if(b%2==1){res*=a;}if(res>INF){return 0;}b/=2;a = a*a;}return res;
}int main(){ll a,b;cin>>a>>b;ll res = fastpow(a,b);if(res==0)cout<<"-1"<<endl;else cout<<res<<endl;return 0;
}

2、01背包

#include<iostream>
using namespace std;
const int maxx = 1e4+10;int dp[maxx][maxx];
int v[maxx];
int w[maxx];int main(){int N,V;cin>>N>>V;for(int i=1;i<=N;i++){cin>>v[i]>>w[i];}for(int i=1;i<=N;i++){for(int j=0;j<=V;j++){if(j<v[i]){dp[i][j] = dp[i-1][j];}else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);}}}cout<<dp[N][V]<<endl;return 0;
}

4700 何以包邮(说实话没懂)

给出x，给出一个价格数组，要求挑一些数出来，总和$m>=x$，且尽量小
想到01背包，它是和要小于一个值(背包大小)，所以我们这里可以采用加负号反向
即当总和不超过sum-x时尽可能大
注意要反向遍历，相当于不断分解

#include<iostream>
using namespace std;
const int maxlen=40;
const int maxx = 3e5+20;int dp[maxx];
int a[maxlen];int main(){int n,x;cin>>n>>x;int sum=0;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}int res = 0;for(int i=1;i<=n;i++){for(int j=sum-x;j>=a[i];j--){dp[j]=max(dp[j],dp[j-a[i]]+a[i]);res = max(res,dp[j]);}}cout<<sum-dp[sum-x]<<endl;return 0;
}