要求这个数本身不能被 \(2\) 整除，加和可以被 \(2\) 整除，那我们分类讨论
删到最后删不动了或者删空了就是不行，输出 \(-1\)。
时间复杂度 \(O(n)\)，代码写的有点乱。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define _for(i,a,b) for(int i = (a);i < b;i ++)
#define _rep(i,a,b) for(int i = (a);i > b;i --)
#define INF 0x3f3f3f3f3f3f3f3f
#define ZHUO 11100000007
#define MOD 1000000007
#define MIKUNUM 39
#define pb push_back
#define debug() printf("Miku Check OK!\n")
#define maxn 50003
#define X first
#define Y second
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--)
{
string s;int n;
cin >> n >> s;
int a = 0, b = 0;
int index = -1;
a = s[s.size()-1]-'0';
_for(i,0,s.size())
b += s[i]-'0';
if(!(a&0x1))
{
while(!s.empty() && !((s[s.size()-1]-'0')&0x1))
s.pop_back();
}
if(b&0x1)
{
for(int i = s.size()-2; i>=0; i --)
{
if((s[i]-'0')&0x1)
{
index = i;
break;
}
else
continue;
}
}
else
index = 100000;
if(s.empty() || index==-1)
printf("-1\n");
else
{
_for(i,0,s.size())
if(i!=index)
printf("%c",s[i]);
printf("\n");
}
}
return 0;
}他问你能不能构造出来，我们先假设能构造出来，那数组就分成两部分，我们将前一部分称为 上升部分，后一部分称为 下降部分。
我们希望什么呢？因为改变数字大小不计代价，所以上升部分越靠前的数越小越好，最小能是多少？答案就是下标为 \(i(1≤i≤n)\) 的地方最小为 \(i-1\)，好给上升部分后面的数“腾位置”。
真就有一个元素达不到这个标准怎么办（ \(a[i] ＜ i-1\) ）？那我们假设已经进入了 下降部分。首先有一点，下降部分都不能比 顶峰（上升部分的最后一个元素或者看作下降部分的第一个元素）大，或者一样大。其次我们想让他越大越好，这是给下降部分后面的数 "腾位置"。如果还有一个元素不能满足标准，他不够大，不能给后面的元素预留最小的足够空间（\(a[i]<n-i-1\)），那我们就知道，这数组变不成我们想要的数组了。
时间复杂度 \(O(n)\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define _for(i,a,b) for(int i = (a);i < b;i ++)
#define _rep(i,a,b) for(int i = (a);i > b;i --)
#define INF 0x3f3f3f3f3f3f3f3f
#define ZHUO 11100000007
#define MOD 1000000007
#define MIKUNUM 39
#define pb push_back
#define debug() printf("Miku Check OK!\n")
#define maxn 350003
#define X first
#define Y second
int a[maxn];
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
_for(i,0,n)
cin >> a[i];
int can = 1;
int st = -1;
_for(i,0,n)
if(a[i]<i)
{
st = i;
break;
}
if(st==-1)
goto end;
_for(i,st,n)
{
a[i] = min(a[i],a[st-1]-1);
if(a[i]<n-i-1)
{
can = 0;
break;
}
}
end:
if(can)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}首先有一点可以确定：你控制你之后的人没有用，所以 \(k\) 最大为 \(m-1\)。然后我们也不用考虑具体怎么控制这些人。观察一下，不管怎么取，最后一定是剩下一个长度为 \(n-m+1\) 的原数组的子数组让你取，而这个子数组具体是哪个子数组，这要看两部分内容：
所以这个子数组就敲定下来了，因为你也只能取头部或者尾部，所以最后答案就是 \(max(a_{1+x+y},a_{1+x+y+(n-m)})\)
这样就有一个很显然的 \(O(n^2)\) 算法，双重循环遍历 \(x\) 和 \(y\) 即可，我们记 \(b_i = \max(a_{1+i}, a_{1+i+(n-m)})\)
最终答案就是 \(\displaystyle \max_{x \in [0 , k]} \bigg[ \min_{y \in [0 , m-1-k]} b_{x+y} \bigg]\)
解释一下，最后的子数组你一定是取子数组两端的最大值，所以就是 \(b_{x+y}\)，但是因为你不确定你没法控制的人都取了什么，你只能按最坏情况考虑，他们都在拆你的台，因此就有在 \(x\) 敲定后， \(y \in[0,m-1-k]\) 中你所能取到的 \(b_{x+y}\) 中的最小值，而在这些最小值中，因为 \(x\) 是你可以控制的，所以取这些最小值中的最大值就是答案。
我们将这个最终答案式等价变形为 \(\displaystyle \max_{x \in [0 , k]} \bigg[ \min_{y' \in [x , x+m-1-k]} b_{y'} \bigg]\) ，也就是令 \(y'=x+y\) ,这样换式子，问题就可以被更好的解释成 ：对于数组 \(b\)，长度为 \(m-k\) 的滑动数组中的最小值的最大值，滑动数组头部的取值为 \([0,k]\)。
用线段树搞一搞就是 \(O(nlogn)\) 的解法，用单调队列搞一搞就是 \(O(n)\)，代码是单调队列实现的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define _for(i,a,b) for(int i = (a);i < b;i ++)
#define _rep(i,a,b) for(int i = (a);i > b;i --)
#define INF 0x3f3f3f3f
#define ZHUO 11100000007
#define MOD 1000000007
#define MIKUNUM 39
#define pb push_back
#define debug() printf("Miku Check OK!\n")
#define maxn 3503
#define X first
#define Y second
int t;
int n, m, k;
int a[maxn];
int getb(int i)
{
return max(a[1+i],a[1+i+(n-m)]);
}
int main()
{
ios::sync_with_stdio(false);
cin >> t;
while(t--)
{
cin >> n >> m >> k;
_for(i,1,n+1)
cin >> a[i];
k = min(k,m-1);
deque<int> dq;
int ans = -INF;
for(int y = 0; y <= m-1;y ++)
{
//维护滑动数组长度
while(dq.size() && dq.front() <= y-(m-k))
dq.pop_front();
//若当前不可能成为该滑动数组最小则出队
while(dq.size() && getb(y) <= getb(dq.back()))
dq.pop_back();
dq.pb(y);
//等滑动数组长度足够时再计算答案
if(dq.size() && y >= m-k-1)
ans = max(ans,getb(dq.front()));
}
printf("%d\n",ans);
}
return 0;
}后面的题慢慢更
原文：https://www.cnblogs.com/Asurudo/p/12258644.html