Codeforces Round 968 (Div. 2) C++ (A-D1)

比赛地址 : 

Dashboard - Codeforces Round 968 (Div. 2) - Codeforces

A

只用考虑第一个和最后一个不相等就行了 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
#define int long long 
#define pb push_back
const int N = 2e5+10;
#define endl '\n'inline void solve(){int n ; cin >> n ;string s ; cin >> s ;char a = s[0] , b = s[s.size()-1] ;if(a==b) cout << "NO" << endl ;else cout << "YES" << endl ; 
}signed main(){IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

B

假设最后ans为v,那么Turtle会删除比v小的 ， Piggy会删除比v大的 ，所以最后答案也就是中位数 ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
#define int long long 
#define pb push_back
const int N = 2e5+10;
#define endl '\n'inline void solve(){int n ; cin >> n ;vector<int> a(n) ;for(int& x : a) cin >> x ;sort(a.begin(),a.end()) ;int res = a[n/2] ;cout << res << endl ;
}signed main(){IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

C

贪心

考虑排序后的答案尽量不让相邻的相等 , 可以先统计每个字符出现的次数 ， 考虑在出现次数多的字符之间插入出现次数少的字符 ;

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
#define int long long 
#define pb push_back
#define PII pair<int,int>
#define x first
#define y second
const int N = 2e5+10;
#define endl '\n'inline void solve(){int n ; cin >> n ;string s ; cin >> s ;string ans = "";// 尽可能打乱顺序vector<PII> a(26) ;for(int i=0;i<26;i++){a[i].y = i ;a[i].x = 0 ;}int ma = 0 ;for(int i=0;i<n;i++){int p = s[i]-'a' ;a[p].x++;ma = max(ma,a[p].x) ;} sort(a.begin(),a.end(),[](PII xx , PII yy){return xx.x>yy.x;});// 最多ma轮for(int i=0;i<ma;i++){for(int j=0;j<26;j++){if(a[j].x>0){ans += 'a'+a[j].y;a[j].x-- ;}}} cout << ans << endl ;
}signed main(){IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

D1

对于每一个序列 ， x对其进行操作 ， 都能够得到该序列的第二个mex值 ;

ps : 先获得第一个mex值 为x ，然后x进去就能得到第二个mex值 ;

假设对于每个序列ai (1<=i<=n) 的第二个mex值为vi ;

那么对于f(x)也就是max(x,max(v)) ;

然后O(1)统计答案即可 ;

代码 ： 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
#define int long long 
#define pb push_back
#define PII pair<int,int>
#define x first
#define y second
const int N = 2e5+10;
#define endl '\n'// sum(f(k))[0,m]
// m -> 1e9inline void solve(){int n , m ; cin >> n >> m ;int ans = 0 ;// 对于每一个序列 ， 得到该序列的第二个mex值 for(int i=0;i<n;i++){int l ; cin >> l ;vector<int> a(l) ;for(int& x : a) cin >> x ;sort(a.begin(),a.end())	;int mex = 0 ;bool ok = true ;for(int i=0;i<l;i++){// 获取第二mex值的最大值 if(a[i]>mex){if(ok) mex++ , ok = false ;else break ;}if(a[i]==mex) mex++ ;}mex+=ok;ans = max(ans,mex) ;}if(m<=ans){int res = (m+1)*ans ;cout << res << endl ;return ;}int res = (ans+1)*ans + (m-ans)*(ans+1+m)/2;cout << res << endl ;
}signed main(){IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}