牛客周赛 Round 35
小红的字符串切割
思路
一遍循环遍历就可以了，到中间位置时候输出一个换行符
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin()+1,x.end()
#define ct(x) cout<<x<<endl
void solve(){
string s;
cin>>s;
for(int i=0;i<s.size();i++){
if(i==s.size()/2){
cout<<endl;
}
cout<<s[i];
}
return ;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
小红的数组分配
思路
很明显我们需要保证每个元素出现的个数都是2的倍数，否则就没办法构成
Code
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define all(x) x.begin(),x.end()
void solve(){
int n;
cin>>n;
std::vector<int> a(n*2+1);
n*=2;
std::map<int, int> mp;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]++;
}
std::vector<int> v;
for(auto x:mp){
if(x.second%2==0){
int ans=x.second/2;
while(ans--){
v.push_back(x.first);
}
}
else{
cout<<-1<<endl;
return ;
}
}
for(int i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
cout<<endl;
for(int i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
return ;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
小红关鸡
思路
有意思的问题，看到这个问题我第一时间是想到用二分去做，但是貌似大佬有更好的办法？？？
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin()+1,x.end()
void solve(){
int n,k;
cin>>n>>k;
std::vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(all(a));
int ans=1e9+10;
std::vector<int> b(n+1),c(n+1);
for(int i=1;i<=n;i++){
int x=a[i]+k;
int l=0,r=n;
while(l<r){
int mid=(l+r)/2;
if(a[mid]>x){
r=mid;
}
else{
l=mid+1;
}
}
// cout<<l<<" "<<endl;
if(a[l]<=x){
b[i]=i-1;
}
else{
b[i]=i-1+(n-l+1);
}
// cout<<b[i]<<" ";
}
for(int i=1;i<=n;i++){
int x=a[i]-k;
int l=1,r=n;
while(l<r){
int mid=(l+r+1)/2;
if(a[mid]<x){
l=mid;
}
else{
r=mid-1;
}
}
// cout<<r<<" ";
if(a[r]>=x){
c[i]=n-i;
}
else{
c[i]=n-i+(r-1+1);
}
// cout<<c[i]<<" ";
}
for(int i=1;i<=n;i++){
ans=min(ans,min(b[i],c[i]));
}
// cout<<ans<<endl;
printf("%.8lf",1-(1.0*ans)/(n*1.0));
}
signed main(){
int t=1;
while(t--) solve();
return 0;
}
小红的排列构造
思路
用一个map处理一下就可以了，记录一下每个数字出现个数，对于出现多次以及不是该区间的数字将他们的位置进行存储，到时候将缺失的存进去就可以了
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
void solve(){
int n;
cin>>n;
std::map<int, int> mp;
std::vector<int> g;
std::vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
// s.insert(a[i]);
mp[a[i]]++;
// g[a[i]].push_back(i);
if(mp[a[i]]>=2||a[i]>n){
g.push_back(i);
}
}
std::vector<int> v;
for(int i=1;i<=n;i++){
if(mp[i]==0){
v.push_back(i);
}
}
if(v.size()==0){
cout<<0<<endl;
return ;
}
else{
cout<<v.size()<<endl;
for(int i=0;i<v.size();i++){
cout<<g[i]<<" "<<v[i]<<endl;
}
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
小红的无向图构造
Code
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
#define all(x) x.begin()+1,x.end()
#define debug(x) cout<<" # "<<x<<endl
typedef pair<int,int> PII;
void solve(){
int n,m;
cin>>n>>m;
std::vector<int> a(n+2);
std::vector<int> g[n+2];
int minn=INF,maxn=-INF;
for(int i=1;i<=n;i++){
cin>>a[i];
g[a[i]].push_back(i);
maxn=max(maxn,a[i]);
minn=min(minn,a[i]);
}
if(m<n-1){
cout<<-1<<endl;
return ;
}
for(int i=minn;i<=maxn;i++){
if(!g[i].size()){
cout<<-1<<endl;
return ;
}
}
int mod=m-(n-1);
std::vector<PII> ans;
for(int i=1;i<=n;i++){
for(auto p:g[i]){
ans.push_back({p,g[i-1][0]});
int j=1,l=g[i-1].size();
while(mod&&j<l){
ans.push_back({p,g[i-1][j++]});
mod--;
}
}
int k=g[i].size();
for(int j=0;j<k&&mod;j++){
for(int q=j+1;q<k&&mod;q++){
ans.push_back({g[i][j],g[i][q]});
mod--;
if(mod==0){
break;
}
}
}
}
if(mod){
cout<<-1<<endl;
return ;
}
for(auto p:ans){
cout<<p.first<<" "<<p.second<<endl;
}
return ;
}
signed main(){
int t=1;
while(t--) solve();
}