Educational Codeforces Round 148 (Rated for Div. 2) 题解

总结：5.21下午VP一场，死在了A题，给我wa崩溃了，浪费了差不多一个小时，BC还挺顺畅，虽然C题是在结束后不久交上去的。。。。

A. New Palindrome

思路：其实思路很简单，“The string s a palindrome”，题目已经说了所给的为回文字符串，所以直接判断一半有几种字符即可(开始的时候计算整个字符串中字符的数量，不知道哪错了。。。至今过不了。。。)

AC代码：

#include<iostream>
#include<cstring>
using namespace std;int a[30];
int main(){int T,sum;string s;cin>>T;while(T--){memset(a,0,sizeof(a));sum=0;cin>>s;for(int i=0;i<s.size()/2;i++){a[s[i]-'a']++;if(a[s[i]-'a']==1){sum++;}}if(sum>=2){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}}return 0;
} 

B. Maximum Sum

思路：开始没想到，其实思路对了还是挺简单的。。。一共进行k此操作，所以一共有k+1种可能的情况，分别是0次删前面k次删后面，1次删前面k-1次删后面，2次删前面k-2次删后面...一共循环k+1次，求最大值即可

AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;const int N=200005;
int a[N],sum[N];
signed main(){int T,n,k,nmax;cin>>T;while(T--){memset(sum,0,sizeof(sum));nmax=0;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);for(int i=1;i<=n;i++){sum[i]=sum[i-1]+a[i];}for(int i=0;i<=k;i++){nmax=max(nmax,sum[n-i]-sum[2*(k-i)]);}cout<<nmax<<'\n';}return 0;
}

C. Contrast Value

思路：算是数学知识，求相邻两个数差的绝对值，如果序列是单调的，差的绝对值的和就等于头和尾差的绝对值，所以直接求有几个上升和下降子序列即可，除了只有一种数的序列，其他情况上升和下降子序列的个数和+1即可

AC代码：

#include<iostream>
using namespace std;const int N=300005;
int a[N];
int main(){int T,n,x,cnt,sum;cin>>T;while(T--){cnt=1;sum=1;cin>>n;for(int i=1;i<=n;i++){cin>>x;if(i==1){a[1]=x;} else if(x!=a[cnt]){a[++cnt]=x;}}for(int j=2;j<=cnt;){if(a[j]>a[j-1]){while(a[j]>a[j-1]&&j<=cnt){j++; }sum++;}else{while(a[j]<a[j-1]&&j<=cnt){j++; }sum++;}}cout<<sum<<'\n';}return 0;
}