万年补题怪~
A.?https://codeforces.com/contest/1637/problem/A
题意：
给定一个长度为n的数数组，从1到n-1里随便选一个数字当做len
然后检查前len个元素序列和后面的元素序列是不是升序，如果不是就各自排序
现在问你给定的数组能不能进行排序
分析：其实就是检查数组是不是升序
AC Code：
#include <iostream>
using namespace std;
int t,n;
int main()
{
cin >>t;
while(t--)
{
cin >>n;
int temp = -1,x,ans = 1;
for(int i = 1; i <= n; i++){
cin >>x;
if(temp > x) ans = 0;
temp = x;
}
if(ans) cout <<"NO" <<endl;
else cout <<"YES" <<endl;
}
return 0;
}B.?https://codeforces.com/contest/1637
题意：
给定长度为n的数组
定义：每一个子序列分成k段，则这个子序列的价值为k+MEX(子序列元素)。
求所有子序列的价值和的最大值
分析：
上一次cf的MEX问题就把我整的够呛，这次看了半天题才看懂，理解不了英语。。。
首先：
要想价值最大，肯定每一个元素分成一段是最优的
所以如果一个元素是0，贡献的价值就是1 +MEX0? = 2；
如果是其他元素，贡献的价值就是1 + 0 = 1
然后想代码：
我的最后一步要求的是所有子序列的价值总和，那就是多次的1和2相加，为了避免重复计算，就可以直接在输入的时候把a[i]改为它能贡献的价值。
至于最后的优化：
既然是所有子序列，那么每个元素出现的次数是跟位置有固定关系的，根据结论直接在输入时求和也未尝不可，也就是sum += 贡献价值*出现次数，这样会免去n^3的子序列遍历
代码就不写了~
C.?https://codeforces.com/contest/1637/problem/C
题意：
给定一个长度为n的数组，进行操作：选定i<j<k, a[j]>=2, a[j] 减2，a[i]和a[k]加一
问：最少进行多少次这样的操作能够将除首尾之外的数组元素全部变成0，如果无法实现就输出-1
分析：
先想最简单的
中间有一个偶数，那么我可以将i，k指向a[1]和a[n]，然后经过a[j]/2次操作将a[j]变为0
如果是一个奇数，那我先要将它充当i或者k，把它先变为偶数。
也就是说，除去首尾元素，每个元素贡献的次数是：奇数，(a[i]+1)/2; 偶数a[i]/2;
推导之后可以得到res = (sum + cnt) /2; sum为除首尾元素之外的元素和，cnt为奇数个数
特殊情况
中间的数字全部为1，无法进行操作，输出-1
只有3个元素，中间的元素是个奇数，不管怎么操作奇数还是奇数，输出-1
AC Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,cnt,sum;
int a[100010];
int main(){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >>t;
while(t--){
sum = cnt = 0;
cin >>n;
bool ans = true;
for(int i=1;i<=n;++i) cin >>a[i];
//3个数且中间数是奇数
if( n==3 && (a[2]&1) ){
cout <<-1 <<endl; continue;
}
for(int i=2;i<n;++i){
sum += a[i];
if(a[i]&1) cnt++;
if(a[i]>1) ans = false;
}
//中间的数全是1
if(ans) { cout <<-1 <<endl; continue; }
cout <<(sum + cnt)/2 <<endl;
}
return 0;
}D.??https://codeforces.com/contest/1637/problem/D
题意：
给定两个长度为n的数组，可以执行任意次数交换ai和bi的操作，最后要使得题目所给公式结果最小，输出最小结果
分析：
观察给出的式子：
也就是说问题变成了：交换元素之后，使得两数组各自元素和的平方相加值最小
所以需要穷举出所有元素和可能的值，然后去找最小值，相当于一个背包问题，我写成递归直接就炸了
石头要不要？
像这种题以我的水平比赛正常是写不出来的，膜佬~
AC Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,res,res1,sum;
//sum记录总体元素和
//res记录最终结果，res1记录(n-2)...的值
int a[101],b[101];
int main(void)
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >>t;
while(t--)
{
res = 1e9,sum = 0,res1 = 0;
//cin
cin >>n;
for(int i = 1; i <= n; i++){
cin >>a[i];
res1 += a[i]*a[i]*(n-2);
sum += a[i];
}
for(int i = 1; i <= n; i++){
cin >>b[i];
res1 += b[i]*b[i]*(n-2);
sum += b[i];
}
bool dp[n+1][sum+1];
memset(dp,false,sizeof(dp));
dp[0][0] = true;
//枚举所有可能出现的元素和
for(int i = 1; i <= n; i++){
for(int j = 1; j <= sum; j++){
if(j >= a[i] & dp[i-1][ j-a[i] ]) dp[i][j] = true;
if(j >= b[i] & dp[i-1][ j-b[i] ]) dp[i][j] = true;
}
}
//找出式2最小值
for(int i = 1; i <= sum; i++){
if(dp[n][i]) res = min(res, i*i + (sum-i)*(sum-i));
}
cout <<res + res1 <<endl;
}
return 0;
}