A. Serval and String Theory

题意：

给你一个字符串，可进行k次交换任意两元素（下标可相等），问是否能使操作后的字符串字典顺序小于其反转后的字典顺序

思路：

分三种大类，第一种，字符串任意元素相等，直接“NO”；

                      第二种，操作数为0，字符串从两头往中间一个一个比较（其实可以直接比较正字符串与翻转字符串字典顺序）

                      第三种，操作数不为0，只要不是第一种情况，直接“YES”；

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	int len=s.size();
	s=' '+s;
	int flag=0;
	for(int i=2;i<=len;i++){
		if(s[i]!=s[1]){
			flag=1;
			break;
		}
	}
	
	if(flag==0){
		cout<<"NO"<<endl;
	}else{
		if(k==0){
			int i=1,j=len;
			while(i<j){
				if(s[i]<s[j]){
					cout<<"YES"<<endl;
					return;
				}else if(s[i]>s[j]){
					cout<<"NO"<<endl;
					return;
				}
				i++,j--;
			}
			cout<<"NO"<<endl;
		}else{
			cout<<"YES"<<endl;
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin>>t;
//	t=1;
	while(t--)solve();
	return 0;
}

这样写更方便 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	string rs=s;
	reverse(s.begin(),s.end());
	if(k==0){
		if(s>rs){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}else{
		if(count(s.begin(),s.end(),s[0])!=n){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin>>t;
//	t=1;
	while(t--)solve();
	return 0;
}

B. Serval and Final MEX 

题意：

给一个数组，可进行任意次（选择两不相等下标l,r，将num[l]~num[r]删去，替换为删去区间未出现的最大值），最后将数组删至一个元素时，使之为0

打印操作次数，每次操作左右区间

思路：

想让最后唯一元素为零，就要保证在最后一次操作时数组中不存在0，

所以，只要将包含0的区间更新即可，

分为数组没有零，数组两端都存在0，一端存在0，0在数组中间，挨个特判即可

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){
	int n;
	cin>>n;
	vector<int>v(n);
	int  flag=0;
	for(int i=0;i<n;i++){
		cin>>v[i];
		if(v[i]==0)flag=1;
	}
	if(v[0]==0&&v[n-1]==0){
		cout<<3<<endl;
		cout<<n/2+1<<' '<<n<<endl;
		cout<<1<<' '<<n/2<<endl;
		cout<<1<<' '<<2<<endl;
	}else{
		if(v[0]==0){
			cout<<2<<endl;
			cout<<1<<' '<<n-1<<endl;
			cout<<1<<' '<<2<<endl;
		}else if(v[n-1]==0){
			cout<<2<<endl;
			cout<<2<<' '<<n<<endl;
			cout<<1<<' '<<2<<endl;
		}else{
			if(flag==0){
				cout<<1<<endl;
				cout<<1<<' '<<n<<endl;
			}else{
				cout<<2<<endl;
				cout<<1<<' '<<n-1<<endl;
				cout<<1<<' '<<2<<endl;
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin>>t;
//	t=1;
	while(t--)solve();
	return 0;
}

 C. Serval and The Formula

题意：

给你两个整数x,y找是否存在k满足(x+k)+(y+k)==(x+k)^(y+k)

思路：

首先，不存在k的情况只有当x==y

注意到异或操作是不进位加法，所以我们希望运算时两个数每一位都不应同时为1

又注意到题中所给的k的范围很大，且2的次方数二进制只有首位为1，所以我们可以找一个很大的2的次方数，减去max(x,y),就是一个满足条件的k

如5 4

k:1000000000-101=111111011

111111011+100=111111111

111111011+101=1000000000

111111111+1000000000=111111111^1000000000

保证只有首位为一，而不会进位

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){
	int x,y;
	cin>>x>>y;
	if(x==y){
		cout<<-1<<endl;
	}else{
		cout<<((1<<30)-max(x,y))<<endl;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin>>t;
//	t=1;
	while(t--)solve();
	return 0;
}

D. Serval and Kaitenzushi Buffet

题意：

有n个盘子，每个盘子里有k块寿司，且其美味度为di

有n分钟的用餐时间，每分钟要么拿一盘，要么吃一个拿的某一盘的一块，要么静坐，但结束时，要求没有浪费，使吃的美味度和最大

思路：

首先，每拿一盘并吃完需要k+1分钟且结束时正好食完，我们可以倒着处理

（拿取为0）

        5 2

        3 6 4 1 2

==>  1 1 0 1 1

        7 1

        3 1 4 1 5 9 2

==>  1 0 1 0 1 0 1 

每一个‘0’是对应的一盘的最大拿取时间，我们只需拿取每一个‘0’（包含‘0’）之前没被拿取的最大值

注意暴力会超时，需用stl

优先队列，multiset均可 

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
vector<int>v,bj;
void solve(){
	int k,n;
	cin>>k>>n;
	v.assign(k+1,0);
	bj.assign(k+1,0);
	for(int i=1;i<=k;i++){
		cin>>v[i];
		if(i%(n+1)==0)bj[i]=1;
	}
	reverse(bj.begin()+1,bj.end());
	int ans=0;
	priority_queue<int>pq;
	for(int i=1;i<=k;i++){
		pq.push(v[i]);
		if(bj[i]==1){
			ans+=pq.top();
			pq.pop();
		}
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin>>t;
//	t=1;
	while(t--)solve();
	return 0;
}

或者将预处理在if中判断使用的bj数组换成(k-i)%(n+1)==n

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
vector<int>v;
void solve(){
	int k,n;
	cin>>k>>n;
	v.assign(k+1,0);
	for(int i=1;i<=k;i++){
		cin>>v[i];
	}
	int ans=0;
	priority_queue<int>pq;
	for(int i=1;i<=k;i++){
		pq.push(v[i]);
		if((k-i)%(n+1)==n){
			ans+=pq.top();
			pq.pop();
		}
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin>>t;
//	t=1;
	while(t--)solve();
	return 0;
}