计蒜客4月训练赛-普及 T3
前言
为记录调了一上午的代码写的题解QWQ
题目描述
蒜头君给定你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [l_i, r_i, val_i]，来进行以下操作：
对于每个 queries[i]，表示在数组 nums 上执行以下操作：
- 从数组 nums 中选择索引范围在 [l_i, r_i]（包含端点，索引从 0 开始）内的一个下标子集。
- 将所选中的每个下标处对应的数组 nums 中的值减去 val_i。
零数组是指数组中所有元素的值都等于 0 的数组。
数组的子集是指从数组中选择的一些元素（可能为空）。
你需要返回使得按顺序执行前 k 个查询操作后，数组 nums 能够转变为零数组的最小可能的非负整数值 k。如果不存在这样的 k，则返回 -1。
输入格式
第一行输入一个正整数 n，代表数组 nums 的大小，范围在 1 到 10 之间。
第二行输入 n 个整数，代表数组 nums 每个元素的大小，范围均在 0 到 1000 之间。
第三行输入一个正整数 m，代表二维数组 queries 的长度，范围在 1 到 1000 之间。
接下来 m 行，每行输入三个整数 l_i、r_i、val_i，分别表示 queries 数组中每个子数组的内容，其中 0 <= l_i <= r_i < n，1 <= val_i <= 10。
输出格式
输出使得按顺序执行前 k 个查询操作后，数组 nums 能够转变为零数组的最小可能的非负整数值 k，如果不存在这样的 k，则输出 -1。
样例输入1
3
2 0 2
3
0 2 1
0 2 1
1 1 3样例输出1
2样例解释1
- 初始数组：未明确给出，但可以通过操作推断。
- 查询0：
l = 0, r = 2, val = 1，将下标[0]和[2]的值减1，数组变为[1, 0, 1]。 - 查询1：再次执行
l = 0, r = 2, val = 1，将下标[0]和[2]的值减1，数组变为[0, 0, 0]，这是一个零数组。因此，最小的k值为2。
样例输入2
4
4 3 2 1
2
1 3 2
0 2 1
样例输出2
-1
- 解释：即使执行完所有查询，也无法使
nums变为零数组。
思路
思路很简单，但细节很多。
发现随着k的增加，只要有一个最小的k满足题目要求，那么>=k的数都一定满足要求。
这具备二份的性质。
然后就第一层二分，第二层直接看在这个情况下能否满足题目要求，不能就往大的二分，能就往小的二分。
最后我们需还要做一个变样的DP——每个j求出那几个数可以靠现在可以减的数组合出来（1<=j<=n）。
怎么实现呢？
首先，我们把现在这种情况的前k个枚举一遍，x[i]<=i<=y[i]的都可以使用（1<=i<=k）。
然后就可以使用DP具体实现了（具体见代码）。
记得DP第二重要反着枚举，不然可能会出现本来x是可以，但你直接把k+2*j也当成可以的了（j为符合要求的某个数值z[i]，实际上大概率是不可以的）。
代码
#include <bits/stdc++.h>
using namespace std;
int n,m,k,a[100010],x[100010],y[100010],z[100010],l,r,mid,sum,dp[100010],now=1,ans,fl,mi=1e9;
vector<int>v[100010];
int main(){ios::sync_with_stdio(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];//输入}cin>>m;for(int i=1;i<=m;i++){cin>>x[i]>>y[i]>>z[i];x[i]++,y[i]++;//因为从零开始，而我们的是从一开始，要加一！！！（超大坑点）}l=1,r=m;while(l<=r){fl=0;mid=(l+r)/2;for(int i=1;i<=n;i++){v[i].clear();//清空（坑点）}for(int i=1;i<=mid;i++){for(int j=x[i];j<=y[i];j++){v[j].push_back(z[i]);//前mid个操作 }}for(int k=1;k<=n;k++){//每个都要枚举看行不行（小坑）sum=0;//初始化 for(int i=0;i<v[k].size();i++){sum+=v[k][i];//sum为可以减的和}if(sum<a[k]){//不行（全减了都不够）（坑点）fl=1;//标记吧 break;}for(int i=1;i<=sum;i++){dp[i]=0;//初始化（小坑）}dp[0]=1;//dp[i]为可不可以组合出减i，显然0是可以的 for(int j=0;j<v[k].size();j++){for(int i=sum;i>=v[k][j];i--){//反着枚举，不然会出现类似于完全背包的情况if(dp[i-v[k][j]]){dp[i]=1;//变形DP，可以组合出来标记为1}} }if(!dp[a[k]]){//减不出这个值 fl=1;break;} }if(!fl){//可以 mi=min(mi,mid);r=mid-1;//不可以实现，尝试更小 }else{l=mid+1;//这都不行，肯定要更大啊 }}if(mi!=1e9){//有方案cout<<mi;//可以有一个k }else{cout<<-1;//不行}return 0;
}看了那么多，能不能点个赞QWQ