cf1832
A. New Palindrome
看回文字符串经过重排是不是还能组成回文字符串。如果字符串不计只出现一次的字符，其余有多个字符都出现偶数次，那么就重排可以组成新的回文字符串。
// Problem: A. New Palindrome
// Contest: Codeforces - Educational Codeforces Round 148 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1832/problem/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
string s;
int cnt[26];
int res;
int T;
int main(){
cin>>T;
while(T--){
cin>>s;
memset(cnt,0,sizeof(cnt));
res=0;
for(int i=0,n=s.length();i<n;i++){
cnt[s[i]-'a']++;
}
for(int i=0;i<26;i++){
if(cnt[i]>=2) res++;
}
if(res>1) puts("YES");
else puts("NO");
}
return 0;
}
B. Maximum Sum
题目链接
每次在k次操作中，每次操作删掉最小的两个数或者最大的一个数。求最后剩下的数的和最大的情况。
直觉上贪心是最小两个数和与最大一个数谁小删除谁，但是这样链样例都过不去。因为每次删除的贡献并不相等。这样的情况遍历才能考虑周全
排完序用前缀和遍历一下就可以考虑所有情况了。
核心公式：res=max(res,sum[n-(k-i)])-sum[i<<1]
n-(k-j)是删除掉几个最大数的前缀和，此时减去i<<1是删除掉几个最小数的前缀和。剩下的就是这种删除策略执行后的值。
// Problem: B. Maximum Sum
// Contest: Codeforces - Educational Codeforces Round 148 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1832/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
typedef pair<LL,int> PLI;
const int N=2e5+10;
int T;
int n,k;
LL a[N];
LL sum[N];
void output(){
for(int i=1;i<=n;i++){
cout<<sum[i]<<" ";
}
cout<<endl;
}
int main(){
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
// output();
LL res=0;
for(int i=0;i<=k;i++)
{
res=max(res,sum[n-(k-i)]-sum[i<<1]);
}
printf("%lld\n",res);
}
return 0;
}
C. Contrast Value
题目链接
给定一个数组定义一个条件：\(\vert a_1-a_2\vert+\vert a_2-a_3\vert+\cdots +\vert a_{n-1} -a_n\vert\).
要求给出一个非空子数组其条件\(\vert b_1-b_2\vert+\vert b_2-b_3\vert+\cdots +\vert b_{n-1} -b_n\vert\)不变.
求符合条件的子数组最小长度
考虑条件若去掉绝对值符号，则上述求和公式变为\(b_1-b_n\),但是去掉绝对值的条件是相邻的绝对值内符号相等，那么把所有相邻的绝对值符号内式子符号相等的情况合并即可，合并后剩下式子加1即为最小规模
// Problem: C. Contrast Value
// Contest: Codeforces - Educational Codeforces Round 148 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1832/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=3e5+10;
int T,n;
int a[N];
void output(vector<int> q){
for(int i=0,si=q.size();i<si;i++){
cout<<q[i]<<" ";
}
cout<<endl;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
vector<int> q;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
q.push_back(a[0]);
for(int i=1;i<n;i++){
if(q[q.size()-1]!=a[i]) q.push_back(a[i]);
}
// output(q);
int res=1;
if(q.size()<=1){
printf("%d\n",res);
}else{
int fla= q[0]-q[1]>0?1:0;
for(int i=1,siz=q.size();i<siz-1;i++){
int t=q[i]-q[i+1]>0?1:0;
if(t!=fla){
fla=t;
res++;
}
}
printf("%d\n",res+1);
}
}
return 0;
}