Educational Codeforces Round 148 (Rated for Div. 2) A，B，C

A. New Palindrome

        要求：对于一个回文串，判断是否可以转换为其他回文串

        思路：如果回文串的前一半存在不相同的字符，就可以转换

#include<bits/stdc++.h>
using namespace std;int n;
string s;void solve(){cin>>s;bool f=0;for(int i=0;i<s.size()/2-1;i++){if(s[i]!=s[i+1]){cout<<"YES\n";f=true;break;}}if(!f)cout<<"NO\n";
} int main()
{cin>>n;while(n--)solve();
}

B. Maximum Sum

        要求：给出一个序列，通过q次操作 总和（减去（最小值+次小值）或 最大值）得到最大的序列和

        刚开始想要贪心，如果最小值+次小值>=最大值就减最大值，否则减最小值+次小值，之后发现子序列

6 2
15 22 12 10 13 11

不能满足情况，贪心时为（tot-（10+11）-22），但实际应该为（tot-22-15）；

所以用了两个前缀和来存储减小值的总和和减大值的总和，之后遍历一下，得到最大值

#include<bits/stdc++.h>
using namespace std;int t;
long long f[200001],ff[200001],a[200001];
/*
1操作：选取最小值和次小值
2操作：选取最大值
f[i]：选取i次1操作时的删减值
ff[i]：选取i次2操作时的删减值
*/void solve(){int n,q;long long tot=0;cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i],tot+=a[i];sort(a+1,a+1+n);//排序for(int i=2;i<=n;i+=2)f[i>>1]=a[i-1]+a[i]+f[(i>>1)-1];for(int i=1;i<=n;i++)ff[i]=ff[i-1]+a[n-i+1];long long mi=1e18;for(int i=0;i<=q;i++)mi=min(mi,f[i]+ff[q-i]);//找出最小的i次1操作和q-i次2操作的删减值cout<<tot-mi<<"\n";
}int main()
{cin>>t;while(t--)solve();
}

C. Contrast Value

        要求：求出a最短的子序列b，满足a的对比值=b的对比值

        分析：分析一下几个情况就能理清思路      

 情况1：1 2 3 5 6

要看到 2-1+3-2是等于3-1的，即对比值为6-1，所以最短为2，而如果序列为递减序列也是这种情况

情况2：1 1 1 1 1

很明显对比值为0，所以应该最短为1

情况3：1 2 3 2 1

可以将这种情况看成递增递减序列的组合，所以最短为3

那么思路就出来了

        遍历一下，看序列的变化性（递增\递减），若变化性变化，长度+1；

#include<bits/stdc++.h>
using namespace std;int T;
int n;
int a[300001];void solve() {cin>>n;for(int i=1; i<=n; i++)cin>>a[i];int f=0;//用表示单调性（-1）递减（1）递增 （0）等值序列int ans=1;for(int i=1; i<n; i++) {if(f==0) {if(a[i]>a[i+1])f=-1;else if(a[i]<a[i+1])f=1;//决定初始单调性} else {if(f==1) {if(a[i]>a[i+1]) {f=-1;ans++;}//转变单调性} else {if(a[i]<a[i+1]) {f=1;ans++;}//转变单调性}}}if(f)ans++;//f不为0时，需要在多选取序列最后一个数cout<<ans<<"\n";
}int main() {cin>>T;while(T--)solve();return 0;
}