小红不想做完全背包 （hard）
题目描述
本题和easy版本的唯一区别是：ppp没有必须等于3的限制。
完全背包是一个经典问题，但小红完全不会完全背包，因此她不想做完全背包。
现在小红拿到了一个长的很像完全背包的题，她希望你帮她解决一下。
给定一个背包，有nnn种物品，每种物品的价值为aia_iai，有无穷多个。小红有一个无穷大的背包，她希望往里面放若干个物品，使得最终所有物品的价值之和为ppp的倍数。小红想知道最终至少要放多少物品？
（注意：不能不放物品）
示例1
输入
复制4 3 1 2 3 4
4 3 1 2 3 4
输出
1
1
错误操作：
我的思路就正确，操作就是在我每次输入都没有存在一个数组中在进行处理。这导致有些没有遍历到或者其前面那个数据的最小值发生改变。导致答案错误。
思路：
我们用dp求最小到m值得操作数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define N 2000
void solve()
{int i,j,k,n,m,t,a[N+50],f[N+50];cin>>n>>m;memset(f,1,sizeof(f));for(i=1;i<=n;i++){cin>>a[i]; a[i]%=m; f[a[i]]=1;}//cout << f[0] <<endl;for(i=1;i<=n;i++){for(j=0;j<m;j++){f[(j+a[i])%m]=min(f[(j+a[i])%m],f[j]+1);}}cout<<f[0];}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;
// cin>>t;0while(t--){solve();} return 0;
} 红不想做莫比乌斯反演杜教筛求因子和的前缀和
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
小红来到了一家蛋糕店，蛋糕店中售卖了若干种不同的长方体蛋糕，具体来讲，蛋糕店中售卖若干种形状为横向长度不大于nnn，纵向长度不大于mmm，高度不大于ppp个单位的蛋糕。每个蛋糕的表面要裹上奶油，也就是说，除了底面以外，其余5个面都需要裹奶油。我们不妨定义：奶油消耗量为暴露在空气中的5个面的面积之和。
我们定义两种蛋糕是不同的，当且仅当两个蛋糕的横向或者纵向长度或高度不同。即分别定义蛋糕横向的长度为iii，纵向的长度为jjj，高度为kkk，则可以用三元组(i,j,k)(i,j,k)(i,j,k)表示蛋糕种类的唯一性。
现在小红希望你求出，共有多少种不同的奶油消耗量为xxx的蛋糕？
输入
复制2 2 2 8
2 2 2 8
输出
复制2
2
思路：
直接以每个正方形来看即可，优化第 3层即可。判断1≤n,m,p≤3000 是否符合即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
void solve()
{ll n,m,p,x,i,j,r = 0,k;cin >> n >> m >> p >> x;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){ll k = (x - i*j) /(2*(i+j));if(k >= 1 && k <= p && i*j + j*k*2 + i*k*2 == x){r++;}} }cout << r<<endl;}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;
// cin>>t;while(t--){solve();} return 0;
} 小红不想做模拟题
思路：
题目意思是间A 区间 或B 区间全部变成 1 在 &
我们可以用 2 个 set 分别 记录 区间 A 的 0 和 区间 B 的 0 的 位置。
当将区间 A l r变成 1 就是 遍历 B 中区间 l r 那个位置 是否为 1
set 的基础运用
t.count(*it) 表示 *it 位置是否存在
s.erase(it)表示 删掉这个位置 it会自动++；
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
void solve()
{int n,q,i;cin >> n;string a,b;cin>>a>>b;set<int> s ={n},t = {n};int ans = 0;for(int i = 0;i < n;i++){if(a[i] == '0') s.insert(i);if(b[i] == '0') t.insert(i); // B的 个数 if(a[i] == '1' && b[i] == '1') ++ans;}cin >> q;while(q--){char ch;int l,r;cin >>ch>>l>>r;--l;--r;if(ch=='A'){auto it = s.lower_bound(l);//cout << *it << endl;while(*it <= r){if(!t.count(*it)) ++ans;//cout << *it<<endl;it = s.erase(it);//cout << *it <<endl;}}else{auto it = t.lower_bound(l);while(*it <= r){if(!s.count(*it)) ++ans;it = t.erase(it);}}cout <<ans<<'\n'; }}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;
// cin>>t;while(t--){solve();} return 0;
} 
解析：
求连续字段翻转一次或0次的升序序列。
我们用 lft 记录 其 升序的 序列长度。
用rgt 记录 其 从右到 左的降序序列长度。
在进行分类讨论：
单增、单减、先增后减、先减后增、先增后减再增。
用纸模拟一下。
我这 里的 x*y 是包含 a[i] ~ a[R] 这一段的
所以 len*(len -1)/2 - 1 的 -1 是减区 a[i]~ a[R]这一段的；
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[200010],lft[200010],rgt[200010];
void solve()
{ll ans = 0;cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];} lft[0] = 0;rgt[n+1] = 0;a[0] = 0;a[n+1] = n+1;for(int i = 1;i <= n;i++){if(a[i] > a[i-1]){lft[i] = lft[i-1] + 1;}else{lft[i] = 1;}ans += lft[i];// 一直递增 的 }for(int i = n ;i >= 1; i--){if(a[i] < a[i+1]){rgt[i] = rgt[i+1] + 1;}else{rgt[i] =1;}}//cout << " ans " << ans<<endl; for(int i = 1;i <= n-1;i++){if(a[i+1] < a[i]) //减de {int R = i+1;while(R +1 <= n && a[R+1] < a[R]){++R;}int len = R - i + 1;//下降时的部分 ans+= 1ll*len*(len-1)/2-1;//cout <<" ： "<< 1ll*len*(len-1)/2-1 <<endl;//曲折的那部分 且包含 递减的那个区间 int x, y;if(a[R] > a[i-1]){x = lft[i-1]+1; }else{x = 1;}if(a[i] < a[R+1]){y = rgt[R+1] + 1;}else{y = 1;}ans += 1ll*x*y;//小区间反转的部分 for(int j = i+1;j < R;j++)//降序 部分 {if(a[j] > a[i-1]) ans+= lft[i-1];if(a[j] < a[R+1]) ans+= rgt[R+1]; }i = R;}}cout << ans<<'\n';}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve(); return 0;
} 时间复杂度为O（n);
