Hello 2023
还是两个，B也是wa了好几次o(╥﹏╥)o，我什么时候才可以做出三个题呢！！！
不过这个D题差一点就写出了（后面没时间了），后来看了大佬的题解，所以我的D有两种解法
C
题目大意是给你一个m，和一个长度为n的数组，我们可以进行的操作是把a[i]变成-a[i],我们最后要知道最少的操作把从1到m的前缀和是一个最小的值（相比于其他的前缀和)
根据前缀和的知识，我们可以知道
am-1<=0
am-2+am-1<=0
......
a1+...am-1<=0
am+1>=0
am+1+am+2>=0
......
am+1+am+2+...+an>=0
我最近是看二分看多了，竟然觉得这个是二分，后来发现是不对的，因为这个最关键的是要让哪几个改变符号
后来我是一个一个求，只要会有不符合条件就改变当前遍历到的数的符号
再后来才知道，这个不是最优的
正确的解法是，先不改变值，我们求和，只要出现了不符合条件的，就改变那个可以让和改变最大的那个数（让每一次操作的贡献达到最大）
具体看代码
#include <iostream>
#include <set>
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,t,a[maxn],m;
void solve()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
int cnt=0;
multiset<int>ms;//这个容器和set一样都可以自动排序，但是不同的是它可以存在重复的数
int sum=0;
for (int i=m;i>=2;i--)
{
sum+=a[i];
ms.insert(a[i]);
if (sum>0)//要让sum变成小于0的话，我们选取那个最大的改变符号，
{
int mx=*prev(ms.end());//这个操作是求容器中的最大值，因为题目告诉我们一定会存在一个cnt满足条件，所以这个最大的数一定是正数，变成负数一定是最小的负数（当前可以改变符号的最大贡献）
int sub=2*mx;//先前已经加上一次了，这一次要减去原来的，然后再减去原来的数（这个是改变符号后的数sum-=mx,sum+=(-1*mx)
ms.erase(prev(ms.end()));//记得删除这个已经改变过符号的数，不要重复改变符号
sum-=sub;
cnt++;
}
}
ms.clear();
sum=0;
for (int i=m+1;i<=n;i++)
{
sum+=a[i];
ms.insert(a[i]);
if (sum<0)
{
int mi=*ms.begin();//这个是要让sum<0,那么我们需要把绝对值最大的负数变成正数，这是的贡献最大
int add=mi*2;//还是那个理由
ms.erase(ms.begin());//还是要删除
sum-=add;
cnt++;
}
}
cout<<cnt<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
题目大意是给你一个a数组，一个b数组，我们要把a数组变成b数组，我们要怎么把a变成b呢
我们还会给你m个x，我能这个x是相当于一个剪刀，我们选择一个l和r，把这一段大于x的都变成x,小于的剪不到，所以不变，所以我想到我们要把l位置的a变成b,r位置的a变成b,只要这一段的最大值是b,那么就不会影响其他位置变成b，所以我用到了st表，但是好久没有用了，都快忘记了（结果vp结束了才过了）
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
const int maxn=2e5+10;
int t,n,m;
vector<int>a,b;
int st[maxn][30];
int lg2[maxn];
void init()
{
for(int i=1;i<=n;i++)
st[i][0]=b[i];//i+2^0-1=i.也就是单个[i,i]的区间
for(int j=1;(1<<j)<=n;j++)//2^j不能超过n的大小
for(int i=1;i+(1<<j)-1<=n;i++)//i+2^j-1不超过n
st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);//由两个预处理区间[i,i+2^(j-1)-1]和
}
int query(int l,int r)
{
int k=lg2[r-l+1];//也可以不用预处理，直接log2(r-l+1)，不过时间可能会慢一点
return max(st[l][k],st[r-(1<<k)+1][k]);
}
void solve()
{
cin>>n;
b=a=vector<int>(n+1,0);
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
bool yes=true;
set<int>st;
map<int,vector<int>>p;//p[i]是要变成i的位置，要是里面的i都可以一刀切，那么第一个位置和最后一个位置这一段的最大值是i,用这种方式判断要把所有要变成i的需要几刀，如果大于i的数量，就是now,每一把刀只能用一次
for (int i=1;i<=n;i++)
{
cin>>b[i];
if (b[i]>a[i]) yes=false;//如果要变大，没有办法，一定是no
if (a[i]!=b[i])
{
st.insert(b[i]);//我先让小达成
p[b[i]].push_back(i);
}
}
cin>>m;
map<int,int>x;
for (int i=1;i<=m;i++)
{
int tmp;
cin>>tmp;
x[tmp]++;//记录tmp这一种刀有几把
}
if (!yes)//有边大的
{
cout<<"NO\n";
return ;
}
init();//预处理st表
int cnt=0;
for (auto now:st)
{
cnt=1;//一定需要1把刀
int l=0;//从l到r判断一个最长的段
int r=1;
int len=p[now].size()-1;
int mx=now;
int cntt=x[now];
if (cntt==0)//如果要变成now,可是没有变成now的刀，直接No
{
cout<<"NO\n";
return ;
}
while (l<=len&&r<=len)//求最少可以要多少把刀
{
while (l<=len&&r<=len)
{
int mmx=query(p[now][l],p[now][r]);
if (mmx>mx)//如果不满足，那么就需要重新一把刀
{
cnt++;
l=r;//记得更新l
break;
}
else r++;
}
if (cnt>x[now])//需要刀的数量大于我们有的数量，输出no
{
cout<<"NO\n";
return ;
}
}
}
cout<<"YES\n";
return ;
}
signed main ()
{
cin>>t;
lg2[0]=-1;
for(int i=1;i<=2e5;i++)//处理log2(i)的值
lg2[i]=lg2[i/2]+1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
看到其他人的做法，单调栈
这个是把所有的操作放进一个单调栈，我们不需要管前面比当前操作小的操作，以为比当前小的一定是切不到了，那么我们不需要管这些，只要除了这些之外，那一个和当前操作最近的操作和当前的操作是一样大的，那么我们可以蹭了上一个刀了，如果是大一些，那一定还是蹭不到的（变不成b)
这些都是我的小小理解
#include <iostream>
#include <stack>
#include <map>
using namespace std;
const int maxn=2e5+10;
int a[maxn],b[maxn],t,n,m;
void solve()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
for (int i=1;i<=n;i++)
{
cin>>b[i];
}
cin>>m;
map<int,int>x;
for (int i=1;i<=m;i++)
{
int tmp;
cin>>tmp;
x[tmp]++;
}
stack<int>s;//这个s里面里面一定是从大到小的
for (int i=1;i<=n;i++)
{
if (b[i]>a[i]) //要变大一定是no
{
cout<<"NO\n";
return ;
}
while (!s.empty()&&b[i]>s.top())s.pop();//往前回溯，直到前面的都大于这一次的b[i],如果除去那些比b[i]小的不用管，上一个也是和b[i]是一样的，那么我们这一次就可以让上一个变成b[i]的刀切到这边来
if (a[i]!=b[i])
{
if (s.empty()||s.top()>b[i])//只要上除去比b[i]小的，前面不和b[i]相等，就不可以蹭刀了，还需要再来一刀
{
if (x[b[i]])
{
x[b[i]]--;
s.push(b[i]);//把这一个操作放进去
}
else //如果没有刀，就不可以了
{
cout<<"NO\n";
return ;
}
}
}
}
cout<<"YES\n";
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}