Codeforces Round #508 (Div. 2) 1038 解题报告 A/B/C/D
A
题意：给你一个序列 ，让你求前k个英文字母（按照abc的顺序）出现的最长公共子序列
题解：直接找一下前k个字母的最小出现次数
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
#define maxn 200000+5
typedef long long int ll;
int a[30];
int main(){
int n,k;
scanf("%d%d",&n,&k);
string s;cin>>s;
for(int i=0;i<n;i++){
a[s[i]-'A']++;
}
int minm=INF;
for(int i=0;i<k;i++){
minm=min(a[i],minm);
}
cout<<minm*k<<endl;
} B
题解：让你把1-n分成两个序列，使得这两个序列的和的gcd大于1
题意：按照奇偶性直接分开就行
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
#define maxn 200000+5
typedef long long int ll;
int a[30];
int main(){
int n;
scanf("%d",&n);
if(n==1||n==2){
cout<<"No"<<endl;
return 0;
}
vector<int>ans1,ans2;
for(int i=1;i<=n;i++){
if(i&1)ans1.push_back(i);
else ans2.push_back(i);
}
cout<<"Yes"<<endl;
cout<<ans1.size()<<" ";
for(int i=0;i<ans1.size();i++){
cout<<ans1[i];
if(i!=ans1.size()-1)cout<<" ";
else cout<<endl;
}
cout<<ans2.size()<<" ";
for(int i=0;i<ans2.size();i++){
cout<<ans2[i]<<" ";
}
} C
题意：给你两个序列 a和b 每轮可以从对面那里删掉一个 或者从自己这里拿走一个数字 让最后每个人拿走数字总和相差最小
题解：从小到大排序，如果自己最大的数字小于对面最大的数字，就删掉对面的，否则就拿起自己的
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
#define maxn 200000+5
typedef long long int ll;
int a[maxn],b[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int j=0;j<n;j++){
scanf("%d",&b[j]);
}
sort(a,a+n);sort(b,b+n);
ll suma=0,sumb=0;
for(int i=n-1,j=n-1;i>=0||j>=0;){
if(a[i]>=b[j]&&i>=0)suma+=a[i],i--;
else j--;
if(b[j]>=a[i]&&j>=0)sumb+=b[j],j--;
else i--;
}
cout<<suma-sumb<<endl;
} D
题意：
题意：有n个史莱姆，每一个史莱姆都可以吃掉相邻的史莱姆，使得自己的值改变，当x吃掉y的时候，x的值变为x-y，问最后所剩下的史莱姆最大是多少。
题解： 三种情况，第一种是所有数都是正数，对于这种情况我们要找一个最小值去减去一个数来获得一个负数，然后用这个负数去减别的正数从而获得更小的负数，最后再用一个正数来减去这个负数从而获得最大值，在这个过程中我们可以发现所有值最终都是被加上的，除了最小值第一次减的时候没有加上以外还少算了一次最小值，所以最终ans就是所有数的和减去2*Min，解释的不太好理解，可以写一下这个过程想想，同理当所有数都是负数的时候就是所有数的绝对值的和减去2*Max，当既有正数又有负数的时候就是输出所有元素的绝对值的和，然后就是对于n等于1和2的情况特判一下就好了。
借鉴大佬的题解
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
#define maxn 500000+5
typedef long long int ll;
int a[maxn];
int main(){
int n;
scanf("%d",&n);
int minm=INF,maxm=-INF;
ll sum=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
minm=min(a[i],minm);
maxm=max(a[i],maxm);
sum+=abs(a[i]);
}
if(n==1){
cout<<a[0]<<endl;
}else if(n==2){
cout<<max(a[0]-a[1],a[1]-a[0])<<endl;
}else {
if(minm>0){
cout<<sum-2*minm<<endl;
}else if(maxm<0){
cout<<sum-2*abs(maxm)<<endl;
}else cout<<sum<<endl;
}
}
